utils.h revision 592a9fc1d8ea420377a2e7efd0600e20b058be2b
1// Copyright 2011 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 <climits> 34 35#include "globals.h" 36#include "checks.h" 37#include "allocation.h" 38 39namespace v8 { 40namespace internal { 41 42// ---------------------------------------------------------------------------- 43// General helper functions 44 45#define IS_POWER_OF_TWO(x) (((x) & ((x) - 1)) == 0) 46 47// Returns true iff x is a power of 2 (or zero). Cannot be used with the 48// maximally negative value of the type T (the -1 overflows). 49template <typename T> 50inline bool IsPowerOf2(T x) { 51 return IS_POWER_OF_TWO(x); 52} 53 54 55// X must be a power of 2. Returns the number of trailing zeros. 56inline int WhichPowerOf2(uint32_t x) { 57 ASSERT(IsPowerOf2(x)); 58 ASSERT(x != 0); 59 int bits = 0; 60#ifdef DEBUG 61 int original_x = x; 62#endif 63 if (x >= 0x10000) { 64 bits += 16; 65 x >>= 16; 66 } 67 if (x >= 0x100) { 68 bits += 8; 69 x >>= 8; 70 } 71 if (x >= 0x10) { 72 bits += 4; 73 x >>= 4; 74 } 75 switch (x) { 76 default: UNREACHABLE(); 77 case 8: bits++; // Fall through. 78 case 4: bits++; // Fall through. 79 case 2: bits++; // Fall through. 80 case 1: break; 81 } 82 ASSERT_EQ(1 << bits, original_x); 83 return bits; 84 return 0; 85} 86 87 88// The C++ standard leaves the semantics of '>>' undefined for 89// negative signed operands. Most implementations do the right thing, 90// though. 91inline int ArithmeticShiftRight(int x, int s) { 92 return x >> s; 93} 94 95 96// Compute the 0-relative offset of some absolute value x of type T. 97// This allows conversion of Addresses and integral types into 98// 0-relative int offsets. 99template <typename T> 100inline intptr_t OffsetFrom(T x) { 101 return x - static_cast<T>(0); 102} 103 104 105// Compute the absolute value of type T for some 0-relative offset x. 106// This allows conversion of 0-relative int offsets into Addresses and 107// integral types. 108template <typename T> 109inline T AddressFrom(intptr_t x) { 110 return static_cast<T>(static_cast<T>(0) + x); 111} 112 113 114// Return the largest multiple of m which is <= x. 115template <typename T> 116inline T RoundDown(T x, intptr_t m) { 117 ASSERT(IsPowerOf2(m)); 118 return AddressFrom<T>(OffsetFrom(x) & -m); 119} 120 121 122// Return the smallest multiple of m which is >= x. 123template <typename T> 124inline T RoundUp(T x, intptr_t m) { 125 return RoundDown<T>(static_cast<T>(x + m - 1), m); 126} 127 128 129template <typename T> 130int Compare(const T& a, const T& b) { 131 if (a == b) 132 return 0; 133 else if (a < b) 134 return -1; 135 else 136 return 1; 137} 138 139 140template <typename T> 141int PointerValueCompare(const T* a, const T* b) { 142 return Compare<T>(*a, *b); 143} 144 145 146// Compare function to compare the object pointer value of two 147// handlified objects. The handles are passed as pointers to the 148// handles. 149template<typename T> class Handle; // Forward declaration. 150template <typename T> 151int HandleObjectPointerCompare(const Handle<T>* a, const Handle<T>* b) { 152 return Compare<T*>(*(*a), *(*b)); 153} 154 155 156// Returns the smallest power of two which is >= x. If you pass in a 157// number that is already a power of two, it is returned as is. 158// Implementation is from "Hacker's Delight" by Henry S. Warren, Jr., 159// figure 3-3, page 48, where the function is called clp2. 160inline uint32_t RoundUpToPowerOf2(uint32_t x) { 161 ASSERT(x <= 0x80000000u); 162 x = x - 1; 163 x = x | (x >> 1); 164 x = x | (x >> 2); 165 x = x | (x >> 4); 166 x = x | (x >> 8); 167 x = x | (x >> 16); 168 return x + 1; 169} 170 171 172inline uint32_t RoundDownToPowerOf2(uint32_t x) { 173 uint32_t rounded_up = RoundUpToPowerOf2(x); 174 if (rounded_up > x) return rounded_up >> 1; 175 return rounded_up; 176} 177 178 179template <typename T, typename U> 180inline bool IsAligned(T value, U alignment) { 181 return (value & (alignment - 1)) == 0; 182} 183 184 185// Returns true if (addr + offset) is aligned. 186inline bool IsAddressAligned(Address addr, 187 intptr_t alignment, 188 int offset = 0) { 189 intptr_t offs = OffsetFrom(addr + offset); 190 return IsAligned(offs, alignment); 191} 192 193 194// Returns the maximum of the two parameters. 195template <typename T> 196T Max(T a, T b) { 197 return a < b ? b : a; 198} 199 200 201// Returns the minimum of the two parameters. 202template <typename T> 203T Min(T a, T b) { 204 return a < b ? a : b; 205} 206 207 208inline int StrLength(const char* string) { 209 size_t length = strlen(string); 210 ASSERT(length == static_cast<size_t>(static_cast<int>(length))); 211 return static_cast<int>(length); 212} 213 214 215// ---------------------------------------------------------------------------- 216// BitField is a help template for encoding and decode bitfield with 217// unsigned content. 218template<class T, int shift, int size> 219class BitField { 220 public: 221 // A uint32_t mask of bit field. To use all bits of a uint32 in a 222 // bitfield without compiler warnings we have to compute 2^32 without 223 // using a shift count of 32. 224 static const uint32_t kMask = ((1U << shift) << size) - (1U << shift); 225 226 // Value for the field with all bits set. 227 static const T kMax = static_cast<T>((1U << size) - 1); 228 229 // Tells whether the provided value fits into the bit field. 230 static bool is_valid(T value) { 231 return (static_cast<uint32_t>(value) & ~static_cast<uint32_t>(kMax)) == 0; 232 } 233 234 // Returns a uint32_t with the bit field value encoded. 235 static uint32_t encode(T value) { 236 ASSERT(is_valid(value)); 237 return static_cast<uint32_t>(value) << shift; 238 } 239 240 // Returns a uint32_t with the bit field value updated. 241 static uint32_t update(uint32_t previous, T value) { 242 return (previous & ~kMask) | encode(value); 243 } 244 245 // Extracts the bit field from the value. 246 static T decode(uint32_t value) { 247 return static_cast<T>((value & kMask) >> shift); 248 } 249}; 250 251 252// ---------------------------------------------------------------------------- 253// Hash function. 254 255// Thomas Wang, Integer Hash Functions. 256// http://www.concentric.net/~Ttwang/tech/inthash.htm 257inline uint32_t ComputeIntegerHash(uint32_t key) { 258 uint32_t hash = key; 259 hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1; 260 hash = hash ^ (hash >> 12); 261 hash = hash + (hash << 2); 262 hash = hash ^ (hash >> 4); 263 hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11); 264 hash = hash ^ (hash >> 16); 265 return hash; 266} 267 268 269inline uint32_t ComputeLongHash(uint64_t key) { 270 uint64_t hash = key; 271 hash = ~hash + (hash << 18); // hash = (hash << 18) - hash - 1; 272 hash = hash ^ (hash >> 31); 273 hash = hash * 21; // hash = (hash + (hash << 2)) + (hash << 4); 274 hash = hash ^ (hash >> 11); 275 hash = hash + (hash << 6); 276 hash = hash ^ (hash >> 22); 277 return (uint32_t) hash; 278} 279 280 281inline uint32_t ComputePointerHash(void* ptr) { 282 return ComputeIntegerHash( 283 static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr))); 284} 285 286 287// ---------------------------------------------------------------------------- 288// Miscellaneous 289 290// A static resource holds a static instance that can be reserved in 291// a local scope using an instance of Access. Attempts to re-reserve 292// the instance will cause an error. 293template <typename T> 294class StaticResource { 295 public: 296 StaticResource() : is_reserved_(false) {} 297 298 private: 299 template <typename S> friend class Access; 300 T instance_; 301 bool is_reserved_; 302}; 303 304 305// Locally scoped access to a static resource. 306template <typename T> 307class Access { 308 public: 309 explicit Access(StaticResource<T>* resource) 310 : resource_(resource) 311 , instance_(&resource->instance_) { 312 ASSERT(!resource->is_reserved_); 313 resource->is_reserved_ = true; 314 } 315 316 ~Access() { 317 resource_->is_reserved_ = false; 318 resource_ = NULL; 319 instance_ = NULL; 320 } 321 322 T* value() { return instance_; } 323 T* operator -> () { return instance_; } 324 325 private: 326 StaticResource<T>* resource_; 327 T* instance_; 328}; 329 330 331template <typename T> 332class Vector { 333 public: 334 Vector() : start_(NULL), length_(0) {} 335 Vector(T* data, int length) : start_(data), length_(length) { 336 ASSERT(length == 0 || (length > 0 && data != NULL)); 337 } 338 339 static Vector<T> New(int length) { 340 return Vector<T>(NewArray<T>(length), length); 341 } 342 343 // Returns a vector using the same backing storage as this one, 344 // spanning from and including 'from', to but not including 'to'. 345 Vector<T> SubVector(int from, int to) { 346 ASSERT(to <= length_); 347 ASSERT(from < to); 348 ASSERT(0 <= from); 349 return Vector<T>(start() + from, to - from); 350 } 351 352 // Returns the length of the vector. 353 int length() const { return length_; } 354 355 // Returns whether or not the vector is empty. 356 bool is_empty() const { return length_ == 0; } 357 358 // Returns the pointer to the start of the data in the vector. 359 T* start() const { return start_; } 360 361 // Access individual vector elements - checks bounds in debug mode. 362 T& operator[](int index) const { 363 ASSERT(0 <= index && index < length_); 364 return start_[index]; 365 } 366 367 const T& at(int index) const { return operator[](index); } 368 369 T& first() { return start_[0]; } 370 371 T& last() { return start_[length_ - 1]; } 372 373 // Returns a clone of this vector with a new backing store. 374 Vector<T> Clone() const { 375 T* result = NewArray<T>(length_); 376 for (int i = 0; i < length_; i++) result[i] = start_[i]; 377 return Vector<T>(result, length_); 378 } 379 380 void Sort(int (*cmp)(const T*, const T*)) { 381 typedef int (*RawComparer)(const void*, const void*); 382 qsort(start(), 383 length(), 384 sizeof(T), 385 reinterpret_cast<RawComparer>(cmp)); 386 } 387 388 void Sort() { 389 Sort(PointerValueCompare<T>); 390 } 391 392 void Truncate(int length) { 393 ASSERT(length <= length_); 394 length_ = length; 395 } 396 397 // Releases the array underlying this vector. Once disposed the 398 // vector is empty. 399 void Dispose() { 400 DeleteArray(start_); 401 start_ = NULL; 402 length_ = 0; 403 } 404 405 inline Vector<T> operator+(int offset) { 406 ASSERT(offset < length_); 407 return Vector<T>(start_ + offset, length_ - offset); 408 } 409 410 // Factory method for creating empty vectors. 411 static Vector<T> empty() { return Vector<T>(NULL, 0); } 412 413 template<typename S> 414 static Vector<T> cast(Vector<S> input) { 415 return Vector<T>(reinterpret_cast<T*>(input.start()), 416 input.length() * sizeof(S) / sizeof(T)); 417 } 418 419 protected: 420 void set_start(T* start) { start_ = start; } 421 422 private: 423 T* start_; 424 int length_; 425}; 426 427 428// A pointer that can only be set once and doesn't allow NULL values. 429template<typename T> 430class SetOncePointer { 431 public: 432 SetOncePointer() : pointer_(NULL) { } 433 434 bool is_set() const { return pointer_ != NULL; } 435 436 T* get() const { 437 ASSERT(pointer_ != NULL); 438 return pointer_; 439 } 440 441 void set(T* value) { 442 ASSERT(pointer_ == NULL && value != NULL); 443 pointer_ = value; 444 } 445 446 private: 447 T* pointer_; 448}; 449 450 451template <typename T, int kSize> 452class EmbeddedVector : public Vector<T> { 453 public: 454 EmbeddedVector() : Vector<T>(buffer_, kSize) { } 455 456 explicit EmbeddedVector(T initial_value) : Vector<T>(buffer_, kSize) { 457 for (int i = 0; i < kSize; ++i) { 458 buffer_[i] = initial_value; 459 } 460 } 461 462 // When copying, make underlying Vector to reference our buffer. 463 EmbeddedVector(const EmbeddedVector& rhs) 464 : Vector<T>(rhs) { 465 memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 466 set_start(buffer_); 467 } 468 469 EmbeddedVector& operator=(const EmbeddedVector& rhs) { 470 if (this == &rhs) return *this; 471 Vector<T>::operator=(rhs); 472 memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 473 this->set_start(buffer_); 474 return *this; 475 } 476 477 private: 478 T buffer_[kSize]; 479}; 480 481 482template <typename T> 483class ScopedVector : public Vector<T> { 484 public: 485 explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { } 486 ~ScopedVector() { 487 DeleteArray(this->start()); 488 } 489 490 private: 491 DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector); 492}; 493 494 495inline Vector<const char> CStrVector(const char* data) { 496 return Vector<const char>(data, StrLength(data)); 497} 498 499inline Vector<char> MutableCStrVector(char* data) { 500 return Vector<char>(data, StrLength(data)); 501} 502 503inline Vector<char> MutableCStrVector(char* data, int max) { 504 int length = StrLength(data); 505 return Vector<char>(data, (length < max) ? length : max); 506} 507 508 509/* 510 * A class that collects values into a backing store. 511 * Specialized versions of the class can allow access to the backing store 512 * in different ways. 513 * There is no guarantee that the backing store is contiguous (and, as a 514 * consequence, no guarantees that consecutively added elements are adjacent 515 * in memory). The collector may move elements unless it has guaranteed not 516 * to. 517 */ 518template <typename T, int growth_factor = 2, int max_growth = 1 * MB> 519class Collector { 520 public: 521 explicit Collector(int initial_capacity = kMinCapacity) 522 : index_(0), size_(0) { 523 current_chunk_ = Vector<T>::New(initial_capacity); 524 } 525 526 virtual ~Collector() { 527 // Free backing store (in reverse allocation order). 528 current_chunk_.Dispose(); 529 for (int i = chunks_.length() - 1; i >= 0; i--) { 530 chunks_.at(i).Dispose(); 531 } 532 } 533 534 // Add a single element. 535 inline void Add(T value) { 536 if (index_ >= current_chunk_.length()) { 537 Grow(1); 538 } 539 current_chunk_[index_] = value; 540 index_++; 541 size_++; 542 } 543 544 // Add a block of contiguous elements and return a Vector backed by the 545 // memory area. 546 // A basic Collector will keep this vector valid as long as the Collector 547 // is alive. 548 inline Vector<T> AddBlock(int size, T initial_value) { 549 ASSERT(size > 0); 550 if (size > current_chunk_.length() - index_) { 551 Grow(size); 552 } 553 T* position = current_chunk_.start() + index_; 554 index_ += size; 555 size_ += size; 556 for (int i = 0; i < size; i++) { 557 position[i] = initial_value; 558 } 559 return Vector<T>(position, size); 560 } 561 562 563 // Add a contiguous block of elements and return a vector backed 564 // by the added block. 565 // A basic Collector will keep this vector valid as long as the Collector 566 // is alive. 567 inline Vector<T> AddBlock(Vector<const T> source) { 568 if (source.length() > current_chunk_.length() - index_) { 569 Grow(source.length()); 570 } 571 T* position = current_chunk_.start() + index_; 572 index_ += source.length(); 573 size_ += source.length(); 574 for (int i = 0; i < source.length(); i++) { 575 position[i] = source[i]; 576 } 577 return Vector<T>(position, source.length()); 578 } 579 580 581 // Write the contents of the collector into the provided vector. 582 void WriteTo(Vector<T> destination) { 583 ASSERT(size_ <= destination.length()); 584 int position = 0; 585 for (int i = 0; i < chunks_.length(); i++) { 586 Vector<T> chunk = chunks_.at(i); 587 for (int j = 0; j < chunk.length(); j++) { 588 destination[position] = chunk[j]; 589 position++; 590 } 591 } 592 for (int i = 0; i < index_; i++) { 593 destination[position] = current_chunk_[i]; 594 position++; 595 } 596 } 597 598 // Allocate a single contiguous vector, copy all the collected 599 // elements to the vector, and return it. 600 // The caller is responsible for freeing the memory of the returned 601 // vector (e.g., using Vector::Dispose). 602 Vector<T> ToVector() { 603 Vector<T> new_store = Vector<T>::New(size_); 604 WriteTo(new_store); 605 return new_store; 606 } 607 608 // Resets the collector to be empty. 609 virtual void Reset(); 610 611 // Total number of elements added to collector so far. 612 inline int size() { return size_; } 613 614 protected: 615 static const int kMinCapacity = 16; 616 List<Vector<T> > chunks_; 617 Vector<T> current_chunk_; // Block of memory currently being written into. 618 int index_; // Current index in current chunk. 619 int size_; // Total number of elements in collector. 620 621 // Creates a new current chunk, and stores the old chunk in the chunks_ list. 622 void Grow(int min_capacity) { 623 ASSERT(growth_factor > 1); 624 int new_capacity; 625 int current_length = current_chunk_.length(); 626 if (current_length < kMinCapacity) { 627 // The collector started out as empty. 628 new_capacity = min_capacity * growth_factor; 629 if (new_capacity < kMinCapacity) new_capacity = kMinCapacity; 630 } else { 631 int growth = current_length * (growth_factor - 1); 632 if (growth > max_growth) { 633 growth = max_growth; 634 } 635 new_capacity = current_length + growth; 636 if (new_capacity < min_capacity) { 637 new_capacity = min_capacity + growth; 638 } 639 } 640 NewChunk(new_capacity); 641 ASSERT(index_ + min_capacity <= current_chunk_.length()); 642 } 643 644 // Before replacing the current chunk, give a subclass the option to move 645 // some of the current data into the new chunk. The function may update 646 // the current index_ value to represent data no longer in the current chunk. 647 // Returns the initial index of the new chunk (after copied data). 648 virtual void NewChunk(int new_capacity) { 649 Vector<T> new_chunk = Vector<T>::New(new_capacity); 650 if (index_ > 0) { 651 chunks_.Add(current_chunk_.SubVector(0, index_)); 652 } else { 653 current_chunk_.Dispose(); 654 } 655 current_chunk_ = new_chunk; 656 index_ = 0; 657 } 658}; 659 660 661/* 662 * A collector that allows sequences of values to be guaranteed to 663 * stay consecutive. 664 * If the backing store grows while a sequence is active, the current 665 * sequence might be moved, but after the sequence is ended, it will 666 * not move again. 667 * NOTICE: Blocks allocated using Collector::AddBlock(int) can move 668 * as well, if inside an active sequence where another element is added. 669 */ 670template <typename T, int growth_factor = 2, int max_growth = 1 * MB> 671class SequenceCollector : public Collector<T, growth_factor, max_growth> { 672 public: 673 explicit SequenceCollector(int initial_capacity) 674 : Collector<T, growth_factor, max_growth>(initial_capacity), 675 sequence_start_(kNoSequence) { } 676 677 virtual ~SequenceCollector() {} 678 679 void StartSequence() { 680 ASSERT(sequence_start_ == kNoSequence); 681 sequence_start_ = this->index_; 682 } 683 684 Vector<T> EndSequence() { 685 ASSERT(sequence_start_ != kNoSequence); 686 int sequence_start = sequence_start_; 687 sequence_start_ = kNoSequence; 688 if (sequence_start == this->index_) return Vector<T>(); 689 return this->current_chunk_.SubVector(sequence_start, this->index_); 690 } 691 692 // Drops the currently added sequence, and all collected elements in it. 693 void DropSequence() { 694 ASSERT(sequence_start_ != kNoSequence); 695 int sequence_length = this->index_ - sequence_start_; 696 this->index_ = sequence_start_; 697 this->size_ -= sequence_length; 698 sequence_start_ = kNoSequence; 699 } 700 701 virtual void Reset() { 702 sequence_start_ = kNoSequence; 703 this->Collector<T, growth_factor, max_growth>::Reset(); 704 } 705 706 private: 707 static const int kNoSequence = -1; 708 int sequence_start_; 709 710 // Move the currently active sequence to the new chunk. 711 virtual void NewChunk(int new_capacity) { 712 if (sequence_start_ == kNoSequence) { 713 // Fall back on default behavior if no sequence has been started. 714 this->Collector<T, growth_factor, max_growth>::NewChunk(new_capacity); 715 return; 716 } 717 int sequence_length = this->index_ - sequence_start_; 718 Vector<T> new_chunk = Vector<T>::New(sequence_length + new_capacity); 719 ASSERT(sequence_length < new_chunk.length()); 720 for (int i = 0; i < sequence_length; i++) { 721 new_chunk[i] = this->current_chunk_[sequence_start_ + i]; 722 } 723 if (sequence_start_ > 0) { 724 this->chunks_.Add(this->current_chunk_.SubVector(0, sequence_start_)); 725 } else { 726 this->current_chunk_.Dispose(); 727 } 728 this->current_chunk_ = new_chunk; 729 this->index_ = sequence_length; 730 sequence_start_ = 0; 731 } 732}; 733 734 735// Compare ASCII/16bit chars to ASCII/16bit chars. 736template <typename lchar, typename rchar> 737inline int CompareChars(const lchar* lhs, const rchar* rhs, int chars) { 738 const lchar* limit = lhs + chars; 739#ifdef V8_HOST_CAN_READ_UNALIGNED 740 if (sizeof(*lhs) == sizeof(*rhs)) { 741 // Number of characters in a uintptr_t. 742 static const int kStepSize = sizeof(uintptr_t) / sizeof(*lhs); // NOLINT 743 while (lhs <= limit - kStepSize) { 744 if (*reinterpret_cast<const uintptr_t*>(lhs) != 745 *reinterpret_cast<const uintptr_t*>(rhs)) { 746 break; 747 } 748 lhs += kStepSize; 749 rhs += kStepSize; 750 } 751 } 752#endif 753 while (lhs < limit) { 754 int r = static_cast<int>(*lhs) - static_cast<int>(*rhs); 755 if (r != 0) return r; 756 ++lhs; 757 ++rhs; 758 } 759 return 0; 760} 761 762 763// Calculate 10^exponent. 764inline int TenToThe(int exponent) { 765 ASSERT(exponent <= 9); 766 ASSERT(exponent >= 1); 767 int answer = 10; 768 for (int i = 1; i < exponent; i++) answer *= 10; 769 return answer; 770} 771 772 773// The type-based aliasing rule allows the compiler to assume that pointers of 774// different types (for some definition of different) never alias each other. 775// Thus the following code does not work: 776// 777// float f = foo(); 778// int fbits = *(int*)(&f); 779// 780// The compiler 'knows' that the int pointer can't refer to f since the types 781// don't match, so the compiler may cache f in a register, leaving random data 782// in fbits. Using C++ style casts makes no difference, however a pointer to 783// char data is assumed to alias any other pointer. This is the 'memcpy 784// exception'. 785// 786// Bit_cast uses the memcpy exception to move the bits from a variable of one 787// type of a variable of another type. Of course the end result is likely to 788// be implementation dependent. Most compilers (gcc-4.2 and MSVC 2005) 789// will completely optimize BitCast away. 790// 791// There is an additional use for BitCast. 792// Recent gccs will warn when they see casts that may result in breakage due to 793// the type-based aliasing rule. If you have checked that there is no breakage 794// you can use BitCast to cast one pointer type to another. This confuses gcc 795// enough that it can no longer see that you have cast one pointer type to 796// another thus avoiding the warning. 797 798// We need different implementations of BitCast for pointer and non-pointer 799// values. We use partial specialization of auxiliary struct to work around 800// issues with template functions overloading. 801template <class Dest, class Source> 802struct BitCastHelper { 803 STATIC_ASSERT(sizeof(Dest) == sizeof(Source)); 804 805 INLINE(static Dest cast(const Source& source)) { 806 Dest dest; 807 memcpy(&dest, &source, sizeof(dest)); 808 return dest; 809 } 810}; 811 812template <class Dest, class Source> 813struct BitCastHelper<Dest, Source*> { 814 INLINE(static Dest cast(Source* source)) { 815 return BitCastHelper<Dest, uintptr_t>:: 816 cast(reinterpret_cast<uintptr_t>(source)); 817 } 818}; 819 820template <class Dest, class Source> 821INLINE(Dest BitCast(const Source& source)); 822 823template <class Dest, class Source> 824inline Dest BitCast(const Source& source) { 825 return BitCastHelper<Dest, Source>::cast(source); 826} 827 828 829template<typename ElementType, int NumElements> 830class EmbeddedContainer { 831 public: 832 EmbeddedContainer() : elems_() { } 833 834 int length() { return NumElements; } 835 ElementType& operator[](int i) { 836 ASSERT(i < length()); 837 return elems_[i]; 838 } 839 840 private: 841 ElementType elems_[NumElements]; 842}; 843 844 845template<typename ElementType> 846class EmbeddedContainer<ElementType, 0> { 847 public: 848 int length() { return 0; } 849 ElementType& operator[](int i) { 850 UNREACHABLE(); 851 static ElementType t = 0; 852 return t; 853 } 854}; 855 856 857// Helper class for building result strings in a character buffer. The 858// purpose of the class is to use safe operations that checks the 859// buffer bounds on all operations in debug mode. 860// This simple base class does not allow formatted output. 861class SimpleStringBuilder { 862 public: 863 // Create a string builder with a buffer of the given size. The 864 // buffer is allocated through NewArray<char> and must be 865 // deallocated by the caller of Finalize(). 866 explicit SimpleStringBuilder(int size); 867 868 SimpleStringBuilder(char* buffer, int size) 869 : buffer_(buffer, size), position_(0) { } 870 871 ~SimpleStringBuilder() { if (!is_finalized()) Finalize(); } 872 873 int size() const { return buffer_.length(); } 874 875 // Get the current position in the builder. 876 int position() const { 877 ASSERT(!is_finalized()); 878 return position_; 879 } 880 881 // Reset the position. 882 void Reset() { position_ = 0; } 883 884 // Add a single character to the builder. It is not allowed to add 885 // 0-characters; use the Finalize() method to terminate the string 886 // instead. 887 void AddCharacter(char c) { 888 ASSERT(c != '\0'); 889 ASSERT(!is_finalized() && position_ < buffer_.length()); 890 buffer_[position_++] = c; 891 } 892 893 // Add an entire string to the builder. Uses strlen() internally to 894 // compute the length of the input string. 895 void AddString(const char* s); 896 897 // Add the first 'n' characters of the given string 's' to the 898 // builder. The input string must have enough characters. 899 void AddSubstring(const char* s, int n); 900 901 // Add character padding to the builder. If count is non-positive, 902 // nothing is added to the builder. 903 void AddPadding(char c, int count); 904 905 // Add the decimal representation of the value. 906 void AddDecimalInteger(int value); 907 908 // Finalize the string by 0-terminating it and returning the buffer. 909 char* Finalize(); 910 911 protected: 912 Vector<char> buffer_; 913 int position_; 914 915 bool is_finalized() const { return position_ < 0; } 916 917 private: 918 DISALLOW_IMPLICIT_CONSTRUCTORS(SimpleStringBuilder); 919}; 920 921 922// A poor man's version of STL's bitset: A bit set of enums E (without explicit 923// values), fitting into an integral type T. 924template <class E, class T = int> 925class EnumSet { 926 public: 927 explicit EnumSet(T bits = 0) : bits_(bits) {} 928 bool IsEmpty() const { return bits_ == 0; } 929 bool Contains(E element) const { return (bits_ & Mask(element)) != 0; } 930 void Add(E element) { bits_ |= Mask(element); } 931 void Remove(E element) { bits_ &= ~Mask(element); } 932 T ToIntegral() const { return bits_; } 933 934 private: 935 T Mask(E element) const { 936 // The strange typing in ASSERT is necessary to avoid stupid warnings, see: 937 // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43680 938 ASSERT(element < static_cast<int>(sizeof(T) * CHAR_BIT)); 939 return 1 << element; 940 } 941 942 T bits_; 943}; 944 945} } // namespace v8::internal 946 947#endif // V8_UTILS_H_ 948