V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
hashmap.h
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 
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 
27 template <typename Key, typename Value, class MatchFun, class AllocationPolicy>
29  public:
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 
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.
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.
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.
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 
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 
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>
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>::
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,
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*
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*
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*
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*
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>
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>
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*
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*
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*
298 TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe(
299  const Key& key, uint32_t hash) const {
300  DCHECK(base::bits::IsPowerOfTwo(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*
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>
334 void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Initialize(
335  uint32_t capacity, AllocationPolicy allocator) {
336  DCHECK(base::bits::IsPowerOfTwo(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>
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>
374  explicit HashEqualityThenKeyMatcher(MatchFun match) : match_(match) {}
375 
376  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>
388  : public TemplateHashMapImpl<
389  void*, void*,
390  HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>,
391  AllocationPolicy> {
392  typedef TemplateHashMapImpl<
394  AllocationPolicy>
395  Base;
396 
397  public:
398  typedef bool (*MatchFun)(void*, void*);
399 
401  MatchFun match, uint32_t capacity = Base::kDefaultHashMapCapacity,
402  AllocationPolicy allocator = AllocationPolicy())
404  allocator) {}
405 
408  AllocationPolicy allocator = AllocationPolicy())
409  : Base(original, allocator) {}
410 
411  private:
412  DISALLOW_COPY_AND_ASSIGN(CustomMatcherTemplateHashMapImpl);
413 };
414 
416  CustomMatcherHashMap;
417 
418 // Match function which compares keys directly by equality.
419 template <typename Key>
421  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>
430  : public TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>,
431  AllocationPolicy> {
433  AllocationPolicy>
434  Base;
435 
436  public:
437  PointerTemplateHashMapImpl(uint32_t capacity = Base::kDefaultHashMapCapacity,
438  AllocationPolicy allocator = AllocationPolicy())
439  : Base(capacity, KeyEqualityMatcher<void*>(), allocator) {}
440 };
441 
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>
447  : private TemplateHashMapImpl<void*, void*,
448  HashEqualityThenKeyMatcher<void*, MatchFun>,
449  AllocationPolicy> {
450  typedef TemplateHashMapImpl<void*, void*,
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:
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())
485  : Base(Base::kDefaultHashMapCapacity,
486  HashEqualityThenKeyMatcher<void*, MatchFun>(match), allocator) {}
487 
488  Iterator begin() const { return Iterator(this, this->Start()); }
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_
Definition: v8.h:2119
Definition: libplatform.h:13