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 using Entry = TemplateHashMapEntry<Key, Value>;
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.
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};
130template <typename Key, typename Value, typename MatchFun,
131 class AllocationPolicy>
132TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::
133 TemplateHashMapImpl(uint32_t initial_capacity, MatchFun match,
134 AllocationPolicy allocator)
135 : match_(match) {
136 Initialize(initial_capacity, allocator);
137}
138
139template <typename Key, typename Value, typename MatchFun,
140 class AllocationPolicy>
141TemplateHashMapImpl<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
152template <typename Key, typename Value, typename MatchFun,
153 class AllocationPolicy>
154TemplateHashMapImpl<Key, Value, MatchFun,
155 AllocationPolicy>::~TemplateHashMapImpl() {
156 AllocationPolicy::Delete(map_);
157}
158
159template <typename Key, typename Value, typename MatchFun,
160 class AllocationPolicy>
161typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
162TemplateHashMapImpl<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
168template <typename Key, typename Value, typename MatchFun,
169 class AllocationPolicy>
170typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
171TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
172 const Key& key, uint32_t hash, AllocationPolicy allocator) {
173 return LookupOrInsert(key, hash, []() { return Value(); }, allocator);
174}
175
176template <typename Key, typename Value, typename MatchFun,
177 class AllocationPolicy>
178template <typename Func>
179typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
180TemplateHashMapImpl<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
192template <typename Key, typename Value, typename MatchFun,
193 class AllocationPolicy>
194typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
195TemplateHashMapImpl<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
201template <typename Key, typename Value, typename MatchFun,
202 class AllocationPolicy>
203Value 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
263template <typename Key, typename Value, typename MatchFun,
264 class AllocationPolicy>
265void 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
273template <typename Key, typename Value, typename MatchFun,
274 class AllocationPolicy>
275typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
276TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Start() const {
277 return Next(map_ - 1);
278}
279
280template <typename Key, typename Value, typename MatchFun,
281 class AllocationPolicy>
282typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
283TemplateHashMapImpl<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
295template <typename Key, typename Value, typename MatchFun,
296 class AllocationPolicy>
297typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
298TemplateHashMapImpl<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
312template <typename Key, typename Value, typename MatchFun,
313 class AllocationPolicy>
314typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
315TemplateHashMapImpl<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
332template <typename Key, typename Value, typename MatchFun,
333 class AllocationPolicy>
334void 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
346template <typename Key, typename Value, typename MatchFun,
347 class AllocationPolicy>
348void 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.
372template <typename Key, typename MatchFun>
373struct HashEqualityThenKeyMatcher {
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.
386template <typename AllocationPolicy>
387class CustomMatcherTemplateHashMapImpl
388 : public TemplateHashMapImpl<
389 void*, void*,
390 HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>,
391 AllocationPolicy> {
392 using Base = TemplateHashMapImpl<
393 void*, void*, HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>,
394 AllocationPolicy>;
395
396 public:
397 using MatchFun = bool (*)(void*, void*);
398
399 CustomMatcherTemplateHashMapImpl(
400 MatchFun match, uint32_t capacity = Base::kDefaultHashMapCapacity,
401 AllocationPolicy allocator = AllocationPolicy())
402 : Base(capacity, HashEqualityThenKeyMatcher<void*, MatchFun>(match),
403 allocator) {}
404
405 CustomMatcherTemplateHashMapImpl(
406 const CustomMatcherTemplateHashMapImpl<AllocationPolicy>* original,
407 AllocationPolicy allocator = AllocationPolicy())
408 : Base(original, allocator) {}
409
410 private:
411 DISALLOW_COPY_AND_ASSIGN(CustomMatcherTemplateHashMapImpl);
412};
413
414using CustomMatcherHashMap =
415 CustomMatcherTemplateHashMapImpl<DefaultAllocationPolicy>;
416
417// Match function which compares keys directly by equality.
418template <typename Key>
419struct KeyEqualityMatcher {
420 bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1,
421 const Key& key2) const {
422 return key1 == key2;
423 }
424};
425
426// Hashmap<void*, void*> which compares the key pointers directly.
427template <typename AllocationPolicy>
428class PointerTemplateHashMapImpl
429 : public TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>,
430 AllocationPolicy> {
431 using Base = TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>,
432 AllocationPolicy>;
433
434 public:
435 PointerTemplateHashMapImpl(uint32_t capacity = Base::kDefaultHashMapCapacity,
436 AllocationPolicy allocator = AllocationPolicy())
437 : Base(capacity, KeyEqualityMatcher<void*>(), allocator) {}
438};
439
440using HashMap = PointerTemplateHashMapImpl<DefaultAllocationPolicy>;
441
442// A hash map for pointer keys and values with an STL-like interface.
443template <class Key, class Value, class MatchFun, class AllocationPolicy>
444class TemplateHashMap
445 : private TemplateHashMapImpl<void*, void*,
446 HashEqualityThenKeyMatcher<void*, MatchFun>,
447 AllocationPolicy> {
448 using Base = TemplateHashMapImpl<void*, void*,
449 HashEqualityThenKeyMatcher<void*, MatchFun>,
450 AllocationPolicy>;
451
452 public:
453 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT
454 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT
455 struct value_type {
456 Key* first;
457 Value* second;
458 };
459
460 class Iterator {
461 public:
462 Iterator& operator++() {
463 entry_ = map_->Next(entry_);
464 return *this;
465 }
466
467 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); }
468 bool operator!=(const Iterator& other) { return entry_ != other.entry_; }
469
470 private:
471 Iterator(const Base* map, typename Base::Entry* entry)
472 : map_(map), entry_(entry) {}
473
474 const Base* map_;
475 typename Base::Entry* entry_;
476
477 friend class TemplateHashMap;
478 };
479
480 TemplateHashMap(MatchFun match,
481 AllocationPolicy allocator = AllocationPolicy())
482 : Base(Base::kDefaultHashMapCapacity,
483 HashEqualityThenKeyMatcher<void*, MatchFun>(match), allocator) {}
484
485 Iterator begin() const { return Iterator(this, this->Start()); }
486 Iterator end() const { return Iterator(this, nullptr); }
487 Iterator find(Key* key, bool insert = false,
488 AllocationPolicy allocator = AllocationPolicy()) {
489 if (insert) {
490 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator));
491 }
492 return Iterator(this, this->Lookup(key, key->Hash()));
493 }
494};
495
496} // namespace base
497} // namespace v8
498
499#endif // V8_BASE_HASHMAP_H_
500