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 // The reason we write our own hash map instead of using unordered_map in STL, | 5 // The reason we write our own hash map instead of using unordered_map in STL, |
6 // is that STL containers use a mutex pool on debug build, which will lead to | 6 // is that STL containers use a mutex pool on debug build, which will lead to |
7 // deadlock when we are using async signal handler. | 7 // deadlock when we are using async signal handler. |
8 | 8 |
9 #ifndef V8_BASE_HASHMAP_H_ | 9 #ifndef V8_BASE_HASHMAP_H_ |
10 #define V8_BASE_HASHMAP_H_ | 10 #define V8_BASE_HASHMAP_H_ |
(...skipping 18 matching lines...) Expand all Loading... |
29 public: | 29 public: |
30 typedef TemplateHashMapEntry<Key, Value> Entry; | 30 typedef TemplateHashMapEntry<Key, Value> Entry; |
31 | 31 |
32 // The default capacity. This is used by the call sites which want | 32 // The default capacity. This is used by the call sites which want |
33 // to pass in a non-default AllocationPolicy but want to use the | 33 // to pass in a non-default AllocationPolicy but want to use the |
34 // default value of capacity specified by the implementation. | 34 // default value of capacity specified by the implementation. |
35 static const uint32_t kDefaultHashMapCapacity = 8; | 35 static const uint32_t kDefaultHashMapCapacity = 8; |
36 | 36 |
37 // initial_capacity is the size of the initial hash map; | 37 // initial_capacity is the size of the initial hash map; |
38 // it must be a power of 2 (and thus must not be 0). | 38 // it must be a power of 2 (and thus must not be 0). |
39 TemplateHashMapImpl(MatchFun match = MatchFun(), | 39 TemplateHashMapImpl(uint32_t capacity = kDefaultHashMapCapacity, |
40 uint32_t capacity = kDefaultHashMapCapacity, | 40 MatchFun match = MatchFun(), |
41 AllocationPolicy allocator = AllocationPolicy()); | 41 AllocationPolicy allocator = AllocationPolicy()); |
42 | 42 |
43 ~TemplateHashMapImpl(); | 43 ~TemplateHashMapImpl(); |
44 | 44 |
45 // If an entry with matching key is found, returns that entry. | 45 // If an entry with matching key is found, returns that entry. |
46 // Otherwise, nullptr is returned. | 46 // Otherwise, nullptr is returned. |
47 Entry* Lookup(const Key& key, uint32_t hash) const; | 47 Entry* Lookup(const Key& key, uint32_t hash) const; |
48 | 48 |
49 // If an entry with matching key is found, returns that entry. | 49 // If an entry with matching key is found, returns that entry. |
50 // If no matching entry is found, a new entry is inserted with | 50 // If no matching entry is found, a new entry is inserted with |
(...skipping 28 matching lines...) Expand all Loading... |
79 // | 79 // |
80 // If entries are inserted during iteration, the effect of | 80 // If entries are inserted during iteration, the effect of |
81 // calling Next() is undefined. | 81 // calling Next() is undefined. |
82 Entry* Start() const; | 82 Entry* Start() const; |
83 Entry* Next(Entry* entry) const; | 83 Entry* Next(Entry* entry) const; |
84 | 84 |
85 private: | 85 private: |
86 Entry* map_; | 86 Entry* map_; |
87 uint32_t capacity_; | 87 uint32_t capacity_; |
88 uint32_t occupancy_; | 88 uint32_t occupancy_; |
| 89 // TODO(leszeks): This takes up space even if it has no state, maybe replace |
| 90 // with something that does the empty base optimisation e.g. std::tuple |
89 MatchFun match_; | 91 MatchFun match_; |
90 | 92 |
91 Entry* map_end() const { return map_ + capacity_; } | 93 Entry* map_end() const { return map_ + capacity_; } |
92 Entry* Probe(const Key& key, uint32_t hash) const; | 94 Entry* Probe(const Key& key, uint32_t hash) const; |
93 Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value, | 95 Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value, |
94 uint32_t hash, | 96 uint32_t hash, |
95 AllocationPolicy allocator = AllocationPolicy()); | 97 AllocationPolicy allocator = AllocationPolicy()); |
96 void Initialize(uint32_t capacity, AllocationPolicy allocator); | 98 void Initialize(uint32_t capacity, AllocationPolicy allocator); |
97 void Resize(AllocationPolicy allocator); | 99 void Resize(AllocationPolicy allocator); |
98 }; | 100 }; |
99 template <typename Key, typename Value, typename MatchFun, | 101 template <typename Key, typename Value, typename MatchFun, |
100 class AllocationPolicy> | 102 class AllocationPolicy> |
101 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>:: | 103 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>:: |
102 TemplateHashMapImpl(MatchFun match, uint32_t initial_capacity, | 104 TemplateHashMapImpl(uint32_t initial_capacity, MatchFun match, |
103 AllocationPolicy allocator) | 105 AllocationPolicy allocator) |
104 : match_(match) { | 106 : match_(match) { |
105 Initialize(initial_capacity, allocator); | 107 Initialize(initial_capacity, allocator); |
106 } | 108 } |
107 | 109 |
108 template <typename Key, typename Value, typename MatchFun, | 110 template <typename Key, typename Value, typename MatchFun, |
109 class AllocationPolicy> | 111 class AllocationPolicy> |
110 TemplateHashMapImpl<Key, Value, MatchFun, | 112 TemplateHashMapImpl<Key, Value, MatchFun, |
111 AllocationPolicy>::~TemplateHashMapImpl() { | 113 AllocationPolicy>::~TemplateHashMapImpl() { |
112 AllocationPolicy::Delete(map_); | 114 AllocationPolicy::Delete(map_); |
(...skipping 199 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
312 entry->hash, allocator); | 314 entry->hash, allocator); |
313 n--; | 315 n--; |
314 } | 316 } |
315 } | 317 } |
316 | 318 |
317 // Delete old map. | 319 // Delete old map. |
318 AllocationPolicy::Delete(map); | 320 AllocationPolicy::Delete(map); |
319 } | 321 } |
320 | 322 |
321 template <typename AllocationPolicy> | 323 template <typename AllocationPolicy> |
322 class PointerTemplateHashMapImpl | 324 class CustomMatcherTemplateHashMapImpl |
323 : public TemplateHashMapImpl<void*, void*, bool (*)(void*, void*), | 325 : public TemplateHashMapImpl<void*, void*, bool (*)(void*, void*), |
324 AllocationPolicy> { | 326 AllocationPolicy> { |
325 typedef TemplateHashMapImpl<void*, void*, bool (*)(void*, void*), | 327 typedef TemplateHashMapImpl<void*, void*, bool (*)(void*, void*), |
326 AllocationPolicy> | 328 AllocationPolicy> |
327 Base; | 329 Base; |
328 | 330 |
329 public: | 331 public: |
330 typedef bool (*MatchFun)(void*, void*); | 332 typedef bool (*MatchFun)(void*, void*); |
331 | 333 |
332 PointerTemplateHashMapImpl(MatchFun match = PointersMatch, | 334 CustomMatcherTemplateHashMapImpl( |
333 uint32_t capacity = Base::kDefaultHashMapCapacity, | 335 MatchFun match, uint32_t capacity = Base::kDefaultHashMapCapacity, |
| 336 AllocationPolicy allocator = AllocationPolicy()) |
| 337 : Base(capacity, match, allocator) {} |
| 338 }; |
| 339 |
| 340 typedef CustomMatcherTemplateHashMapImpl<DefaultAllocationPolicy> |
| 341 CustomMatcherHashMap; |
| 342 |
| 343 template <typename AllocationPolicy> |
| 344 class PointerTemplateHashMapImpl |
| 345 : public TemplateHashMapImpl<void*, void*, std::equal_to<void*>, |
| 346 AllocationPolicy> { |
| 347 typedef TemplateHashMapImpl<void*, void*, std::equal_to<void*>, |
| 348 AllocationPolicy> |
| 349 Base; |
| 350 |
| 351 public: |
| 352 PointerTemplateHashMapImpl(uint32_t capacity = Base::kDefaultHashMapCapacity, |
334 AllocationPolicy allocator = AllocationPolicy()) | 353 AllocationPolicy allocator = AllocationPolicy()) |
335 : Base(match, capacity, allocator) {} | 354 : Base(capacity, std::equal_to<void*>(), allocator) {} |
336 | |
337 static bool PointersMatch(void* key1, void* key2) { return key1 == key2; } | |
338 }; | 355 }; |
339 | 356 |
340 typedef PointerTemplateHashMapImpl<DefaultAllocationPolicy> HashMap; | 357 typedef PointerTemplateHashMapImpl<DefaultAllocationPolicy> HashMap; |
341 | 358 |
342 // A hash map for pointer keys and values with an STL-like interface. | 359 // A hash map for pointer keys and values with an STL-like interface. |
343 template <class Key, class Value, class AllocationPolicy> | 360 template <class Key, class Value, class MatchFun, class AllocationPolicy> |
344 class TemplateHashMap : private PointerTemplateHashMapImpl<AllocationPolicy> { | 361 class TemplateHashMap |
345 typedef PointerTemplateHashMapImpl<AllocationPolicy> Base; | 362 : private TemplateHashMapImpl<void*, void*, MatchFun, AllocationPolicy> { |
| 363 typedef TemplateHashMapImpl<void*, void*, MatchFun, AllocationPolicy> Base; |
346 | 364 |
347 public: | 365 public: |
348 typedef bool (*MatchFun)(void*, void*); | |
349 | |
350 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT | 366 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT |
351 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT | 367 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT |
352 struct value_type { | 368 struct value_type { |
353 Key* first; | 369 Key* first; |
354 Value* second; | 370 Value* second; |
355 }; | 371 }; |
356 | 372 |
357 class Iterator { | 373 class Iterator { |
358 public: | 374 public: |
359 Iterator& operator++() { | 375 Iterator& operator++() { |
360 entry_ = map_->Next(entry_); | 376 entry_ = map_->Next(entry_); |
361 return *this; | 377 return *this; |
362 } | 378 } |
363 | 379 |
364 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } | 380 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } |
365 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } | 381 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } |
366 | 382 |
367 private: | 383 private: |
368 Iterator(const Base* map, typename Base::Entry* entry) | 384 Iterator(const Base* map, typename Base::Entry* entry) |
369 : map_(map), entry_(entry) {} | 385 : map_(map), entry_(entry) {} |
370 | 386 |
371 const Base* map_; | 387 const Base* map_; |
372 typename Base::Entry* entry_; | 388 typename Base::Entry* entry_; |
373 | 389 |
374 friend class TemplateHashMap; | 390 friend class TemplateHashMap; |
375 }; | 391 }; |
376 | 392 |
377 TemplateHashMap(MatchFun match, | 393 TemplateHashMap(MatchFun match, |
378 AllocationPolicy allocator = AllocationPolicy()) | 394 AllocationPolicy allocator = AllocationPolicy()) |
379 : Base(match, Base::kDefaultHashMapCapacity, allocator) {} | 395 : Base(Base::kDefaultHashMapCapacity, match, allocator) {} |
380 | 396 |
381 Iterator begin() const { return Iterator(this, this->Start()); } | 397 Iterator begin() const { return Iterator(this, this->Start()); } |
382 Iterator end() const { return Iterator(this, nullptr); } | 398 Iterator end() const { return Iterator(this, nullptr); } |
383 Iterator find(Key* key, bool insert = false, | 399 Iterator find(Key* key, bool insert = false, |
384 AllocationPolicy allocator = AllocationPolicy()) { | 400 AllocationPolicy allocator = AllocationPolicy()) { |
385 if (insert) { | 401 if (insert) { |
386 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); | 402 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); |
387 } | 403 } |
388 return Iterator(this, this->Lookup(key, key->Hash())); | 404 return Iterator(this, this->Lookup(key, key->Hash())); |
389 } | 405 } |
390 }; | 406 }; |
391 | 407 |
392 } // namespace base | 408 } // namespace base |
393 } // namespace v8 | 409 } // namespace v8 |
394 | 410 |
395 #endif // V8_BASE_HASHMAP_H_ | 411 #endif // V8_BASE_HASHMAP_H_ |
OLD | NEW |