Line data Source code
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:
23 6564915 : V8_INLINE void* New(size_t size) { return malloc(size); }
24 6553389 : 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 : 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 2565534 : map_ = nullptr;
82 2565534 : occupancy_ = 0;
83 2565534 : 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 49034 : Initialize(capacity_, allocator);
107 49034 : 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 9364598 : 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>::
133 : TemplateHashMapImpl(uint32_t initial_capacity, MatchFun match,
134 : AllocationPolicy allocator)
135 1466388 : : match_(match) {
136 21974598 : Initialize(initial_capacity, allocator);
137 : }
138 :
139 : template <typename Key, typename Value, typename MatchFun,
140 : class AllocationPolicy>
141 3459562 : 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 3459562 : match_(original->match_) {
148 6919124 : map_ = reinterpret_cast<Entry*>(allocator.New(capacity_ * sizeof(Entry)));
149 3459562 : memcpy(map_, original->map_, capacity_ * sizeof(Entry));
150 3459562 : }
151 :
152 : template <typename Key, typename Value, typename MatchFun,
153 : class AllocationPolicy>
154 : TemplateHashMapImpl<Key, Value, MatchFun,
155 : AllocationPolicy>::~TemplateHashMapImpl() {
156 3300687 : AllocationPolicy::Delete(map_);
157 7295318 : }
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 66871 : Entry* entry = Probe(key, hash);
165 433378720 : 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 164241495 : 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 415929778 : 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 96877176 : Entry* entry = Probe(key, hash);
185 415934590 : if (entry->exists()) {
186 : return entry;
187 : }
188 :
189 213290741 : 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 8785757 : TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::InsertNew(
196 : const Key& key, uint32_t hash, AllocationPolicy allocator) {
197 8785757 : Entry* entry = Probe(key, hash);
198 8785758 : return FillEmptyEntry(entry, key, Value(), hash, allocator);
199 : }
200 :
201 : template <typename Key, typename Value, typename MatchFun,
202 : class AllocationPolicy>
203 317219 : 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 317219 : if (!p->exists()) {
208 : // Key not found nothing to remove.
209 : return nullptr;
210 : }
211 :
212 56771 : 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 201721 : q = q + 1;
234 201721 : 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 201721 : if (!q->exists()) {
242 : break;
243 : }
244 :
245 : // Find the initial position for the entry at position q.
246 144950 : 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 144950 : if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) {
252 65653 : *p = *q;
253 : p = q;
254 : }
255 : }
256 :
257 : // Clear the entry which is allowed to en emptied.
258 : p->clear();
259 56771 : occupancy_--;
260 56771 : 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 1728743729 : for (size_t i = 0; i < capacity_; ++i) {
268 850428899 : map_[i].clear();
269 : }
270 27885931 : 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 495715 : 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 26510301 : for (entry++; entry < end; entry++) {
288 23743626 : 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 294865917 : TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe(
299 : const Key& key, uint32_t hash) const {
300 : DCHECK(base::bits::IsPowerOfTwo(capacity_));
301 1118400096 : size_t i = hash & (capacity_ - 1);
302 : DCHECK(i < capacity_);
303 :
304 : DCHECK(occupancy_ < capacity_); // Guarantees loop termination.
305 4084186261 : while (map_[i].exists() && !match_(hash, map_[i].hash, key, map_[i].key)) {
306 2204084838 : i = (i + 1) & (capacity_ - 1);
307 : }
308 :
309 294866290 : 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 476664475 : 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 476664475 : new (entry) Entry(key, value, hash);
321 476664475 : occupancy_++;
322 :
323 : // Grow the map if we reached >= 80% occupancy.
324 476664475 : if (occupancy_ + occupancy_ / 4 >= capacity_) {
325 5398228 : Resize(allocator);
326 3320544 : entry = Probe(key, hash);
327 : }
328 :
329 476664490 : return entry;
330 : }
331 :
332 : template <typename Key, typename Value, typename MatchFun,
333 : class AllocationPolicy>
334 27421726 : void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Initialize(
335 : uint32_t capacity, AllocationPolicy allocator) {
336 : DCHECK(base::bits::IsPowerOfTwo(capacity));
337 54843535 : map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry)));
338 27421809 : if (map_ == nullptr) {
339 0 : FATAL("Out of memory: HashMap::Initialize");
340 : return;
341 : }
342 27421809 : capacity_ = capacity;
343 : Clear();
344 27421809 : }
345 :
346 : template <typename Key, typename Value, typename MatchFun,
347 : class AllocationPolicy>
348 5398194 : void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Resize(
349 : AllocationPolicy allocator) {
350 5398194 : Entry* map = map_;
351 5398194 : uint32_t n = occupancy_;
352 :
353 : // Allocate larger map.
354 5398194 : Initialize(capacity_ * 2, allocator);
355 :
356 : // Rehash all current entries.
357 631544498 : for (Entry* entry = map; n > 0; entry++) {
358 313073182 : if (entry->exists()) {
359 254593308 : Entry* new_entry = Probe(entry->key, entry->hash);
360 254593148 : new_entry = FillEmptyEntry(new_entry, entry->key, entry->value,
361 : entry->hash, allocator);
362 254593186 : n--;
363 : }
364 : }
365 :
366 : // Delete old map.
367 : AllocationPolicy::Delete(map);
368 5398256 : }
369 :
370 : // Match function which compares hashes before executing a (potentially
371 : // expensive) key comparison.
372 : template <typename Key, typename MatchFun>
373 : struct 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 411706267 : 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 4245950 : class 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 668329 : allocator) {}
404 :
405 : CustomMatcherTemplateHashMapImpl(
406 : const CustomMatcherTemplateHashMapImpl<AllocationPolicy>* original,
407 : AllocationPolicy allocator = AllocationPolicy())
408 2995455 : : Base(original, allocator) {}
409 :
410 : private:
411 : DISALLOW_COPY_AND_ASSIGN(CustomMatcherTemplateHashMapImpl);
412 : };
413 :
414 : using CustomMatcherHashMap =
415 : CustomMatcherTemplateHashMapImpl<DefaultAllocationPolicy>;
416 :
417 : // Match function which compares keys directly by equality.
418 : template <typename Key>
419 : struct 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.
427 : template <typename AllocationPolicy>
428 158625 : class 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 17229256 : : Base(capacity, KeyEqualityMatcher<void*>(), allocator) {}
438 : };
439 :
440 : using HashMap = PointerTemplateHashMapImpl<DefaultAllocationPolicy>;
441 :
442 : // A hash map for pointer keys and values with an STL-like interface.
443 : template <class Key, class Value, class MatchFun, class AllocationPolicy>
444 203285 : class 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 5776 : Iterator find(Key* key, bool insert = false,
488 : AllocationPolicy allocator = AllocationPolicy()) {
489 5776 : if (insert) {
490 11552 : return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator));
491 : }
492 0 : return Iterator(this, this->Lookup(key, key->Hash()));
493 : }
494 : };
495 :
496 : } // namespace base
497 : } // namespace v8
498 :
499 : #endif // V8_BASE_HASHMAP_H_
|
