13ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// Copyright 2012 the V8 project authors. All rights reserved. 2a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Redistribution and use in source and binary forms, with or without 3a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// modification, are permitted provided that the following conditions are 4a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// met: 5a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 6a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Redistributions of source code must retain the above copyright 7a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// notice, this list of conditions and the following disclaimer. 8a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Redistributions in binary form must reproduce the above 9a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// copyright notice, this list of conditions and the following 10a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// disclaimer in the documentation and/or other materials provided 11a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// with the distribution. 12a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// * Neither the name of Google Inc. nor the names of its 13a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// contributors may be used to endorse or promote products derived 14a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// from this software without specific prior written permission. 15a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 16a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 28a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#ifndef V8_UTILS_H_ 29a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#define V8_UTILS_H_ 30a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 31a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#include <stdlib.h> 326ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#include <string.h> 3369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch#include <climits> 34a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 358a31eba00023874d4a1dcdc5f411cc4336776874Shimeng (Simon) Wang#include "globals.h" 363e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu#include "checks.h" 378a31eba00023874d4a1dcdc5f411cc4336776874Shimeng (Simon) Wang#include "allocation.h" 383e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu 39a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocknamespace v8 { 40a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocknamespace internal { 41a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 42a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ---------------------------------------------------------------------------- 43a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// General helper functions 44a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 457f4d5bd8c03935e2c0cd412e561b8fc5a6a880aeBen Murdoch#define IS_POWER_OF_TWO(x) (((x) & ((x) - 1)) == 0) 467f4d5bd8c03935e2c0cd412e561b8fc5a6a880aeBen Murdoch 473ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block// Returns true iff x is a power of 2 (or zero). Cannot be used with the 483ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block// maximally negative value of the type T (the -1 overflows). 49a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline bool IsPowerOf2(T x) { 517f4d5bd8c03935e2c0cd412e561b8fc5a6a880aeBen Murdoch return IS_POWER_OF_TWO(x); 52a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 53a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 54a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 559dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen// X must be a power of 2. Returns the number of trailing zeros. 563ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline int WhichPowerOf2(uint32_t x) { 579dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen ASSERT(IsPowerOf2(x)); 589dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen ASSERT(x != 0); 599dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen int bits = 0; 609dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen#ifdef DEBUG 619dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen int original_x = x; 629dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen#endif 639dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen if (x >= 0x10000) { 649dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen bits += 16; 659dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen x >>= 16; 669dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen } 679dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen if (x >= 0x100) { 689dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen bits += 8; 699dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen x >>= 8; 709dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen } 719dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen if (x >= 0x10) { 729dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen bits += 4; 739dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen x >>= 4; 749dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen } 759dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen switch (x) { 769dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen default: UNREACHABLE(); 779dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen case 8: bits++; // Fall through. 789dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen case 4: bits++; // Fall through. 799dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen case 2: bits++; // Fall through. 809dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen case 1: break; 819dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen } 829dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen ASSERT_EQ(1 << bits, original_x); 839dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen return bits; 849dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen return 0; 859dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen} 869dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen 879dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen 88a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// The C++ standard leaves the semantics of '>>' undefined for 89a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// negative signed operands. Most implementations do the right thing, 90a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// though. 913ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline int ArithmeticShiftRight(int x, int s) { 92a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return x >> s; 93a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 94a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 95a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 96a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Compute the 0-relative offset of some absolute value x of type T. 97a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This allows conversion of Addresses and integral types into 98a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 0-relative int offsets. 99a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 1003ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline intptr_t OffsetFrom(T x) { 101a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return x - static_cast<T>(0); 102a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 103a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 104a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 105a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Compute the absolute value of type T for some 0-relative offset x. 106a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This allows conversion of 0-relative int offsets into Addresses and 107a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// integral types. 108a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 1093ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline T AddressFrom(intptr_t x) { 110d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block return static_cast<T>(static_cast<T>(0) + x); 111a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 112a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 113a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 114a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Return the largest multiple of m which is <= x. 115a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 1163ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline T RoundDown(T x, intptr_t m) { 117a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(IsPowerOf2(m)); 118a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return AddressFrom<T>(OffsetFrom(x) & -m); 119a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 120a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 121a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 122a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Return the smallest multiple of m which is >= x. 123a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 1243ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline T RoundUp(T x, intptr_t m) { 1253ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return RoundDown<T>(static_cast<T>(x + m - 1), m); 126a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 127a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 128a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 129a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 1303ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochint Compare(const T& a, const T& b) { 131a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (a == b) 132a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return 0; 133a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else if (a < b) 134a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return -1; 135a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else 136a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return 1; 137a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 138a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 139a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 140a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 1413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochint PointerValueCompare(const T* a, const T* b) { 142a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Compare<T>(*a, *b); 143a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 144a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 145a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1463ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// Compare function to compare the object pointer value of two 1473ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// handlified objects. The handles are passed as pointers to the 1483ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch// handles. 1493ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate<typename T> class Handle; // Forward declaration. 1503ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate <typename T> 1513ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochint HandleObjectPointerCompare(const Handle<T>* a, const Handle<T>* b) { 1523ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return Compare<T*>(*(*a), *(*b)); 1533ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 1543ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1553ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 156a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Returns the smallest power of two which is >= x. If you pass in a 157a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// number that is already a power of two, it is returned as is. 1583e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu// Implementation is from "Hacker's Delight" by Henry S. Warren, Jr., 1593e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu// figure 3-3, page 48, where the function is called clp2. 1603ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline uint32_t RoundUpToPowerOf2(uint32_t x) { 1613e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu ASSERT(x <= 0x80000000u); 1623e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x - 1; 1633e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x | (x >> 1); 1643e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x | (x >> 2); 1653e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x | (x >> 4); 1663e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x | (x >> 8); 1673e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x | (x >> 16); 1683e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu return x + 1; 1693e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu} 1703e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu 171a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 1723ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline uint32_t RoundDownToPowerOf2(uint32_t x) { 1733ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch uint32_t rounded_up = RoundUpToPowerOf2(x); 1743ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch if (rounded_up > x) return rounded_up >> 1; 1753ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return rounded_up; 1763ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 177592a9fc1d8ea420377a2e7efd0600e20b058be2bBen Murdoch 1783ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochtemplate <typename T, typename U> 1803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline bool IsAligned(T value, U alignment) { 181a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return (value & (alignment - 1)) == 0; 182a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 183a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 184a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 185a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Returns true if (addr + offset) is aligned. 1863ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline bool IsAddressAligned(Address addr, 1873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch intptr_t alignment, 1883ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch int offset = 0) { 189a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block intptr_t offs = OffsetFrom(addr + offset); 190a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return IsAligned(offs, alignment); 191a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 192a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 193a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 194a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Returns the maximum of the two parameters. 195a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 1963ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochT Max(T a, T b) { 197a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return a < b ? b : a; 198a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 199a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 200a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 201a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Returns the minimum of the two parameters. 202a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 2033ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochT Min(T a, T b) { 204a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return a < b ? a : b; 205a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 206a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 207a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 208d0582a6c46733687d045e4188a1bcd0123c758a1Steve Blockinline int StrLength(const char* string) { 209d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block size_t length = strlen(string); 210d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block ASSERT(length == static_cast<size_t>(static_cast<int>(length))); 211d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block return static_cast<int>(length); 212d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block} 213d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block 214d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block 215a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ---------------------------------------------------------------------------- 216a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// BitField is a help template for encoding and decode bitfield with 217a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// unsigned content. 218a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<class T, int shift, int size> 219a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass BitField { 220a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 221589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch // A uint32_t mask of bit field. To use all bits of a uint32 in a 222589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch // bitfield without compiler warnings we have to compute 2^32 without 223589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch // using a shift count of 32. 224589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch static const uint32_t kMask = ((1U << shift) << size) - (1U << shift); 225589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch 226589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch // Value for the field with all bits set. 227589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch static const T kMax = static_cast<T>((1U << size) - 1); 228589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch 229a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Tells whether the provided value fits into the bit field. 230a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static bool is_valid(T value) { 231589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch return (static_cast<uint32_t>(value) & ~static_cast<uint32_t>(kMax)) == 0; 232a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 233a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 234a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns a uint32_t with the bit field value encoded. 235a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static uint32_t encode(T value) { 236a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(is_valid(value)); 237a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return static_cast<uint32_t>(value) << shift; 238a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 239a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 240257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch // Returns a uint32_t with the bit field value updated. 241257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch static uint32_t update(uint32_t previous, T value) { 242589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch return (previous & ~kMask) | encode(value); 243257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch } 244257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 245a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Extracts the bit field from the value. 246a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static T decode(uint32_t value) { 247589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch return static_cast<T>((value & kMask) >> shift); 248b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 249a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 250a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 251a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 252a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ---------------------------------------------------------------------------- 253a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Hash function. 254a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 255c7cc028aaeedbbfa11c11d0b7b243b3d9e837ed9Ben Murdochstatic const uint32_t kZeroHashSeed = 0; 256c7cc028aaeedbbfa11c11d0b7b243b3d9e837ed9Ben Murdoch 2573e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu// Thomas Wang, Integer Hash Functions. 2583e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu// http://www.concentric.net/~Ttwang/tech/inthash.htm 2593ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline uint32_t ComputeIntegerHash(uint32_t key, uint32_t seed) { 2603e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu uint32_t hash = key; 261c7cc028aaeedbbfa11c11d0b7b243b3d9e837ed9Ben Murdoch hash = hash ^ seed; 2623e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1; 2633e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = hash ^ (hash >> 12); 2643e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = hash + (hash << 2); 2653e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = hash ^ (hash >> 4); 2663e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11); 2673e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = hash ^ (hash >> 16); 2683e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu return hash; 2693e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu} 270a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 271a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 2723ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline uint32_t ComputeLongHash(uint64_t key) { 2733ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch uint64_t hash = key; 2743ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch hash = ~hash + (hash << 18); // hash = (hash << 18) - hash - 1; 2753ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch hash = hash ^ (hash >> 31); 2763ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch hash = hash * 21; // hash = (hash + (hash << 2)) + (hash << 4); 2773ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch hash = hash ^ (hash >> 11); 2783ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch hash = hash + (hash << 6); 2793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch hash = hash ^ (hash >> 22); 2803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return (uint32_t) hash; 2813ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 2823ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2833ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 2843ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline uint32_t ComputePointerHash(void* ptr) { 285257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch return ComputeIntegerHash( 286c7cc028aaeedbbfa11c11d0b7b243b3d9e837ed9Ben Murdoch static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr)), 287c7cc028aaeedbbfa11c11d0b7b243b3d9e837ed9Ben Murdoch v8::internal::kZeroHashSeed); 288257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch} 289257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 290257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 291a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ---------------------------------------------------------------------------- 292a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Miscellaneous 293a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 294a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// A static resource holds a static instance that can be reserved in 295a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// a local scope using an instance of Access. Attempts to re-reserve 296a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// the instance will cause an error. 297a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 298a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass StaticResource { 299a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 300a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block StaticResource() : is_reserved_(false) {} 301a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 302a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block private: 303a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block template <typename S> friend class Access; 304a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T instance_; 305a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block bool is_reserved_; 306a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 307a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 308a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 309a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Locally scoped access to a static resource. 310a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 311a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass Access { 312a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 313a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block explicit Access(StaticResource<T>* resource) 314a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block : resource_(resource) 315a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block , instance_(&resource->instance_) { 316a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(!resource->is_reserved_); 317a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block resource->is_reserved_ = true; 318a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 319a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 320a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ~Access() { 321a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block resource_->is_reserved_ = false; 322a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block resource_ = NULL; 323a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block instance_ = NULL; 324a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 325a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 326a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* value() { return instance_; } 327a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* operator -> () { return instance_; } 328a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 329a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block private: 330a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block StaticResource<T>* resource_; 331a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* instance_; 332a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 333a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 334a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 335a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 336a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass Vector { 337a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 338a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Vector() : start_(NULL), length_(0) {} 339a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Vector(T* data, int length) : start_(data), length_(length) { 340a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(length == 0 || (length > 0 && data != NULL)); 341a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 342a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 343a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static Vector<T> New(int length) { 344a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Vector<T>(NewArray<T>(length), length); 345a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 346a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 347a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns a vector using the same backing storage as this one, 348a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // spanning from and including 'from', to but not including 'to'. 349a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Vector<T> SubVector(int from, int to) { 350a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(to <= length_); 351a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(from < to); 35280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(0 <= from); 353a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Vector<T>(start() + from, to - from); 354a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 355a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 356a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns the length of the vector. 357a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block int length() const { return length_; } 358a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 359a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns whether or not the vector is empty. 360a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block bool is_empty() const { return length_ == 0; } 361a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 362a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns the pointer to the start of the data in the vector. 363a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* start() const { return start_; } 364a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 365a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Access individual vector elements - checks bounds in debug mode. 366a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T& operator[](int index) const { 367a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(0 <= index && index < length_); 368a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return start_[index]; 369a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 370a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 371b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const T& at(int index) const { return operator[](index); } 3728a31eba00023874d4a1dcdc5f411cc4336776874Shimeng (Simon) Wang 373a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T& first() { return start_[0]; } 374a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 375a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T& last() { return start_[length_ - 1]; } 376a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 377a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns a clone of this vector with a new backing store. 378a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Vector<T> Clone() const { 379a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* result = NewArray<T>(length_); 380a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (int i = 0; i < length_; i++) result[i] = start_[i]; 381a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Vector<T>(result, length_); 382a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 383a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 384a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Sort(int (*cmp)(const T*, const T*)) { 385a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block typedef int (*RawComparer)(const void*, const void*); 386a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block qsort(start(), 387a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block length(), 388a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block sizeof(T), 389a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block reinterpret_cast<RawComparer>(cmp)); 390a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 391a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 392a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Sort() { 393a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Sort(PointerValueCompare<T>); 394a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 395a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 396a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Truncate(int length) { 397a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(length <= length_); 398a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block length_ = length; 399a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 400a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 401a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Releases the array underlying this vector. Once disposed the 402a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // vector is empty. 403a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Dispose() { 404a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block DeleteArray(start_); 405a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block start_ = NULL; 406a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block length_ = 0; 407a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 408a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 409a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block inline Vector<T> operator+(int offset) { 410a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(offset < length_); 411a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Vector<T>(start_ + offset, length_ - offset); 412a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 413a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 414a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Factory method for creating empty vectors. 415a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static Vector<T> empty() { return Vector<T>(NULL, 0); } 416a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 4170d5e116f6aee03185f237311a943491bb079a768Kristian Monsen template<typename S> 4180d5e116f6aee03185f237311a943491bb079a768Kristian Monsen static Vector<T> cast(Vector<S> input) { 4190d5e116f6aee03185f237311a943491bb079a768Kristian Monsen return Vector<T>(reinterpret_cast<T*>(input.start()), 4200d5e116f6aee03185f237311a943491bb079a768Kristian Monsen input.length() * sizeof(S) / sizeof(T)); 4210d5e116f6aee03185f237311a943491bb079a768Kristian Monsen } 4220d5e116f6aee03185f237311a943491bb079a768Kristian Monsen 423a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block protected: 424a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void set_start(T* start) { start_ = start; } 425a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 426a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block private: 427a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* start_; 428a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block int length_; 429a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 430a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 431a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 432b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// A pointer that can only be set once and doesn't allow NULL values. 433b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochtemplate<typename T> 434b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass SetOncePointer { 435b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 436b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SetOncePointer() : pointer_(NULL) { } 437b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 438b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool is_set() const { return pointer_ != NULL; } 439b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 440b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch T* get() const { 441b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(pointer_ != NULL); 442b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pointer_; 443b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 444b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 445b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void set(T* value) { 446b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(pointer_ == NULL && value != NULL); 447b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pointer_ = value; 448b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 449b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 450b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 451b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch T* pointer_; 452b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 453b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 454b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 455a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T, int kSize> 456a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass EmbeddedVector : public Vector<T> { 457a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 458a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block EmbeddedVector() : Vector<T>(buffer_, kSize) { } 459a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 460b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch explicit EmbeddedVector(T initial_value) : Vector<T>(buffer_, kSize) { 461b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < kSize; ++i) { 462b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch buffer_[i] = initial_value; 463b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 464b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 465b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 466a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // When copying, make underlying Vector to reference our buffer. 467a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block EmbeddedVector(const EmbeddedVector& rhs) 468a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block : Vector<T>(rhs) { 469a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 470a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block set_start(buffer_); 471a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 472a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 473a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block EmbeddedVector& operator=(const EmbeddedVector& rhs) { 474a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this == &rhs) return *this; 475a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Vector<T>::operator=(rhs); 476a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 4776ded16be15dd865a9b21ea304d5273c8be299c87Steve Block this->set_start(buffer_); 478a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return *this; 479a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 480a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 481a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block private: 482a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T buffer_[kSize]; 483a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 484a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 485a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 486a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 487a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass ScopedVector : public Vector<T> { 488a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 489a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { } 490a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ~ScopedVector() { 491a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block DeleteArray(this->start()); 492a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 49325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 49425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen private: 49525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector); 496a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 497a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 498a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 499a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockinline Vector<const char> CStrVector(const char* data) { 500d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block return Vector<const char>(data, StrLength(data)); 501a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 502a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 503a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockinline Vector<char> MutableCStrVector(char* data) { 504d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block return Vector<char>(data, StrLength(data)); 505a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 506a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 507a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockinline Vector<char> MutableCStrVector(char* data, int max) { 508d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block int length = StrLength(data); 509a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Vector<char>(data, (length < max) ? length : max); 510a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 511a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 512a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 51380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen/* 51480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * A class that collects values into a backing store. 51580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * Specialized versions of the class can allow access to the backing store 51680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * in different ways. 51780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * There is no guarantee that the backing store is contiguous (and, as a 51880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * consequence, no guarantees that consecutively added elements are adjacent 51980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * in memory). The collector may move elements unless it has guaranteed not 52080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * to. 52180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen */ 52280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsentemplate <typename T, int growth_factor = 2, int max_growth = 1 * MB> 52380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsenclass Collector { 52480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen public: 52580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen explicit Collector(int initial_capacity = kMinCapacity) 52680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen : index_(0), size_(0) { 52780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen current_chunk_ = Vector<T>::New(initial_capacity); 52880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 52980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 53080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen virtual ~Collector() { 53180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Free backing store (in reverse allocation order). 53280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen current_chunk_.Dispose(); 53380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int i = chunks_.length() - 1; i >= 0; i--) { 53480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen chunks_.at(i).Dispose(); 53580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 53680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 53780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 53880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Add a single element. 53980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen inline void Add(T value) { 54080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen if (index_ >= current_chunk_.length()) { 54180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Grow(1); 54280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 54380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen current_chunk_[index_] = value; 54480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen index_++; 54580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen size_++; 54680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 54780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 54880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Add a block of contiguous elements and return a Vector backed by the 54980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // memory area. 55080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // A basic Collector will keep this vector valid as long as the Collector 55180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // is alive. 55280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen inline Vector<T> AddBlock(int size, T initial_value) { 55380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(size > 0); 55480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen if (size > current_chunk_.length() - index_) { 55580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Grow(size); 55680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 55780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen T* position = current_chunk_.start() + index_; 55880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen index_ += size; 55980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen size_ += size; 56080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int i = 0; i < size; i++) { 56180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen position[i] = initial_value; 56280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 56380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen return Vector<T>(position, size); 56480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 56580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 56680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 5679fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block // Add a contiguous block of elements and return a vector backed 5689fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block // by the added block. 5699fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block // A basic Collector will keep this vector valid as long as the Collector 5709fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block // is alive. 5719fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block inline Vector<T> AddBlock(Vector<const T> source) { 5729fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (source.length() > current_chunk_.length() - index_) { 5739fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block Grow(source.length()); 5749fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 5759fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block T* position = current_chunk_.start() + index_; 5769fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block index_ += source.length(); 5779fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block size_ += source.length(); 5789fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block for (int i = 0; i < source.length(); i++) { 5799fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block position[i] = source[i]; 5809fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 5819fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block return Vector<T>(position, source.length()); 5829fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 5839fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 5849fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 58580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Write the contents of the collector into the provided vector. 58680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen void WriteTo(Vector<T> destination) { 58780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(size_ <= destination.length()); 58880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int position = 0; 58980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int i = 0; i < chunks_.length(); i++) { 59080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Vector<T> chunk = chunks_.at(i); 59180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int j = 0; j < chunk.length(); j++) { 59280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen destination[position] = chunk[j]; 59380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen position++; 59480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 59580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 59680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int i = 0; i < index_; i++) { 59780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen destination[position] = current_chunk_[i]; 59880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen position++; 59980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 60080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 60180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 60280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Allocate a single contiguous vector, copy all the collected 60380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // elements to the vector, and return it. 60480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // The caller is responsible for freeing the memory of the returned 60580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // vector (e.g., using Vector::Dispose). 60680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Vector<T> ToVector() { 60780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Vector<T> new_store = Vector<T>::New(size_); 60880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen WriteTo(new_store); 60980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen return new_store; 61080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 61180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 61280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Resets the collector to be empty. 613257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch virtual void Reset(); 61480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 61580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Total number of elements added to collector so far. 61680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen inline int size() { return size_; } 61780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 61880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen protected: 61980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen static const int kMinCapacity = 16; 62080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen List<Vector<T> > chunks_; 62180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Vector<T> current_chunk_; // Block of memory currently being written into. 62280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int index_; // Current index in current chunk. 62380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int size_; // Total number of elements in collector. 62480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 62580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Creates a new current chunk, and stores the old chunk in the chunks_ list. 62680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen void Grow(int min_capacity) { 62780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(growth_factor > 1); 628589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch int new_capacity; 629589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch int current_length = current_chunk_.length(); 630589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch if (current_length < kMinCapacity) { 631589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch // The collector started out as empty. 632589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch new_capacity = min_capacity * growth_factor; 633589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch if (new_capacity < kMinCapacity) new_capacity = kMinCapacity; 63480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } else { 635589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch int growth = current_length * (growth_factor - 1); 636589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch if (growth > max_growth) { 637589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch growth = max_growth; 638589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch } 639589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch new_capacity = current_length + growth; 640589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch if (new_capacity < min_capacity) { 641589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch new_capacity = min_capacity + growth; 642589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch } 64380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 644589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch NewChunk(new_capacity); 64580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(index_ + min_capacity <= current_chunk_.length()); 64680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 64780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 64880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Before replacing the current chunk, give a subclass the option to move 64980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // some of the current data into the new chunk. The function may update 65080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // the current index_ value to represent data no longer in the current chunk. 65180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Returns the initial index of the new chunk (after copied data). 652589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch virtual void NewChunk(int new_capacity) { 653589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch Vector<T> new_chunk = Vector<T>::New(new_capacity); 654589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch if (index_ > 0) { 655589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch chunks_.Add(current_chunk_.SubVector(0, index_)); 656589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch } else { 657589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch current_chunk_.Dispose(); 658589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch } 659589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch current_chunk_ = new_chunk; 660589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch index_ = 0; 66180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 66280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen}; 66380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 66480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 66580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen/* 66680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * A collector that allows sequences of values to be guaranteed to 66780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * stay consecutive. 66880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * If the backing store grows while a sequence is active, the current 66980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * sequence might be moved, but after the sequence is ended, it will 67080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * not move again. 67180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * NOTICE: Blocks allocated using Collector::AddBlock(int) can move 67280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * as well, if inside an active sequence where another element is added. 67380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen */ 67480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsentemplate <typename T, int growth_factor = 2, int max_growth = 1 * MB> 67580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsenclass SequenceCollector : public Collector<T, growth_factor, max_growth> { 67680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen public: 67780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen explicit SequenceCollector(int initial_capacity) 67880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen : Collector<T, growth_factor, max_growth>(initial_capacity), 67980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen sequence_start_(kNoSequence) { } 68080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 68180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen virtual ~SequenceCollector() {} 68280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 68380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen void StartSequence() { 68480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(sequence_start_ == kNoSequence); 68580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen sequence_start_ = this->index_; 68680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 68780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 68880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Vector<T> EndSequence() { 68980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(sequence_start_ != kNoSequence); 69080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int sequence_start = sequence_start_; 69180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen sequence_start_ = kNoSequence; 69280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen if (sequence_start == this->index_) return Vector<T>(); 69380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen return this->current_chunk_.SubVector(sequence_start, this->index_); 69480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 69580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 69680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Drops the currently added sequence, and all collected elements in it. 69780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen void DropSequence() { 69880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(sequence_start_ != kNoSequence); 69980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int sequence_length = this->index_ - sequence_start_; 70080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen this->index_ = sequence_start_; 70180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen this->size_ -= sequence_length; 70280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen sequence_start_ = kNoSequence; 70380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 70480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 70580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen virtual void Reset() { 70680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen sequence_start_ = kNoSequence; 70780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen this->Collector<T, growth_factor, max_growth>::Reset(); 70880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 70980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 71080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen private: 71180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen static const int kNoSequence = -1; 71280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int sequence_start_; 71380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 71480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Move the currently active sequence to the new chunk. 715589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch virtual void NewChunk(int new_capacity) { 716589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch if (sequence_start_ == kNoSequence) { 717589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch // Fall back on default behavior if no sequence has been started. 718589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch this->Collector<T, growth_factor, max_growth>::NewChunk(new_capacity); 719589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch return; 72080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 721589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch int sequence_length = this->index_ - sequence_start_; 722589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch Vector<T> new_chunk = Vector<T>::New(sequence_length + new_capacity); 723589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch ASSERT(sequence_length < new_chunk.length()); 724589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch for (int i = 0; i < sequence_length; i++) { 725589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch new_chunk[i] = this->current_chunk_[sequence_start_ + i]; 726589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch } 727589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch if (sequence_start_ > 0) { 728589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch this->chunks_.Add(this->current_chunk_.SubVector(0, sequence_start_)); 729589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch } else { 730589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch this->current_chunk_.Dispose(); 731589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch } 732589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch this->current_chunk_ = new_chunk; 733589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch this->index_ = sequence_length; 734589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch sequence_start_ = 0; 73580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 73680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen}; 73780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 73880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 7396ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Compare ASCII/16bit chars to ASCII/16bit chars. 7406ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate <typename lchar, typename rchar> 7413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline int CompareChars(const lchar* lhs, const rchar* rhs, int chars) { 7426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const lchar* limit = lhs + chars; 7436ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#ifdef V8_HOST_CAN_READ_UNALIGNED 7446ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (sizeof(*lhs) == sizeof(*rhs)) { 7456ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Number of characters in a uintptr_t. 7466ded16be15dd865a9b21ea304d5273c8be299c87Steve Block static const int kStepSize = sizeof(uintptr_t) / sizeof(*lhs); // NOLINT 7476ded16be15dd865a9b21ea304d5273c8be299c87Steve Block while (lhs <= limit - kStepSize) { 7486ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (*reinterpret_cast<const uintptr_t*>(lhs) != 7496ded16be15dd865a9b21ea304d5273c8be299c87Steve Block *reinterpret_cast<const uintptr_t*>(rhs)) { 7506ded16be15dd865a9b21ea304d5273c8be299c87Steve Block break; 7516ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 7526ded16be15dd865a9b21ea304d5273c8be299c87Steve Block lhs += kStepSize; 7536ded16be15dd865a9b21ea304d5273c8be299c87Steve Block rhs += kStepSize; 7546ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 7556ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 7566ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#endif 7576ded16be15dd865a9b21ea304d5273c8be299c87Steve Block while (lhs < limit) { 7586ded16be15dd865a9b21ea304d5273c8be299c87Steve Block int r = static_cast<int>(*lhs) - static_cast<int>(*rhs); 7596ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (r != 0) return r; 7606ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ++lhs; 7616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ++rhs; 7626ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 7636ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return 0; 7646ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 7656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 7666ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 767d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block// Calculate 10^exponent. 7683ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdochinline int TenToThe(int exponent) { 7693e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu ASSERT(exponent <= 9); 7703e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu ASSERT(exponent >= 1); 7713e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu int answer = 10; 7723e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu for (int i = 1; i < exponent; i++) answer *= 10; 7733e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu return answer; 7743e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu} 775d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block 7766ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 7776ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// The type-based aliasing rule allows the compiler to assume that pointers of 7786ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// different types (for some definition of different) never alias each other. 7796ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Thus the following code does not work: 7806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 7816ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// float f = foo(); 7826ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// int fbits = *(int*)(&f); 7836ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 7846ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// The compiler 'knows' that the int pointer can't refer to f since the types 7856ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// don't match, so the compiler may cache f in a register, leaving random data 7866ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// in fbits. Using C++ style casts makes no difference, however a pointer to 7876ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// char data is assumed to alias any other pointer. This is the 'memcpy 7886ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// exception'. 7896ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 7906ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Bit_cast uses the memcpy exception to move the bits from a variable of one 7916ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// type of a variable of another type. Of course the end result is likely to 7926ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// be implementation dependent. Most compilers (gcc-4.2 and MSVC 2005) 7936ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// will completely optimize BitCast away. 7946ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 7956ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// There is an additional use for BitCast. 7966ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Recent gccs will warn when they see casts that may result in breakage due to 7976ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// the type-based aliasing rule. If you have checked that there is no breakage 7986ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// you can use BitCast to cast one pointer type to another. This confuses gcc 7996ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// enough that it can no longer see that you have cast one pointer type to 8006ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// another thus avoiding the warning. 8011e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 8021e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block// We need different implementations of BitCast for pointer and non-pointer 8031e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block// values. We use partial specialization of auxiliary struct to work around 8041e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block// issues with template functions overloading. 8056ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate <class Dest, class Source> 8061e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockstruct BitCastHelper { 8071e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block STATIC_ASSERT(sizeof(Dest) == sizeof(Source)); 8086ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 8091e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block INLINE(static Dest cast(const Source& source)) { 8101e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block Dest dest; 8111e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block memcpy(&dest, &source, sizeof(dest)); 8121e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return dest; 8131e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block } 8141e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block}; 8156ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 816756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merricktemplate <class Dest, class Source> 8171e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockstruct BitCastHelper<Dest, Source*> { 8181e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block INLINE(static Dest cast(Source* source)) { 8191e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return BitCastHelper<Dest, uintptr_t>:: 8201e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block cast(reinterpret_cast<uintptr_t>(source)); 8211e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block } 8221e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block}; 8231e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block 8241e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blocktemplate <class Dest, class Source> 82544f0eee88ff00398ff7f715fab053374d808c90dSteve BlockINLINE(Dest BitCast(const Source& source)); 82644f0eee88ff00398ff7f715fab053374d808c90dSteve Block 82744f0eee88ff00398ff7f715fab053374d808c90dSteve Blocktemplate <class Dest, class Source> 8281e0659c275bb392c045087af4f6b0d7565cb3d77Steve Blockinline Dest BitCast(const Source& source) { 8291e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block return BitCastHelper<Dest, Source>::cast(source); 830756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merrick} 831a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 8323fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8333fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdochtemplate<typename ElementType, int NumElements> 8343fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdochclass EmbeddedContainer { 8353fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch public: 8363fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch EmbeddedContainer() : elems_() { } 8373fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8383fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch int length() { return NumElements; } 8393fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch ElementType& operator[](int i) { 8403fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch ASSERT(i < length()); 8413fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch return elems_[i]; 8423fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch } 8433fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8443fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch private: 8453fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch ElementType elems_[NumElements]; 8463fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch}; 8473fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8483fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8493fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdochtemplate<typename ElementType> 8503fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdochclass EmbeddedContainer<ElementType, 0> { 8513fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch public: 8523fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch int length() { return 0; } 8533fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch ElementType& operator[](int i) { 8543fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch UNREACHABLE(); 8553fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch static ElementType t = 0; 8563fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch return t; 8573fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch } 8583fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch}; 8593fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8603fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8613fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch// Helper class for building result strings in a character buffer. The 8623fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch// purpose of the class is to use safe operations that checks the 8633fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch// buffer bounds on all operations in debug mode. 8643fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch// This simple base class does not allow formatted output. 8653fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdochclass SimpleStringBuilder { 8663fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch public: 8673fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Create a string builder with a buffer of the given size. The 8683fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // buffer is allocated through NewArray<char> and must be 8693fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // deallocated by the caller of Finalize(). 8703fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch explicit SimpleStringBuilder(int size); 8713fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8723fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch SimpleStringBuilder(char* buffer, int size) 8733fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch : buffer_(buffer, size), position_(0) { } 8743fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8753fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch ~SimpleStringBuilder() { if (!is_finalized()) Finalize(); } 8763fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8773fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch int size() const { return buffer_.length(); } 8783fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8793fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Get the current position in the builder. 8803fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch int position() const { 8813fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch ASSERT(!is_finalized()); 8823fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch return position_; 8833fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch } 8843fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8853fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Reset the position. 8863fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch void Reset() { position_ = 0; } 8873fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8883fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Add a single character to the builder. It is not allowed to add 8893fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // 0-characters; use the Finalize() method to terminate the string 8903fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // instead. 8913fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch void AddCharacter(char c) { 8923fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch ASSERT(c != '\0'); 8933fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch ASSERT(!is_finalized() && position_ < buffer_.length()); 8943fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch buffer_[position_++] = c; 8953fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch } 8963fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 8973fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Add an entire string to the builder. Uses strlen() internally to 8983fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // compute the length of the input string. 8993fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch void AddString(const char* s); 9003fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 9013fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Add the first 'n' characters of the given string 's' to the 9023fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // builder. The input string must have enough characters. 9033fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch void AddSubstring(const char* s, int n); 9043fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 9053fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Add character padding to the builder. If count is non-positive, 9063fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // nothing is added to the builder. 9073fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch void AddPadding(char c, int count); 9083fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 9093fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Add the decimal representation of the value. 9103fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch void AddDecimalInteger(int value); 9113fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 9123fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch // Finalize the string by 0-terminating it and returning the buffer. 9133fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch char* Finalize(); 9143fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 9153fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch protected: 9163fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch Vector<char> buffer_; 9173fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch int position_; 9183fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 9193fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch bool is_finalized() const { return position_ < 0; } 920589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch 9213fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch private: 9223fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch DISALLOW_IMPLICIT_CONSTRUCTORS(SimpleStringBuilder); 9233fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch}; 9243fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch 92569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 92669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// A poor man's version of STL's bitset: A bit set of enums E (without explicit 92769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// values), fitting into an integral type T. 92869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdochtemplate <class E, class T = int> 92969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdochclass EnumSet { 93069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch public: 93169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch explicit EnumSet(T bits = 0) : bits_(bits) {} 93269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch bool IsEmpty() const { return bits_ == 0; } 93369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch bool Contains(E element) const { return (bits_ & Mask(element)) != 0; } 9343ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool ContainsAnyOf(const EnumSet& set) const { 9353ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch return (bits_ & set.bits_) != 0; 9363ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 93769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch void Add(E element) { bits_ |= Mask(element); } 9383ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void Add(const EnumSet& set) { bits_ |= set.bits_; } 93969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch void Remove(E element) { bits_ &= ~Mask(element); } 9403ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void Remove(const EnumSet& set) { bits_ &= ~set.bits_; } 9413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void RemoveAll() { bits_ = 0; } 9423ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch void Intersect(const EnumSet& set) { bits_ &= set.bits_; } 94369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch T ToIntegral() const { return bits_; } 9443ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch bool operator==(const EnumSet& set) { return bits_ == set.bits_; } 94569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 94669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch private: 94769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch T Mask(E element) const { 94869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch // The strange typing in ASSERT is necessary to avoid stupid warnings, see: 94969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43680 95069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch ASSERT(element < static_cast<int>(sizeof(T) * CHAR_BIT)); 95169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch return 1 << element; 95269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 95369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 95469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch T bits_; 95569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch}; 95669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 957756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merrick} } // namespace v8::internal 9586ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 959a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#endif // V8_UTILS_H_ 960