Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1371)

Side by Side Diff: src/base/hashmap.h

Issue 2369963002: [base] Remove PointersMatch, making a separate std::equals hashmap (Closed)
Patch Set: Created 4 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
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
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_
OLDNEW
« no previous file with comments | « src/ast/scopes.cc ('k') | src/bootstrapper.cc » ('j') | src/profiler/heap-snapshot-generator.cc » ('J')

Powered by Google App Engine
This is Rietveld 408576698