utils.h revision 9fac840a46e8b7e26894f4792ba26dde14c56b04
1a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Copyright 2006-2008 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> 33a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 348a31eba00023874d4a1dcdc5f411cc4336776874Shimeng (Simon) Wang#include "globals.h" 353e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu#include "checks.h" 368a31eba00023874d4a1dcdc5f411cc4336776874Shimeng (Simon) Wang#include "allocation.h" 373e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu 38a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocknamespace v8 { 39a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocknamespace internal { 40a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 41a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ---------------------------------------------------------------------------- 42a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// General helper functions 43a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 447f4d5bd8c03935e2c0cd412e561b8fc5a6a880aeBen Murdoch#define IS_POWER_OF_TWO(x) (((x) & ((x) - 1)) == 0) 457f4d5bd8c03935e2c0cd412e561b8fc5a6a880aeBen Murdoch 463ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block// Returns true iff x is a power of 2 (or zero). Cannot be used with the 473ce2e2076e8e3e60cf1810eec160ea2d8557e9e7Steve Block// maximally negative value of the type T (the -1 overflows). 48a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 49a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic inline bool IsPowerOf2(T x) { 507f4d5bd8c03935e2c0cd412e561b8fc5a6a880aeBen Murdoch return IS_POWER_OF_TWO(x); 51a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 52a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 53a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 549dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen// X must be a power of 2. Returns the number of trailing zeros. 559dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsentemplate <typename T> 569dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsenstatic inline int WhichPowerOf2(T x) { 579dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen ASSERT(IsPowerOf2(x)); 589dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen ASSERT(x != 0); 599dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen if (x < 0) return 31; 609dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen int bits = 0; 619dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen#ifdef DEBUG 629dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen int original_x = x; 639dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen#endif 649dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen if (x >= 0x10000) { 659dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen bits += 16; 669dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen x >>= 16; 679dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen } 689dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen if (x >= 0x100) { 699dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen bits += 8; 709dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen x >>= 8; 719dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen } 729dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen if (x >= 0x10) { 739dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen bits += 4; 749dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen x >>= 4; 759dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen } 769dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen switch (x) { 779dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen default: UNREACHABLE(); 789dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen case 8: bits++; // Fall through. 799dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen case 4: bits++; // Fall through. 809dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen case 2: bits++; // Fall through. 819dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen case 1: break; 829dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen } 839dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen ASSERT_EQ(1 << bits, original_x); 849dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen return bits; 859dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen return 0; 869dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen} 879dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen 889dcf7e2f83591d471e88bf7d230651900b8e424bKristian Monsen 89a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// The C++ standard leaves the semantics of '>>' undefined for 90a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// negative signed operands. Most implementations do the right thing, 91a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// though. 92a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic inline int ArithmeticShiftRight(int x, int s) { 93a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return x >> s; 94a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 95a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 96a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 97a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Compute the 0-relative offset of some absolute value x of type T. 98a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This allows conversion of Addresses and integral types into 99a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 0-relative int offsets. 100a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 101a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic inline intptr_t OffsetFrom(T x) { 102a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return x - static_cast<T>(0); 103a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 104a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 105a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 106a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Compute the absolute value of type T for some 0-relative offset x. 107a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This allows conversion of 0-relative int offsets into Addresses and 108a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// integral types. 109a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 110a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic inline T AddressFrom(intptr_t x) { 111d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block return static_cast<T>(static_cast<T>(0) + x); 112a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 113a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 114a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 115a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Return the largest multiple of m which is <= x. 116a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 117a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic inline T RoundDown(T x, int m) { 118a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(IsPowerOf2(m)); 119a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return AddressFrom<T>(OffsetFrom(x) & -m); 120a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 121a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 122a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 123a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Return the smallest multiple of m which is >= x. 124a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 125a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic inline T RoundUp(T x, int m) { 126a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return RoundDown(x + m - 1, m); 127a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 128a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 129a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 130a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 131a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic int Compare(const T& a, const T& b) { 132a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (a == b) 133a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return 0; 134a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else if (a < b) 135a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return -1; 136a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else 137a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return 1; 138a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 139a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 140a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 141a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 142a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic int PointerValueCompare(const T* a, const T* b) { 143a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Compare<T>(*a, *b); 144a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 145a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 146a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 147a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Returns the smallest power of two which is >= x. If you pass in a 148a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// number that is already a power of two, it is returned as is. 1493e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu// Implementation is from "Hacker's Delight" by Henry S. Warren, Jr., 1503e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu// figure 3-3, page 48, where the function is called clp2. 1513e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhustatic inline uint32_t RoundUpToPowerOf2(uint32_t x) { 1523e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu ASSERT(x <= 0x80000000u); 1533e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x - 1; 1543e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x | (x >> 1); 1553e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x | (x >> 2); 1563e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x | (x >> 4); 1573e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x | (x >> 8); 1583e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu x = x | (x >> 16); 1593e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu return x + 1; 1603e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu} 1613e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu 162a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 163a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 164a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 165a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic inline bool IsAligned(T value, T alignment) { 166a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(IsPowerOf2(alignment)); 167a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return (value & (alignment - 1)) == 0; 168a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 169a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 170a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 171a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Returns true if (addr + offset) is aligned. 172a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic inline bool IsAddressAligned(Address addr, 173a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block intptr_t alignment, 174a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block int offset) { 175a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block intptr_t offs = OffsetFrom(addr + offset); 176a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return IsAligned(offs, alignment); 177a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 178a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 179a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 180a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Returns the maximum of the two parameters. 181a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 182a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic T Max(T a, T b) { 183a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return a < b ? b : a; 184a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 185a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 186a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 187a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Returns the minimum of the two parameters. 188a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 189a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockstatic T Min(T a, T b) { 190a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return a < b ? a : b; 191a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 192a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 193a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 194d0582a6c46733687d045e4188a1bcd0123c758a1Steve Blockinline int StrLength(const char* string) { 195d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block size_t length = strlen(string); 196d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block ASSERT(length == static_cast<size_t>(static_cast<int>(length))); 197d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block return static_cast<int>(length); 198d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block} 199d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block 200d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block 201a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ---------------------------------------------------------------------------- 202a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// BitField is a help template for encoding and decode bitfield with 203a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// unsigned content. 204a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate<class T, int shift, int size> 205a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass BitField { 206a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 207a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Tells whether the provided value fits into the bit field. 208a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static bool is_valid(T value) { 209a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return (static_cast<uint32_t>(value) & ~((1U << (size)) - 1)) == 0; 210a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 211a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 212a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns a uint32_t mask of bit field. 213a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static uint32_t mask() { 214402d937239b0e2fd11bf2f4fe972ad78aa9fd481Andrei Popescu // To use all bits of a uint32 in a bitfield without compiler warnings we 215402d937239b0e2fd11bf2f4fe972ad78aa9fd481Andrei Popescu // have to compute 2^32 without using a shift count of 32. 216402d937239b0e2fd11bf2f4fe972ad78aa9fd481Andrei Popescu return ((1U << shift) << size) - (1U << shift); 217a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 218a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 219a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns a uint32_t with the bit field value encoded. 220a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static uint32_t encode(T value) { 221a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(is_valid(value)); 222a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return static_cast<uint32_t>(value) << shift; 223a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 224a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 225a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Extracts the bit field from the value. 226a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static T decode(uint32_t value) { 227402d937239b0e2fd11bf2f4fe972ad78aa9fd481Andrei Popescu return static_cast<T>((value & mask()) >> shift); 228a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 229b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 230b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch // Value for the field with all bits set. 231b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch static T max() { 232b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return decode(mask()); 233b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 234a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 235a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 236a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 237a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ---------------------------------------------------------------------------- 238a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Hash function. 239a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 2403e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu// Thomas Wang, Integer Hash Functions. 2413e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu// http://www.concentric.net/~Ttwang/tech/inthash.htm 2423e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhustatic inline uint32_t ComputeIntegerHash(uint32_t key) { 2433e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu uint32_t hash = key; 2443e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1; 2453e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = hash ^ (hash >> 12); 2463e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = hash + (hash << 2); 2473e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = hash ^ (hash >> 4); 2483e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11); 2493e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu hash = hash ^ (hash >> 16); 2503e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu return hash; 2513e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu} 252a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 253a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 254a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// ---------------------------------------------------------------------------- 255a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Miscellaneous 256a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 257a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// A static resource holds a static instance that can be reserved in 258a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// a local scope using an instance of Access. Attempts to re-reserve 259a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// the instance will cause an error. 260a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 261a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass StaticResource { 262a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 263a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block StaticResource() : is_reserved_(false) {} 264a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 265a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block private: 266a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block template <typename S> friend class Access; 267a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T instance_; 268a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block bool is_reserved_; 269a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 270a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 271a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 272a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Locally scoped access to a static resource. 273a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 274a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass Access { 275a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 276a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block explicit Access(StaticResource<T>* resource) 277a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block : resource_(resource) 278a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block , instance_(&resource->instance_) { 279a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(!resource->is_reserved_); 280a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block resource->is_reserved_ = true; 281a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 282a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 283a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ~Access() { 284a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block resource_->is_reserved_ = false; 285a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block resource_ = NULL; 286a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block instance_ = NULL; 287a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 288a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 289a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* value() { return instance_; } 290a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* operator -> () { return instance_; } 291a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 292a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block private: 293a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block StaticResource<T>* resource_; 294a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* instance_; 295a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 296a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 297a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 298a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 299a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass Vector { 300a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 301a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Vector() : start_(NULL), length_(0) {} 302a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Vector(T* data, int length) : start_(data), length_(length) { 303a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(length == 0 || (length > 0 && data != NULL)); 304a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 305a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 306a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static Vector<T> New(int length) { 307a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Vector<T>(NewArray<T>(length), length); 308a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 309a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 310a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns a vector using the same backing storage as this one, 311a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // spanning from and including 'from', to but not including 'to'. 312a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Vector<T> SubVector(int from, int to) { 313a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(to <= length_); 314a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(from < to); 31580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(0 <= from); 316a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Vector<T>(start() + from, to - from); 317a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 318a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 319a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns the length of the vector. 320a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block int length() const { return length_; } 321a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 322a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns whether or not the vector is empty. 323a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block bool is_empty() const { return length_ == 0; } 324a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 325a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns the pointer to the start of the data in the vector. 326a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* start() const { return start_; } 327a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 328a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Access individual vector elements - checks bounds in debug mode. 329a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T& operator[](int index) const { 330a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(0 <= index && index < length_); 331a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return start_[index]; 332a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 333a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 334b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch const T& at(int index) const { return operator[](index); } 3358a31eba00023874d4a1dcdc5f411cc4336776874Shimeng (Simon) Wang 336a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T& first() { return start_[0]; } 337a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 338a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T& last() { return start_[length_ - 1]; } 339a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 340a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Returns a clone of this vector with a new backing store. 341a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Vector<T> Clone() const { 342a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* result = NewArray<T>(length_); 343a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (int i = 0; i < length_; i++) result[i] = start_[i]; 344a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Vector<T>(result, length_); 345a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 346a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 347a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Sort(int (*cmp)(const T*, const T*)) { 348a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block typedef int (*RawComparer)(const void*, const void*); 349a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block qsort(start(), 350a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block length(), 351a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block sizeof(T), 352a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block reinterpret_cast<RawComparer>(cmp)); 353a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 354a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 355a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Sort() { 356a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Sort(PointerValueCompare<T>); 357a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 358a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 359a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Truncate(int length) { 360a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(length <= length_); 361a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block length_ = length; 362a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 363a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 364a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Releases the array underlying this vector. Once disposed the 365a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // vector is empty. 366a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void Dispose() { 367a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block DeleteArray(start_); 368a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block start_ = NULL; 369a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block length_ = 0; 370a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 371a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 372a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block inline Vector<T> operator+(int offset) { 373a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ASSERT(offset < length_); 374a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Vector<T>(start_ + offset, length_ - offset); 375a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 376a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 377a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Factory method for creating empty vectors. 378a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static Vector<T> empty() { return Vector<T>(NULL, 0); } 379a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 3800d5e116f6aee03185f237311a943491bb079a768Kristian Monsen template<typename S> 3810d5e116f6aee03185f237311a943491bb079a768Kristian Monsen static Vector<T> cast(Vector<S> input) { 3820d5e116f6aee03185f237311a943491bb079a768Kristian Monsen return Vector<T>(reinterpret_cast<T*>(input.start()), 3830d5e116f6aee03185f237311a943491bb079a768Kristian Monsen input.length() * sizeof(S) / sizeof(T)); 3840d5e116f6aee03185f237311a943491bb079a768Kristian Monsen } 3850d5e116f6aee03185f237311a943491bb079a768Kristian Monsen 386a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block protected: 387a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block void set_start(T* start) { start_ = start; } 388a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 389a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block private: 390a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T* start_; 391a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block int length_; 392a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 393a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 394a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 395b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch// A pointer that can only be set once and doesn't allow NULL values. 396b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochtemplate<typename T> 397b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass SetOncePointer { 398b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch public: 399b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch SetOncePointer() : pointer_(NULL) { } 400b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 401b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch bool is_set() const { return pointer_ != NULL; } 402b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 403b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch T* get() const { 404b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(pointer_ != NULL); 405b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch return pointer_; 406b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 407b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 408b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch void set(T* value) { 409b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch ASSERT(pointer_ == NULL && value != NULL); 410b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch pointer_ = value; 411b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 412b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 413b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch private: 414b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch T* pointer_; 415b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch}; 416b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 417b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 418a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T, int kSize> 419a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass EmbeddedVector : public Vector<T> { 420a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 421a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block EmbeddedVector() : Vector<T>(buffer_, kSize) { } 422a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 423b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch explicit EmbeddedVector(T initial_value) : Vector<T>(buffer_, kSize) { 424b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch for (int i = 0; i < kSize; ++i) { 425b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch buffer_[i] = initial_value; 426b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 427b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch } 428b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch 429a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // When copying, make underlying Vector to reference our buffer. 430a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block EmbeddedVector(const EmbeddedVector& rhs) 431a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block : Vector<T>(rhs) { 432a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 433a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block set_start(buffer_); 434a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 435a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 436a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block EmbeddedVector& operator=(const EmbeddedVector& rhs) { 437a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this == &rhs) return *this; 438a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Vector<T>::operator=(rhs); 439a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block memcpy(buffer_, rhs.buffer_, sizeof(T) * kSize); 4406ded16be15dd865a9b21ea304d5273c8be299c87Steve Block this->set_start(buffer_); 441a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return *this; 442a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 443a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 444a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block private: 445a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block T buffer_[kSize]; 446a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 447a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 448a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 449a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blocktemplate <typename T> 450a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass ScopedVector : public Vector<T> { 451a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 452a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { } 453a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ~ScopedVector() { 454a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block DeleteArray(this->start()); 455a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 45625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 45725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen private: 45825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector); 459a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 460a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 461a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 462a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockinline Vector<const char> CStrVector(const char* data) { 463d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block return Vector<const char>(data, StrLength(data)); 464a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 465a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 466a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockinline Vector<char> MutableCStrVector(char* data) { 467d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block return Vector<char>(data, StrLength(data)); 468a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 469a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 470a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockinline Vector<char> MutableCStrVector(char* data, int max) { 471d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block int length = StrLength(data); 472a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return Vector<char>(data, (length < max) ? length : max); 473a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 474a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 475a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 47680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen/* 47780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * A class that collects values into a backing store. 47880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * Specialized versions of the class can allow access to the backing store 47980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * in different ways. 48080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * There is no guarantee that the backing store is contiguous (and, as a 48180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * consequence, no guarantees that consecutively added elements are adjacent 48280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * in memory). The collector may move elements unless it has guaranteed not 48380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * to. 48480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen */ 48580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsentemplate <typename T, int growth_factor = 2, int max_growth = 1 * MB> 48680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsenclass Collector { 48780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen public: 48880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen explicit Collector(int initial_capacity = kMinCapacity) 48980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen : index_(0), size_(0) { 49080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen if (initial_capacity < kMinCapacity) { 49180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen initial_capacity = kMinCapacity; 49280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 49380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen current_chunk_ = Vector<T>::New(initial_capacity); 49480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 49580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 49680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen virtual ~Collector() { 49780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Free backing store (in reverse allocation order). 49880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen current_chunk_.Dispose(); 49980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int i = chunks_.length() - 1; i >= 0; i--) { 50080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen chunks_.at(i).Dispose(); 50180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 50280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 50380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 50480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Add a single element. 50580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen inline void Add(T value) { 50680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen if (index_ >= current_chunk_.length()) { 50780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Grow(1); 50880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 50980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen current_chunk_[index_] = value; 51080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen index_++; 51180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen size_++; 51280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 51380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 51480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Add a block of contiguous elements and return a Vector backed by the 51580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // memory area. 51680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // A basic Collector will keep this vector valid as long as the Collector 51780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // is alive. 51880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen inline Vector<T> AddBlock(int size, T initial_value) { 51980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(size > 0); 52080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen if (size > current_chunk_.length() - index_) { 52180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Grow(size); 52280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 52380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen T* position = current_chunk_.start() + index_; 52480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen index_ += size; 52580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen size_ += size; 52680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int i = 0; i < size; i++) { 52780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen position[i] = initial_value; 52880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 52980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen return Vector<T>(position, size); 53080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 53180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 53280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 5339fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block // Add a contiguous block of elements and return a vector backed 5349fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block // by the added block. 5359fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block // A basic Collector will keep this vector valid as long as the Collector 5369fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block // is alive. 5379fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block inline Vector<T> AddBlock(Vector<const T> source) { 5389fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block if (source.length() > current_chunk_.length() - index_) { 5399fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block Grow(source.length()); 5409fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 5419fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block T* position = current_chunk_.start() + index_; 5429fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block index_ += source.length(); 5439fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block size_ += source.length(); 5449fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block for (int i = 0; i < source.length(); i++) { 5459fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block position[i] = source[i]; 5469fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 5479fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block return Vector<T>(position, source.length()); 5489fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block } 5499fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 5509fac840a46e8b7e26894f4792ba26dde14c56b04Steve Block 55180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Write the contents of the collector into the provided vector. 55280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen void WriteTo(Vector<T> destination) { 55380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(size_ <= destination.length()); 55480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int position = 0; 55580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int i = 0; i < chunks_.length(); i++) { 55680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Vector<T> chunk = chunks_.at(i); 55780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int j = 0; j < chunk.length(); j++) { 55880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen destination[position] = chunk[j]; 55980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen position++; 56080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 56180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 56280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int i = 0; i < index_; i++) { 56380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen destination[position] = current_chunk_[i]; 56480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen position++; 56580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 56680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 56780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 56880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Allocate a single contiguous vector, copy all the collected 56980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // elements to the vector, and return it. 57080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // The caller is responsible for freeing the memory of the returned 57180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // vector (e.g., using Vector::Dispose). 57280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Vector<T> ToVector() { 57380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Vector<T> new_store = Vector<T>::New(size_); 57480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen WriteTo(new_store); 57580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen return new_store; 57680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 57780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 57880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Resets the collector to be empty. 57980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen virtual void Reset() { 58080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int i = chunks_.length() - 1; i >= 0; i--) { 58180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen chunks_.at(i).Dispose(); 58280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 58380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen chunks_.Rewind(0); 58480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen index_ = 0; 58580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen size_ = 0; 58680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 58780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 58880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Total number of elements added to collector so far. 58980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen inline int size() { return size_; } 59080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 59180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen protected: 59280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen static const int kMinCapacity = 16; 59380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen List<Vector<T> > chunks_; 59480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Vector<T> current_chunk_; // Block of memory currently being written into. 59580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int index_; // Current index in current chunk. 59680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int size_; // Total number of elements in collector. 59780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 59880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Creates a new current chunk, and stores the old chunk in the chunks_ list. 59980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen void Grow(int min_capacity) { 60080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(growth_factor > 1); 60180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int growth = current_chunk_.length() * (growth_factor - 1); 60280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen if (growth > max_growth) { 60380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen growth = max_growth; 60480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 60580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int new_capacity = current_chunk_.length() + growth; 60680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen if (new_capacity < min_capacity) { 60780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen new_capacity = min_capacity + growth; 60880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 60980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Vector<T> new_chunk = Vector<T>::New(new_capacity); 61080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int new_index = PrepareGrow(new_chunk); 61180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen if (index_ > 0) { 61280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen chunks_.Add(current_chunk_.SubVector(0, index_)); 61380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } else { 61480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Can happen if the call to PrepareGrow moves everything into 61580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // the new chunk. 61680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen current_chunk_.Dispose(); 61780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 61880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen current_chunk_ = new_chunk; 61980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen index_ = new_index; 62080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(index_ + min_capacity <= current_chunk_.length()); 62180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 62280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 62380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Before replacing the current chunk, give a subclass the option to move 62480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // some of the current data into the new chunk. The function may update 62580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // the current index_ value to represent data no longer in the current chunk. 62680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Returns the initial index of the new chunk (after copied data). 62780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen virtual int PrepareGrow(Vector<T> new_chunk) { 62880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen return 0; 62980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 63080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen}; 63180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 63280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 63380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen/* 63480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * A collector that allows sequences of values to be guaranteed to 63580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * stay consecutive. 63680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * If the backing store grows while a sequence is active, the current 63780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * sequence might be moved, but after the sequence is ended, it will 63880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * not move again. 63980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * NOTICE: Blocks allocated using Collector::AddBlock(int) can move 64080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen * as well, if inside an active sequence where another element is added. 64180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen */ 64280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsentemplate <typename T, int growth_factor = 2, int max_growth = 1 * MB> 64380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsenclass SequenceCollector : public Collector<T, growth_factor, max_growth> { 64480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen public: 64580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen explicit SequenceCollector(int initial_capacity) 64680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen : Collector<T, growth_factor, max_growth>(initial_capacity), 64780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen sequence_start_(kNoSequence) { } 64880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 64980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen virtual ~SequenceCollector() {} 65080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 65180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen void StartSequence() { 65280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(sequence_start_ == kNoSequence); 65380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen sequence_start_ = this->index_; 65480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 65580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 65680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen Vector<T> EndSequence() { 65780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(sequence_start_ != kNoSequence); 65880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int sequence_start = sequence_start_; 65980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen sequence_start_ = kNoSequence; 66080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen if (sequence_start == this->index_) return Vector<T>(); 66180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen return this->current_chunk_.SubVector(sequence_start, this->index_); 66280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 66380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 66480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Drops the currently added sequence, and all collected elements in it. 66580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen void DropSequence() { 66680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(sequence_start_ != kNoSequence); 66780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int sequence_length = this->index_ - sequence_start_; 66880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen this->index_ = sequence_start_; 66980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen this->size_ -= sequence_length; 67080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen sequence_start_ = kNoSequence; 67180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 67280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 67380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen virtual void Reset() { 67480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen sequence_start_ = kNoSequence; 67580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen this->Collector<T, growth_factor, max_growth>::Reset(); 67680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 67780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 67880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen private: 67980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen static const int kNoSequence = -1; 68080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int sequence_start_; 68180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 68280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // Move the currently active sequence to the new chunk. 68380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen virtual int PrepareGrow(Vector<T> new_chunk) { 68480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen if (sequence_start_ != kNoSequence) { 68580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen int sequence_length = this->index_ - sequence_start_; 68680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // The new chunk is always larger than the current chunk, so there 68780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen // is room for the copy. 68880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen ASSERT(sequence_length < new_chunk.length()); 68980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen for (int i = 0; i < sequence_length; i++) { 69080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen new_chunk[i] = this->current_chunk_[sequence_start_ + i]; 69180d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 69280d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen this->index_ = sequence_start_; 69380d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen sequence_start_ = 0; 69480d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen return sequence_length; 69580d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 69680d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen return 0; 69780d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen } 69880d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen}; 69980d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 70080d68eab642096c1a48b6474d6ec33064b0ad1f5Kristian Monsen 7016ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Compare ASCII/16bit chars to ASCII/16bit chars. 7026ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate <typename lchar, typename rchar> 7036ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockstatic inline int CompareChars(const lchar* lhs, const rchar* rhs, int chars) { 7046ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const lchar* limit = lhs + chars; 7056ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#ifdef V8_HOST_CAN_READ_UNALIGNED 7066ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (sizeof(*lhs) == sizeof(*rhs)) { 7076ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Number of characters in a uintptr_t. 7086ded16be15dd865a9b21ea304d5273c8be299c87Steve Block static const int kStepSize = sizeof(uintptr_t) / sizeof(*lhs); // NOLINT 7096ded16be15dd865a9b21ea304d5273c8be299c87Steve Block while (lhs <= limit - kStepSize) { 7106ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (*reinterpret_cast<const uintptr_t*>(lhs) != 7116ded16be15dd865a9b21ea304d5273c8be299c87Steve Block *reinterpret_cast<const uintptr_t*>(rhs)) { 7126ded16be15dd865a9b21ea304d5273c8be299c87Steve Block break; 7136ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 7146ded16be15dd865a9b21ea304d5273c8be299c87Steve Block lhs += kStepSize; 7156ded16be15dd865a9b21ea304d5273c8be299c87Steve Block rhs += kStepSize; 7166ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 7176ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 7186ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#endif 7196ded16be15dd865a9b21ea304d5273c8be299c87Steve Block while (lhs < limit) { 7206ded16be15dd865a9b21ea304d5273c8be299c87Steve Block int r = static_cast<int>(*lhs) - static_cast<int>(*rhs); 7216ded16be15dd865a9b21ea304d5273c8be299c87Steve Block if (r != 0) return r; 7226ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ++lhs; 7236ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ++rhs; 7246ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 7256ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return 0; 7266ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 7276ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 7286ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 729d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block// Calculate 10^exponent. 7303e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhustatic inline int TenToThe(int exponent) { 7313e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu ASSERT(exponent <= 9); 7323e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu ASSERT(exponent >= 1); 7333e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu int answer = 10; 7343e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu for (int i = 1; i < exponent; i++) answer *= 10; 7353e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu return answer; 7363e5fa29ddb82551500b118e9bf37af3966277b70Teng-Hui Zhu} 737d0582a6c46733687d045e4188a1bcd0123c758a1Steve Block 7386ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 7396ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// The type-based aliasing rule allows the compiler to assume that pointers of 7406ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// different types (for some definition of different) never alias each other. 7416ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Thus the following code does not work: 7426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 7436ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// float f = foo(); 7446ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// int fbits = *(int*)(&f); 7456ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 7466ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// The compiler 'knows' that the int pointer can't refer to f since the types 7476ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// don't match, so the compiler may cache f in a register, leaving random data 7486ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// in fbits. Using C++ style casts makes no difference, however a pointer to 7496ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// char data is assumed to alias any other pointer. This is the 'memcpy 7506ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// exception'. 7516ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 7526ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Bit_cast uses the memcpy exception to move the bits from a variable of one 7536ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// type of a variable of another type. Of course the end result is likely to 7546ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// be implementation dependent. Most compilers (gcc-4.2 and MSVC 2005) 7556ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// will completely optimize BitCast away. 7566ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 7576ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// There is an additional use for BitCast. 7586ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Recent gccs will warn when they see casts that may result in breakage due to 7596ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// the type-based aliasing rule. If you have checked that there is no breakage 7606ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// you can use BitCast to cast one pointer type to another. This confuses gcc 7616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// enough that it can no longer see that you have cast one pointer type to 7626ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// another thus avoiding the warning. 7636ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocktemplate <class Dest, class Source> 7646ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockinline Dest BitCast(const Source& source) { 7656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Compile time assertion: sizeof(Dest) == sizeof(Source) 7666ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // A compile error here means your Dest and Source have different sizes. 7676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block typedef char VerifySizesAreEqual[sizeof(Dest) == sizeof(Source) ? 1 : -1]; 7686ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 7696ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Dest dest; 7706ded16be15dd865a9b21ea304d5273c8be299c87Steve Block memcpy(&dest, &source, sizeof(dest)); 7716ded16be15dd865a9b21ea304d5273c8be299c87Steve Block return dest; 7726ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 7736ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 774756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merricktemplate <class Dest, class Source> 775791712a13f1814dd3ab5d1a5ab8ff5dbc476f6d6Steve Blockinline Dest BitCast(Source* source) { 776791712a13f1814dd3ab5d1a5ab8ff5dbc476f6d6Steve Block return BitCast<Dest>(reinterpret_cast<uintptr_t>(source)); 777756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merrick} 778a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 779756813857a4c2a4d8ad2e805969d5768d3cf43a0Iain Merrick} } // namespace v8::internal 7806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 781a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block#endif // V8_UTILS_H_ 782