OLD | NEW |
1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 29 matching lines...) Expand all Loading... |
40 namespace internal { | 40 namespace internal { |
41 | 41 |
42 // ---------------------------------------------------------------------------- | 42 // ---------------------------------------------------------------------------- |
43 // General helper functions | 43 // General helper functions |
44 | 44 |
45 #define IS_POWER_OF_TWO(x) (((x) & ((x) - 1)) == 0) | 45 #define IS_POWER_OF_TWO(x) (((x) & ((x) - 1)) == 0) |
46 | 46 |
47 // Returns true iff x is a power of 2 (or zero). Cannot be used with the | 47 // Returns true iff x is a power of 2 (or zero). Cannot be used with the |
48 // maximally negative value of the type T (the -1 overflows). | 48 // maximally negative value of the type T (the -1 overflows). |
49 template <typename T> | 49 template <typename T> |
50 static inline bool IsPowerOf2(T x) { | 50 inline bool IsPowerOf2(T x) { |
51 return IS_POWER_OF_TWO(x); | 51 return IS_POWER_OF_TWO(x); |
52 } | 52 } |
53 | 53 |
54 | 54 |
55 // X must be a power of 2. Returns the number of trailing zeros. | 55 // X must be a power of 2. Returns the number of trailing zeros. |
56 static inline int WhichPowerOf2(uint32_t x) { | 56 inline int WhichPowerOf2(uint32_t x) { |
57 ASSERT(IsPowerOf2(x)); | 57 ASSERT(IsPowerOf2(x)); |
58 ASSERT(x != 0); | 58 ASSERT(x != 0); |
59 int bits = 0; | 59 int bits = 0; |
60 #ifdef DEBUG | 60 #ifdef DEBUG |
61 int original_x = x; | 61 int original_x = x; |
62 #endif | 62 #endif |
63 if (x >= 0x10000) { | 63 if (x >= 0x10000) { |
64 bits += 16; | 64 bits += 16; |
65 x >>= 16; | 65 x >>= 16; |
66 } | 66 } |
(...skipping 14 matching lines...) Expand all Loading... |
81 } | 81 } |
82 ASSERT_EQ(1 << bits, original_x); | 82 ASSERT_EQ(1 << bits, original_x); |
83 return bits; | 83 return bits; |
84 return 0; | 84 return 0; |
85 } | 85 } |
86 | 86 |
87 | 87 |
88 // The C++ standard leaves the semantics of '>>' undefined for | 88 // The C++ standard leaves the semantics of '>>' undefined for |
89 // negative signed operands. Most implementations do the right thing, | 89 // negative signed operands. Most implementations do the right thing, |
90 // though. | 90 // though. |
91 static inline int ArithmeticShiftRight(int x, int s) { | 91 inline int ArithmeticShiftRight(int x, int s) { |
92 return x >> s; | 92 return x >> s; |
93 } | 93 } |
94 | 94 |
95 | 95 |
96 // Compute the 0-relative offset of some absolute value x of type T. | 96 // Compute the 0-relative offset of some absolute value x of type T. |
97 // This allows conversion of Addresses and integral types into | 97 // This allows conversion of Addresses and integral types into |
98 // 0-relative int offsets. | 98 // 0-relative int offsets. |
99 template <typename T> | 99 template <typename T> |
100 static inline intptr_t OffsetFrom(T x) { | 100 inline intptr_t OffsetFrom(T x) { |
101 return x - static_cast<T>(0); | 101 return x - static_cast<T>(0); |
102 } | 102 } |
103 | 103 |
104 | 104 |
105 // Compute the absolute value of type T for some 0-relative offset x. | 105 // Compute the absolute value of type T for some 0-relative offset x. |
106 // This allows conversion of 0-relative int offsets into Addresses and | 106 // This allows conversion of 0-relative int offsets into Addresses and |
107 // integral types. | 107 // integral types. |
108 template <typename T> | 108 template <typename T> |
109 static inline T AddressFrom(intptr_t x) { | 109 inline T AddressFrom(intptr_t x) { |
110 return static_cast<T>(static_cast<T>(0) + x); | 110 return static_cast<T>(static_cast<T>(0) + x); |
111 } | 111 } |
112 | 112 |
113 | 113 |
114 // Return the largest multiple of m which is <= x. | 114 // Return the largest multiple of m which is <= x. |
115 template <typename T> | 115 template <typename T> |
116 static inline T RoundDown(T x, intptr_t m) { | 116 inline T RoundDown(T x, intptr_t m) { |
117 ASSERT(IsPowerOf2(m)); | 117 ASSERT(IsPowerOf2(m)); |
118 return AddressFrom<T>(OffsetFrom(x) & -m); | 118 return AddressFrom<T>(OffsetFrom(x) & -m); |
119 } | 119 } |
120 | 120 |
121 | 121 |
122 // Return the smallest multiple of m which is >= x. | 122 // Return the smallest multiple of m which is >= x. |
123 template <typename T> | 123 template <typename T> |
124 static inline T RoundUp(T x, intptr_t m) { | 124 inline T RoundUp(T x, intptr_t m) { |
125 return RoundDown<T>(static_cast<T>(x + m - 1), m); | 125 return RoundDown<T>(static_cast<T>(x + m - 1), m); |
126 } | 126 } |
127 | 127 |
128 | 128 |
129 template <typename T> | 129 template <typename T> |
130 static int Compare(const T& a, const T& b) { | 130 int Compare(const T& a, const T& b) { |
131 if (a == b) | 131 if (a == b) |
132 return 0; | 132 return 0; |
133 else if (a < b) | 133 else if (a < b) |
134 return -1; | 134 return -1; |
135 else | 135 else |
136 return 1; | 136 return 1; |
137 } | 137 } |
138 | 138 |
139 | 139 |
140 template <typename T> | 140 template <typename T> |
141 static int PointerValueCompare(const T* a, const T* b) { | 141 int PointerValueCompare(const T* a, const T* b) { |
142 return Compare<T>(*a, *b); | 142 return Compare<T>(*a, *b); |
143 } | 143 } |
144 | 144 |
145 | 145 |
146 // Compare function to compare the object pointer value of two | 146 // Compare function to compare the object pointer value of two |
147 // handlified objects. The handles are passed as pointers to the | 147 // handlified objects. The handles are passed as pointers to the |
148 // handles. | 148 // handles. |
149 template<typename T> class Handle; // Forward declaration. | 149 template<typename T> class Handle; // Forward declaration. |
150 template <typename T> | 150 template <typename T> |
151 static int HandleObjectPointerCompare(const Handle<T>* a, const Handle<T>* b) { | 151 int HandleObjectPointerCompare(const Handle<T>* a, const Handle<T>* b) { |
152 return Compare<T*>(*(*a), *(*b)); | 152 return Compare<T*>(*(*a), *(*b)); |
153 } | 153 } |
154 | 154 |
155 | 155 |
156 // Returns the smallest power of two which is >= x. If you pass in a | 156 // Returns the smallest power of two which is >= x. If you pass in a |
157 // number that is already a power of two, it is returned as is. | 157 // number that is already a power of two, it is returned as is. |
158 // Implementation is from "Hacker's Delight" by Henry S. Warren, Jr., | 158 // Implementation is from "Hacker's Delight" by Henry S. Warren, Jr., |
159 // figure 3-3, page 48, where the function is called clp2. | 159 // figure 3-3, page 48, where the function is called clp2. |
160 static inline uint32_t RoundUpToPowerOf2(uint32_t x) { | 160 inline uint32_t RoundUpToPowerOf2(uint32_t x) { |
161 ASSERT(x <= 0x80000000u); | 161 ASSERT(x <= 0x80000000u); |
162 x = x - 1; | 162 x = x - 1; |
163 x = x | (x >> 1); | 163 x = x | (x >> 1); |
164 x = x | (x >> 2); | 164 x = x | (x >> 2); |
165 x = x | (x >> 4); | 165 x = x | (x >> 4); |
166 x = x | (x >> 8); | 166 x = x | (x >> 8); |
167 x = x | (x >> 16); | 167 x = x | (x >> 16); |
168 return x + 1; | 168 return x + 1; |
169 } | 169 } |
170 | 170 |
171 | 171 |
172 static inline uint32_t RoundDownToPowerOf2(uint32_t x) { | 172 inline uint32_t RoundDownToPowerOf2(uint32_t x) { |
173 uint32_t rounded_up = RoundUpToPowerOf2(x); | 173 uint32_t rounded_up = RoundUpToPowerOf2(x); |
174 if (rounded_up > x) return rounded_up >> 1; | 174 if (rounded_up > x) return rounded_up >> 1; |
175 return rounded_up; | 175 return rounded_up; |
176 } | 176 } |
177 | 177 |
178 | 178 |
179 template <typename T, typename U> | 179 template <typename T, typename U> |
180 static inline bool IsAligned(T value, U alignment) { | 180 inline bool IsAligned(T value, U alignment) { |
181 return (value & (alignment - 1)) == 0; | 181 return (value & (alignment - 1)) == 0; |
182 } | 182 } |
183 | 183 |
184 | 184 |
185 // Returns true if (addr + offset) is aligned. | 185 // Returns true if (addr + offset) is aligned. |
186 static inline bool IsAddressAligned(Address addr, | 186 inline bool IsAddressAligned(Address addr, |
187 intptr_t alignment, | 187 intptr_t alignment, |
188 int offset = 0) { | 188 int offset = 0) { |
189 intptr_t offs = OffsetFrom(addr + offset); | 189 intptr_t offs = OffsetFrom(addr + offset); |
190 return IsAligned(offs, alignment); | 190 return IsAligned(offs, alignment); |
191 } | 191 } |
192 | 192 |
193 | 193 |
194 // Returns the maximum of the two parameters. | 194 // Returns the maximum of the two parameters. |
195 template <typename T> | 195 template <typename T> |
196 static T Max(T a, T b) { | 196 T Max(T a, T b) { |
197 return a < b ? b : a; | 197 return a < b ? b : a; |
198 } | 198 } |
199 | 199 |
200 | 200 |
201 // Returns the minimum of the two parameters. | 201 // Returns the minimum of the two parameters. |
202 template <typename T> | 202 template <typename T> |
203 static T Min(T a, T b) { | 203 T Min(T a, T b) { |
204 return a < b ? a : b; | 204 return a < b ? a : b; |
205 } | 205 } |
206 | 206 |
207 | 207 |
208 inline int StrLength(const char* string) { | 208 inline int StrLength(const char* string) { |
209 size_t length = strlen(string); | 209 size_t length = strlen(string); |
210 ASSERT(length == static_cast<size_t>(static_cast<int>(length))); | 210 ASSERT(length == static_cast<size_t>(static_cast<int>(length))); |
211 return static_cast<int>(length); | 211 return static_cast<int>(length); |
212 } | 212 } |
213 | 213 |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
247 return static_cast<T>((value & kMask) >> shift); | 247 return static_cast<T>((value & kMask) >> shift); |
248 } | 248 } |
249 }; | 249 }; |
250 | 250 |
251 | 251 |
252 // ---------------------------------------------------------------------------- | 252 // ---------------------------------------------------------------------------- |
253 // Hash function. | 253 // Hash function. |
254 | 254 |
255 // Thomas Wang, Integer Hash Functions. | 255 // Thomas Wang, Integer Hash Functions. |
256 // http://www.concentric.net/~Ttwang/tech/inthash.htm | 256 // http://www.concentric.net/~Ttwang/tech/inthash.htm |
257 static inline uint32_t ComputeIntegerHash(uint32_t key) { | 257 inline uint32_t ComputeIntegerHash(uint32_t key) { |
258 uint32_t hash = key; | 258 uint32_t hash = key; |
259 hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1; | 259 hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1; |
260 hash = hash ^ (hash >> 12); | 260 hash = hash ^ (hash >> 12); |
261 hash = hash + (hash << 2); | 261 hash = hash + (hash << 2); |
262 hash = hash ^ (hash >> 4); | 262 hash = hash ^ (hash >> 4); |
263 hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11); | 263 hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11); |
264 hash = hash ^ (hash >> 16); | 264 hash = hash ^ (hash >> 16); |
265 return hash; | 265 return hash; |
266 } | 266 } |
267 | 267 |
268 | 268 |
269 static inline uint32_t ComputeLongHash(uint64_t key) { | 269 inline uint32_t ComputeLongHash(uint64_t key) { |
270 uint64_t hash = key; | 270 uint64_t hash = key; |
271 hash = ~hash + (hash << 18); // hash = (hash << 18) - hash - 1; | 271 hash = ~hash + (hash << 18); // hash = (hash << 18) - hash - 1; |
272 hash = hash ^ (hash >> 31); | 272 hash = hash ^ (hash >> 31); |
273 hash = hash * 21; // hash = (hash + (hash << 2)) + (hash << 4); | 273 hash = hash * 21; // hash = (hash + (hash << 2)) + (hash << 4); |
274 hash = hash ^ (hash >> 11); | 274 hash = hash ^ (hash >> 11); |
275 hash = hash + (hash << 6); | 275 hash = hash + (hash << 6); |
276 hash = hash ^ (hash >> 22); | 276 hash = hash ^ (hash >> 22); |
277 return (uint32_t) hash; | 277 return (uint32_t) hash; |
278 } | 278 } |
279 | 279 |
280 | 280 |
281 static inline uint32_t ComputePointerHash(void* ptr) { | 281 inline uint32_t ComputePointerHash(void* ptr) { |
282 return ComputeIntegerHash( | 282 return ComputeIntegerHash( |
283 static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr))); | 283 static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr))); |
284 } | 284 } |
285 | 285 |
286 | 286 |
287 // ---------------------------------------------------------------------------- | 287 // ---------------------------------------------------------------------------- |
288 // Miscellaneous | 288 // Miscellaneous |
289 | 289 |
290 // A static resource holds a static instance that can be reserved in | 290 // A static resource holds a static instance that can be reserved in |
291 // a local scope using an instance of Access. Attempts to re-reserve | 291 // a local scope using an instance of Access. Attempts to re-reserve |
(...skipping 435 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
727 } | 727 } |
728 this->current_chunk_ = new_chunk; | 728 this->current_chunk_ = new_chunk; |
729 this->index_ = sequence_length; | 729 this->index_ = sequence_length; |
730 sequence_start_ = 0; | 730 sequence_start_ = 0; |
731 } | 731 } |
732 }; | 732 }; |
733 | 733 |
734 | 734 |
735 // Compare ASCII/16bit chars to ASCII/16bit chars. | 735 // Compare ASCII/16bit chars to ASCII/16bit chars. |
736 template <typename lchar, typename rchar> | 736 template <typename lchar, typename rchar> |
737 static inline int CompareChars(const lchar* lhs, const rchar* rhs, int chars) { | 737 inline int CompareChars(const lchar* lhs, const rchar* rhs, int chars) { |
738 const lchar* limit = lhs + chars; | 738 const lchar* limit = lhs + chars; |
739 #ifdef V8_HOST_CAN_READ_UNALIGNED | 739 #ifdef V8_HOST_CAN_READ_UNALIGNED |
740 if (sizeof(*lhs) == sizeof(*rhs)) { | 740 if (sizeof(*lhs) == sizeof(*rhs)) { |
741 // Number of characters in a uintptr_t. | 741 // Number of characters in a uintptr_t. |
742 static const int kStepSize = sizeof(uintptr_t) / sizeof(*lhs); // NOLINT | 742 static const int kStepSize = sizeof(uintptr_t) / sizeof(*lhs); // NOLINT |
743 while (lhs <= limit - kStepSize) { | 743 while (lhs <= limit - kStepSize) { |
744 if (*reinterpret_cast<const uintptr_t*>(lhs) != | 744 if (*reinterpret_cast<const uintptr_t*>(lhs) != |
745 *reinterpret_cast<const uintptr_t*>(rhs)) { | 745 *reinterpret_cast<const uintptr_t*>(rhs)) { |
746 break; | 746 break; |
747 } | 747 } |
748 lhs += kStepSize; | 748 lhs += kStepSize; |
749 rhs += kStepSize; | 749 rhs += kStepSize; |
750 } | 750 } |
751 } | 751 } |
752 #endif | 752 #endif |
753 while (lhs < limit) { | 753 while (lhs < limit) { |
754 int r = static_cast<int>(*lhs) - static_cast<int>(*rhs); | 754 int r = static_cast<int>(*lhs) - static_cast<int>(*rhs); |
755 if (r != 0) return r; | 755 if (r != 0) return r; |
756 ++lhs; | 756 ++lhs; |
757 ++rhs; | 757 ++rhs; |
758 } | 758 } |
759 return 0; | 759 return 0; |
760 } | 760 } |
761 | 761 |
762 | 762 |
763 // Calculate 10^exponent. | 763 // Calculate 10^exponent. |
764 static inline int TenToThe(int exponent) { | 764 inline int TenToThe(int exponent) { |
765 ASSERT(exponent <= 9); | 765 ASSERT(exponent <= 9); |
766 ASSERT(exponent >= 1); | 766 ASSERT(exponent >= 1); |
767 int answer = 10; | 767 int answer = 10; |
768 for (int i = 1; i < exponent; i++) answer *= 10; | 768 for (int i = 1; i < exponent; i++) answer *= 10; |
769 return answer; | 769 return answer; |
770 } | 770 } |
771 | 771 |
772 | 772 |
773 // The type-based aliasing rule allows the compiler to assume that pointers of | 773 // The type-based aliasing rule allows the compiler to assume that pointers of |
774 // different types (for some definition of different) never alias each other. | 774 // different types (for some definition of different) never alias each other. |
(...skipping 163 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
938 ASSERT(element < static_cast<int>(sizeof(T) * CHAR_BIT)); | 938 ASSERT(element < static_cast<int>(sizeof(T) * CHAR_BIT)); |
939 return 1 << element; | 939 return 1 << element; |
940 } | 940 } |
941 | 941 |
942 T bits_; | 942 T bits_; |
943 }; | 943 }; |
944 | 944 |
945 } } // namespace v8::internal | 945 } } // namespace v8::internal |
946 | 946 |
947 #endif // V8_UTILS_H_ | 947 #endif // V8_UTILS_H_ |
OLD | NEW |