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 5963287 : V8_INLINE void* New(size_t size) { return malloc(size); }
24 5951846 : 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.
79 : void Invalidate() {
80 : AllocationPolicy::Delete(map_);
81 2454777 : map_ = nullptr;
82 2454777 : occupancy_ = 0;
83 2454777 : 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 42917 : Initialize(capacity_, allocator);
107 42917 : 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 9145972 : 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 1444624 : : match_(match) {
136 21623264 : Initialize(initial_capacity, allocator);
137 : }
138 :
139 : template <typename Key, typename Value, typename MatchFun,
140 : class AllocationPolicy>
141 3412108 : 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 3412108 : match_(original->match_) {
148 6824217 : map_ = reinterpret_cast<Entry*>(allocator.New(capacity_ * sizeof(Entry)));
149 3412109 : memcpy(map_, original->map_, capacity_ * sizeof(Entry));
150 3412109 : }
151 :
152 : template <typename Key, typename Value, typename MatchFun,
153 : class AllocationPolicy>
154 : TemplateHashMapImpl<Key, Value, MatchFun,
155 : AllocationPolicy>::~TemplateHashMapImpl() {
156 3262222 : 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 175888523 : TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Lookup(
163 175888523 : const Key& key, uint32_t hash) const {
164 55123 : Entry* entry = Probe(key, hash);
165 400359040 : 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 172131101 : 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 420657531 : TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
181 : const Key& key, uint32_t hash, const Func& value_func,
182 305712020 : AllocationPolicy allocator) {
183 : // Find a matching entry.
184 102805646 : Entry* entry = Probe(key, hash);
185 420661538 : if (entry->exists()) {
186 : return entry;
187 : }
188 :
189 217271289 : 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 8566281 : TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::InsertNew(
196 : const Key& key, uint32_t hash, AllocationPolicy allocator) {
197 8566281 : Entry* entry = Probe(key, hash);
198 8566295 : return FillEmptyEntry(entry, key, Value(), hash, allocator);
199 : }
200 :
201 : template <typename Key, typename Value, typename MatchFun,
202 : class AllocationPolicy>
203 376357 : Value TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Remove(
204 540175 : const Key& key, uint32_t hash) {
205 : // Lookup the entry for the key to remove.
206 : Entry* p = Probe(key, hash);
207 376357 : if (!p->exists()) {
208 : // Key not found nothing to remove.
209 : return nullptr;
210 : }
211 :
212 57538 : 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 163818 : Entry* q = p; // Start at the entry to remove.
231 : while (true) {
232 : // Move q to the next entry.
233 163818 : q = q + 1;
234 163818 : 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 163818 : if (!q->exists()) {
242 : break;
243 : }
244 :
245 : // Find the initial position for the entry at position q.
246 106280 : 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 106280 : if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) {
252 52481 : *p = *q;
253 : p = q;
254 : }
255 : }
256 :
257 : // Clear the entry which is allowed to en emptied.
258 : p->clear();
259 57538 : occupancy_--;
260 57538 : 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 797760607 : for (size_t i = 0; i < capacity_; ++i) {
268 797760607 : map_[i].clear();
269 : }
270 27327273 : 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 447794 : 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 32490198 : Entry* entry) const {
285 : const Entry* end = map_end();
286 : DCHECK(map_ - 1 <= entry && entry < end);
287 23439331 : for (entry++; entry < end; entry++) {
288 23508044 : 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 276853686 : TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe(
299 1179885473 : const Key& key, uint32_t hash) const {
300 : DCHECK(base::bits::IsPowerOfTwo(capacity_));
301 1068819130 : size_t i = hash & (capacity_ - 1);
302 : DCHECK(i < capacity_);
303 :
304 : DCHECK(occupancy_ < capacity_); // Guarantees loop termination.
305 4978478448 : while (map_[i].exists() && !match_(hash, map_[i].hash, key, map_[i].key)) {
306 2027936758 : i = (i + 1) & (capacity_ - 1);
307 : }
308 :
309 276851926 : 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 459493342 : TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::FillEmptyEntry(
316 : Entry* entry, const Key& key, const Value& value, uint32_t hash,
317 2316340 : AllocationPolicy allocator) {
318 : DCHECK(!entry->exists());
319 :
320 459493342 : new (entry) Entry(key, value, hash);
321 459493342 : occupancy_++;
322 :
323 : // Grow the map if we reached >= 80% occupancy.
324 459493342 : if (occupancy_ + occupancy_ / 4 >= capacity_) {
325 5204139 : Resize(allocator);
326 2756157 : entry = Probe(key, hash);
327 : }
328 :
329 459493412 : return entry;
330 : }
331 :
332 : template <typename Key, typename Value, typename MatchFun,
333 : class AllocationPolicy>
334 26869527 : void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Initialize(
335 : uint32_t capacity, AllocationPolicy allocator) {
336 : DCHECK(base::bits::IsPowerOfTwo(capacity));
337 53740637 : map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry)));
338 26871110 : if (map_ == nullptr) {
339 0 : FATAL("Out of memory: HashMap::Initialize");
340 : return;
341 : }
342 26871110 : capacity_ = capacity;
343 : Clear();
344 26871110 : }
345 :
346 : template <typename Key, typename Value, typename MatchFun,
347 : class AllocationPolicy>
348 5203795 : void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Resize(
349 53565561 : AllocationPolicy allocator) {
350 5203795 : Entry* map = map_;
351 5203795 : uint32_t n = occupancy_;
352 :
353 : // Allocate larger map.
354 5203795 : Initialize(capacity_ * 2, allocator);
355 :
356 : // Rehash all current entries.
357 475691500 : for (Entry* entry = map; n > 0; entry++) {
358 283041602 : if (entry->exists()) {
359 233671629 : Entry* new_entry = Probe(entry->key, entry->hash);
360 233670382 : new_entry = FillEmptyEntry(new_entry, entry->key, entry->value,
361 233670382 : entry->hash, allocator);
362 233671524 : n--;
363 : }
364 : }
365 :
366 : // Delete old map.
367 : AllocationPolicy::Delete(map);
368 5204251 : }
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 424718273 : 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())
403 : : Base(capacity, HashEqualityThenKeyMatcher<void*, MatchFun>(match),
404 662069 : allocator) {}
405 :
406 : CustomMatcherTemplateHashMapImpl(
407 : const CustomMatcherTemplateHashMapImpl<AllocationPolicy>* original,
408 : AllocationPolicy allocator = AllocationPolicy())
409 2955957 : : 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 {
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>
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())
439 16921512 : : 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:
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 5340 : Iterator find(Key* key, bool insert = false,
491 : AllocationPolicy allocator = AllocationPolicy()) {
492 5340 : if (insert) {
493 10681 : return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator));
494 : }
495 0 : return Iterator(this, this->Lookup(key, key->Hash()));
496 : }
497 : };
498 :
499 : } // namespace base
500 : } // namespace v8
501 :
502 : #endif // V8_BASE_HASHMAP_H_
|
