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 251 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
262 class AllocationPolicy> | 262 class AllocationPolicy> |
263 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* | 263 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* |
264 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe( | 264 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe( |
265 const Key& key, uint32_t hash) const { | 265 const Key& key, uint32_t hash) const { |
266 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); | 266 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); |
267 Entry* entry = map_ + (hash & (capacity_ - 1)); | 267 Entry* entry = map_ + (hash & (capacity_ - 1)); |
268 const Entry* end = map_end(); | 268 const Entry* end = map_end(); |
269 DCHECK(map_ <= entry && entry < end); | 269 DCHECK(map_ <= entry && entry < end); |
270 | 270 |
271 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. | 271 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. |
272 while (entry->exists() && (hash != entry->hash || !match_(key, entry->key))) { | 272 while (entry->exists() && !match_(hash, entry->hash, key, entry->key)) { |
273 entry++; | 273 entry++; |
274 if (entry >= end) { | 274 if (entry >= end) { |
275 entry = map_; | 275 entry = map_; |
276 } | 276 } |
277 } | 277 } |
278 | 278 |
279 return entry; | 279 return entry; |
280 } | 280 } |
281 | 281 |
282 template <typename Key, typename Value, typename MatchFun, | 282 template <typename Key, typename Value, typename MatchFun, |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
330 new_entry = FillEmptyEntry(new_entry, entry->key, entry->value, | 330 new_entry = FillEmptyEntry(new_entry, entry->key, entry->value, |
331 entry->hash, allocator); | 331 entry->hash, allocator); |
332 n--; | 332 n--; |
333 } | 333 } |
334 } | 334 } |
335 | 335 |
336 // Delete old map. | 336 // Delete old map. |
337 AllocationPolicy::Delete(map); | 337 AllocationPolicy::Delete(map); |
338 } | 338 } |
339 | 339 |
| 340 // Match function which compares hashes before executing a (potentially |
| 341 // expensive) key comparison. |
| 342 template <typename Key, typename MatchFun> |
| 343 struct HashEqualityThenKeyMatcher { |
| 344 explicit HashEqualityThenKeyMatcher(MatchFun match) : match_(match) {} |
| 345 |
| 346 bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1, |
| 347 const Key& key2) const { |
| 348 return hash1 == hash2 && match_(key1, key2); |
| 349 } |
| 350 |
| 351 private: |
| 352 MatchFun match_; |
| 353 }; |
| 354 |
| 355 // Hashmap<void*, void*> which takes a custom key comparison function pointer. |
340 template <typename AllocationPolicy> | 356 template <typename AllocationPolicy> |
341 class CustomMatcherTemplateHashMapImpl | 357 class CustomMatcherTemplateHashMapImpl |
342 : public TemplateHashMapImpl<void*, void*, bool (*)(void*, void*), | 358 : public TemplateHashMapImpl< |
343 AllocationPolicy> { | 359 void*, void*, |
344 typedef TemplateHashMapImpl<void*, void*, bool (*)(void*, void*), | 360 HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>, |
345 AllocationPolicy> | 361 AllocationPolicy> { |
| 362 typedef TemplateHashMapImpl< |
| 363 void*, void*, HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>, |
| 364 AllocationPolicy> |
346 Base; | 365 Base; |
347 | 366 |
348 public: | 367 public: |
349 typedef bool (*MatchFun)(void*, void*); | 368 typedef bool (*MatchFun)(void*, void*); |
350 | 369 |
351 CustomMatcherTemplateHashMapImpl( | 370 CustomMatcherTemplateHashMapImpl( |
352 MatchFun match, uint32_t capacity = Base::kDefaultHashMapCapacity, | 371 MatchFun match, uint32_t capacity = Base::kDefaultHashMapCapacity, |
353 AllocationPolicy allocator = AllocationPolicy()) | 372 AllocationPolicy allocator = AllocationPolicy()) |
354 : Base(capacity, match, allocator) {} | 373 : Base(capacity, HashEqualityThenKeyMatcher<void*, MatchFun>(match), |
| 374 allocator) {} |
355 }; | 375 }; |
356 | 376 |
357 typedef CustomMatcherTemplateHashMapImpl<DefaultAllocationPolicy> | 377 typedef CustomMatcherTemplateHashMapImpl<DefaultAllocationPolicy> |
358 CustomMatcherHashMap; | 378 CustomMatcherHashMap; |
359 | 379 |
| 380 // Match function which compares keys directly by equality. |
| 381 template <typename Key> |
| 382 struct KeyEqualityMatcher { |
| 383 bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1, |
| 384 const Key& key2) const { |
| 385 return key1 == key2; |
| 386 } |
| 387 }; |
| 388 |
| 389 // Hashmap<void*, void*> which compares the key pointers directly. |
360 template <typename AllocationPolicy> | 390 template <typename AllocationPolicy> |
361 class PointerTemplateHashMapImpl | 391 class PointerTemplateHashMapImpl |
362 : public TemplateHashMapImpl<void*, void*, std::equal_to<void*>, | 392 : public TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>, |
363 AllocationPolicy> { | 393 AllocationPolicy> { |
364 typedef TemplateHashMapImpl<void*, void*, std::equal_to<void*>, | 394 typedef TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>, |
365 AllocationPolicy> | 395 AllocationPolicy> |
366 Base; | 396 Base; |
367 | 397 |
368 public: | 398 public: |
369 PointerTemplateHashMapImpl(uint32_t capacity = Base::kDefaultHashMapCapacity, | 399 PointerTemplateHashMapImpl(uint32_t capacity = Base::kDefaultHashMapCapacity, |
370 AllocationPolicy allocator = AllocationPolicy()) | 400 AllocationPolicy allocator = AllocationPolicy()) |
371 : Base(capacity, std::equal_to<void*>(), allocator) {} | 401 : Base(capacity, KeyEqualityMatcher<void*>(), allocator) {} |
372 }; | 402 }; |
373 | 403 |
374 typedef PointerTemplateHashMapImpl<DefaultAllocationPolicy> HashMap; | 404 typedef PointerTemplateHashMapImpl<DefaultAllocationPolicy> HashMap; |
375 | 405 |
376 // A hash map for pointer keys and values with an STL-like interface. | 406 // A hash map for pointer keys and values with an STL-like interface. |
377 template <class Key, class Value, class MatchFun, class AllocationPolicy> | 407 template <class Key, class Value, class MatchFun, class AllocationPolicy> |
378 class TemplateHashMap | 408 class TemplateHashMap |
379 : private TemplateHashMapImpl<void*, void*, MatchFun, AllocationPolicy> { | 409 : private TemplateHashMapImpl<void*, void*, |
380 typedef TemplateHashMapImpl<void*, void*, MatchFun, AllocationPolicy> Base; | 410 HashEqualityThenKeyMatcher<void*, MatchFun>, |
| 411 AllocationPolicy> { |
| 412 typedef TemplateHashMapImpl<void*, void*, |
| 413 HashEqualityThenKeyMatcher<void*, MatchFun>, |
| 414 AllocationPolicy> |
| 415 Base; |
381 | 416 |
382 public: | 417 public: |
383 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT | 418 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT |
384 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT | 419 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT |
385 struct value_type { | 420 struct value_type { |
386 Key* first; | 421 Key* first; |
387 Value* second; | 422 Value* second; |
388 }; | 423 }; |
389 | 424 |
390 class Iterator { | 425 class Iterator { |
(...skipping 11 matching lines...) Expand all Loading... |
402 : map_(map), entry_(entry) {} | 437 : map_(map), entry_(entry) {} |
403 | 438 |
404 const Base* map_; | 439 const Base* map_; |
405 typename Base::Entry* entry_; | 440 typename Base::Entry* entry_; |
406 | 441 |
407 friend class TemplateHashMap; | 442 friend class TemplateHashMap; |
408 }; | 443 }; |
409 | 444 |
410 TemplateHashMap(MatchFun match, | 445 TemplateHashMap(MatchFun match, |
411 AllocationPolicy allocator = AllocationPolicy()) | 446 AllocationPolicy allocator = AllocationPolicy()) |
412 : Base(Base::kDefaultHashMapCapacity, match, allocator) {} | 447 : Base(Base::kDefaultHashMapCapacity, |
| 448 HashEqualityThenKeyMatcher<void*, MatchFun>(match), allocator) {} |
413 | 449 |
414 Iterator begin() const { return Iterator(this, this->Start()); } | 450 Iterator begin() const { return Iterator(this, this->Start()); } |
415 Iterator end() const { return Iterator(this, nullptr); } | 451 Iterator end() const { return Iterator(this, nullptr); } |
416 Iterator find(Key* key, bool insert = false, | 452 Iterator find(Key* key, bool insert = false, |
417 AllocationPolicy allocator = AllocationPolicy()) { | 453 AllocationPolicy allocator = AllocationPolicy()) { |
418 if (insert) { | 454 if (insert) { |
419 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); | 455 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); |
420 } | 456 } |
421 return Iterator(this, this->Lookup(key, key->Hash())); | 457 return Iterator(this, this->Lookup(key, key->Hash())); |
422 } | 458 } |
423 }; | 459 }; |
424 | 460 |
425 } // namespace base | 461 } // namespace base |
426 } // namespace v8 | 462 } // namespace v8 |
427 | 463 |
428 #endif // V8_BASE_HASHMAP_H_ | 464 #endif // V8_BASE_HASHMAP_H_ |
OLD | NEW |