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