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 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
63 AllocationPolicy allocator = AllocationPolicy()); | 63 AllocationPolicy allocator = AllocationPolicy()); |
64 | 64 |
65 // Removes the entry with matching key. | 65 // Removes the entry with matching key. |
66 // It returns the value of the deleted entry | 66 // It returns the value of the deleted entry |
67 // or null if there is no value for such key. | 67 // or null if there is no value for such key. |
68 Value Remove(const Key& key, uint32_t hash); | 68 Value Remove(const Key& key, uint32_t hash); |
69 | 69 |
70 // Empties the hash map (occupancy() == 0). | 70 // Empties the hash map (occupancy() == 0). |
71 void Clear(); | 71 void Clear(); |
72 | 72 |
| 73 // Empties the map and makes it unusable for allocation. |
| 74 void Invalidate() { |
| 75 AllocationPolicy::Delete(map_); |
| 76 map_ = nullptr; |
| 77 occupancy_ = 0; |
| 78 capacity_ = 0; |
| 79 } |
| 80 |
73 // The number of (non-empty) entries in the table. | 81 // The number of (non-empty) entries in the table. |
74 uint32_t occupancy() const { return occupancy_; } | 82 uint32_t occupancy() const { return occupancy_; } |
75 | 83 |
76 // The capacity of the table. The implementation | 84 // The capacity of the table. The implementation |
77 // makes sure that occupancy is at most 80% of | 85 // makes sure that occupancy is at most 80% of |
78 // the table capacity. | 86 // the table capacity. |
79 uint32_t capacity() const { return capacity_; } | 87 uint32_t capacity() const { return capacity_; } |
80 | 88 |
81 // Iteration | 89 // Iteration |
82 // | 90 // |
83 // for (Entry* p = map.Start(); p != nullptr; p = map.Next(p)) { | 91 // for (Entry* p = map.Start(); p != nullptr; p = map.Next(p)) { |
84 // ... | 92 // ... |
85 // } | 93 // } |
86 // | 94 // |
87 // If entries are inserted during iteration, the effect of | 95 // If entries are inserted during iteration, the effect of |
88 // calling Next() is undefined. | 96 // calling Next() is undefined. |
89 Entry* Start() const; | 97 Entry* Start() const; |
90 Entry* Next(Entry* entry) const; | 98 Entry* Next(Entry* entry) const; |
91 | 99 |
| 100 void Reset(AllocationPolicy allocator) { |
| 101 Initialize(capacity_, allocator); |
| 102 occupancy_ = 0; |
| 103 } |
| 104 |
| 105 protected: |
| 106 void Initialize(uint32_t capacity, AllocationPolicy allocator); |
| 107 |
92 private: | 108 private: |
93 Entry* map_; | 109 Entry* map_; |
94 uint32_t capacity_; | 110 uint32_t capacity_; |
95 uint32_t occupancy_; | 111 uint32_t occupancy_; |
96 // TODO(leszeks): This takes up space even if it has no state, maybe replace | 112 // TODO(leszeks): This takes up space even if it has no state, maybe replace |
97 // with something that does the empty base optimisation e.g. std::tuple | 113 // with something that does the empty base optimisation e.g. std::tuple |
98 MatchFun match_; | 114 MatchFun match_; |
99 | 115 |
100 Entry* map_end() const { return map_ + capacity_; } | 116 Entry* map_end() const { return map_ + capacity_; } |
101 Entry* Probe(const Key& key, uint32_t hash) const; | 117 Entry* Probe(const Key& key, uint32_t hash) const; |
102 Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value, | 118 Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value, |
103 uint32_t hash, | 119 uint32_t hash, |
104 AllocationPolicy allocator = AllocationPolicy()); | 120 AllocationPolicy allocator = AllocationPolicy()); |
105 void Initialize(uint32_t capacity, AllocationPolicy allocator); | |
106 void Resize(AllocationPolicy allocator); | 121 void Resize(AllocationPolicy allocator); |
107 }; | 122 }; |
108 template <typename Key, typename Value, typename MatchFun, | 123 template <typename Key, typename Value, typename MatchFun, |
109 class AllocationPolicy> | 124 class AllocationPolicy> |
110 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>:: | 125 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>:: |
111 TemplateHashMapImpl(uint32_t initial_capacity, MatchFun match, | 126 TemplateHashMapImpl(uint32_t initial_capacity, MatchFun match, |
112 AllocationPolicy allocator) | 127 AllocationPolicy allocator) |
113 : match_(match) { | 128 : match_(match) { |
114 Initialize(initial_capacity, allocator); | 129 Initialize(initial_capacity, allocator); |
115 } | 130 } |
(...skipping 334 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
450 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); | 465 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); |
451 } | 466 } |
452 return Iterator(this, this->Lookup(key, key->Hash())); | 467 return Iterator(this, this->Lookup(key, key->Hash())); |
453 } | 468 } |
454 }; | 469 }; |
455 | 470 |
456 } // namespace base | 471 } // namespace base |
457 } // namespace v8 | 472 } // namespace v8 |
458 | 473 |
459 #endif // V8_BASE_HASHMAP_H_ | 474 #endif // V8_BASE_HASHMAP_H_ |
OLD | NEW |