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_ |
11 | 11 |
12 #include <stdlib.h> | 12 #include <stdlib.h> |
13 | 13 |
14 #include "src/base/bits.h" | 14 #include "src/base/bits.h" |
| 15 #include "src/base/hashmap-entry.h" |
15 #include "src/base/logging.h" | 16 #include "src/base/logging.h" |
16 | 17 |
17 namespace v8 { | 18 namespace v8 { |
18 namespace base { | 19 namespace base { |
19 | 20 |
20 class DefaultAllocationPolicy { | 21 class DefaultAllocationPolicy { |
21 public: | 22 public: |
22 V8_INLINE void* New(size_t size) { return malloc(size); } | 23 V8_INLINE void* New(size_t size) { return malloc(size); } |
23 V8_INLINE static void Delete(void* p) { free(p); } | 24 V8_INLINE static void Delete(void* p) { free(p); } |
24 }; | 25 }; |
25 | 26 |
26 template <class AllocationPolicy> | 27 // Metaprogramming helper to allow pointer keys to be passed by value and |
| 28 // non-pointer keys by const reference. |
| 29 template <typename Key> |
| 30 struct MatchFunHelper; |
| 31 |
| 32 template <typename Key, typename Value, class AllocationPolicy> |
27 class TemplateHashMapImpl { | 33 class TemplateHashMapImpl { |
28 public: | 34 public: |
29 typedef bool (*MatchFun)(void* key1, void* key2); | 35 typedef typename MatchFunHelper<Key>::Fun MatchFun; |
| 36 typedef TemplateHashMapEntry<Key, Value> Entry; |
30 | 37 |
31 // The default capacity. This is used by the call sites which want | 38 // The default capacity. This is used by the call sites which want |
32 // to pass in a non-default AllocationPolicy but want to use the | 39 // to pass in a non-default AllocationPolicy but want to use the |
33 // default value of capacity specified by the implementation. | 40 // default value of capacity specified by the implementation. |
34 static const uint32_t kDefaultHashMapCapacity = 8; | 41 static const uint32_t kDefaultHashMapCapacity = 8; |
35 | 42 |
36 // initial_capacity is the size of the initial hash map; | 43 // initial_capacity is the size of the initial hash map; |
37 // it must be a power of 2 (and thus must not be 0). | 44 // it must be a power of 2 (and thus must not be 0). |
38 TemplateHashMapImpl(MatchFun match, | 45 TemplateHashMapImpl(MatchFun match, |
39 uint32_t capacity = kDefaultHashMapCapacity, | 46 uint32_t capacity = kDefaultHashMapCapacity, |
40 AllocationPolicy allocator = AllocationPolicy()); | 47 AllocationPolicy allocator = AllocationPolicy()); |
41 | 48 |
42 ~TemplateHashMapImpl(); | 49 ~TemplateHashMapImpl(); |
43 | 50 |
44 // HashMap entries are (key, value, hash) triplets. | |
45 // Some clients may not need to use the value slot | |
46 // (e.g. implementers of sets, where the key is the value). | |
47 struct Entry { | |
48 void* key; | |
49 void* value; | |
50 uint32_t hash; // The full hash value for key | |
51 }; | |
52 | |
53 // If an entry with matching key is found, returns that entry. | 51 // If an entry with matching key is found, returns that entry. |
54 // Otherwise, NULL is returned. | 52 // Otherwise, nullptr is returned. |
55 Entry* Lookup(void* key, uint32_t hash) const; | 53 Entry* Lookup(const Key& key, uint32_t hash) const; |
56 | 54 |
57 // If an entry with matching key is found, returns that entry. | 55 // If an entry with matching key is found, returns that entry. |
58 // If no matching entry is found, a new entry is inserted with | 56 // If no matching entry is found, a new entry is inserted with |
59 // corresponding key, key hash, and NULL value. | 57 // corresponding key, key hash, and default initialized value. |
60 Entry* LookupOrInsert(void* key, uint32_t hash, | 58 Entry* LookupOrInsert(const Key& key, uint32_t hash, |
61 AllocationPolicy allocator = AllocationPolicy()); | 59 AllocationPolicy allocator = AllocationPolicy()); |
62 | 60 |
63 Entry* InsertNew(void* key, uint32_t hash, | 61 Entry* InsertNew(const Key& key, uint32_t hash, |
64 AllocationPolicy allocator = AllocationPolicy()); | 62 AllocationPolicy allocator = AllocationPolicy()); |
65 | 63 |
66 // Removes the entry with matching key. | 64 // Removes the entry with matching key. |
67 // It returns the value of the deleted entry | 65 // It returns the value of the deleted entry |
68 // or null if there is no value for such key. | 66 // or null if there is no value for such key. |
69 void* Remove(void* key, uint32_t hash); | 67 Value Remove(const Key& key, uint32_t hash); |
70 | 68 |
71 // Empties the hash map (occupancy() == 0). | 69 // Empties the hash map (occupancy() == 0). |
72 void Clear(); | 70 void Clear(); |
73 | 71 |
74 // The number of (non-empty) entries in the table. | 72 // The number of (non-empty) entries in the table. |
75 uint32_t occupancy() const { return occupancy_; } | 73 uint32_t occupancy() const { return occupancy_; } |
76 | 74 |
77 // The capacity of the table. The implementation | 75 // The capacity of the table. The implementation |
78 // makes sure that occupancy is at most 80% of | 76 // makes sure that occupancy is at most 80% of |
79 // the table capacity. | 77 // the table capacity. |
80 uint32_t capacity() const { return capacity_; } | 78 uint32_t capacity() const { return capacity_; } |
81 | 79 |
82 // Iteration | 80 // Iteration |
83 // | 81 // |
84 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { | 82 // for (Entry* p = map.Start(); p != nullptr; p = map.Next(p)) { |
85 // ... | 83 // ... |
86 // } | 84 // } |
87 // | 85 // |
88 // If entries are inserted during iteration, the effect of | 86 // If entries are inserted during iteration, the effect of |
89 // calling Next() is undefined. | 87 // calling Next() is undefined. |
90 Entry* Start() const; | 88 Entry* Start() const; |
91 Entry* Next(Entry* p) const; | 89 Entry* Next(Entry* p) const; |
92 | 90 |
93 // Some match functions defined for convenience. | 91 // Some match functions defined for convenience. |
94 static bool PointersMatch(void* key1, void* key2) { return key1 == key2; } | 92 // TODO(leszeks): This isn't really matching pointers, so the name doesn't |
| 93 // really make sense, but we should remove this entirely and template the map |
| 94 // on the matching function. |
| 95 static bool PointersMatch(typename MatchFunHelper<Key>::KeyRef key1, |
| 96 typename MatchFunHelper<Key>::KeyRef key2) { |
| 97 return key1 == key2; |
| 98 } |
95 | 99 |
96 private: | 100 private: |
97 MatchFun match_; | 101 MatchFun match_; |
98 Entry* map_; | 102 Entry* map_; |
99 uint32_t capacity_; | 103 uint32_t capacity_; |
100 uint32_t occupancy_; | 104 uint32_t occupancy_; |
101 | 105 |
102 Entry* map_end() const { return map_ + capacity_; } | 106 Entry* map_end() const { return map_ + capacity_; } |
103 Entry* Probe(void* key, uint32_t hash) const; | 107 Entry* Probe(const Key& key, uint32_t hash) const; |
104 void Initialize(uint32_t capacity, AllocationPolicy allocator); | 108 void Initialize(uint32_t capacity, AllocationPolicy allocator); |
105 void Resize(AllocationPolicy allocator); | 109 void Resize(AllocationPolicy allocator); |
106 }; | 110 }; |
107 | 111 |
108 typedef TemplateHashMapImpl<DefaultAllocationPolicy> HashMap; | 112 template <typename Key> |
| 113 struct MatchFunHelper { |
| 114 typedef const Key& KeyRef; |
| 115 typedef bool (*Fun)(KeyRef key1, KeyRef key2); |
| 116 }; |
109 | 117 |
110 template <class AllocationPolicy> | 118 template <typename Key> |
111 TemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl( | 119 struct MatchFunHelper<Key*> { |
| 120 typedef Key* KeyRef; |
| 121 typedef bool (*Fun)(KeyRef key1, KeyRef key2); |
| 122 }; |
| 123 |
| 124 typedef TemplateHashMapImpl<void*, void*, DefaultAllocationPolicy> HashMap; |
| 125 |
| 126 template <typename Key, typename Value, class AllocationPolicy> |
| 127 TemplateHashMapImpl<Key, Value, AllocationPolicy>::TemplateHashMapImpl( |
112 MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) { | 128 MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) { |
113 match_ = match; | 129 match_ = match; |
114 Initialize(initial_capacity, allocator); | 130 Initialize(initial_capacity, allocator); |
115 } | 131 } |
116 | 132 |
117 template <class AllocationPolicy> | 133 template <typename Key, typename Value, class AllocationPolicy> |
118 TemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() { | 134 TemplateHashMapImpl<Key, Value, AllocationPolicy>::~TemplateHashMapImpl() { |
119 AllocationPolicy::Delete(map_); | 135 AllocationPolicy::Delete(map_); |
120 } | 136 } |
121 | 137 |
122 template <class AllocationPolicy> | 138 template <typename Key, typename Value, class AllocationPolicy> |
123 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 139 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* |
124 TemplateHashMapImpl<AllocationPolicy>::Lookup(void* key, uint32_t hash) const { | 140 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Lookup(const Key& key, |
| 141 uint32_t hash) const { |
125 Entry* p = Probe(key, hash); | 142 Entry* p = Probe(key, hash); |
126 return p->key != NULL ? p : NULL; | 143 return p->exists() ? p : nullptr; |
127 } | 144 } |
128 | 145 |
129 template <class AllocationPolicy> | 146 template <typename Key, typename Value, class AllocationPolicy> |
130 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 147 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* |
131 TemplateHashMapImpl<AllocationPolicy>::LookupOrInsert( | 148 TemplateHashMapImpl<Key, Value, AllocationPolicy>::LookupOrInsert( |
132 void* key, uint32_t hash, AllocationPolicy allocator) { | 149 const Key& key, uint32_t hash, AllocationPolicy allocator) { |
133 // Find a matching entry. | 150 // Find a matching entry. |
134 Entry* p = Probe(key, hash); | 151 Entry* p = Probe(key, hash); |
135 if (p->key != NULL) { | 152 if (p->exists()) { |
136 return p; | 153 return p; |
137 } | 154 } |
138 | 155 |
139 return InsertNew(key, hash, allocator); | 156 return InsertNew(key, hash, allocator); |
140 } | 157 } |
141 | 158 |
142 template <class AllocationPolicy> | 159 template <typename Key, typename Value, class AllocationPolicy> |
143 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 160 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* |
144 TemplateHashMapImpl<AllocationPolicy>::InsertNew(void* key, uint32_t hash, | 161 TemplateHashMapImpl<Key, Value, AllocationPolicy>::InsertNew( |
145 AllocationPolicy allocator) { | 162 const Key& key, uint32_t hash, AllocationPolicy allocator) { |
146 // Find a matching entry. | 163 // Find a matching entry. |
147 Entry* p = Probe(key, hash); | 164 Entry* p = Probe(key, hash); |
148 DCHECK(p->key == NULL); | 165 DCHECK(!p->exists()); |
149 | 166 |
150 // No entry found; insert one. | 167 // No entry found; construct one in-place in the empty slot using placement |
151 p->key = key; | 168 // new. |
152 p->value = NULL; | 169 new (p) Entry(key, Value(), hash); |
153 p->hash = hash; | |
154 occupancy_++; | 170 occupancy_++; |
155 | 171 |
156 // Grow the map if we reached >= 80% occupancy. | 172 // Grow the map if we reached >= 80% occupancy. |
157 if (occupancy_ + occupancy_ / 4 >= capacity_) { | 173 if (occupancy_ + occupancy_ / 4 >= capacity_) { |
158 Resize(allocator); | 174 Resize(allocator); |
159 p = Probe(key, hash); | 175 p = Probe(key, hash); |
160 } | 176 } |
161 | 177 |
162 return p; | 178 return p; |
163 } | 179 } |
164 | 180 |
165 template <class AllocationPolicy> | 181 template <typename Key, typename Value, class AllocationPolicy> |
166 void* TemplateHashMapImpl<AllocationPolicy>::Remove(void* key, uint32_t hash) { | 182 Value TemplateHashMapImpl<Key, Value, AllocationPolicy>::Remove(const Key& key, |
| 183 uint32_t hash) { |
167 // Lookup the entry for the key to remove. | 184 // Lookup the entry for the key to remove. |
168 Entry* p = Probe(key, hash); | 185 Entry* p = Probe(key, hash); |
169 if (p->key == NULL) { | 186 if (!p->exists()) { |
170 // Key not found nothing to remove. | 187 // Key not found nothing to remove. |
171 return NULL; | 188 return nullptr; |
172 } | 189 } |
173 | 190 |
174 void* value = p->value; | 191 Value value = p->value; |
175 // To remove an entry we need to ensure that it does not create an empty | 192 // To remove an entry we need to ensure that it does not create an empty |
176 // entry that will cause the search for another entry to stop too soon. If all | 193 // entry that will cause the search for another entry to stop too soon. If all |
177 // the entries between the entry to remove and the next empty slot have their | 194 // the entries between the entry to remove and the next empty slot have their |
178 // initial position inside this interval, clearing the entry to remove will | 195 // initial position inside this interval, clearing the entry to remove will |
179 // not break the search. If, while searching for the next empty entry, an | 196 // not break the search. If, while searching for the next empty entry, an |
180 // entry is encountered which does not have its initial position between the | 197 // entry is encountered which does not have its initial position between the |
181 // entry to remove and the position looked at, then this entry can be moved to | 198 // entry to remove and the position looked at, then this entry can be moved to |
182 // the place of the entry to remove without breaking the search for it. The | 199 // the place of the entry to remove without breaking the search for it. The |
183 // entry made vacant by this move is now the entry to remove and the process | 200 // entry made vacant by this move is now the entry to remove and the process |
184 // starts over. | 201 // starts over. |
185 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. | 202 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. |
186 | 203 |
187 // This guarantees loop termination as there is at least one empty entry so | 204 // This guarantees loop termination as there is at least one empty entry so |
188 // eventually the removed entry will have an empty entry after it. | 205 // eventually the removed entry will have an empty entry after it. |
189 DCHECK(occupancy_ < capacity_); | 206 DCHECK(occupancy_ < capacity_); |
190 | 207 |
191 // p is the candidate entry to clear. q is used to scan forwards. | 208 // p is the candidate entry to clear. q is used to scan forwards. |
192 Entry* q = p; // Start at the entry to remove. | 209 Entry* q = p; // Start at the entry to remove. |
193 while (true) { | 210 while (true) { |
194 // Move q to the next entry. | 211 // Move q to the next entry. |
195 q = q + 1; | 212 q = q + 1; |
196 if (q == map_end()) { | 213 if (q == map_end()) { |
197 q = map_; | 214 q = map_; |
198 } | 215 } |
199 | 216 |
200 // All entries between p and q have their initial position between p and q | 217 // All entries between p and q have their initial position between p and q |
201 // and the entry p can be cleared without breaking the search for these | 218 // and the entry p can be cleared without breaking the search for these |
202 // entries. | 219 // entries. |
203 if (q->key == NULL) { | 220 if (!q->exists()) { |
204 break; | 221 break; |
205 } | 222 } |
206 | 223 |
207 // Find the initial position for the entry at position q. | 224 // Find the initial position for the entry at position q. |
208 Entry* r = map_ + (q->hash & (capacity_ - 1)); | 225 Entry* r = map_ + (q->hash & (capacity_ - 1)); |
209 | 226 |
210 // If the entry at position q has its initial position outside the range | 227 // If the entry at position q has its initial position outside the range |
211 // between p and q it can be moved forward to position p and will still be | 228 // between p and q it can be moved forward to position p and will still be |
212 // found. There is now a new candidate entry for clearing. | 229 // found. There is now a new candidate entry for clearing. |
213 if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) { | 230 if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) { |
214 *p = *q; | 231 *p = *q; |
215 p = q; | 232 p = q; |
216 } | 233 } |
217 } | 234 } |
218 | 235 |
219 // Clear the entry which is allowed to en emptied. | 236 // Clear the entry which is allowed to en emptied. |
220 p->key = NULL; | 237 p->clear(); |
221 occupancy_--; | 238 occupancy_--; |
222 return value; | 239 return value; |
223 } | 240 } |
224 | 241 |
225 template <class AllocationPolicy> | 242 template <typename Key, typename Value, class AllocationPolicy> |
226 void TemplateHashMapImpl<AllocationPolicy>::Clear() { | 243 void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Clear() { |
227 // Mark all entries as empty. | 244 // Mark all entries as empty. |
228 const Entry* end = map_end(); | 245 const Entry* end = map_end(); |
229 for (Entry* p = map_; p < end; p++) { | 246 for (Entry* p = map_; p < end; p++) { |
230 p->key = NULL; | 247 p->clear(); |
231 } | 248 } |
232 occupancy_ = 0; | 249 occupancy_ = 0; |
233 } | 250 } |
234 | 251 |
235 template <class AllocationPolicy> | 252 template <typename Key, typename Value, class AllocationPolicy> |
236 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 253 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* |
237 TemplateHashMapImpl<AllocationPolicy>::Start() const { | 254 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Start() const { |
238 return Next(map_ - 1); | 255 return Next(map_ - 1); |
239 } | 256 } |
240 | 257 |
241 template <class AllocationPolicy> | 258 template <typename Key, typename Value, class AllocationPolicy> |
242 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 259 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* |
243 TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const { | 260 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Next(Entry* p) const { |
244 const Entry* end = map_end(); | 261 const Entry* end = map_end(); |
245 DCHECK(map_ - 1 <= p && p < end); | 262 DCHECK(map_ - 1 <= p && p < end); |
246 for (p++; p < end; p++) { | 263 for (p++; p < end; p++) { |
247 if (p->key != NULL) { | 264 if (p->exists()) { |
248 return p; | 265 return p; |
249 } | 266 } |
250 } | 267 } |
251 return NULL; | 268 return nullptr; |
252 } | 269 } |
253 | 270 |
254 template <class AllocationPolicy> | 271 template <typename Key, typename Value, class AllocationPolicy> |
255 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 272 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* |
256 TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) const { | 273 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Probe(const Key& key, |
257 DCHECK(key != NULL); | 274 uint32_t hash) const { |
258 | |
259 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); | 275 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); |
260 Entry* p = map_ + (hash & (capacity_ - 1)); | 276 Entry* p = map_ + (hash & (capacity_ - 1)); |
261 const Entry* end = map_end(); | 277 const Entry* end = map_end(); |
262 DCHECK(map_ <= p && p < end); | 278 DCHECK(map_ <= p && p < end); |
263 | 279 |
264 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. | 280 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. |
265 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { | 281 while (p->exists() && (hash != p->hash || !match_(key, p->key))) { |
266 p++; | 282 p++; |
267 if (p >= end) { | 283 if (p >= end) { |
268 p = map_; | 284 p = map_; |
269 } | 285 } |
270 } | 286 } |
271 | 287 |
272 return p; | 288 return p; |
273 } | 289 } |
274 | 290 |
275 template <class AllocationPolicy> | 291 template <typename Key, typename Value, class AllocationPolicy> |
276 void TemplateHashMapImpl<AllocationPolicy>::Initialize( | 292 void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Initialize( |
277 uint32_t capacity, AllocationPolicy allocator) { | 293 uint32_t capacity, AllocationPolicy allocator) { |
278 DCHECK(base::bits::IsPowerOfTwo32(capacity)); | 294 DCHECK(base::bits::IsPowerOfTwo32(capacity)); |
279 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); | 295 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); |
280 if (map_ == NULL) { | 296 if (map_ == nullptr) { |
281 FATAL("Out of memory: HashMap::Initialize"); | 297 FATAL("Out of memory: HashMap::Initialize"); |
282 return; | 298 return; |
283 } | 299 } |
284 capacity_ = capacity; | 300 capacity_ = capacity; |
285 Clear(); | 301 Clear(); |
286 } | 302 } |
287 | 303 |
288 template <class AllocationPolicy> | 304 template <typename Key, typename Value, class AllocationPolicy> |
289 void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) { | 305 void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Resize( |
| 306 AllocationPolicy allocator) { |
290 Entry* map = map_; | 307 Entry* map = map_; |
291 uint32_t n = occupancy_; | 308 uint32_t n = occupancy_; |
292 | 309 |
293 // Allocate larger map. | 310 // Allocate larger map. |
294 Initialize(capacity_ * 2, allocator); | 311 Initialize(capacity_ * 2, allocator); |
295 | 312 |
296 // Rehash all current entries. | 313 // Rehash all current entries. |
297 for (Entry* p = map; n > 0; p++) { | 314 for (Entry* p = map; n > 0; p++) { |
298 if (p->key != NULL) { | 315 if (p->exists()) { |
299 Entry* entry = LookupOrInsert(p->key, p->hash, allocator); | 316 Entry* entry = LookupOrInsert(p->key, p->hash, allocator); |
300 entry->value = p->value; | 317 entry->value = p->value; |
301 n--; | 318 n--; |
302 } | 319 } |
303 } | 320 } |
304 | 321 |
305 // Delete old map. | 322 // Delete old map. |
306 AllocationPolicy::Delete(map); | 323 AllocationPolicy::Delete(map); |
307 } | 324 } |
308 | 325 |
309 // A hash map for pointer keys and values with an STL-like interface. | 326 // A hash map for pointer keys and values with an STL-like interface. |
310 template <class Key, class Value, class AllocationPolicy> | 327 template <class Key, class Value, class AllocationPolicy> |
311 class TemplateHashMap : private TemplateHashMapImpl<AllocationPolicy> { | 328 class TemplateHashMap |
| 329 : private TemplateHashMapImpl<void*, void*, AllocationPolicy> { |
312 public: | 330 public: |
313 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT | 331 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT |
314 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT | 332 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT |
315 struct value_type { | 333 struct value_type { |
316 Key* first; | 334 Key* first; |
317 Value* second; | 335 Value* second; |
318 }; | 336 }; |
319 | 337 |
320 class Iterator { | 338 class Iterator { |
321 public: | 339 public: |
322 Iterator& operator++() { | 340 Iterator& operator++() { |
323 entry_ = map_->Next(entry_); | 341 entry_ = map_->Next(entry_); |
324 return *this; | 342 return *this; |
325 } | 343 } |
326 | 344 |
327 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } | 345 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } |
328 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } | 346 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } |
329 | 347 |
330 private: | 348 private: |
331 Iterator(const TemplateHashMapImpl<AllocationPolicy>* map, | 349 Iterator(const TemplateHashMapImpl<void*, void*, AllocationPolicy>* map, |
332 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) | 350 typename TemplateHashMapImpl<void*, void*, |
| 351 AllocationPolicy>::Entry* entry) |
333 : map_(map), entry_(entry) {} | 352 : map_(map), entry_(entry) {} |
334 | 353 |
335 const TemplateHashMapImpl<AllocationPolicy>* map_; | 354 const TemplateHashMapImpl<void*, void*, AllocationPolicy>* map_; |
336 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_; | 355 typename TemplateHashMapImpl<void*, void*, AllocationPolicy>::Entry* entry_; |
337 | 356 |
338 friend class TemplateHashMap; | 357 friend class TemplateHashMap; |
339 }; | 358 }; |
340 | 359 |
341 TemplateHashMap( | 360 TemplateHashMap(typename TemplateHashMapImpl< |
342 typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match, | 361 void*, void*, AllocationPolicy>::MatchFun match, |
343 AllocationPolicy allocator = AllocationPolicy()) | 362 AllocationPolicy allocator = AllocationPolicy()) |
344 : TemplateHashMapImpl<AllocationPolicy>( | 363 : TemplateHashMapImpl<void*, void*, AllocationPolicy>( |
345 match, | 364 match, |
346 TemplateHashMapImpl<AllocationPolicy>::kDefaultHashMapCapacity, | 365 TemplateHashMapImpl<void*, void*, |
| 366 AllocationPolicy>::kDefaultHashMapCapacity, |
347 allocator) {} | 367 allocator) {} |
348 | 368 |
349 Iterator begin() const { return Iterator(this, this->Start()); } | 369 Iterator begin() const { return Iterator(this, this->Start()); } |
350 Iterator end() const { return Iterator(this, NULL); } | 370 Iterator end() const { return Iterator(this, nullptr); } |
351 Iterator find(Key* key, bool insert = false, | 371 Iterator find(Key* key, bool insert = false, |
352 AllocationPolicy allocator = AllocationPolicy()) { | 372 AllocationPolicy allocator = AllocationPolicy()) { |
353 if (insert) { | 373 if (insert) { |
354 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); | 374 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); |
355 } | 375 } |
356 return Iterator(this, this->Lookup(key, key->Hash())); | 376 return Iterator(this, this->Lookup(key, key->Hash())); |
357 } | 377 } |
358 }; | 378 }; |
359 | 379 |
360 } // namespace base | 380 } // namespace base |
361 } // namespace v8 | 381 } // namespace v8 |
362 | 382 |
363 #endif // V8_BASE_HASHMAP_H_ | 383 #endif // V8_BASE_HASHMAP_H_ |
OLD | NEW |