| 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 |