OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_HASHMAP_H_ | 5 #ifndef V8_HASHMAP_H_ |
6 #define V8_HASHMAP_H_ | 6 #define V8_HASHMAP_H_ |
7 | 7 |
8 #include "src/allocation.h" | 8 #include "src/allocation.h" |
| 9 #include "src/base/bits.h" |
9 #include "src/base/logging.h" | 10 #include "src/base/logging.h" |
10 #include "src/utils.h" | 11 #include "src/utils.h" |
11 | 12 |
12 namespace v8 { | 13 namespace v8 { |
13 namespace internal { | 14 namespace internal { |
14 | 15 |
15 template<class AllocationPolicy> | 16 template<class AllocationPolicy> |
16 class TemplateHashMapImpl { | 17 class TemplateHashMapImpl { |
17 public: | 18 public: |
18 typedef bool (*MatchFun) (void* key1, void* key2); | 19 typedef bool (*MatchFun) (void* key1, void* key2); |
(...skipping 213 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
232 } | 233 } |
233 return NULL; | 234 return NULL; |
234 } | 235 } |
235 | 236 |
236 | 237 |
237 template<class AllocationPolicy> | 238 template<class AllocationPolicy> |
238 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 239 typename TemplateHashMapImpl<AllocationPolicy>::Entry* |
239 TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) { | 240 TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) { |
240 DCHECK(key != NULL); | 241 DCHECK(key != NULL); |
241 | 242 |
242 DCHECK(IsPowerOf2(capacity_)); | 243 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); |
243 Entry* p = map_ + (hash & (capacity_ - 1)); | 244 Entry* p = map_ + (hash & (capacity_ - 1)); |
244 const Entry* end = map_end(); | 245 const Entry* end = map_end(); |
245 DCHECK(map_ <= p && p < end); | 246 DCHECK(map_ <= p && p < end); |
246 | 247 |
247 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. | 248 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. |
248 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { | 249 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { |
249 p++; | 250 p++; |
250 if (p >= end) { | 251 if (p >= end) { |
251 p = map_; | 252 p = map_; |
252 } | 253 } |
253 } | 254 } |
254 | 255 |
255 return p; | 256 return p; |
256 } | 257 } |
257 | 258 |
258 | 259 |
259 template<class AllocationPolicy> | 260 template<class AllocationPolicy> |
260 void TemplateHashMapImpl<AllocationPolicy>::Initialize( | 261 void TemplateHashMapImpl<AllocationPolicy>::Initialize( |
261 uint32_t capacity, AllocationPolicy allocator) { | 262 uint32_t capacity, AllocationPolicy allocator) { |
262 DCHECK(IsPowerOf2(capacity)); | 263 DCHECK(base::bits::IsPowerOfTwo32(capacity)); |
263 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); | 264 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); |
264 if (map_ == NULL) { | 265 if (map_ == NULL) { |
265 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); | 266 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); |
266 return; | 267 return; |
267 } | 268 } |
268 capacity_ = capacity; | 269 capacity_ = capacity; |
269 Clear(); | 270 Clear(); |
270 } | 271 } |
271 | 272 |
272 | 273 |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
337 Iterator end() const { return Iterator(this, NULL); } | 338 Iterator end() const { return Iterator(this, NULL); } |
338 Iterator find(Key* key, bool insert = false, | 339 Iterator find(Key* key, bool insert = false, |
339 AllocationPolicy allocator = AllocationPolicy()) { | 340 AllocationPolicy allocator = AllocationPolicy()) { |
340 return Iterator(this, this->Lookup(key, key->Hash(), insert, allocator)); | 341 return Iterator(this, this->Lookup(key, key->Hash(), insert, allocator)); |
341 } | 342 } |
342 }; | 343 }; |
343 | 344 |
344 } } // namespace v8::internal | 345 } } // namespace v8::internal |
345 | 346 |
346 #endif // V8_HASHMAP_H_ | 347 #endif // V8_HASHMAP_H_ |
OLD | NEW |