src/v8/src/utils.h

   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 <limits.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <algorithm>
  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 Writer’s 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   bool operator!=(const BailoutId& other) const { return id_ != other.id_; }
1122
1123  private:
1124   static const int kNoneId = -1;
1125
1126   // Using 0 could disguise errors.
1127   static const int kFunctionEntryId = 2;
1128
1129   // This AST id identifies the point after the declarations have been visited.
1130   // We need it to capture the environment effects of declarations that emit
1131   // code (function declarations).
1132   static const int kDeclarationsId = 3;
1133
1134   // Every FunctionState starts with this id.
1135   static const int kFirstUsableId = 4;
1136
1137   // Every compiled stub starts with this id.
1138   static const int kStubEntryId = 5;
1139
1140   int id_;
1141 };
1142
1143
1144 template <class C>
1145 class ContainerPointerWrapper {
1146  public:
1147   typedef typename C::iterator iterator;
1148   typedef typename C::reverse_iterator reverse_iterator;
1149   explicit ContainerPointerWrapper(C* container) : container_(container) {}
1150   iterator begin() { return container_->begin(); }
1151   iterator end() { return container_->end(); }
1152   reverse_iterator rbegin() { return container_->rbegin(); }
1153   reverse_iterator rend() { return container_->rend(); }
1154  private:
1155   C* container_;
1156 };
1157
1158 } }  // namespace v8::internal
1159
1160 #endif  // V8_UTILS_H_