utils.h revision a7e24c173cf37484693b9abb38e494fa7bd7baeb
1// Copyright 2006-2008 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 33namespace v8 { 34namespace internal { 35 36// ---------------------------------------------------------------------------- 37// General helper functions 38 39// Returns true iff x is a power of 2. Does not work for zero. 40template <typename T> 41static inline bool IsPowerOf2(T x) { 42 return (x & (x - 1)) == 0; 43} 44 45 46// The C++ standard leaves the semantics of '>>' undefined for 47// negative signed operands. Most implementations do the right thing, 48// though. 49static inline int ArithmeticShiftRight(int x, int s) { 50 return x >> s; 51} 52 53 54// Compute the 0-relative offset of some absolute value x of type T. 55// This allows conversion of Addresses and integral types into 56// 0-relative int offsets. 57template <typename T> 58static inline intptr_t OffsetFrom(T x) { 59 return x - static_cast<T>(0); 60} 61 62 63// Compute the absolute value of type T for some 0-relative offset x. 64// This allows conversion of 0-relative int offsets into Addresses and 65// integral types. 66template <typename T> 67static inline T AddressFrom(intptr_t x) { 68 return static_cast<T>(0) + x; 69} 70 71 72// Return the largest multiple of m which is <= x. 73template <typename T> 74static inline T RoundDown(T x, int m) { 75 ASSERT(IsPowerOf2(m)); 76 return AddressFrom<T>(OffsetFrom(x) & -m); 77} 78 79 80// Return the smallest multiple of m which is >= x. 81template <typename T> 82static inline T RoundUp(T x, int m) { 83 return RoundDown(x + m - 1, m); 84} 85 86 87template <typename T> 88static int Compare(const T& a, const T& b) { 89 if (a == b) 90 return 0; 91 else if (a < b) 92 return -1; 93 else 94 return 1; 95} 96 97 98template <typename T> 99static int PointerValueCompare(const T* a, const T* b) { 100 return Compare<T>(*a, *b); 101} 102 103 104// Returns the smallest power of two which is >= x. If you pass in a 105// number that is already a power of two, it is returned as is. 106uint32_t RoundUpToPowerOf2(uint32_t x); 107 108 109template <typename T> 110static inline bool IsAligned(T value, T alignment) { 111 ASSERT(IsPowerOf2(alignment)); 112 return (value & (alignment - 1)) == 0; 113} 114 115 116// Returns true if (addr + offset) is aligned. 117static inline bool IsAddressAligned(Address addr, 118 intptr_t alignment, 119 int offset) { 120 intptr_t offs = OffsetFrom(addr + offset); 121 return IsAligned(offs, alignment); 122} 123 124 125// Returns the maximum of the two parameters. 126template <typename T> 127static T Max(T a, T b) { 128 return a < b ? b : a; 129} 130 131 132// Returns the minimum of the two parameters. 133template <typename T> 134static T Min(T a, T b) { 135 return a < b ? a : b; 136} 137 138 139// ---------------------------------------------------------------------------- 140// BitField is a help template for encoding and decode bitfield with 141// unsigned content. 142template<class T, int shift, int size> 143class BitField { 144 public: 145 // Tells whether the provided value fits into the bit field. 146 static bool is_valid(T value) { 147 return (static_cast<uint32_t>(value) & ~((1U << (size)) - 1)) == 0; 148 } 149 150 // Returns a uint32_t mask of bit field. 151 static uint32_t mask() { 152 return (1U << (size + shift)) - (1U << shift); 153 } 154 155 // Returns a uint32_t with the bit field value encoded. 156 static uint32_t encode(T value) { 157 ASSERT(is_valid(value)); 158 return static_cast<uint32_t>(value) << shift; 159 } 160 161 // Extracts the bit field from the value. 162 static T decode(uint32_t value) { 163 return static_cast<T>((value >> shift) & ((1U << (size)) - 1)); 164 } 165}; 166 167 168// ---------------------------------------------------------------------------- 169// Support for compressed, machine-independent encoding 170// and decoding of integer values of arbitrary size. 171 172// Encoding and decoding from/to a buffer at position p; 173// the result is the position after the encoded integer. 174// Small signed integers in the range -64 <= x && x < 64 175// are encoded in 1 byte; larger values are encoded in 2 176// or more bytes. At most sizeof(int) + 1 bytes are used 177// in the worst case. 178byte* EncodeInt(byte* p, int x); 179byte* DecodeInt(byte* p, int* x); 180 181 182// Encoding and decoding from/to a buffer at position p - 1 183// moving backward; the result is the position of the last 184// byte written. These routines are useful to read/write 185// into a buffer starting at the end of the buffer. 186byte* EncodeUnsignedIntBackward(byte* p, unsigned int x); 187 188// The decoding function is inlined since its performance is 189// important to mark-sweep garbage collection. 190inline byte* DecodeUnsignedIntBackward(byte* p, unsigned int* x) { 191 byte b = *--p; 192 if (b >= 128) { 193 *x = static_cast<unsigned int>(b) - 128; 194 return p; 195 } 196 unsigned int r = static_cast<unsigned int>(b); 197 unsigned int s = 7; 198 b = *--p; 199 while (b < 128) { 200 r |= static_cast<unsigned int>(b) << s; 201 s += 7; 202 b = *--p; 203 } 204 // b >= 128 205 *x = r | ((static_cast<unsigned int>(b) - 128) << s); 206 return p; 207} 208 209 210// ---------------------------------------------------------------------------- 211// Hash function. 212 213uint32_t ComputeIntegerHash(uint32_t key); 214 215 216// ---------------------------------------------------------------------------- 217// I/O support. 218 219// Our version of printf(). Avoids compilation errors that we get 220// with standard printf when attempting to print pointers, etc. 221// (the errors are due to the extra compilation flags, which we 222// want elsewhere). 223void PrintF(const char* format, ...); 224 225// Our version of fflush. 226void Flush(); 227 228 229// Read a line of characters after printing the prompt to stdout. The resulting 230// char* needs to be disposed off with DeleteArray by the caller. 231char* ReadLine(const char* prompt); 232 233 234// Read and return the raw bytes in a file. the size of the buffer is returned 235// in size. 236// The returned buffer must be freed by the caller. 237byte* ReadBytes(const char* filename, int* size, bool verbose = true); 238 239 240// Write size chars from str to the file given by filename. 241// The file is overwritten. Returns the number of chars written. 242int WriteChars(const char* filename, 243 const char* str, 244 int size, 245 bool verbose = true); 246 247 248// Write size bytes to the file given by filename. 249// The file is overwritten. Returns the number of bytes written. 250int WriteBytes(const char* filename, 251 const byte* bytes, 252 int size, 253 bool verbose = true); 254 255 256// Write the C code 257// const char* <varname> = "<str>"; 258// const int <varname>_len = <len>; 259// to the file given by filename. Only the first len chars are written. 260int WriteAsCFile(const char* filename, const char* varname, 261 const char* str, int size, bool verbose = true); 262 263 264// ---------------------------------------------------------------------------- 265// Miscellaneous 266 267// A static resource holds a static instance that can be reserved in 268// a local scope using an instance of Access. Attempts to re-reserve 269// the instance will cause an error. 270template <typename T> 271class StaticResource { 272 public: 273 StaticResource() : is_reserved_(false) {} 274 275 private: 276 template <typename S> friend class Access; 277 T instance_; 278 bool is_reserved_; 279}; 280 281 282// Locally scoped access to a static resource. 283template <typename T> 284class Access { 285 public: 286 explicit Access(StaticResource<T>* resource) 287 : resource_(resource) 288 , instance_(&resource->instance_) { 289 ASSERT(!resource->is_reserved_); 290 resource->is_reserved_ = true; 291 } 292 293 ~Access() { 294 resource_->is_reserved_ = false; 295 resource_ = NULL; 296 instance_ = NULL; 297 } 298 299 T* value() { return instance_; } 300 T* operator -> () { return instance_; } 301 302 private: 303 StaticResource<T>* resource_; 304 T* instance_; 305}; 306 307 308template <typename T> 309class Vector { 310 public: 311 Vector() : start_(NULL), length_(0) {} 312 Vector(T* data, int length) : start_(data), length_(length) { 313 ASSERT(length == 0 || (length > 0 && data != NULL)); 314 } 315 316 static Vector<T> New(int length) { 317 return Vector<T>(NewArray<T>(length), length); 318 } 319 320 // Returns a vector using the same backing storage as this one, 321 // spanning from and including 'from', to but not including 'to'. 322 Vector<T> SubVector(int from, int to) { 323 ASSERT(from < length_); 324 ASSERT(to <= length_); 325 ASSERT(from < to); 326 return Vector<T>(start() + from, to - from); 327 } 328 329 // Returns the length of the vector. 330 int length() const { return length_; } 331 332 // Returns whether or not the vector is empty. 333 bool is_empty() const { return length_ == 0; } 334 335 // Returns the pointer to the start of the data in the vector. 336 T* start() const { return start_; } 337 338 // Access individual vector elements - checks bounds in debug mode. 339 T& operator[](int index) const { 340 ASSERT(0 <= index && index < length_); 341 return start_[index]; 342 } 343 344 T& first() { return start_[0]; } 345 346 T& last() { return start_[length_ - 1]; } 347 348 // Returns a clone of this vector with a new backing store. 349 Vector<T> Clone() const { 350 T* result = NewArray<T>(length_); 351 for (int i = 0; i < length_; i++) result[i] = start_[i]; 352 return Vector<T>(result, length_); 353 } 354 355 void Sort(int (*cmp)(const T*, const T*)) { 356 typedef int (*RawComparer)(const void*, const void*); 357 qsort(start(), 358 length(), 359 sizeof(T), 360 reinterpret_cast<RawComparer>(cmp)); 361 } 362 363 void Sort() { 364 Sort(PointerValueCompare<T>); 365 } 366 367 void Truncate(int length) { 368 ASSERT(length <= length_); 369 length_ = length; 370 } 371 372 // Releases the array underlying this vector. Once disposed the 373 // vector is empty. 374 void Dispose() { 375 if (is_empty()) return; 376 DeleteArray(start_); 377 start_ = NULL; 378 length_ = 0; 379 } 380 381 inline Vector<T> operator+(int offset) { 382 ASSERT(offset < length_); 383 return Vector<T>(start_ + offset, length_ - offset); 384 } 385 386 // Factory method for creating empty vectors. 387 static Vector<T> empty() { return Vector<T>(NULL, 0); } 388 389 protected: 390 void set_start(T* start) { start_ = start; } 391 392 private: 393 T* start_; 394 int length_; 395}; 396 397 398// A temporary assignment sets a (non-local) variable to a value on 399// construction and resets it the value on destruction. 400template <typename T> 401class TempAssign { 402 public: 403 TempAssign(T* var, T value): var_(var), old_value_(*var) { 404 *var = value; 405 } 406 407 ~TempAssign() { *var_ = old_value_; } 408 409 private: 410 T* var_; 411 T old_value_; 412}; 413 414 415template <typename T, int kSize> 416class EmbeddedVector : public Vector<T> { 417 public: 418 EmbeddedVector() : Vector<T>(buffer_, kSize) { } 419 420 // When copying, make underlying Vector to reference our buffer. 421 EmbeddedVector(const EmbeddedVector& rhs) 422 : Vector<T>(rhs) { 423 memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 424 set_start(buffer_); 425 } 426 427 EmbeddedVector& operator=(const EmbeddedVector& rhs) { 428 if (this == &rhs) return *this; 429 Vector<T>::operator=(rhs); 430 memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 431 set_start(buffer_); 432 return *this; 433 } 434 435 private: 436 T buffer_[kSize]; 437}; 438 439 440template <typename T> 441class ScopedVector : public Vector<T> { 442 public: 443 explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { } 444 ~ScopedVector() { 445 DeleteArray(this->start()); 446 } 447}; 448 449 450inline Vector<const char> CStrVector(const char* data) { 451 return Vector<const char>(data, static_cast<int>(strlen(data))); 452} 453 454inline Vector<char> MutableCStrVector(char* data) { 455 return Vector<char>(data, static_cast<int>(strlen(data))); 456} 457 458inline Vector<char> MutableCStrVector(char* data, int max) { 459 int length = static_cast<int>(strlen(data)); 460 return Vector<char>(data, (length < max) ? length : max); 461} 462 463template <typename T> 464inline Vector< Handle<Object> > HandleVector(v8::internal::Handle<T>* elms, 465 int length) { 466 return Vector< Handle<Object> >( 467 reinterpret_cast<v8::internal::Handle<Object>*>(elms), length); 468} 469 470 471// Simple support to read a file into a 0-terminated C-string. 472// The returned buffer must be freed by the caller. 473// On return, *exits tells whether the file existed. 474Vector<const char> ReadFile(const char* filename, 475 bool* exists, 476 bool verbose = true); 477 478 479// Simple wrapper that allows an ExternalString to refer to a 480// Vector<const char>. Doesn't assume ownership of the data. 481class AsciiStringAdapter: public v8::String::ExternalAsciiStringResource { 482 public: 483 explicit AsciiStringAdapter(Vector<const char> data) : data_(data) {} 484 485 virtual const char* data() const { return data_.start(); } 486 487 virtual size_t length() const { return data_.length(); } 488 489 private: 490 Vector<const char> data_; 491}; 492 493 494// Helper class for building result strings in a character buffer. The 495// purpose of the class is to use safe operations that checks the 496// buffer bounds on all operations in debug mode. 497class StringBuilder { 498 public: 499 // Create a string builder with a buffer of the given size. The 500 // buffer is allocated through NewArray<char> and must be 501 // deallocated by the caller of Finalize(). 502 explicit StringBuilder(int size); 503 504 StringBuilder(char* buffer, int size) 505 : buffer_(buffer, size), position_(0) { } 506 507 ~StringBuilder() { if (!is_finalized()) Finalize(); } 508 509 int size() const { return buffer_.length(); } 510 511 // Get the current position in the builder. 512 int position() const { 513 ASSERT(!is_finalized()); 514 return position_; 515 } 516 517 // Reset the position. 518 void Reset() { position_ = 0; } 519 520 // Add a single character to the builder. It is not allowed to add 521 // 0-characters; use the Finalize() method to terminate the string 522 // instead. 523 void AddCharacter(char c) { 524 ASSERT(c != '\0'); 525 ASSERT(!is_finalized() && position_ < buffer_.length()); 526 buffer_[position_++] = c; 527 } 528 529 // Add an entire string to the builder. Uses strlen() internally to 530 // compute the length of the input string. 531 void AddString(const char* s); 532 533 // Add the first 'n' characters of the given string 's' to the 534 // builder. The input string must have enough characters. 535 void AddSubstring(const char* s, int n); 536 537 // Add formatted contents to the builder just like printf(). 538 void AddFormatted(const char* format, ...); 539 540 // Add character padding to the builder. If count is non-positive, 541 // nothing is added to the builder. 542 void AddPadding(char c, int count); 543 544 // Finalize the string by 0-terminating it and returning the buffer. 545 char* Finalize(); 546 547 private: 548 Vector<char> buffer_; 549 int position_; 550 551 bool is_finalized() const { return position_ < 0; } 552 553 DISALLOW_IMPLICIT_CONSTRUCTORS(StringBuilder); 554}; 555 556 557// Copy from ASCII/16bit chars to ASCII/16bit chars. 558template <typename sourcechar, typename sinkchar> 559static inline void CopyChars(sinkchar* dest, const sourcechar* src, int chars) { 560 sinkchar* limit = dest + chars; 561#ifdef V8_HOST_CAN_READ_UNALIGNED 562 if (sizeof(*dest) == sizeof(*src)) { 563 // Number of characters in a uint32_t. 564 static const int kStepSize = sizeof(uint32_t) / sizeof(*dest); // NOLINT 565 while (dest <= limit - kStepSize) { 566 *reinterpret_cast<uint32_t*>(dest) = 567 *reinterpret_cast<const uint32_t*>(src); 568 dest += kStepSize; 569 src += kStepSize; 570 } 571 } 572#endif 573 while (dest < limit) { 574 *dest++ = static_cast<sinkchar>(*src++); 575 } 576} 577 578 579} } // namespace v8::internal 580 581#endif // V8_UTILS_H_ 582