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/hashmap-entry.h" |
16 #include "src/base/logging.h" | 16 #include "src/base/logging.h" |
17 | 17 |
18 namespace v8 { | 18 namespace v8 { |
19 namespace base { | 19 namespace base { |
20 | 20 |
21 class DefaultAllocationPolicy { | 21 class DefaultAllocationPolicy { |
22 public: | 22 public: |
23 V8_INLINE void* New(size_t size) { return malloc(size); } | 23 V8_INLINE void* New(size_t size) { return malloc(size); } |
24 V8_INLINE static void Delete(void* p) { free(p); } | 24 V8_INLINE static void Delete(void* p) { free(p); } |
25 }; | 25 }; |
26 | 26 |
27 // Metaprogramming helper to allow pointer keys to be passed by value and | 27 template <typename Key, typename Value, class MatchFun, class AllocationPolicy> |
28 // non-pointer keys by const reference. | |
29 template <typename Key> | |
30 struct MatchFunHelper; | |
31 | |
32 template <typename Key, typename Value, class AllocationPolicy> | |
33 class TemplateHashMapImpl { | 28 class TemplateHashMapImpl { |
34 public: | 29 public: |
35 typedef typename MatchFunHelper<Key>::Fun MatchFun; | |
36 typedef TemplateHashMapEntry<Key, Value> Entry; | 30 typedef TemplateHashMapEntry<Key, Value> Entry; |
37 | 31 |
38 // 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 |
39 // 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 |
40 // default value of capacity specified by the implementation. | 34 // default value of capacity specified by the implementation. |
41 static const uint32_t kDefaultHashMapCapacity = 8; | 35 static const uint32_t kDefaultHashMapCapacity = 8; |
42 | 36 |
43 // initial_capacity is the size of the initial hash map; | 37 // initial_capacity is the size of the initial hash map; |
44 // 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). |
45 TemplateHashMapImpl(MatchFun match, | 39 TemplateHashMapImpl(MatchFun match = MatchFun(), |
46 uint32_t capacity = kDefaultHashMapCapacity, | 40 uint32_t capacity = kDefaultHashMapCapacity, |
47 AllocationPolicy allocator = AllocationPolicy()); | 41 AllocationPolicy allocator = AllocationPolicy()); |
48 | 42 |
49 ~TemplateHashMapImpl(); | 43 ~TemplateHashMapImpl(); |
50 | 44 |
51 // If an entry with matching key is found, returns that entry. | 45 // If an entry with matching key is found, returns that entry. |
52 // Otherwise, nullptr is returned. | 46 // Otherwise, nullptr is returned. |
53 Entry* Lookup(const Key& key, uint32_t hash) const; | 47 Entry* Lookup(const Key& key, uint32_t hash) const; |
54 | 48 |
55 // If an entry with matching key is found, returns that entry. | 49 // If an entry with matching key is found, returns that entry. |
(...skipping 25 matching lines...) Expand all Loading... |
81 // | 75 // |
82 // for (Entry* p = map.Start(); p != nullptr; p = map.Next(p)) { | 76 // for (Entry* p = map.Start(); p != nullptr; p = map.Next(p)) { |
83 // ... | 77 // ... |
84 // } | 78 // } |
85 // | 79 // |
86 // If entries are inserted during iteration, the effect of | 80 // If entries are inserted during iteration, the effect of |
87 // calling Next() is undefined. | 81 // calling Next() is undefined. |
88 Entry* Start() const; | 82 Entry* Start() const; |
89 Entry* Next(Entry* entry) const; | 83 Entry* Next(Entry* entry) const; |
90 | 84 |
91 // Some match functions defined for convenience. | |
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 } | |
99 | |
100 private: | 85 private: |
101 MatchFun match_; | |
102 Entry* map_; | 86 Entry* map_; |
103 uint32_t capacity_; | 87 uint32_t capacity_; |
104 uint32_t occupancy_; | 88 uint32_t occupancy_; |
| 89 MatchFun match_; |
105 | 90 |
106 Entry* map_end() const { return map_ + capacity_; } | 91 Entry* map_end() const { return map_ + capacity_; } |
107 Entry* Probe(const Key& key, uint32_t hash) const; | 92 Entry* Probe(const Key& key, uint32_t hash) const; |
108 Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value, | 93 Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value, |
109 uint32_t hash, | 94 uint32_t hash, |
110 AllocationPolicy allocator = AllocationPolicy()); | 95 AllocationPolicy allocator = AllocationPolicy()); |
111 void Initialize(uint32_t capacity, AllocationPolicy allocator); | 96 void Initialize(uint32_t capacity, AllocationPolicy allocator); |
112 void Resize(AllocationPolicy allocator); | 97 void Resize(AllocationPolicy allocator); |
113 }; | 98 }; |
114 | 99 template <typename Key, typename Value, typename MatchFun, |
115 template <typename Key> | 100 class AllocationPolicy> |
116 struct MatchFunHelper { | 101 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>:: |
117 typedef const Key& KeyRef; | 102 TemplateHashMapImpl(MatchFun match, uint32_t initial_capacity, |
118 typedef bool (*Fun)(KeyRef key1, KeyRef key2); | 103 AllocationPolicy allocator) |
119 }; | 104 : match_(match) { |
120 | |
121 template <typename Key> | |
122 struct MatchFunHelper<Key*> { | |
123 typedef Key* KeyRef; | |
124 typedef bool (*Fun)(KeyRef key1, KeyRef key2); | |
125 }; | |
126 | |
127 typedef TemplateHashMapImpl<void*, void*, DefaultAllocationPolicy> HashMap; | |
128 | |
129 template <typename Key, typename Value, class AllocationPolicy> | |
130 TemplateHashMapImpl<Key, Value, AllocationPolicy>::TemplateHashMapImpl( | |
131 MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) { | |
132 match_ = match; | |
133 Initialize(initial_capacity, allocator); | 105 Initialize(initial_capacity, allocator); |
134 } | 106 } |
135 | 107 |
136 template <typename Key, typename Value, class AllocationPolicy> | 108 template <typename Key, typename Value, typename MatchFun, |
137 TemplateHashMapImpl<Key, Value, AllocationPolicy>::~TemplateHashMapImpl() { | 109 class AllocationPolicy> |
| 110 TemplateHashMapImpl<Key, Value, MatchFun, |
| 111 AllocationPolicy>::~TemplateHashMapImpl() { |
138 AllocationPolicy::Delete(map_); | 112 AllocationPolicy::Delete(map_); |
139 } | 113 } |
140 | 114 |
141 template <typename Key, typename Value, class AllocationPolicy> | 115 template <typename Key, typename Value, typename MatchFun, |
142 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* | 116 class AllocationPolicy> |
143 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Lookup(const Key& key, | 117 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* |
144 uint32_t hash) const { | 118 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Lookup( |
| 119 const Key& key, uint32_t hash) const { |
145 Entry* entry = Probe(key, hash); | 120 Entry* entry = Probe(key, hash); |
146 return entry->exists() ? entry : nullptr; | 121 return entry->exists() ? entry : nullptr; |
147 } | 122 } |
148 | 123 |
149 template <typename Key, typename Value, class AllocationPolicy> | 124 template <typename Key, typename Value, typename MatchFun, |
150 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* | 125 class AllocationPolicy> |
151 TemplateHashMapImpl<Key, Value, AllocationPolicy>::LookupOrInsert( | 126 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* |
| 127 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert( |
152 const Key& key, uint32_t hash, AllocationPolicy allocator) { | 128 const Key& key, uint32_t hash, AllocationPolicy allocator) { |
153 // Find a matching entry. | 129 // Find a matching entry. |
154 Entry* entry = Probe(key, hash); | 130 Entry* entry = Probe(key, hash); |
155 if (entry->exists()) { | 131 if (entry->exists()) { |
156 return entry; | 132 return entry; |
157 } | 133 } |
158 | 134 |
159 return FillEmptyEntry(entry, key, Value(), hash, allocator); | 135 return FillEmptyEntry(entry, key, Value(), hash, allocator); |
160 } | 136 } |
161 | 137 |
162 template <typename Key, typename Value, class AllocationPolicy> | 138 template <typename Key, typename Value, typename MatchFun, |
163 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* | 139 class AllocationPolicy> |
164 TemplateHashMapImpl<Key, Value, AllocationPolicy>::InsertNew( | 140 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* |
| 141 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::InsertNew( |
165 const Key& key, uint32_t hash, AllocationPolicy allocator) { | 142 const Key& key, uint32_t hash, AllocationPolicy allocator) { |
166 Entry* entry = Probe(key, hash); | 143 Entry* entry = Probe(key, hash); |
167 return FillEmptyEntry(entry, key, Value(), hash, allocator); | 144 return FillEmptyEntry(entry, key, Value(), hash, allocator); |
168 } | 145 } |
169 | 146 |
170 template <typename Key, typename Value, class AllocationPolicy> | 147 template <typename Key, typename Value, typename MatchFun, |
171 Value TemplateHashMapImpl<Key, Value, AllocationPolicy>::Remove(const Key& key, | 148 class AllocationPolicy> |
172 uint32_t hash) { | 149 Value TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Remove( |
| 150 const Key& key, uint32_t hash) { |
173 // Lookup the entry for the key to remove. | 151 // Lookup the entry for the key to remove. |
174 Entry* p = Probe(key, hash); | 152 Entry* p = Probe(key, hash); |
175 if (!p->exists()) { | 153 if (!p->exists()) { |
176 // Key not found nothing to remove. | 154 // Key not found nothing to remove. |
177 return nullptr; | 155 return nullptr; |
178 } | 156 } |
179 | 157 |
180 Value value = p->value; | 158 Value value = p->value; |
181 // To remove an entry we need to ensure that it does not create an empty | 159 // To remove an entry we need to ensure that it does not create an empty |
182 // entry that will cause the search for another entry to stop too soon. If all | 160 // entry that will cause the search for another entry to stop too soon. If all |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
221 p = q; | 199 p = q; |
222 } | 200 } |
223 } | 201 } |
224 | 202 |
225 // Clear the entry which is allowed to en emptied. | 203 // Clear the entry which is allowed to en emptied. |
226 p->clear(); | 204 p->clear(); |
227 occupancy_--; | 205 occupancy_--; |
228 return value; | 206 return value; |
229 } | 207 } |
230 | 208 |
231 template <typename Key, typename Value, class AllocationPolicy> | 209 template <typename Key, typename Value, typename MatchFun, |
232 void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Clear() { | 210 class AllocationPolicy> |
| 211 void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Clear() { |
233 // Mark all entries as empty. | 212 // Mark all entries as empty. |
234 const Entry* end = map_end(); | 213 const Entry* end = map_end(); |
235 for (Entry* entry = map_; entry < end; entry++) { | 214 for (Entry* entry = map_; entry < end; entry++) { |
236 entry->clear(); | 215 entry->clear(); |
237 } | 216 } |
238 occupancy_ = 0; | 217 occupancy_ = 0; |
239 } | 218 } |
240 | 219 |
241 template <typename Key, typename Value, class AllocationPolicy> | 220 template <typename Key, typename Value, typename MatchFun, |
242 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* | 221 class AllocationPolicy> |
243 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Start() const { | 222 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* |
| 223 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Start() const { |
244 return Next(map_ - 1); | 224 return Next(map_ - 1); |
245 } | 225 } |
246 | 226 |
247 template <typename Key, typename Value, class AllocationPolicy> | 227 template <typename Key, typename Value, typename MatchFun, |
248 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* | 228 class AllocationPolicy> |
249 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Next(Entry* entry) const { | 229 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* |
| 230 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Next( |
| 231 Entry* entry) const { |
250 const Entry* end = map_end(); | 232 const Entry* end = map_end(); |
251 DCHECK(map_ - 1 <= entry && entry < end); | 233 DCHECK(map_ - 1 <= entry && entry < end); |
252 for (entry++; entry < end; entry++) { | 234 for (entry++; entry < end; entry++) { |
253 if (entry->exists()) { | 235 if (entry->exists()) { |
254 return entry; | 236 return entry; |
255 } | 237 } |
256 } | 238 } |
257 return nullptr; | 239 return nullptr; |
258 } | 240 } |
259 | 241 |
260 template <typename Key, typename Value, class AllocationPolicy> | 242 template <typename Key, typename Value, typename MatchFun, |
261 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* | 243 class AllocationPolicy> |
262 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Probe(const Key& key, | 244 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* |
263 uint32_t hash) const { | 245 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe( |
| 246 const Key& key, uint32_t hash) const { |
264 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); | 247 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); |
265 Entry* entry = map_ + (hash & (capacity_ - 1)); | 248 Entry* entry = map_ + (hash & (capacity_ - 1)); |
266 const Entry* end = map_end(); | 249 const Entry* end = map_end(); |
267 DCHECK(map_ <= entry && entry < end); | 250 DCHECK(map_ <= entry && entry < end); |
268 | 251 |
269 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. | 252 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. |
270 while (entry->exists() && (hash != entry->hash || !match_(key, entry->key))) { | 253 while (entry->exists() && (hash != entry->hash || !match_(key, entry->key))) { |
271 entry++; | 254 entry++; |
272 if (entry >= end) { | 255 if (entry >= end) { |
273 entry = map_; | 256 entry = map_; |
274 } | 257 } |
275 } | 258 } |
276 | 259 |
277 return entry; | 260 return entry; |
278 } | 261 } |
279 | 262 |
280 template <typename Key, typename Value, class AllocationPolicy> | 263 template <typename Key, typename Value, typename MatchFun, |
281 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry* | 264 class AllocationPolicy> |
282 TemplateHashMapImpl<Key, Value, AllocationPolicy>::FillEmptyEntry( | 265 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* |
| 266 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::FillEmptyEntry( |
283 Entry* entry, const Key& key, const Value& value, uint32_t hash, | 267 Entry* entry, const Key& key, const Value& value, uint32_t hash, |
284 AllocationPolicy allocator) { | 268 AllocationPolicy allocator) { |
285 DCHECK(!entry->exists()); | 269 DCHECK(!entry->exists()); |
286 | 270 |
287 new (entry) Entry(key, value, hash); | 271 new (entry) Entry(key, value, hash); |
288 occupancy_++; | 272 occupancy_++; |
289 | 273 |
290 // Grow the map if we reached >= 80% occupancy. | 274 // Grow the map if we reached >= 80% occupancy. |
291 if (occupancy_ + occupancy_ / 4 >= capacity_) { | 275 if (occupancy_ + occupancy_ / 4 >= capacity_) { |
292 Resize(allocator); | 276 Resize(allocator); |
293 entry = Probe(key, hash); | 277 entry = Probe(key, hash); |
294 } | 278 } |
295 | 279 |
296 return entry; | 280 return entry; |
297 } | 281 } |
298 | 282 |
299 template <typename Key, typename Value, class AllocationPolicy> | 283 template <typename Key, typename Value, typename MatchFun, |
300 void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Initialize( | 284 class AllocationPolicy> |
| 285 void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Initialize( |
301 uint32_t capacity, AllocationPolicy allocator) { | 286 uint32_t capacity, AllocationPolicy allocator) { |
302 DCHECK(base::bits::IsPowerOfTwo32(capacity)); | 287 DCHECK(base::bits::IsPowerOfTwo32(capacity)); |
303 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); | 288 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); |
304 if (map_ == nullptr) { | 289 if (map_ == nullptr) { |
305 FATAL("Out of memory: HashMap::Initialize"); | 290 FATAL("Out of memory: HashMap::Initialize"); |
306 return; | 291 return; |
307 } | 292 } |
308 capacity_ = capacity; | 293 capacity_ = capacity; |
309 Clear(); | 294 Clear(); |
310 } | 295 } |
311 | 296 |
312 template <typename Key, typename Value, class AllocationPolicy> | 297 template <typename Key, typename Value, typename MatchFun, |
313 void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Resize( | 298 class AllocationPolicy> |
| 299 void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Resize( |
314 AllocationPolicy allocator) { | 300 AllocationPolicy allocator) { |
315 Entry* map = map_; | 301 Entry* map = map_; |
316 uint32_t n = occupancy_; | 302 uint32_t n = occupancy_; |
317 | 303 |
318 // Allocate larger map. | 304 // Allocate larger map. |
319 Initialize(capacity_ * 2, allocator); | 305 Initialize(capacity_ * 2, allocator); |
320 | 306 |
321 // Rehash all current entries. | 307 // Rehash all current entries. |
322 for (Entry* entry = map; n > 0; entry++) { | 308 for (Entry* entry = map; n > 0; entry++) { |
323 if (entry->exists()) { | 309 if (entry->exists()) { |
324 Entry* new_entry = Probe(entry->key, entry->hash); | 310 Entry* new_entry = Probe(entry->key, entry->hash); |
325 new_entry = FillEmptyEntry(new_entry, entry->key, entry->value, | 311 new_entry = FillEmptyEntry(new_entry, entry->key, entry->value, |
326 entry->hash, allocator); | 312 entry->hash, allocator); |
327 n--; | 313 n--; |
328 } | 314 } |
329 } | 315 } |
330 | 316 |
331 // Delete old map. | 317 // Delete old map. |
332 AllocationPolicy::Delete(map); | 318 AllocationPolicy::Delete(map); |
333 } | 319 } |
334 | 320 |
| 321 template <typename AllocationPolicy> |
| 322 class PointerTemplateHashMapImpl |
| 323 : public TemplateHashMapImpl<void*, void*, bool (*)(void*, void*), |
| 324 AllocationPolicy> { |
| 325 typedef TemplateHashMapImpl<void*, void*, bool (*)(void*, void*), |
| 326 AllocationPolicy> |
| 327 Base; |
| 328 |
| 329 public: |
| 330 typedef bool (*MatchFun)(void*, void*); |
| 331 |
| 332 PointerTemplateHashMapImpl(MatchFun match = PointersMatch, |
| 333 uint32_t capacity = Base::kDefaultHashMapCapacity, |
| 334 AllocationPolicy allocator = AllocationPolicy()) |
| 335 : Base(match, capacity, allocator) {} |
| 336 |
| 337 static bool PointersMatch(void* key1, void* key2) { return key1 == key2; } |
| 338 }; |
| 339 |
| 340 typedef PointerTemplateHashMapImpl<DefaultAllocationPolicy> HashMap; |
| 341 |
335 // A hash map for pointer keys and values with an STL-like interface. | 342 // A hash map for pointer keys and values with an STL-like interface. |
336 template <class Key, class Value, class AllocationPolicy> | 343 template <class Key, class Value, class AllocationPolicy> |
337 class TemplateHashMap | 344 class TemplateHashMap : private PointerTemplateHashMapImpl<AllocationPolicy> { |
338 : private TemplateHashMapImpl<void*, void*, AllocationPolicy> { | 345 typedef PointerTemplateHashMapImpl<AllocationPolicy> Base; |
| 346 |
339 public: | 347 public: |
| 348 typedef bool (*MatchFun)(void*, void*); |
| 349 |
340 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT | 350 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT |
341 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT | 351 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT |
342 struct value_type { | 352 struct value_type { |
343 Key* first; | 353 Key* first; |
344 Value* second; | 354 Value* second; |
345 }; | 355 }; |
346 | 356 |
347 class Iterator { | 357 class Iterator { |
348 public: | 358 public: |
349 Iterator& operator++() { | 359 Iterator& operator++() { |
350 entry_ = map_->Next(entry_); | 360 entry_ = map_->Next(entry_); |
351 return *this; | 361 return *this; |
352 } | 362 } |
353 | 363 |
354 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } | 364 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } |
355 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } | 365 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } |
356 | 366 |
357 private: | 367 private: |
358 Iterator(const TemplateHashMapImpl<void*, void*, AllocationPolicy>* map, | 368 Iterator(const Base* map, typename Base::Entry* entry) |
359 typename TemplateHashMapImpl<void*, void*, | |
360 AllocationPolicy>::Entry* entry) | |
361 : map_(map), entry_(entry) {} | 369 : map_(map), entry_(entry) {} |
362 | 370 |
363 const TemplateHashMapImpl<void*, void*, AllocationPolicy>* map_; | 371 const Base* map_; |
364 typename TemplateHashMapImpl<void*, void*, AllocationPolicy>::Entry* entry_; | 372 typename Base::Entry* entry_; |
365 | 373 |
366 friend class TemplateHashMap; | 374 friend class TemplateHashMap; |
367 }; | 375 }; |
368 | 376 |
369 TemplateHashMap(typename TemplateHashMapImpl< | 377 TemplateHashMap(MatchFun match, |
370 void*, void*, AllocationPolicy>::MatchFun match, | |
371 AllocationPolicy allocator = AllocationPolicy()) | 378 AllocationPolicy allocator = AllocationPolicy()) |
372 : TemplateHashMapImpl<void*, void*, AllocationPolicy>( | 379 : Base(match, Base::kDefaultHashMapCapacity, allocator) {} |
373 match, | |
374 TemplateHashMapImpl<void*, void*, | |
375 AllocationPolicy>::kDefaultHashMapCapacity, | |
376 allocator) {} | |
377 | 380 |
378 Iterator begin() const { return Iterator(this, this->Start()); } | 381 Iterator begin() const { return Iterator(this, this->Start()); } |
379 Iterator end() const { return Iterator(this, nullptr); } | 382 Iterator end() const { return Iterator(this, nullptr); } |
380 Iterator find(Key* key, bool insert = false, | 383 Iterator find(Key* key, bool insert = false, |
381 AllocationPolicy allocator = AllocationPolicy()) { | 384 AllocationPolicy allocator = AllocationPolicy()) { |
382 if (insert) { | 385 if (insert) { |
383 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); | 386 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); |
384 } | 387 } |
385 return Iterator(this, this->Lookup(key, key->Hash())); | 388 return Iterator(this, this->Lookup(key, key->Hash())); |
386 } | 389 } |
387 }; | 390 }; |
388 | 391 |
389 } // namespace base | 392 } // namespace base |
390 } // namespace v8 | 393 } // namespace v8 |
391 | 394 |
392 #endif // V8_BASE_HASHMAP_H_ | 395 #endif // V8_BASE_HASHMAP_H_ |
OLD | NEW |