• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
3 // found in the LICENSE file.
4 
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
7 // deadlock when we are using async signal handler.
8 
9 #ifndef V8_BASE_HASHMAP_H_
10 #define V8_BASE_HASHMAP_H_
11 
12 #include <stdlib.h>
13 
14 #include "src/base/bits.h"
15 #include "src/base/hashmap-entry.h"
16 #include "src/base/logging.h"
17 
18 namespace v8 {
19 namespace base {
20 
21 class DefaultAllocationPolicy {
22  public:
New(size_t size)23   V8_INLINE void* New(size_t size) { return malloc(size); }
Delete(void * p)24   V8_INLINE static void Delete(void* p) { free(p); }
25 };
26 
27 template <typename Key, typename Value, class MatchFun, class AllocationPolicy>
28 class TemplateHashMapImpl {
29  public:
30   typedef TemplateHashMapEntry<Key, Value> Entry;
31 
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
34   // default value of capacity specified by the implementation.
35   static const uint32_t kDefaultHashMapCapacity = 8;
36 
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).
39   TemplateHashMapImpl(uint32_t capacity = kDefaultHashMapCapacity,
40                       MatchFun match = MatchFun(),
41                       AllocationPolicy allocator = AllocationPolicy());
42 
43   // Clones the given hashmap and creates a copy with the same entries.
44   TemplateHashMapImpl(const TemplateHashMapImpl<Key, Value, MatchFun,
45                                                 AllocationPolicy>* original,
46                       AllocationPolicy allocator = AllocationPolicy());
47 
48   ~TemplateHashMapImpl();
49 
50   // If an entry with matching key is found, returns that entry.
51   // Otherwise, nullptr is returned.
52   Entry* Lookup(const Key& key, uint32_t hash) const;
53 
54   // If an entry with matching key is found, returns that entry.
55   // If no matching entry is found, a new entry is inserted with
56   // corresponding key, key hash, and default initialized value.
57   Entry* LookupOrInsert(const Key& key, uint32_t hash,
58                         AllocationPolicy allocator = AllocationPolicy());
59 
60   // If an entry with matching key is found, returns that entry.
61   // If no matching entry is found, a new entry is inserted with
62   // corresponding key, key hash, and value created by func.
63   template <typename Func>
64   Entry* LookupOrInsert(const Key& key, uint32_t hash, const Func& value_func,
65                         AllocationPolicy allocator = AllocationPolicy());
66 
67   Entry* InsertNew(const Key& key, uint32_t hash,
68                    AllocationPolicy allocator = AllocationPolicy());
69 
70   // Removes the entry with matching key.
71   // It returns the value of the deleted entry
72   // or null if there is no value for such key.
73   Value Remove(const Key& key, uint32_t hash);
74 
75   // Empties the hash map (occupancy() == 0).
76   void Clear();
77 
78   // Empties the map and makes it unusable for allocation.
Invalidate()79   void Invalidate() {
80     AllocationPolicy::Delete(map_);
81     map_ = nullptr;
82     occupancy_ = 0;
83     capacity_ = 0;
84   }
85 
86   // The number of (non-empty) entries in the table.
occupancy()87   uint32_t occupancy() const { return occupancy_; }
88 
89   // The capacity of the table. The implementation
90   // makes sure that occupancy is at most 80% of
91   // the table capacity.
capacity()92   uint32_t capacity() const { return capacity_; }
93 
94   // Iteration
95   //
96   // for (Entry* p = map.Start(); p != nullptr; p = map.Next(p)) {
97   //   ...
98   // }
99   //
100   // If entries are inserted during iteration, the effect of
101   // calling Next() is undefined.
102   Entry* Start() const;
103   Entry* Next(Entry* entry) const;
104 
Reset(AllocationPolicy allocator)105   void Reset(AllocationPolicy allocator) {
106     Initialize(capacity_, allocator);
107     occupancy_ = 0;
108   }
109 
110  protected:
111   void Initialize(uint32_t capacity, AllocationPolicy allocator);
112 
113  private:
114   Entry* map_;
115   uint32_t capacity_;
116   uint32_t occupancy_;
117   // TODO(leszeks): This takes up space even if it has no state, maybe replace
118   // with something that does the empty base optimisation e.g. std::tuple
119   MatchFun match_;
120 
map_end()121   Entry* map_end() const { return map_ + capacity_; }
122   Entry* Probe(const Key& key, uint32_t hash) const;
123   Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value,
124                         uint32_t hash,
125                         AllocationPolicy allocator = AllocationPolicy());
126   void Resize(AllocationPolicy allocator);
127 
128   DISALLOW_COPY_AND_ASSIGN(TemplateHashMapImpl);
129 };
130 template <typename Key, typename Value, typename MatchFun,
131           class AllocationPolicy>
132 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::
TemplateHashMapImpl(uint32_t initial_capacity,MatchFun match,AllocationPolicy allocator)133     TemplateHashMapImpl(uint32_t initial_capacity, MatchFun match,
134                         AllocationPolicy allocator)
135     : match_(match) {
136   Initialize(initial_capacity, allocator);
137 }
138 
139 template <typename Key, typename Value, typename MatchFun,
140           class AllocationPolicy>
141 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::
TemplateHashMapImpl(const TemplateHashMapImpl<Key,Value,MatchFun,AllocationPolicy> * original,AllocationPolicy allocator)142     TemplateHashMapImpl(const TemplateHashMapImpl<Key, Value, MatchFun,
143                                                   AllocationPolicy>* original,
144                         AllocationPolicy allocator)
145     : capacity_(original->capacity_),
146       occupancy_(original->occupancy_),
147       match_(original->match_) {
148   map_ = reinterpret_cast<Entry*>(allocator.New(capacity_ * sizeof(Entry)));
149   memcpy(map_, original->map_, capacity_ * sizeof(Entry));
150 }
151 
152 template <typename Key, typename Value, typename MatchFun,
153           class AllocationPolicy>
154 TemplateHashMapImpl<Key, Value, MatchFun,
~TemplateHashMapImpl()155                     AllocationPolicy>::~TemplateHashMapImpl() {
156   AllocationPolicy::Delete(map_);
157 }
158 
159 template <typename Key, typename Value, typename MatchFun,
160           class AllocationPolicy>
161 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
Lookup(const Key & key,uint32_t hash)162 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Lookup(
163     const Key& key, uint32_t hash) const {
164   Entry* entry = Probe(key, hash);
165   return entry->exists() ? entry : nullptr;
166 }
167 
168 template <typename Key, typename Value, typename MatchFun,
169           class AllocationPolicy>
170 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
LookupOrInsert(const Key & key,uint32_t hash,AllocationPolicy allocator)171 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
172     const Key& key, uint32_t hash, AllocationPolicy allocator) {
173   return LookupOrInsert(key, hash, []() { return Value(); }, allocator);
174 }
175 
176 template <typename Key, typename Value, typename MatchFun,
177           class AllocationPolicy>
178 template <typename Func>
179 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
LookupOrInsert(const Key & key,uint32_t hash,const Func & value_func,AllocationPolicy allocator)180 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
181     const Key& key, uint32_t hash, const Func& value_func,
182     AllocationPolicy allocator) {
183   // Find a matching entry.
184   Entry* entry = Probe(key, hash);
185   if (entry->exists()) {
186     return entry;
187   }
188 
189   return FillEmptyEntry(entry, key, value_func(), hash, allocator);
190 }
191 
192 template <typename Key, typename Value, typename MatchFun,
193           class AllocationPolicy>
194 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
InsertNew(const Key & key,uint32_t hash,AllocationPolicy allocator)195 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::InsertNew(
196     const Key& key, uint32_t hash, AllocationPolicy allocator) {
197   Entry* entry = Probe(key, hash);
198   return FillEmptyEntry(entry, key, Value(), hash, allocator);
199 }
200 
201 template <typename Key, typename Value, typename MatchFun,
202           class AllocationPolicy>
Remove(const Key & key,uint32_t hash)203 Value TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Remove(
204     const Key& key, uint32_t hash) {
205   // Lookup the entry for the key to remove.
206   Entry* p = Probe(key, hash);
207   if (!p->exists()) {
208     // Key not found nothing to remove.
209     return nullptr;
210   }
211 
212   Value value = p->value;
213   // To remove an entry we need to ensure that it does not create an empty
214   // entry that will cause the search for another entry to stop too soon. If all
215   // the entries between the entry to remove and the next empty slot have their
216   // initial position inside this interval, clearing the entry to remove will
217   // not break the search. If, while searching for the next empty entry, an
218   // entry is encountered which does not have its initial position between the
219   // entry to remove and the position looked at, then this entry can be moved to
220   // the place of the entry to remove without breaking the search for it. The
221   // entry made vacant by this move is now the entry to remove and the process
222   // starts over.
223   // Algorithm from http://en.wikipedia.org/wiki/Open_addressing.
224 
225   // This guarantees loop termination as there is at least one empty entry so
226   // eventually the removed entry will have an empty entry after it.
227   DCHECK(occupancy_ < capacity_);
228 
229   // p is the candidate entry to clear. q is used to scan forwards.
230   Entry* q = p;  // Start at the entry to remove.
231   while (true) {
232     // Move q to the next entry.
233     q = q + 1;
234     if (q == map_end()) {
235       q = map_;
236     }
237 
238     // All entries between p and q have their initial position between p and q
239     // and the entry p can be cleared without breaking the search for these
240     // entries.
241     if (!q->exists()) {
242       break;
243     }
244 
245     // Find the initial position for the entry at position q.
246     Entry* r = map_ + (q->hash & (capacity_ - 1));
247 
248     // If the entry at position q has its initial position outside the range
249     // between p and q it can be moved forward to position p and will still be
250     // found. There is now a new candidate entry for clearing.
251     if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) {
252       *p = *q;
253       p = q;
254     }
255   }
256 
257   // Clear the entry which is allowed to en emptied.
258   p->clear();
259   occupancy_--;
260   return value;
261 }
262 
263 template <typename Key, typename Value, typename MatchFun,
264           class AllocationPolicy>
Clear()265 void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Clear() {
266   // Mark all entries as empty.
267   for (size_t i = 0; i < capacity_; ++i) {
268     map_[i].clear();
269   }
270   occupancy_ = 0;
271 }
272 
273 template <typename Key, typename Value, typename MatchFun,
274           class AllocationPolicy>
275 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
Start()276 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Start() const {
277   return Next(map_ - 1);
278 }
279 
280 template <typename Key, typename Value, typename MatchFun,
281           class AllocationPolicy>
282 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
Next(Entry * entry)283 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Next(
284     Entry* entry) const {
285   const Entry* end = map_end();
286   DCHECK(map_ - 1 <= entry && entry < end);
287   for (entry++; entry < end; entry++) {
288     if (entry->exists()) {
289       return entry;
290     }
291   }
292   return nullptr;
293 }
294 
295 template <typename Key, typename Value, typename MatchFun,
296           class AllocationPolicy>
297 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
Probe(const Key & key,uint32_t hash)298 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe(
299     const Key& key, uint32_t hash) const {
300   DCHECK(base::bits::IsPowerOfTwo32(capacity_));
301   size_t i = hash & (capacity_ - 1);
302   DCHECK(i < capacity_);
303 
304   DCHECK(occupancy_ < capacity_);  // Guarantees loop termination.
305   while (map_[i].exists() && !match_(hash, map_[i].hash, key, map_[i].key)) {
306     i = (i + 1) & (capacity_ - 1);
307   }
308 
309   return &map_[i];
310 }
311 
312 template <typename Key, typename Value, typename MatchFun,
313           class AllocationPolicy>
314 typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
FillEmptyEntry(Entry * entry,const Key & key,const Value & value,uint32_t hash,AllocationPolicy allocator)315 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::FillEmptyEntry(
316     Entry* entry, const Key& key, const Value& value, uint32_t hash,
317     AllocationPolicy allocator) {
318   DCHECK(!entry->exists());
319 
320   new (entry) Entry(key, value, hash);
321   occupancy_++;
322 
323   // Grow the map if we reached >= 80% occupancy.
324   if (occupancy_ + occupancy_ / 4 >= capacity_) {
325     Resize(allocator);
326     entry = Probe(key, hash);
327   }
328 
329   return entry;
330 }
331 
332 template <typename Key, typename Value, typename MatchFun,
333           class AllocationPolicy>
Initialize(uint32_t capacity,AllocationPolicy allocator)334 void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Initialize(
335     uint32_t capacity, AllocationPolicy allocator) {
336   DCHECK(base::bits::IsPowerOfTwo32(capacity));
337   map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry)));
338   if (map_ == nullptr) {
339     FATAL("Out of memory: HashMap::Initialize");
340     return;
341   }
342   capacity_ = capacity;
343   Clear();
344 }
345 
346 template <typename Key, typename Value, typename MatchFun,
347           class AllocationPolicy>
Resize(AllocationPolicy allocator)348 void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Resize(
349     AllocationPolicy allocator) {
350   Entry* map = map_;
351   uint32_t n = occupancy_;
352 
353   // Allocate larger map.
354   Initialize(capacity_ * 2, allocator);
355 
356   // Rehash all current entries.
357   for (Entry* entry = map; n > 0; entry++) {
358     if (entry->exists()) {
359       Entry* new_entry = Probe(entry->key, entry->hash);
360       new_entry = FillEmptyEntry(new_entry, entry->key, entry->value,
361                                  entry->hash, allocator);
362       n--;
363     }
364   }
365 
366   // Delete old map.
367   AllocationPolicy::Delete(map);
368 }
369 
370 // Match function which compares hashes before executing a (potentially
371 // expensive) key comparison.
372 template <typename Key, typename MatchFun>
373 struct HashEqualityThenKeyMatcher {
HashEqualityThenKeyMatcherHashEqualityThenKeyMatcher374   explicit HashEqualityThenKeyMatcher(MatchFun match) : match_(match) {}
375 
operatorHashEqualityThenKeyMatcher376   bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1,
377                   const Key& key2) const {
378     return hash1 == hash2 && match_(key1, key2);
379   }
380 
381  private:
382   MatchFun match_;
383 };
384 
385 // Hashmap<void*, void*> which takes a custom key comparison function pointer.
386 template <typename AllocationPolicy>
387 class CustomMatcherTemplateHashMapImpl
388     : public TemplateHashMapImpl<
389           void*, void*,
390           HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>,
391           AllocationPolicy> {
392   typedef TemplateHashMapImpl<
393       void*, void*, HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>,
394       AllocationPolicy>
395       Base;
396 
397  public:
398   typedef bool (*MatchFun)(void*, void*);
399 
400   CustomMatcherTemplateHashMapImpl(
401       MatchFun match, uint32_t capacity = Base::kDefaultHashMapCapacity,
402       AllocationPolicy allocator = AllocationPolicy())
Base(capacity,HashEqualityThenKeyMatcher<void *,MatchFun> (match),allocator)403       : Base(capacity, HashEqualityThenKeyMatcher<void*, MatchFun>(match),
404              allocator) {}
405 
406   CustomMatcherTemplateHashMapImpl(
407       const CustomMatcherTemplateHashMapImpl<AllocationPolicy>* original,
408       AllocationPolicy allocator = AllocationPolicy())
Base(original,allocator)409       : Base(original, allocator) {}
410 
411  private:
412   DISALLOW_COPY_AND_ASSIGN(CustomMatcherTemplateHashMapImpl);
413 };
414 
415 typedef CustomMatcherTemplateHashMapImpl<DefaultAllocationPolicy>
416     CustomMatcherHashMap;
417 
418 // Match function which compares keys directly by equality.
419 template <typename Key>
420 struct KeyEqualityMatcher {
operatorKeyEqualityMatcher421   bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1,
422                   const Key& key2) const {
423     return key1 == key2;
424   }
425 };
426 
427 // Hashmap<void*, void*> which compares the key pointers directly.
428 template <typename AllocationPolicy>
429 class PointerTemplateHashMapImpl
430     : public TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>,
431                                  AllocationPolicy> {
432   typedef TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>,
433                               AllocationPolicy>
434       Base;
435 
436  public:
437   PointerTemplateHashMapImpl(uint32_t capacity = Base::kDefaultHashMapCapacity,
438                              AllocationPolicy allocator = AllocationPolicy())
Base(capacity,KeyEqualityMatcher<void * > (),allocator)439       : Base(capacity, KeyEqualityMatcher<void*>(), allocator) {}
440 };
441 
442 typedef PointerTemplateHashMapImpl<DefaultAllocationPolicy> HashMap;
443 
444 // A hash map for pointer keys and values with an STL-like interface.
445 template <class Key, class Value, class MatchFun, class AllocationPolicy>
446 class TemplateHashMap
447     : private TemplateHashMapImpl<void*, void*,
448                                   HashEqualityThenKeyMatcher<void*, MatchFun>,
449                                   AllocationPolicy> {
450   typedef TemplateHashMapImpl<void*, void*,
451                               HashEqualityThenKeyMatcher<void*, MatchFun>,
452                               AllocationPolicy>
453       Base;
454 
455  public:
456   STATIC_ASSERT(sizeof(Key*) == sizeof(void*));    // NOLINT
457   STATIC_ASSERT(sizeof(Value*) == sizeof(void*));  // NOLINT
458   struct value_type {
459     Key* first;
460     Value* second;
461   };
462 
463   class Iterator {
464    public:
465     Iterator& operator++() {
466       entry_ = map_->Next(entry_);
467       return *this;
468     }
469 
470     value_type* operator->() { return reinterpret_cast<value_type*>(entry_); }
471     bool operator!=(const Iterator& other) { return entry_ != other.entry_; }
472 
473    private:
Iterator(const Base * map,typename Base::Entry * entry)474     Iterator(const Base* map, typename Base::Entry* entry)
475         : map_(map), entry_(entry) {}
476 
477     const Base* map_;
478     typename Base::Entry* entry_;
479 
480     friend class TemplateHashMap;
481   };
482 
483   TemplateHashMap(MatchFun match,
484                   AllocationPolicy allocator = AllocationPolicy())
Base(Base::kDefaultHashMapCapacity,HashEqualityThenKeyMatcher<void *,MatchFun> (match),allocator)485       : Base(Base::kDefaultHashMapCapacity,
486              HashEqualityThenKeyMatcher<void*, MatchFun>(match), allocator) {}
487 
begin()488   Iterator begin() const { return Iterator(this, this->Start()); }
end()489   Iterator end() const { return Iterator(this, nullptr); }
490   Iterator find(Key* key, bool insert = false,
491                 AllocationPolicy allocator = AllocationPolicy()) {
492     if (insert) {
493       return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator));
494     }
495     return Iterator(this, this->Lookup(key, key->Hash()));
496   }
497 };
498 
499 }  // namespace base
500 }  // namespace v8
501 
502 #endif  // V8_BASE_HASHMAP_H_
503