Home | History | Annotate | Download | only in src
      1 // Copyright 2012 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 #ifndef V8_UTILS_H_
     29 #define V8_UTILS_H_
     30 
     31 #include <stdlib.h>
     32 #include <string.h>
     33 #include <algorithm>
     34 #include <climits>
     35 
     36 #include "allocation.h"
     37 #include "checks.h"
     38 #include "globals.h"
     39 
     40 namespace v8 {
     41 namespace internal {
     42 
     43 // ----------------------------------------------------------------------------
     44 // General helper functions
     45 
     46 #define IS_POWER_OF_TWO(x) (((x) & ((x) - 1)) == 0)
     47 
     48 // Returns true iff x is a power of 2 (or zero). Cannot be used with the
     49 // maximally negative value of the type T (the -1 overflows).
     50 template <typename T>
     51 inline bool IsPowerOf2(T x) {
     52   return IS_POWER_OF_TWO(x);
     53 }
     54 
     55 
     56 // X must be a power of 2.  Returns the number of trailing zeros.
     57 inline int WhichPowerOf2(uint32_t x) {
     58   ASSERT(IsPowerOf2(x));
     59   ASSERT(x != 0);
     60   int bits = 0;
     61 #ifdef DEBUG
     62   int original_x = x;
     63 #endif
     64   if (x >= 0x10000) {
     65     bits += 16;
     66     x >>= 16;
     67   }
     68   if (x >= 0x100) {
     69     bits += 8;
     70     x >>= 8;
     71   }
     72   if (x >= 0x10) {
     73     bits += 4;
     74     x >>= 4;
     75   }
     76   switch (x) {
     77     default: UNREACHABLE();
     78     case 8: bits++;  // Fall through.
     79     case 4: bits++;  // Fall through.
     80     case 2: bits++;  // Fall through.
     81     case 1: break;
     82   }
     83   ASSERT_EQ(1 << bits, original_x);
     84   return bits;
     85   return 0;
     86 }
     87 
     88 
     89 inline int MostSignificantBit(uint32_t x) {
     90   static const int msb4[] = {0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4};
     91   int nibble = 0;
     92   if (x & 0xffff0000) {
     93     nibble += 16;
     94     x >>= 16;
     95   }
     96   if (x & 0xff00) {
     97     nibble += 8;
     98     x >>= 8;
     99   }
    100   if (x & 0xf0) {
    101     nibble += 4;
    102     x >>= 4;
    103   }
    104   return nibble + msb4[x];
    105 }
    106 
    107 
    108 // Magic numbers for integer division.
    109 // These are kind of 2's complement reciprocal of the divisors.
    110 // Details and proofs can be found in:
    111 // - Hacker's Delight, Henry S. Warren, Jr.
    112 // - The PowerPC Compiler Writers Guide
    113 // and probably many others.
    114 // See details in the implementation of the algorithm in
    115 // lithium-codegen-arm.cc : LCodeGen::TryEmitSignedIntegerDivisionByConstant().
    116 struct DivMagicNumbers {
    117   unsigned M;
    118   unsigned s;
    119 };
    120 
    121 const DivMagicNumbers InvalidDivMagicNumber= {0, 0};
    122 const DivMagicNumbers DivMagicNumberFor3   = {0x55555556, 0};
    123 const DivMagicNumbers DivMagicNumberFor5   = {0x66666667, 1};
    124 const DivMagicNumbers DivMagicNumberFor7   = {0x92492493, 2};
    125 const DivMagicNumbers DivMagicNumberFor9   = {0x38e38e39, 1};
    126 const DivMagicNumbers DivMagicNumberFor11  = {0x2e8ba2e9, 1};
    127 const DivMagicNumbers DivMagicNumberFor25  = {0x51eb851f, 3};
    128 const DivMagicNumbers DivMagicNumberFor125 = {0x10624dd3, 3};
    129 const DivMagicNumbers DivMagicNumberFor625 = {0x68db8bad, 8};
    130 
    131 const DivMagicNumbers DivMagicNumberFor(int32_t divisor);
    132 
    133 
    134 // The C++ standard leaves the semantics of '>>' undefined for
    135 // negative signed operands. Most implementations do the right thing,
    136 // though.
    137 inline int ArithmeticShiftRight(int x, int s) {
    138   return x >> s;
    139 }
    140 
    141 
    142 // Compute the 0-relative offset of some absolute value x of type T.
    143 // This allows conversion of Addresses and integral types into
    144 // 0-relative int offsets.
    145 template <typename T>
    146 inline intptr_t OffsetFrom(T x) {
    147   return x - static_cast<T>(0);
    148 }
    149 
    150 
    151 // Compute the absolute value of type T for some 0-relative offset x.
    152 // This allows conversion of 0-relative int offsets into Addresses and
    153 // integral types.
    154 template <typename T>
    155 inline T AddressFrom(intptr_t x) {
    156   return static_cast<T>(static_cast<T>(0) + x);
    157 }
    158 
    159 
    160 // Return the largest multiple of m which is <= x.
    161 template <typename T>
    162 inline T RoundDown(T x, intptr_t m) {
    163   ASSERT(IsPowerOf2(m));
    164   return AddressFrom<T>(OffsetFrom(x) & -m);
    165 }
    166 
    167 
    168 // Return the smallest multiple of m which is >= x.
    169 template <typename T>
    170 inline T RoundUp(T x, intptr_t m) {
    171   return RoundDown<T>(static_cast<T>(x + m - 1), m);
    172 }
    173 
    174 
    175 template <typename T>
    176 int Compare(const T& a, const T& b) {
    177   if (a == b)
    178     return 0;
    179   else if (a < b)
    180     return -1;
    181   else
    182     return 1;
    183 }
    184 
    185 
    186 template <typename T>
    187 int PointerValueCompare(const T* a, const T* b) {
    188   return Compare<T>(*a, *b);
    189 }
    190 
    191 
    192 // Compare function to compare the object pointer value of two
    193 // handlified objects. The handles are passed as pointers to the
    194 // handles.
    195 template<typename T> class Handle;  // Forward declaration.
    196 template <typename T>
    197 int HandleObjectPointerCompare(const Handle<T>* a, const Handle<T>* b) {
    198   return Compare<T*>(*(*a), *(*b));
    199 }
    200 
    201 
    202 // Returns the smallest power of two which is >= x. If you pass in a
    203 // number that is already a power of two, it is returned as is.
    204 // Implementation is from "Hacker's Delight" by Henry S. Warren, Jr.,
    205 // figure 3-3, page 48, where the function is called clp2.
    206 inline uint32_t RoundUpToPowerOf2(uint32_t x) {
    207   ASSERT(x <= 0x80000000u);
    208   x = x - 1;
    209   x = x | (x >> 1);
    210   x = x | (x >> 2);
    211   x = x | (x >> 4);
    212   x = x | (x >> 8);
    213   x = x | (x >> 16);
    214   return x + 1;
    215 }
    216 
    217 
    218 inline uint32_t RoundDownToPowerOf2(uint32_t x) {
    219   uint32_t rounded_up = RoundUpToPowerOf2(x);
    220   if (rounded_up > x) return rounded_up >> 1;
    221   return rounded_up;
    222 }
    223 
    224 
    225 template <typename T, typename U>
    226 inline bool IsAligned(T value, U alignment) {
    227   return (value & (alignment - 1)) == 0;
    228 }
    229 
    230 
    231 // Returns true if (addr + offset) is aligned.
    232 inline bool IsAddressAligned(Address addr,
    233                              intptr_t alignment,
    234                              int offset = 0) {
    235   intptr_t offs = OffsetFrom(addr + offset);
    236   return IsAligned(offs, alignment);
    237 }
    238 
    239 
    240 // Returns the maximum of the two parameters.
    241 template <typename T>
    242 T Max(T a, T b) {
    243   return a < b ? b : a;
    244 }
    245 
    246 
    247 // Returns the minimum of the two parameters.
    248 template <typename T>
    249 T Min(T a, T b) {
    250   return a < b ? a : b;
    251 }
    252 
    253 
    254 // Returns the absolute value of its argument.
    255 template <typename T>
    256 T Abs(T a) {
    257   return a < 0 ? -a : a;
    258 }
    259 
    260 
    261 // Returns the negative absolute value of its argument.
    262 template <typename T>
    263 T NegAbs(T a) {
    264   return a < 0 ? a : -a;
    265 }
    266 
    267 
    268 inline int StrLength(const char* string) {
    269   size_t length = strlen(string);
    270   ASSERT(length == static_cast<size_t>(static_cast<int>(length)));
    271   return static_cast<int>(length);
    272 }
    273 
    274 
    275 // ----------------------------------------------------------------------------
    276 // BitField is a help template for encoding and decode bitfield with
    277 // unsigned content.
    278 
    279 template<class T, int shift, int size, class U>
    280 class BitFieldBase {
    281  public:
    282   // A type U mask of bit field.  To use all bits of a type U of x bits
    283   // in a bitfield without compiler warnings we have to compute 2^x
    284   // without using a shift count of x in the computation.
    285   static const U kOne = static_cast<U>(1U);
    286   static const U kMask = ((kOne << shift) << size) - (kOne << shift);
    287   static const U kShift = shift;
    288   static const U kSize = size;
    289 
    290   // Value for the field with all bits set.
    291   static const T kMax = static_cast<T>((1U << size) - 1);
    292 
    293   // Tells whether the provided value fits into the bit field.
    294   static bool is_valid(T value) {
    295     return (static_cast<U>(value) & ~static_cast<U>(kMax)) == 0;
    296   }
    297 
    298   // Returns a type U with the bit field value encoded.
    299   static U encode(T value) {
    300     ASSERT(is_valid(value));
    301     return static_cast<U>(value) << shift;
    302   }
    303 
    304   // Returns a type U with the bit field value updated.
    305   static U update(U previous, T value) {
    306     return (previous & ~kMask) | encode(value);
    307   }
    308 
    309   // Extracts the bit field from the value.
    310   static T decode(U value) {
    311     return static_cast<T>((value & kMask) >> shift);
    312   }
    313 };
    314 
    315 
    316 template<class T, int shift, int size>
    317 class BitField : public BitFieldBase<T, shift, size, uint32_t> { };
    318 
    319 
    320 template<class T, int shift, int size>
    321 class BitField64 : public BitFieldBase<T, shift, size, uint64_t> { };
    322 
    323 
    324 // ----------------------------------------------------------------------------
    325 // Hash function.
    326 
    327 static const uint32_t kZeroHashSeed = 0;
    328 
    329 // Thomas Wang, Integer Hash Functions.
    330 // http://www.concentric.net/~Ttwang/tech/inthash.htm
    331 inline uint32_t ComputeIntegerHash(uint32_t key, uint32_t seed) {
    332   uint32_t hash = key;
    333   hash = hash ^ seed;
    334   hash = ~hash + (hash << 15);  // hash = (hash << 15) - hash - 1;
    335   hash = hash ^ (hash >> 12);
    336   hash = hash + (hash << 2);
    337   hash = hash ^ (hash >> 4);
    338   hash = hash * 2057;  // hash = (hash + (hash << 3)) + (hash << 11);
    339   hash = hash ^ (hash >> 16);
    340   return hash;
    341 }
    342 
    343 
    344 inline uint32_t ComputeLongHash(uint64_t key) {
    345   uint64_t hash = key;
    346   hash = ~hash + (hash << 18);  // hash = (hash << 18) - hash - 1;
    347   hash = hash ^ (hash >> 31);
    348   hash = hash * 21;  // hash = (hash + (hash << 2)) + (hash << 4);
    349   hash = hash ^ (hash >> 11);
    350   hash = hash + (hash << 6);
    351   hash = hash ^ (hash >> 22);
    352   return static_cast<uint32_t>(hash);
    353 }
    354 
    355 
    356 inline uint32_t ComputePointerHash(void* ptr) {
    357   return ComputeIntegerHash(
    358       static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr)),
    359       v8::internal::kZeroHashSeed);
    360 }
    361 
    362 
    363 // ----------------------------------------------------------------------------
    364 // Miscellaneous
    365 
    366 // A static resource holds a static instance that can be reserved in
    367 // a local scope using an instance of Access.  Attempts to re-reserve
    368 // the instance will cause an error.
    369 template <typename T>
    370 class StaticResource {
    371  public:
    372   StaticResource() : is_reserved_(false)  {}
    373 
    374  private:
    375   template <typename S> friend class Access;
    376   T instance_;
    377   bool is_reserved_;
    378 };
    379 
    380 
    381 // Locally scoped access to a static resource.
    382 template <typename T>
    383 class Access {
    384  public:
    385   explicit Access(StaticResource<T>* resource)
    386     : resource_(resource)
    387     , instance_(&resource->instance_) {
    388     ASSERT(!resource->is_reserved_);
    389     resource->is_reserved_ = true;
    390   }
    391 
    392   ~Access() {
    393     resource_->is_reserved_ = false;
    394     resource_ = NULL;
    395     instance_ = NULL;
    396   }
    397 
    398   T* value()  { return instance_; }
    399   T* operator -> ()  { return instance_; }
    400 
    401  private:
    402   StaticResource<T>* resource_;
    403   T* instance_;
    404 };
    405 
    406 
    407 template <typename T>
    408 class Vector {
    409  public:
    410   Vector() : start_(NULL), length_(0) {}
    411   Vector(T* data, int length) : start_(data), length_(length) {
    412     ASSERT(length == 0 || (length > 0 && data != NULL));
    413   }
    414 
    415   static Vector<T> New(int length) {
    416     return Vector<T>(NewArray<T>(length), length);
    417   }
    418 
    419   // Returns a vector using the same backing storage as this one,
    420   // spanning from and including 'from', to but not including 'to'.
    421   Vector<T> SubVector(int from, int to) {
    422     SLOW_ASSERT(to <= length_);
    423     SLOW_ASSERT(from < to);
    424     ASSERT(0 <= from);
    425     return Vector<T>(start() + from, to - from);
    426   }
    427 
    428   // Returns the length of the vector.
    429   int length() const { return length_; }
    430 
    431   // Returns whether or not the vector is empty.
    432   bool is_empty() const { return length_ == 0; }
    433 
    434   // Returns the pointer to the start of the data in the vector.
    435   T* start() const { return start_; }
    436 
    437   // Access individual vector elements - checks bounds in debug mode.
    438   T& operator[](int index) const {
    439     ASSERT(0 <= index && index < length_);
    440     return start_[index];
    441   }
    442 
    443   const T& at(int index) const { return operator[](index); }
    444 
    445   T& first() { return start_[0]; }
    446 
    447   T& last() { return start_[length_ - 1]; }
    448 
    449   // Returns a clone of this vector with a new backing store.
    450   Vector<T> Clone() const {
    451     T* result = NewArray<T>(length_);
    452     for (int i = 0; i < length_; i++) result[i] = start_[i];
    453     return Vector<T>(result, length_);
    454   }
    455 
    456   void Sort(int (*cmp)(const T*, const T*)) {
    457     std::sort(start(), start() + length(), RawComparer(cmp));
    458   }
    459 
    460   void Sort() {
    461     std::sort(start(), start() + length());
    462   }
    463 
    464   void Truncate(int length) {
    465     ASSERT(length <= length_);
    466     length_ = length;
    467   }
    468 
    469   // Releases the array underlying this vector. Once disposed the
    470   // vector is empty.
    471   void Dispose() {
    472     DeleteArray(start_);
    473     start_ = NULL;
    474     length_ = 0;
    475   }
    476 
    477   inline Vector<T> operator+(int offset) {
    478     ASSERT(offset < length_);
    479     return Vector<T>(start_ + offset, length_ - offset);
    480   }
    481 
    482   // Factory method for creating empty vectors.
    483   static Vector<T> empty() { return Vector<T>(NULL, 0); }
    484 
    485   template<typename S>
    486   static Vector<T> cast(Vector<S> input) {
    487     return Vector<T>(reinterpret_cast<T*>(input.start()),
    488                      input.length() * sizeof(S) / sizeof(T));
    489   }
    490 
    491  protected:
    492   void set_start(T* start) { start_ = start; }
    493 
    494  private:
    495   T* start_;
    496   int length_;
    497 
    498   class RawComparer {
    499    public:
    500     explicit RawComparer(int (*cmp)(const T*, const T*)) : cmp_(cmp) {}
    501     bool operator()(const T& a, const T& b) {
    502       return cmp_(&a, &b) < 0;
    503     }
    504 
    505    private:
    506     int (*cmp_)(const T*, const T*);
    507   };
    508 };
    509 
    510 
    511 // A pointer that can only be set once and doesn't allow NULL values.
    512 template<typename T>
    513 class SetOncePointer {
    514  public:
    515   SetOncePointer() : pointer_(NULL) { }
    516 
    517   bool is_set() const { return pointer_ != NULL; }
    518 
    519   T* get() const {
    520     ASSERT(pointer_ != NULL);
    521     return pointer_;
    522   }
    523 
    524   void set(T* value) {
    525     ASSERT(pointer_ == NULL && value != NULL);
    526     pointer_ = value;
    527   }
    528 
    529  private:
    530   T* pointer_;
    531 };
    532 
    533 
    534 template <typename T, int kSize>
    535 class EmbeddedVector : public Vector<T> {
    536  public:
    537   EmbeddedVector() : Vector<T>(buffer_, kSize) { }
    538 
    539   explicit EmbeddedVector(T initial_value) : Vector<T>(buffer_, kSize) {
    540     for (int i = 0; i < kSize; ++i) {
    541       buffer_[i] = initial_value;
    542     }
    543   }
    544 
    545   // When copying, make underlying Vector to reference our buffer.
    546   EmbeddedVector(const EmbeddedVector& rhs)
    547       : Vector<T>(rhs) {
    548     // TODO(jkummerow): Refactor #includes and use OS::MemCopy() instead.
    549     memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize);
    550     set_start(buffer_);
    551   }
    552 
    553   EmbeddedVector& operator=(const EmbeddedVector& rhs) {
    554     if (this == &rhs) return *this;
    555     Vector<T>::operator=(rhs);
    556     // TODO(jkummerow): Refactor #includes and use OS::MemCopy() instead.
    557     memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize);
    558     this->set_start(buffer_);
    559     return *this;
    560   }
    561 
    562  private:
    563   T buffer_[kSize];
    564 };
    565 
    566 
    567 template <typename T>
    568 class ScopedVector : public Vector<T> {
    569  public:
    570   explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { }
    571   ~ScopedVector() {
    572     DeleteArray(this->start());
    573   }
    574 
    575  private:
    576   DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector);
    577 };
    578 
    579 #define STATIC_ASCII_VECTOR(x)                        \
    580   v8::internal::Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(x), \
    581                                       ARRAY_SIZE(x)-1)
    582 
    583 inline Vector<const char> CStrVector(const char* data) {
    584   return Vector<const char>(data, StrLength(data));
    585 }
    586 
    587 inline Vector<const uint8_t> OneByteVector(const char* data, int length) {
    588   return Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), length);
    589 }
    590 
    591 inline Vector<const uint8_t> OneByteVector(const char* data) {
    592   return OneByteVector(data, StrLength(data));
    593 }
    594 
    595 inline Vector<char> MutableCStrVector(char* data) {
    596   return Vector<char>(data, StrLength(data));
    597 }
    598 
    599 inline Vector<char> MutableCStrVector(char* data, int max) {
    600   int length = StrLength(data);
    601   return Vector<char>(data, (length < max) ? length : max);
    602 }
    603 
    604 
    605 /*
    606  * A class that collects values into a backing store.
    607  * Specialized versions of the class can allow access to the backing store
    608  * in different ways.
    609  * There is no guarantee that the backing store is contiguous (and, as a
    610  * consequence, no guarantees that consecutively added elements are adjacent
    611  * in memory). The collector may move elements unless it has guaranteed not
    612  * to.
    613  */
    614 template <typename T, int growth_factor = 2, int max_growth = 1 * MB>
    615 class Collector {
    616  public:
    617   explicit Collector(int initial_capacity = kMinCapacity)
    618       : index_(0), size_(0) {
    619     current_chunk_ = Vector<T>::New(initial_capacity);
    620   }
    621 
    622   virtual ~Collector() {
    623     // Free backing store (in reverse allocation order).
    624     current_chunk_.Dispose();
    625     for (int i = chunks_.length() - 1; i >= 0; i--) {
    626       chunks_.at(i).Dispose();
    627     }
    628   }
    629 
    630   // Add a single element.
    631   inline void Add(T value) {
    632     if (index_ >= current_chunk_.length()) {
    633       Grow(1);
    634     }
    635     current_chunk_[index_] = value;
    636     index_++;
    637     size_++;
    638   }
    639 
    640   // Add a block of contiguous elements and return a Vector backed by the
    641   // memory area.
    642   // A basic Collector will keep this vector valid as long as the Collector
    643   // is alive.
    644   inline Vector<T> AddBlock(int size, T initial_value) {
    645     ASSERT(size > 0);
    646     if (size > current_chunk_.length() - index_) {
    647       Grow(size);
    648     }
    649     T* position = current_chunk_.start() + index_;
    650     index_ += size;
    651     size_ += size;
    652     for (int i = 0; i < size; i++) {
    653       position[i] = initial_value;
    654     }
    655     return Vector<T>(position, size);
    656   }
    657 
    658 
    659   // Add a contiguous block of elements and return a vector backed
    660   // by the added block.
    661   // A basic Collector will keep this vector valid as long as the Collector
    662   // is alive.
    663   inline Vector<T> AddBlock(Vector<const T> source) {
    664     if (source.length() > current_chunk_.length() - index_) {
    665       Grow(source.length());
    666     }
    667     T* position = current_chunk_.start() + index_;
    668     index_ += source.length();
    669     size_ += source.length();
    670     for (int i = 0; i < source.length(); i++) {
    671       position[i] = source[i];
    672     }
    673     return Vector<T>(position, source.length());
    674   }
    675 
    676 
    677   // Write the contents of the collector into the provided vector.
    678   void WriteTo(Vector<T> destination) {
    679     ASSERT(size_ <= destination.length());
    680     int position = 0;
    681     for (int i = 0; i < chunks_.length(); i++) {
    682       Vector<T> chunk = chunks_.at(i);
    683       for (int j = 0; j < chunk.length(); j++) {
    684         destination[position] = chunk[j];
    685         position++;
    686       }
    687     }
    688     for (int i = 0; i < index_; i++) {
    689       destination[position] = current_chunk_[i];
    690       position++;
    691     }
    692   }
    693 
    694   // Allocate a single contiguous vector, copy all the collected
    695   // elements to the vector, and return it.
    696   // The caller is responsible for freeing the memory of the returned
    697   // vector (e.g., using Vector::Dispose).
    698   Vector<T> ToVector() {
    699     Vector<T> new_store = Vector<T>::New(size_);
    700     WriteTo(new_store);
    701     return new_store;
    702   }
    703 
    704   // Resets the collector to be empty.
    705   virtual void Reset();
    706 
    707   // Total number of elements added to collector so far.
    708   inline int size() { return size_; }
    709 
    710  protected:
    711   static const int kMinCapacity = 16;
    712   List<Vector<T> > chunks_;
    713   Vector<T> current_chunk_;  // Block of memory currently being written into.
    714   int index_;  // Current index in current chunk.
    715   int size_;  // Total number of elements in collector.
    716 
    717   // Creates a new current chunk, and stores the old chunk in the chunks_ list.
    718   void Grow(int min_capacity) {
    719     ASSERT(growth_factor > 1);
    720     int new_capacity;
    721     int current_length = current_chunk_.length();
    722     if (current_length < kMinCapacity) {
    723       // The collector started out as empty.
    724       new_capacity = min_capacity * growth_factor;
    725       if (new_capacity < kMinCapacity) new_capacity = kMinCapacity;
    726     } else {
    727       int growth = current_length * (growth_factor - 1);
    728       if (growth > max_growth) {
    729         growth = max_growth;
    730       }
    731       new_capacity = current_length + growth;
    732       if (new_capacity < min_capacity) {
    733         new_capacity = min_capacity + growth;
    734       }
    735     }
    736     NewChunk(new_capacity);
    737     ASSERT(index_ + min_capacity <= current_chunk_.length());
    738   }
    739 
    740   // Before replacing the current chunk, give a subclass the option to move
    741   // some of the current data into the new chunk. The function may update
    742   // the current index_ value to represent data no longer in the current chunk.
    743   // Returns the initial index of the new chunk (after copied data).
    744   virtual void NewChunk(int new_capacity)  {
    745     Vector<T> new_chunk = Vector<T>::New(new_capacity);
    746     if (index_ > 0) {
    747       chunks_.Add(current_chunk_.SubVector(0, index_));
    748     } else {
    749       current_chunk_.Dispose();
    750     }
    751     current_chunk_ = new_chunk;
    752     index_ = 0;
    753   }
    754 };
    755 
    756 
    757 /*
    758  * A collector that allows sequences of values to be guaranteed to
    759  * stay consecutive.
    760  * If the backing store grows while a sequence is active, the current
    761  * sequence might be moved, but after the sequence is ended, it will
    762  * not move again.
    763  * NOTICE: Blocks allocated using Collector::AddBlock(int) can move
    764  * as well, if inside an active sequence where another element is added.
    765  */
    766 template <typename T, int growth_factor = 2, int max_growth = 1 * MB>
    767 class SequenceCollector : public Collector<T, growth_factor, max_growth> {
    768  public:
    769   explicit SequenceCollector(int initial_capacity)
    770       : Collector<T, growth_factor, max_growth>(initial_capacity),
    771         sequence_start_(kNoSequence) { }
    772 
    773   virtual ~SequenceCollector() {}
    774 
    775   void StartSequence() {
    776     ASSERT(sequence_start_ == kNoSequence);
    777     sequence_start_ = this->index_;
    778   }
    779 
    780   Vector<T> EndSequence() {
    781     ASSERT(sequence_start_ != kNoSequence);
    782     int sequence_start = sequence_start_;
    783     sequence_start_ = kNoSequence;
    784     if (sequence_start == this->index_) return Vector<T>();
    785     return this->current_chunk_.SubVector(sequence_start, this->index_);
    786   }
    787 
    788   // Drops the currently added sequence, and all collected elements in it.
    789   void DropSequence() {
    790     ASSERT(sequence_start_ != kNoSequence);
    791     int sequence_length = this->index_ - sequence_start_;
    792     this->index_ = sequence_start_;
    793     this->size_ -= sequence_length;
    794     sequence_start_ = kNoSequence;
    795   }
    796 
    797   virtual void Reset() {
    798     sequence_start_ = kNoSequence;
    799     this->Collector<T, growth_factor, max_growth>::Reset();
    800   }
    801 
    802  private:
    803   static const int kNoSequence = -1;
    804   int sequence_start_;
    805 
    806   // Move the currently active sequence to the new chunk.
    807   virtual void NewChunk(int new_capacity) {
    808     if (sequence_start_ == kNoSequence) {
    809       // Fall back on default behavior if no sequence has been started.
    810       this->Collector<T, growth_factor, max_growth>::NewChunk(new_capacity);
    811       return;
    812     }
    813     int sequence_length = this->index_ - sequence_start_;
    814     Vector<T> new_chunk = Vector<T>::New(sequence_length + new_capacity);
    815     ASSERT(sequence_length < new_chunk.length());
    816     for (int i = 0; i < sequence_length; i++) {
    817       new_chunk[i] = this->current_chunk_[sequence_start_ + i];
    818     }
    819     if (sequence_start_ > 0) {
    820       this->chunks_.Add(this->current_chunk_.SubVector(0, sequence_start_));
    821     } else {
    822       this->current_chunk_.Dispose();
    823     }
    824     this->current_chunk_ = new_chunk;
    825     this->index_ = sequence_length;
    826     sequence_start_ = 0;
    827   }
    828 };
    829 
    830 
    831 // Compare ASCII/16bit chars to ASCII/16bit chars.
    832 template <typename lchar, typename rchar>
    833 inline int CompareCharsUnsigned(const lchar* lhs,
    834                                 const rchar* rhs,
    835                                 int chars) {
    836   const lchar* limit = lhs + chars;
    837 #ifdef V8_HOST_CAN_READ_UNALIGNED
    838   if (sizeof(*lhs) == sizeof(*rhs)) {
    839     // Number of characters in a uintptr_t.
    840     static const int kStepSize = sizeof(uintptr_t) / sizeof(*lhs);  // NOLINT
    841     while (lhs <= limit - kStepSize) {
    842       if (*reinterpret_cast<const uintptr_t*>(lhs) !=
    843           *reinterpret_cast<const uintptr_t*>(rhs)) {
    844         break;
    845       }
    846       lhs += kStepSize;
    847       rhs += kStepSize;
    848     }
    849   }
    850 #endif
    851   while (lhs < limit) {
    852     int r = static_cast<int>(*lhs) - static_cast<int>(*rhs);
    853     if (r != 0) return r;
    854     ++lhs;
    855     ++rhs;
    856   }
    857   return 0;
    858 }
    859 
    860 template<typename lchar, typename rchar>
    861 inline int CompareChars(const lchar* lhs, const rchar* rhs, int chars) {
    862   ASSERT(sizeof(lchar) <= 2);
    863   ASSERT(sizeof(rchar) <= 2);
    864   if (sizeof(lchar) == 1) {
    865     if (sizeof(rchar) == 1) {
    866       return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
    867                                   reinterpret_cast<const uint8_t*>(rhs),
    868                                   chars);
    869     } else {
    870       return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
    871                                   reinterpret_cast<const uint16_t*>(rhs),
    872                                   chars);
    873     }
    874   } else {
    875     if (sizeof(rchar) == 1) {
    876       return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
    877                                   reinterpret_cast<const uint8_t*>(rhs),
    878                                   chars);
    879     } else {
    880       return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
    881                                   reinterpret_cast<const uint16_t*>(rhs),
    882                                   chars);
    883     }
    884   }
    885 }
    886 
    887 
    888 // Calculate 10^exponent.
    889 inline int TenToThe(int exponent) {
    890   ASSERT(exponent <= 9);
    891   ASSERT(exponent >= 1);
    892   int answer = 10;
    893   for (int i = 1; i < exponent; i++) answer *= 10;
    894   return answer;
    895 }
    896 
    897 
    898 // The type-based aliasing rule allows the compiler to assume that pointers of
    899 // different types (for some definition of different) never alias each other.
    900 // Thus the following code does not work:
    901 //
    902 // float f = foo();
    903 // int fbits = *(int*)(&f);
    904 //
    905 // The compiler 'knows' that the int pointer can't refer to f since the types
    906 // don't match, so the compiler may cache f in a register, leaving random data
    907 // in fbits.  Using C++ style casts makes no difference, however a pointer to
    908 // char data is assumed to alias any other pointer.  This is the 'memcpy
    909 // exception'.
    910 //
    911 // Bit_cast uses the memcpy exception to move the bits from a variable of one
    912 // type of a variable of another type.  Of course the end result is likely to
    913 // be implementation dependent.  Most compilers (gcc-4.2 and MSVC 2005)
    914 // will completely optimize BitCast away.
    915 //
    916 // There is an additional use for BitCast.
    917 // Recent gccs will warn when they see casts that may result in breakage due to
    918 // the type-based aliasing rule.  If you have checked that there is no breakage
    919 // you can use BitCast to cast one pointer type to another.  This confuses gcc
    920 // enough that it can no longer see that you have cast one pointer type to
    921 // another thus avoiding the warning.
    922 
    923 // We need different implementations of BitCast for pointer and non-pointer
    924 // values. We use partial specialization of auxiliary struct to work around
    925 // issues with template functions overloading.
    926 template <class Dest, class Source>
    927 struct BitCastHelper {
    928   STATIC_ASSERT(sizeof(Dest) == sizeof(Source));
    929 
    930   INLINE(static Dest cast(const Source& source)) {
    931     Dest dest;
    932     // TODO(jkummerow): Refactor #includes and use OS::MemCopy() instead.
    933     memcpy(&dest, &source, sizeof(dest));
    934     return dest;
    935   }
    936 };
    937 
    938 template <class Dest, class Source>
    939 struct BitCastHelper<Dest, Source*> {
    940   INLINE(static Dest cast(Source* source)) {
    941     return BitCastHelper<Dest, uintptr_t>::
    942         cast(reinterpret_cast<uintptr_t>(source));
    943   }
    944 };
    945 
    946 template <class Dest, class Source>
    947 INLINE(Dest BitCast(const Source& source));
    948 
    949 template <class Dest, class Source>
    950 inline Dest BitCast(const Source& source) {
    951   return BitCastHelper<Dest, Source>::cast(source);
    952 }
    953 
    954 
    955 template<typename ElementType, int NumElements>
    956 class EmbeddedContainer {
    957  public:
    958   EmbeddedContainer() : elems_() { }
    959 
    960   int length() const { return NumElements; }
    961   const ElementType& operator[](int i) const {
    962     ASSERT(i < length());
    963     return elems_[i];
    964   }
    965   ElementType& operator[](int i) {
    966     ASSERT(i < length());
    967     return elems_[i];
    968   }
    969 
    970  private:
    971   ElementType elems_[NumElements];
    972 };
    973 
    974 
    975 template<typename ElementType>
    976 class EmbeddedContainer<ElementType, 0> {
    977  public:
    978   int length() const { return 0; }
    979   const ElementType& operator[](int i) const {
    980     UNREACHABLE();
    981     static ElementType t = 0;
    982     return t;
    983   }
    984   ElementType& operator[](int i) {
    985     UNREACHABLE();
    986     static ElementType t = 0;
    987     return t;
    988   }
    989 };
    990 
    991 
    992 // Helper class for building result strings in a character buffer. The
    993 // purpose of the class is to use safe operations that checks the
    994 // buffer bounds on all operations in debug mode.
    995 // This simple base class does not allow formatted output.
    996 class SimpleStringBuilder {
    997  public:
    998   // Create a string builder with a buffer of the given size. The
    999   // buffer is allocated through NewArray<char> and must be
   1000   // deallocated by the caller of Finalize().
   1001   explicit SimpleStringBuilder(int size);
   1002 
   1003   SimpleStringBuilder(char* buffer, int size)
   1004       : buffer_(buffer, size), position_(0) { }
   1005 
   1006   ~SimpleStringBuilder() { if (!is_finalized()) Finalize(); }
   1007 
   1008   int size() const { return buffer_.length(); }
   1009 
   1010   // Get the current position in the builder.
   1011   int position() const {
   1012     ASSERT(!is_finalized());
   1013     return position_;
   1014   }
   1015 
   1016   // Reset the position.
   1017   void Reset() { position_ = 0; }
   1018 
   1019   // Add a single character to the builder. It is not allowed to add
   1020   // 0-characters; use the Finalize() method to terminate the string
   1021   // instead.
   1022   void AddCharacter(char c) {
   1023     ASSERT(c != '\0');
   1024     ASSERT(!is_finalized() && position_ < buffer_.length());
   1025     buffer_[position_++] = c;
   1026   }
   1027 
   1028   // Add an entire string to the builder. Uses strlen() internally to
   1029   // compute the length of the input string.
   1030   void AddString(const char* s);
   1031 
   1032   // Add the first 'n' characters of the given string 's' to the
   1033   // builder. The input string must have enough characters.
   1034   void AddSubstring(const char* s, int n);
   1035 
   1036   // Add character padding to the builder. If count is non-positive,
   1037   // nothing is added to the builder.
   1038   void AddPadding(char c, int count);
   1039 
   1040   // Add the decimal representation of the value.
   1041   void AddDecimalInteger(int value);
   1042 
   1043   // Finalize the string by 0-terminating it and returning the buffer.
   1044   char* Finalize();
   1045 
   1046  protected:
   1047   Vector<char> buffer_;
   1048   int position_;
   1049 
   1050   bool is_finalized() const { return position_ < 0; }
   1051 
   1052  private:
   1053   DISALLOW_IMPLICIT_CONSTRUCTORS(SimpleStringBuilder);
   1054 };
   1055 
   1056 
   1057 // A poor man's version of STL's bitset: A bit set of enums E (without explicit
   1058 // values), fitting into an integral type T.
   1059 template <class E, class T = int>
   1060 class EnumSet {
   1061  public:
   1062   explicit EnumSet(T bits = 0) : bits_(bits) {}
   1063   bool IsEmpty() const { return bits_ == 0; }
   1064   bool Contains(E element) const { return (bits_ & Mask(element)) != 0; }
   1065   bool ContainsAnyOf(const EnumSet& set) const {
   1066     return (bits_ & set.bits_) != 0;
   1067   }
   1068   void Add(E element) { bits_ |= Mask(element); }
   1069   void Add(const EnumSet& set) { bits_ |= set.bits_; }
   1070   void Remove(E element) { bits_ &= ~Mask(element); }
   1071   void Remove(const EnumSet& set) { bits_ &= ~set.bits_; }
   1072   void RemoveAll() { bits_ = 0; }
   1073   void Intersect(const EnumSet& set) { bits_ &= set.bits_; }
   1074   T ToIntegral() const { return bits_; }
   1075   bool operator==(const EnumSet& set) { return bits_ == set.bits_; }
   1076   bool operator!=(const EnumSet& set) { return bits_ != set.bits_; }
   1077   EnumSet<E, T> operator|(const EnumSet& set) const {
   1078     return EnumSet<E, T>(bits_ | set.bits_);
   1079   }
   1080 
   1081  private:
   1082   T Mask(E element) const {
   1083     // The strange typing in ASSERT is necessary to avoid stupid warnings, see:
   1084     // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43680
   1085     ASSERT(static_cast<int>(element) < static_cast<int>(sizeof(T) * CHAR_BIT));
   1086     return static_cast<T>(1) << element;
   1087   }
   1088 
   1089   T bits_;
   1090 };
   1091 
   1092 
   1093 class TypeFeedbackId {
   1094  public:
   1095   explicit TypeFeedbackId(int id) : id_(id) { }
   1096   int ToInt() const { return id_; }
   1097 
   1098   static TypeFeedbackId None() { return TypeFeedbackId(kNoneId); }
   1099   bool IsNone() const { return id_ == kNoneId; }
   1100 
   1101  private:
   1102   static const int kNoneId = -1;
   1103 
   1104   int id_;
   1105 };
   1106 
   1107 
   1108 class BailoutId {
   1109  public:
   1110   explicit BailoutId(int id) : id_(id) { }
   1111   int ToInt() const { return id_; }
   1112 
   1113   static BailoutId None() { return BailoutId(kNoneId); }
   1114   static BailoutId FunctionEntry() { return BailoutId(kFunctionEntryId); }
   1115   static BailoutId Declarations() { return BailoutId(kDeclarationsId); }
   1116   static BailoutId FirstUsable() { return BailoutId(kFirstUsableId); }
   1117   static BailoutId StubEntry() { return BailoutId(kStubEntryId); }
   1118 
   1119   bool IsNone() const { return id_ == kNoneId; }
   1120   bool operator==(const BailoutId& other) const { return id_ == other.id_; }
   1121 
   1122  private:
   1123   static const int kNoneId = -1;
   1124 
   1125   // Using 0 could disguise errors.
   1126   static const int kFunctionEntryId = 2;
   1127 
   1128   // This AST id identifies the point after the declarations have been visited.
   1129   // We need it to capture the environment effects of declarations that emit
   1130   // code (function declarations).
   1131   static const int kDeclarationsId = 3;
   1132 
   1133   // Every FunctionState starts with this id.
   1134   static const int kFirstUsableId = 4;
   1135 
   1136   // Every compiled stub starts with this id.
   1137   static const int kStubEntryId = 5;
   1138 
   1139   int id_;
   1140 };
   1141 
   1142 } }  // namespace v8::internal
   1143 
   1144 #endif  // V8_UTILS_H_
   1145