1/*
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012, 2015 Apple Inc. All rights reserved.
3 * Copyright (C) 2008 David Levin <levin@chromium.org>
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB. If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 *
20 */
21
22#pragma once
23
24#include <atomic>
25#include <iterator>
26#include <mutex>
27#include <string.h>
28#include <type_traits>
29#include <utility>
30#include <wtf/Assertions.h>
31#include <wtf/FastMalloc.h>
32#include <wtf/HashTraits.h>
33#include <wtf/Lock.h>
34#include <wtf/MathExtras.h>
35#include <wtf/RandomNumber.h>
36#include <wtf/StdLibExtras.h>
37#include <wtf/ValueCheck.h>
38
39#define DUMP_HASHTABLE_STATS 0
40#define DUMP_HASHTABLE_STATS_PER_TABLE 0
41
42#if DUMP_HASHTABLE_STATS_PER_TABLE
43#include <wtf/DataLog.h>
44#endif
45
46namespace WTF {
47
48// Enables internal WTF consistency checks that are invoked automatically. Non-WTF callers can call checkTableConsistency() even if internal checks are disabled.
49#define CHECK_HASHTABLE_CONSISTENCY 0
50
51#ifdef NDEBUG
52#define CHECK_HASHTABLE_ITERATORS 0
53#define CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 0
54#else
55#define CHECK_HASHTABLE_ITERATORS 1
56#define CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 1
57#endif
58
59#if DUMP_HASHTABLE_STATS
60
61 struct HashTableStats {
62 // The following variables are all atomically incremented when modified.
63 WTF_EXPORT_PRIVATE static std::atomic<unsigned> numAccesses;
64 WTF_EXPORT_PRIVATE static std::atomic<unsigned> numRehashes;
65 WTF_EXPORT_PRIVATE static std::atomic<unsigned> numRemoves;
66 WTF_EXPORT_PRIVATE static std::atomic<unsigned> numReinserts;
67
68 // The following variables are only modified in the recordCollisionAtCount method within a mutex.
69 WTF_EXPORT_PRIVATE static unsigned maxCollisions;
70 WTF_EXPORT_PRIVATE static unsigned numCollisions;
71 WTF_EXPORT_PRIVATE static unsigned collisionGraph[4096];
72
73 WTF_EXPORT_PRIVATE static void recordCollisionAtCount(unsigned count);
74 WTF_EXPORT_PRIVATE static void dumpStats();
75 };
76
77#endif
78
79 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
80 class HashTable;
81 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
82 class HashTableIterator;
83 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
84 class HashTableConstIterator;
85
86 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
87 void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
88 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
89
90 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
91 void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
92
93#if !CHECK_HASHTABLE_ITERATORS
94
95 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
96 inline void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
97 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
98
99 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
100 inline void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
101
102#endif
103
104 typedef enum { HashItemKnownGood } HashItemKnownGoodTag;
105
106 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
107 class HashTableConstIterator : public std::iterator<std::forward_iterator_tag, Value, std::ptrdiff_t, const Value*, const Value&> {
108 private:
109 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
110 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
111 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
112 typedef Value ValueType;
113 typedef const ValueType& ReferenceType;
114 typedef const ValueType* PointerType;
115
116 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
117 friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
118
119 void skipEmptyBuckets()
120 {
121 while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position))
122 ++m_position;
123 }
124
125 HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition)
126 : m_position(position), m_endPosition(endPosition)
127 {
128 addIterator(table, this);
129 skipEmptyBuckets();
130 }
131
132 HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition, HashItemKnownGoodTag)
133 : m_position(position), m_endPosition(endPosition)
134 {
135 addIterator(table, this);
136 }
137
138 public:
139 HashTableConstIterator()
140 {
141 addIterator(static_cast<const HashTableType*>(0), this);
142 }
143
144 // default copy, assignment and destructor are OK if CHECK_HASHTABLE_ITERATORS is 0
145
146#if CHECK_HASHTABLE_ITERATORS
147 ~HashTableConstIterator()
148 {
149 removeIterator(this);
150 }
151
152 HashTableConstIterator(const const_iterator& other)
153 : m_position(other.m_position), m_endPosition(other.m_endPosition)
154 {
155 addIterator(other.m_table, this);
156 }
157
158 const_iterator& operator=(const const_iterator& other)
159 {
160 m_position = other.m_position;
161 m_endPosition = other.m_endPosition;
162
163 removeIterator(this);
164 addIterator(other.m_table, this);
165
166 return *this;
167 }
168#endif
169
170 PointerType get() const
171 {
172 checkValidity();
173 return m_position;
174 }
175 ReferenceType operator*() const { return *get(); }
176 PointerType operator->() const { return get(); }
177
178 const_iterator& operator++()
179 {
180 checkValidity();
181 ASSERT(m_position != m_endPosition);
182 ++m_position;
183 skipEmptyBuckets();
184 return *this;
185 }
186
187 // postfix ++ intentionally omitted
188
189 // Comparison.
190 bool operator==(const const_iterator& other) const
191 {
192 checkValidity(other);
193 return m_position == other.m_position;
194 }
195 bool operator!=(const const_iterator& other) const
196 {
197 checkValidity(other);
198 return m_position != other.m_position;
199 }
200 bool operator==(const iterator& other) const
201 {
202 return *this == static_cast<const_iterator>(other);
203 }
204 bool operator!=(const iterator& other) const
205 {
206 return *this != static_cast<const_iterator>(other);
207 }
208
209 private:
210 void checkValidity() const
211 {
212#if CHECK_HASHTABLE_ITERATORS
213 ASSERT(m_table);
214#endif
215 }
216
217
218#if CHECK_HASHTABLE_ITERATORS
219 void checkValidity(const const_iterator& other) const
220 {
221 ASSERT(m_table);
222 ASSERT_UNUSED(other, other.m_table);
223 ASSERT(m_table == other.m_table);
224 }
225#else
226 void checkValidity(const const_iterator&) const { }
227#endif
228
229 PointerType m_position { nullptr };
230 PointerType m_endPosition { nullptr };
231
232#if CHECK_HASHTABLE_ITERATORS
233 public:
234 // Any modifications of the m_next or m_previous of an iterator that is in a linked list of a HashTable::m_iterator,
235 // should be guarded with m_table->m_mutex.
236 mutable const HashTableType* m_table;
237 mutable const_iterator* m_next;
238 mutable const_iterator* m_previous;
239#endif
240 };
241
242 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
243 class HashTableIterator : public std::iterator<std::forward_iterator_tag, Value, std::ptrdiff_t, Value*, Value&> {
244 private:
245 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
246 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
247 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
248 typedef Value ValueType;
249 typedef ValueType& ReferenceType;
250 typedef ValueType* PointerType;
251
252 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
253
254 HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { }
255 HashTableIterator(HashTableType* table, PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(table, pos, end, tag) { }
256
257 public:
258 HashTableIterator() { }
259
260 // default copy, assignment and destructor are OK
261
262 PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
263 ReferenceType operator*() const { return *get(); }
264 PointerType operator->() const { return get(); }
265
266 iterator& operator++() { ++m_iterator; return *this; }
267
268 // postfix ++ intentionally omitted
269
270 // Comparison.
271 bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
272 bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
273 bool operator==(const const_iterator& other) const { return m_iterator == other; }
274 bool operator!=(const const_iterator& other) const { return m_iterator != other; }
275
276 operator const_iterator() const { return m_iterator; }
277
278 private:
279 const_iterator m_iterator;
280 };
281
282 template<typename ValueTraits, typename HashFunctions> class IdentityHashTranslator {
283 public:
284 template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
285 template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
286 template<typename T, typename U, typename V> static void translate(T& location, const U&, V&& value)
287 {
288 ValueTraits::assignToEmpty(location, std::forward<V>(value));
289 }
290 };
291
292 template<typename IteratorType> struct HashTableAddResult {
293 HashTableAddResult() : isNewEntry(false) { }
294 HashTableAddResult(IteratorType iter, bool isNewEntry) : iterator(iter), isNewEntry(isNewEntry) { }
295 IteratorType iterator;
296 bool isNewEntry;
297
298 explicit operator bool() const { return isNewEntry; }
299 };
300
301 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
302 class HashTable {
303 public:
304 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
305 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
306 typedef Traits ValueTraits;
307 typedef Key KeyType;
308 typedef Value ValueType;
309 typedef IdentityHashTranslator<ValueTraits, HashFunctions> IdentityTranslatorType;
310 typedef HashTableAddResult<iterator> AddResult;
311
312#if DUMP_HASHTABLE_STATS_PER_TABLE
313 struct Stats {
314 Stats()
315 : numAccesses(0)
316 , numRehashes(0)
317 , numRemoves(0)
318 , numReinserts(0)
319 , maxCollisions(0)
320 , numCollisions(0)
321 , collisionGraph()
322 {
323 }
324
325 unsigned numAccesses;
326 unsigned numRehashes;
327 unsigned numRemoves;
328 unsigned numReinserts;
329
330 unsigned maxCollisions;
331 unsigned numCollisions;
332 unsigned collisionGraph[4096];
333
334 void recordCollisionAtCount(unsigned count)
335 {
336 if (count > maxCollisions)
337 maxCollisions = count;
338 numCollisions++;
339 collisionGraph[count]++;
340 }
341
342 void dumpStats()
343 {
344 dataLogF("\nWTF::HashTable::Stats dump\n\n");
345 dataLogF("%d accesses\n", numAccesses);
346 dataLogF("%d total collisions, average %.2f probes per access\n", numCollisions, 1.0 * (numAccesses + numCollisions) / numAccesses);
347 dataLogF("longest collision chain: %d\n", maxCollisions);
348 for (unsigned i = 1; i <= maxCollisions; i++) {
349 dataLogF(" %d lookups with exactly %d collisions (%.2f%% , %.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses);
350 }
351 dataLogF("%d rehashes\n", numRehashes);
352 dataLogF("%d reinserts\n", numReinserts);
353 }
354 };
355#endif
356
357 HashTable();
358 ~HashTable()
359 {
360 invalidateIterators();
361 if (m_table)
362 deallocateTable(m_table, m_tableSize);
363#if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION
364 m_table = (ValueType*)(uintptr_t)0xbbadbeef;
365#endif
366 }
367
368 HashTable(const HashTable&);
369 void swap(HashTable&);
370 HashTable& operator=(const HashTable&);
371
372 HashTable(HashTable&&);
373 HashTable& operator=(HashTable&&);
374
375 // When the hash table is empty, just return the same iterator for end as for begin.
376 // This is more efficient because we don't have to skip all the empty and deleted
377 // buckets, and iterating an empty table is a common case that's worth optimizing.
378 iterator begin() { return isEmpty() ? end() : makeIterator(m_table); }
379 iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
380 const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); }
381 const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
382
383 iterator random()
384 {
385 if (isEmpty())
386 return end();
387
388 while (1) {
389 auto& bucket = m_table[weakRandomUint32() & m_tableSizeMask];
390 if (!isEmptyOrDeletedBucket(bucket))
391 return makeKnownGoodIterator(&bucket);
392 };
393 }
394
395 const_iterator random() const { return static_cast<const_iterator>(const_cast<HashTable*>(this)->random()); }
396
397 unsigned size() const { return m_keyCount; }
398 unsigned capacity() const { return m_tableSize; }
399 bool isEmpty() const { return !m_keyCount; }
400
401 AddResult add(const ValueType& value) { return add<IdentityTranslatorType>(Extractor::extract(value), value); }
402 AddResult add(ValueType&& value) { return add<IdentityTranslatorType>(Extractor::extract(value), WTFMove(value)); }
403
404 // A special version of add() that finds the object by hashing and comparing
405 // with some other type, to avoid the cost of type conversion if the object is already
406 // in the table.
407 template<typename HashTranslator, typename T, typename Extra> AddResult add(T&& key, Extra&&);
408 template<typename HashTranslator, typename T, typename Extra> AddResult addPassingHashCode(T&& key, Extra&&);
409
410 iterator find(const KeyType& key) { return find<IdentityTranslatorType>(key); }
411 const_iterator find(const KeyType& key) const { return find<IdentityTranslatorType>(key); }
412 bool contains(const KeyType& key) const { return contains<IdentityTranslatorType>(key); }
413
414 template<typename HashTranslator, typename T> iterator find(const T&);
415 template<typename HashTranslator, typename T> const_iterator find(const T&) const;
416 template<typename HashTranslator, typename T> bool contains(const T&) const;
417
418 void remove(const KeyType&);
419 void remove(iterator);
420 void removeWithoutEntryConsistencyCheck(iterator);
421 void removeWithoutEntryConsistencyCheck(const_iterator);
422 template<typename Functor>
423 bool removeIf(const Functor&);
424 void clear();
425
426 static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
427 static bool isReleasedWeakBucket(const ValueType& value) { return isHashTraitsReleasedWeakValue<KeyTraits>(Extractor::extract(value)); }
428 static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
429 static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
430
431 ValueType* lookup(const Key& key) { return lookup<IdentityTranslatorType>(key); }
432 template<typename HashTranslator, typename T> ValueType* lookup(const T&);
433 template<typename HashTranslator, typename T> ValueType* inlineLookup(const T&);
434
435#if !ASSERT_DISABLED
436 void checkTableConsistency() const;
437#else
438 static void checkTableConsistency() { }
439#endif
440#if CHECK_HASHTABLE_CONSISTENCY
441 void internalCheckTableConsistency() const { checkTableConsistency(); }
442 void internalCheckTableConsistencyExceptSize() const { checkTableConsistencyExceptSize(); }
443#else
444 static void internalCheckTableConsistencyExceptSize() { }
445 static void internalCheckTableConsistency() { }
446#endif
447
448 private:
449 static ValueType* allocateTable(unsigned size);
450 static void deallocateTable(ValueType* table, unsigned size);
451
452 typedef std::pair<ValueType*, bool> LookupType;
453 typedef std::pair<LookupType, unsigned> FullLookupType;
454
455 LookupType lookupForWriting(const Key& key) { return lookupForWriting<IdentityTranslatorType>(key); };
456 template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&);
457 template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&);
458
459 template<typename HashTranslator, typename T, typename Extra> void addUniqueForInitialization(T&& key, Extra&&);
460
461 template<typename HashTranslator, typename T> void checkKey(const T&);
462
463 void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
464 void removeAndInvalidate(ValueType*);
465 void remove(ValueType*);
466
467 bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
468 bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
469 bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; }
470 ValueType* expand(ValueType* entry = nullptr);
471 void shrink() { rehash(m_tableSize / 2, nullptr); }
472
473 void deleteReleasedWeakBuckets();
474
475 ValueType* rehash(unsigned newTableSize, ValueType* entry);
476 ValueType* reinsert(ValueType&&);
477
478 static void initializeBucket(ValueType& bucket);
479 static void deleteBucket(ValueType& bucket) { hashTraitsDeleteBucket<Traits>(bucket); }
480
481 FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
482 { return FullLookupType(LookupType(position, found), hash); }
483
484 iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
485 const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
486 iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
487 const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
488
489#if !ASSERT_DISABLED
490 void checkTableConsistencyExceptSize() const;
491#else
492 static void checkTableConsistencyExceptSize() { }
493#endif
494
495#if CHECK_HASHTABLE_ITERATORS
496 void invalidateIterators();
497#else
498 static void invalidateIterators() { }
499#endif
500
501 static const unsigned m_maxLoad = 2;
502 static const unsigned m_minLoad = 6;
503
504 ValueType* m_table;
505 unsigned m_tableSize;
506 unsigned m_tableSizeMask;
507 unsigned m_keyCount;
508 unsigned m_deletedCount;
509
510#if CHECK_HASHTABLE_ITERATORS
511 public:
512 // All access to m_iterators should be guarded with m_mutex.
513 mutable const_iterator* m_iterators;
514 // Use std::unique_ptr so HashTable can still be memmove'd or memcpy'ed.
515 mutable std::unique_ptr<Lock> m_mutex;
516#endif
517
518#if DUMP_HASHTABLE_STATS_PER_TABLE
519 public:
520 mutable std::unique_ptr<Stats> m_stats;
521#endif
522 };
523
524 // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
525 template<unsigned size> struct OneifyLowBits;
526 template<>
527 struct OneifyLowBits<0> {
528 static const unsigned value = 0;
529 };
530 template<unsigned number>
531 struct OneifyLowBits {
532 static const unsigned value = number | OneifyLowBits<(number >> 1)>::value;
533 };
534 // Compute the first power of two integer that is an upper bound of the parameter 'number'.
535 template<unsigned number>
536 struct UpperPowerOfTwoBound {
537 static const unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2;
538 };
539
540 // Because power of two numbers are the limit of maxLoad, their capacity is twice the
541 // UpperPowerOfTwoBound, or 4 times their values.
542 template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter;
543 template<unsigned size>
544 struct HashTableCapacityForSizeSplitter<size, true> {
545 static const unsigned value = size * 4;
546 };
547 template<unsigned size>
548 struct HashTableCapacityForSizeSplitter<size, false> {
549 static const unsigned value = UpperPowerOfTwoBound<size>::value;
550 };
551
552 // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter.
553 // This is done at compile time to initialize the HashTraits.
554 template<unsigned size>
555 struct HashTableCapacityForSize {
556 static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
557 COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
558 COMPILE_ASSERT(!static_cast<unsigned>(value >> 31), HashTableNoCapacityOverflow);
559 COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
560 };
561
562 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
563 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
564 : m_table(0)
565 , m_tableSize(0)
566 , m_tableSizeMask(0)
567 , m_keyCount(0)
568 , m_deletedCount(0)
569#if CHECK_HASHTABLE_ITERATORS
570 , m_iterators(0)
571 , m_mutex(std::make_unique<Lock>())
572#endif
573#if DUMP_HASHTABLE_STATS_PER_TABLE
574 , m_stats(std::make_unique<Stats>())
575#endif
576 {
577 }
578
579 inline unsigned doubleHash(unsigned key)
580 {
581 key = ~key + (key >> 23);
582 key ^= (key << 12);
583 key ^= (key >> 7);
584 key ^= (key << 2);
585 key ^= (key >> 20);
586 return key;
587 }
588
589#if ASSERT_DISABLED
590
591 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
592 template<typename HashTranslator, typename T>
593 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
594 {
595 }
596
597#else
598
599 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
600 template<typename HashTranslator, typename T>
601 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)
602 {
603 if (!HashFunctions::safeToCompareToEmptyOrDeleted)
604 return;
605 ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
606 typename std::aligned_storage<sizeof(ValueType), std::alignment_of<ValueType>::value>::type deletedValueBuffer;
607 ValueType* deletedValuePtr = reinterpret_cast_ptr<ValueType*>(&deletedValueBuffer);
608 ValueType& deletedValue = *deletedValuePtr;
609 Traits::constructDeletedValue(deletedValue);
610 ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
611 }
612
613#endif
614
615 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
616 template<typename HashTranslator, typename T>
617 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key) -> ValueType*
618 {
619 return inlineLookup<HashTranslator>(key);
620 }
621
622 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
623 template<typename HashTranslator, typename T>
624 ALWAYS_INLINE auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::inlineLookup(const T& key) -> ValueType*
625 {
626 checkKey<HashTranslator>(key);
627
628 unsigned k = 0;
629 unsigned sizeMask = m_tableSizeMask;
630 ValueType* table = m_table;
631 unsigned h = HashTranslator::hash(key);
632 unsigned i = h & sizeMask;
633
634 if (!table)
635 return 0;
636
637#if DUMP_HASHTABLE_STATS
638 ++HashTableStats::numAccesses;
639 unsigned probeCount = 0;
640#endif
641
642#if DUMP_HASHTABLE_STATS_PER_TABLE
643 ++m_stats->numAccesses;
644#endif
645
646 while (1) {
647 ValueType* entry = table + i;
648
649 // we count on the compiler to optimize out this branch
650 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
651 if (HashTranslator::equal(Extractor::extract(*entry), key))
652 return entry;
653
654 if (isEmptyBucket(*entry))
655 return 0;
656 } else {
657 if (isEmptyBucket(*entry))
658 return 0;
659
660 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
661 return entry;
662 }
663#if DUMP_HASHTABLE_STATS
664 ++probeCount;
665 HashTableStats::recordCollisionAtCount(probeCount);
666#endif
667
668#if DUMP_HASHTABLE_STATS_PER_TABLE
669 m_stats->recordCollisionAtCount(probeCount);
670#endif
671
672 if (k == 0)
673 k = 1 | doubleHash(h);
674 i = (i + k) & sizeMask;
675 }
676 }
677
678 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
679 template<typename HashTranslator, typename T>
680 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key) -> LookupType
681 {
682 ASSERT(m_table);
683 checkKey<HashTranslator>(key);
684
685 unsigned k = 0;
686 ValueType* table = m_table;
687 unsigned sizeMask = m_tableSizeMask;
688 unsigned h = HashTranslator::hash(key);
689 unsigned i = h & sizeMask;
690
691#if DUMP_HASHTABLE_STATS
692 ++HashTableStats::numAccesses;
693 unsigned probeCount = 0;
694#endif
695
696#if DUMP_HASHTABLE_STATS_PER_TABLE
697 ++m_stats->numAccesses;
698#endif
699
700 ValueType* deletedEntry = 0;
701
702 while (1) {
703 ValueType* entry = table + i;
704
705 // we count on the compiler to optimize out this branch
706 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
707 if (isEmptyBucket(*entry))
708 return LookupType(deletedEntry ? deletedEntry : entry, false);
709
710 if (HashTranslator::equal(Extractor::extract(*entry), key))
711 return LookupType(entry, true);
712
713 if (isDeletedBucket(*entry))
714 deletedEntry = entry;
715 } else {
716 if (isEmptyBucket(*entry))
717 return LookupType(deletedEntry ? deletedEntry : entry, false);
718
719 if (isDeletedBucket(*entry))
720 deletedEntry = entry;
721 else if (HashTranslator::equal(Extractor::extract(*entry), key))
722 return LookupType(entry, true);
723 }
724#if DUMP_HASHTABLE_STATS
725 ++probeCount;
726 HashTableStats::recordCollisionAtCount(probeCount);
727#endif
728
729#if DUMP_HASHTABLE_STATS_PER_TABLE
730 m_stats->recordCollisionAtCount(probeCount);
731#endif
732
733 if (k == 0)
734 k = 1 | doubleHash(h);
735 i = (i + k) & sizeMask;
736 }
737 }
738
739 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
740 template<typename HashTranslator, typename T>
741 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key) -> FullLookupType
742 {
743 ASSERT(m_table);
744 checkKey<HashTranslator>(key);
745
746 unsigned k = 0;
747 ValueType* table = m_table;
748 unsigned sizeMask = m_tableSizeMask;
749 unsigned h = HashTranslator::hash(key);
750 unsigned i = h & sizeMask;
751
752#if DUMP_HASHTABLE_STATS
753 ++HashTableStats::numAccesses;
754 unsigned probeCount = 0;
755#endif
756
757#if DUMP_HASHTABLE_STATS_PER_TABLE
758 ++m_stats->numAccesses;
759#endif
760
761 ValueType* deletedEntry = 0;
762
763 while (1) {
764 ValueType* entry = table + i;
765
766 // we count on the compiler to optimize out this branch
767 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
768 if (isEmptyBucket(*entry))
769 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
770
771 if (HashTranslator::equal(Extractor::extract(*entry), key))
772 return makeLookupResult(entry, true, h);
773
774 if (isDeletedBucket(*entry))
775 deletedEntry = entry;
776 } else {
777 if (isEmptyBucket(*entry))
778 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
779
780 if (isDeletedBucket(*entry))
781 deletedEntry = entry;
782 else if (HashTranslator::equal(Extractor::extract(*entry), key))
783 return makeLookupResult(entry, true, h);
784 }
785#if DUMP_HASHTABLE_STATS
786 ++probeCount;
787 HashTableStats::recordCollisionAtCount(probeCount);
788#endif
789
790#if DUMP_HASHTABLE_STATS_PER_TABLE
791 m_stats->recordCollisionAtCount(probeCount);
792#endif
793
794 if (k == 0)
795 k = 1 | doubleHash(h);
796 i = (i + k) & sizeMask;
797 }
798 }
799
800 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
801 template<typename HashTranslator, typename T, typename Extra>
802 ALWAYS_INLINE void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addUniqueForInitialization(T&& key, Extra&& extra)
803 {
804 ASSERT(m_table);
805
806 checkKey<HashTranslator>(key);
807
808 invalidateIterators();
809
810 internalCheckTableConsistency();
811
812 unsigned k = 0;
813 ValueType* table = m_table;
814 unsigned sizeMask = m_tableSizeMask;
815 unsigned h = HashTranslator::hash(key);
816 unsigned i = h & sizeMask;
817
818#if DUMP_HASHTABLE_STATS
819 ++HashTableStats::numAccesses;
820 unsigned probeCount = 0;
821#endif
822
823#if DUMP_HASHTABLE_STATS_PER_TABLE
824 ++m_stats->numAccesses;
825#endif
826
827 ValueType* entry;
828 while (1) {
829 entry = table + i;
830
831 if (isEmptyBucket(*entry))
832 break;
833
834#if DUMP_HASHTABLE_STATS
835 ++probeCount;
836 HashTableStats::recordCollisionAtCount(probeCount);
837#endif
838
839#if DUMP_HASHTABLE_STATS_PER_TABLE
840 m_stats->recordCollisionAtCount(probeCount);
841#endif
842
843 if (k == 0)
844 k = 1 | doubleHash(h);
845 i = (i + k) & sizeMask;
846 }
847
848 HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
849
850 internalCheckTableConsistency();
851 }
852
853 template<bool emptyValueIsZero> struct HashTableBucketInitializer;
854
855 template<> struct HashTableBucketInitializer<false> {
856 template<typename Traits, typename Value> static void initialize(Value& bucket)
857 {
858 Traits::template constructEmptyValue<Traits>(bucket);
859 }
860 };
861
862 template<> struct HashTableBucketInitializer<true> {
863 template<typename Traits, typename Value> static void initialize(Value& bucket)
864 {
865 // This initializes the bucket without copying the empty value.
866 // That makes it possible to use this with types that don't support copying.
867 // The memset to 0 looks like a slow operation but is optimized by the compilers.
868 memset(static_cast<void*>(std::addressof(bucket)), 0, sizeof(bucket));
869 }
870 };
871
872 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
873 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::initializeBucket(ValueType& bucket)
874 {
875 HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket);
876 }
877
878 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
879 template<typename HashTranslator, typename T, typename Extra>
880 ALWAYS_INLINE auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(T&& key, Extra&& extra) -> AddResult
881 {
882 checkKey<HashTranslator>(key);
883
884 invalidateIterators();
885
886 if (!m_table)
887 expand(nullptr);
888
889 internalCheckTableConsistency();
890
891 ASSERT(m_table);
892
893 unsigned k = 0;
894 ValueType* table = m_table;
895 unsigned sizeMask = m_tableSizeMask;
896 unsigned h = HashTranslator::hash(key);
897 unsigned i = h & sizeMask;
898
899#if DUMP_HASHTABLE_STATS
900 ++HashTableStats::numAccesses;
901 unsigned probeCount = 0;
902#endif
903
904#if DUMP_HASHTABLE_STATS_PER_TABLE
905 ++m_stats->numAccesses;
906#endif
907
908 ValueType* deletedEntry = 0;
909 ValueType* entry;
910 while (1) {
911 entry = table + i;
912
913 // we count on the compiler to optimize out this branch
914 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
915 if (isEmptyBucket(*entry))
916 break;
917
918 if (HashTranslator::equal(Extractor::extract(*entry), key))
919 return AddResult(makeKnownGoodIterator(entry), false);
920
921 if (isDeletedBucket(*entry))
922 deletedEntry = entry;
923 } else {
924 if (isEmptyBucket(*entry))
925 break;
926
927 if (isDeletedBucket(*entry))
928 deletedEntry = entry;
929 else if (HashTranslator::equal(Extractor::extract(*entry), key))
930 return AddResult(makeKnownGoodIterator(entry), false);
931 }
932#if DUMP_HASHTABLE_STATS
933 ++probeCount;
934 HashTableStats::recordCollisionAtCount(probeCount);
935#endif
936
937#if DUMP_HASHTABLE_STATS_PER_TABLE
938 m_stats->recordCollisionAtCount(probeCount);
939#endif
940
941 if (k == 0)
942 k = 1 | doubleHash(h);
943 i = (i + k) & sizeMask;
944 }
945
946 if (deletedEntry) {
947 initializeBucket(*deletedEntry);
948 entry = deletedEntry;
949 --m_deletedCount;
950 }
951
952 HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
953 ++m_keyCount;
954
955 if (shouldExpand())
956 entry = expand(entry);
957
958 internalCheckTableConsistency();
959
960 return AddResult(makeKnownGoodIterator(entry), true);
961 }
962
963 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
964 template<typename HashTranslator, typename T, typename Extra>
965 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addPassingHashCode(T&& key, Extra&& extra) -> AddResult
966 {
967 checkKey<HashTranslator>(key);
968
969 invalidateIterators();
970
971 if (!m_table)
972 expand();
973
974 internalCheckTableConsistency();
975
976 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key);
977
978 ValueType* entry = lookupResult.first.first;
979 bool found = lookupResult.first.second;
980 unsigned h = lookupResult.second;
981
982 if (found)
983 return AddResult(makeKnownGoodIterator(entry), false);
984
985 if (isDeletedBucket(*entry)) {
986 initializeBucket(*entry);
987 --m_deletedCount;
988 }
989
990 HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra), h);
991 ++m_keyCount;
992
993 if (shouldExpand())
994 entry = expand(entry);
995
996 internalCheckTableConsistency();
997
998 return AddResult(makeKnownGoodIterator(entry), true);
999 }
1000
1001 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1002 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType&& entry) -> ValueType*
1003 {
1004 ASSERT(m_table);
1005 ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
1006 ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
1007#if DUMP_HASHTABLE_STATS
1008 ++HashTableStats::numReinserts;
1009#endif
1010#if DUMP_HASHTABLE_STATS_PER_TABLE
1011 ++m_stats->numReinserts;
1012#endif
1013
1014 Value* newEntry = lookupForWriting(Extractor::extract(entry)).first;
1015 newEntry->~Value();
1016 new (NotNull, newEntry) ValueType(WTFMove(entry));
1017
1018 return newEntry;
1019 }
1020
1021 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1022 template <typename HashTranslator, typename T>
1023 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) -> iterator
1024 {
1025 if (!m_table)
1026 return end();
1027
1028 ValueType* entry = lookup<HashTranslator>(key);
1029 if (!entry)
1030 return end();
1031
1032 return makeKnownGoodIterator(entry);
1033 }
1034
1035 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1036 template <typename HashTranslator, typename T>
1037 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const -> const_iterator
1038 {
1039 if (!m_table)
1040 return end();
1041
1042 ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
1043 if (!entry)
1044 return end();
1045
1046 return makeKnownGoodConstIterator(entry);
1047 }
1048
1049 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1050 template <typename HashTranslator, typename T>
1051 bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const
1052 {
1053 if (!m_table)
1054 return false;
1055
1056 return const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
1057 }
1058
1059 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1060 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos)
1061 {
1062 invalidateIterators();
1063 remove(pos);
1064 }
1065
1066 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1067 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos)
1068 {
1069 invalidateIterators();
1070 internalCheckTableConsistency();
1071 remove(pos);
1072 }
1073
1074 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1075 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
1076 {
1077#if DUMP_HASHTABLE_STATS
1078 ++HashTableStats::numRemoves;
1079#endif
1080#if DUMP_HASHTABLE_STATS_PER_TABLE
1081 ++m_stats->numRemoves;
1082#endif
1083
1084 deleteBucket(*pos);
1085 ++m_deletedCount;
1086 --m_keyCount;
1087
1088 if (shouldShrink())
1089 shrink();
1090
1091 internalCheckTableConsistency();
1092 }
1093
1094 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1095 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
1096 {
1097 if (it == end())
1098 return;
1099
1100 removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position));
1101 }
1102
1103 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1104 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it)
1105 {
1106 if (it == end())
1107 return;
1108
1109 removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position));
1110 }
1111
1112 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1113 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(const_iterator it)
1114 {
1115 if (it == end())
1116 return;
1117
1118 removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_position));
1119 }
1120
1121 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1122 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
1123 {
1124 remove(find(key));
1125 }
1126
1127 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1128 template<typename Functor>
1129 inline bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeIf(const Functor& functor)
1130 {
1131 // We must use local copies in case "functor" or "deleteBucket"
1132 // make a function call, which prevents the compiler from keeping
1133 // the values in register.
1134 unsigned removedBucketCount = 0;
1135 ValueType* table = m_table;
1136
1137 for (unsigned i = m_tableSize; i--;) {
1138 ValueType& bucket = table[i];
1139 if (isEmptyOrDeletedBucket(bucket))
1140 continue;
1141
1142 if (!functor(bucket))
1143 continue;
1144
1145 deleteBucket(bucket);
1146 ++removedBucketCount;
1147 }
1148 m_deletedCount += removedBucketCount;
1149 m_keyCount -= removedBucketCount;
1150
1151 if (shouldShrink())
1152 shrink();
1153
1154 internalCheckTableConsistency();
1155 return removedBucketCount;
1156 }
1157
1158 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1159 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(unsigned size) -> ValueType*
1160 {
1161 // would use a template member function with explicit specializations here, but
1162 // gcc doesn't appear to support that
1163 if (Traits::emptyValueIsZero)
1164 return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType)));
1165 ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
1166 for (unsigned i = 0; i < size; i++)
1167 initializeBucket(result[i]);
1168 return result;
1169 }
1170
1171 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1172 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, unsigned size)
1173 {
1174 for (unsigned i = 0; i < size; ++i) {
1175 if (!isDeletedBucket(table[i]))
1176 table[i].~ValueType();
1177 }
1178 fastFree(table);
1179 }
1180
1181 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1182 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand(ValueType* entry) -> ValueType*
1183 {
1184 if (KeyTraits::hasIsReleasedWeakValueFunction)
1185 deleteReleasedWeakBuckets();
1186
1187 unsigned newSize;
1188 if (m_tableSize == 0)
1189 newSize = KeyTraits::minimumTableSize;
1190 else if (mustRehashInPlace())
1191 newSize = m_tableSize;
1192 else
1193 newSize = m_tableSize * 2;
1194
1195 return rehash(newSize, entry);
1196 }
1197
1198 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1199 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deleteReleasedWeakBuckets()
1200 {
1201 for (unsigned i = 0; i < m_tableSize; ++i) {
1202 auto& entry = m_table[i];
1203 if (isReleasedWeakBucket(entry)) {
1204 deleteBucket(entry);
1205 ++m_deletedCount;
1206 --m_keyCount;
1207 }
1208 }
1209 }
1210
1211 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1212 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(unsigned newTableSize, ValueType* entry) -> ValueType*
1213 {
1214 internalCheckTableConsistencyExceptSize();
1215
1216 unsigned oldTableSize = m_tableSize;
1217 ValueType* oldTable = m_table;
1218
1219#if DUMP_HASHTABLE_STATS
1220 if (oldTableSize != 0)
1221 ++HashTableStats::numRehashes;
1222#endif
1223
1224#if DUMP_HASHTABLE_STATS_PER_TABLE
1225 if (oldTableSize != 0)
1226 ++m_stats->numRehashes;
1227#endif
1228
1229 m_tableSize = newTableSize;
1230 m_tableSizeMask = newTableSize - 1;
1231 m_table = allocateTable(newTableSize);
1232
1233 Value* newEntry = nullptr;
1234 for (unsigned i = 0; i != oldTableSize; ++i) {
1235 auto& oldEntry = oldTable[i];
1236 if (isDeletedBucket(oldEntry)) {
1237 ASSERT(std::addressof(oldEntry) != entry);
1238 continue;
1239 }
1240
1241 if (isEmptyBucket(oldEntry)) {
1242 ASSERT(std::addressof(oldEntry) != entry);
1243 oldTable[i].~ValueType();
1244 continue;
1245 }
1246
1247 if (isReleasedWeakBucket(oldEntry)) {
1248 ASSERT(std::addressof(oldEntry) != entry);
1249 oldEntry.~ValueType();
1250 --m_keyCount;
1251 continue;
1252 }
1253
1254 Value* reinsertedEntry = reinsert(WTFMove(oldEntry));
1255 oldEntry.~ValueType();
1256 if (std::addressof(oldEntry) == entry) {
1257 ASSERT(!newEntry);
1258 newEntry = reinsertedEntry;
1259 }
1260 }
1261
1262 m_deletedCount = 0;
1263
1264 fastFree(oldTable);
1265
1266 internalCheckTableConsistency();
1267 return newEntry;
1268 }
1269
1270 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1271 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
1272 {
1273 invalidateIterators();
1274 if (!m_table)
1275 return;
1276
1277 deallocateTable(m_table, m_tableSize);
1278 m_table = 0;
1279 m_tableSize = 0;
1280 m_tableSizeMask = 0;
1281 m_keyCount = 0;
1282 m_deletedCount = 0;
1283 }
1284
1285 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1286 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
1287 : m_table(nullptr)
1288 , m_tableSize(0)
1289 , m_tableSizeMask(0)
1290 , m_keyCount(0)
1291 , m_deletedCount(0)
1292#if CHECK_HASHTABLE_ITERATORS
1293 , m_iterators(nullptr)
1294 , m_mutex(std::make_unique<Lock>())
1295#endif
1296#if DUMP_HASHTABLE_STATS_PER_TABLE
1297 , m_stats(std::make_unique<Stats>(*other.m_stats))
1298#endif
1299 {
1300 unsigned otherKeyCount = other.size();
1301 if (!otherKeyCount)
1302 return;
1303
1304 unsigned bestTableSize = WTF::roundUpToPowerOfTwo(otherKeyCount) * 2;
1305
1306 // With maxLoad at 1/2 and minLoad at 1/6, our average load is 2/6.
1307 // If we are getting halfway between 2/6 and 1/2 (past 5/12), we double the size to avoid being too close to
1308 // loadMax and bring the ratio close to 2/6. This give us a load in the bounds [3/12, 5/12).
1309 bool aboveThreeQuarterLoad = otherKeyCount * 12 >= bestTableSize * 5;
1310 if (aboveThreeQuarterLoad)
1311 bestTableSize *= 2;
1312
1313 unsigned minimumTableSize = KeyTraits::minimumTableSize;
1314 m_tableSize = std::max<unsigned>(bestTableSize, minimumTableSize);
1315 m_tableSizeMask = m_tableSize - 1;
1316 m_keyCount = otherKeyCount;
1317 m_table = allocateTable(m_tableSize);
1318
1319 for (const auto& otherValue : other)
1320 addUniqueForInitialization<IdentityTranslatorType>(Extractor::extract(otherValue), otherValue);
1321 }
1322
1323 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1324 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
1325 {
1326 invalidateIterators();
1327 other.invalidateIterators();
1328
1329 std::swap(m_table, other.m_table);
1330 std::swap(m_tableSize, other.m_tableSize);
1331 std::swap(m_tableSizeMask, other.m_tableSizeMask);
1332 std::swap(m_keyCount, other.m_keyCount);
1333 std::swap(m_deletedCount, other.m_deletedCount);
1334
1335#if DUMP_HASHTABLE_STATS_PER_TABLE
1336 m_stats.swap(other.m_stats);
1337#endif
1338 }
1339
1340 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1341 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other) -> HashTable&
1342 {
1343 HashTable tmp(other);
1344 swap(tmp);
1345 return *this;
1346 }
1347
1348 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1349 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(HashTable&& other)
1350#if CHECK_HASHTABLE_ITERATORS
1351 : m_iterators(nullptr)
1352 , m_mutex(std::make_unique<Lock>())
1353#endif
1354 {
1355 other.invalidateIterators();
1356
1357 m_table = other.m_table;
1358 m_tableSize = other.m_tableSize;
1359 m_tableSizeMask = other.m_tableSizeMask;
1360 m_keyCount = other.m_keyCount;
1361 m_deletedCount = other.m_deletedCount;
1362
1363 other.m_table = nullptr;
1364 other.m_tableSize = 0;
1365 other.m_tableSizeMask = 0;
1366 other.m_keyCount = 0;
1367 other.m_deletedCount = 0;
1368
1369#if DUMP_HASHTABLE_STATS_PER_TABLE
1370 m_stats = WTFMove(other.m_stats);
1371 other.m_stats = nullptr;
1372#endif
1373 }
1374
1375 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1376 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(HashTable&& other) -> HashTable&
1377 {
1378 HashTable temp = WTFMove(other);
1379 swap(temp);
1380 return *this;
1381 }
1382
1383#if !ASSERT_DISABLED
1384
1385 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1386 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
1387 {
1388 checkTableConsistencyExceptSize();
1389 ASSERT(!m_table || !shouldExpand());
1390 ASSERT(!shouldShrink());
1391 }
1392
1393 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1394 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
1395 {
1396 if (!m_table)
1397 return;
1398
1399 unsigned count = 0;
1400 unsigned deletedCount = 0;
1401 for (unsigned j = 0; j < m_tableSize; ++j) {
1402 ValueType* entry = m_table + j;
1403 if (isEmptyBucket(*entry))
1404 continue;
1405
1406 if (isDeletedBucket(*entry)) {
1407 ++deletedCount;
1408 continue;
1409 }
1410
1411 auto& key = Extractor::extract(*entry);
1412 const_iterator it = find(key);
1413 ASSERT(entry == it.m_position);
1414 ++count;
1415
1416 ValueCheck<Key>::checkConsistency(key);
1417 }
1418
1419 ASSERT(count == m_keyCount);
1420 ASSERT(deletedCount == m_deletedCount);
1421 ASSERT(m_tableSize >= KeyTraits::minimumTableSize);
1422 ASSERT(m_tableSizeMask);
1423 ASSERT(m_tableSize == m_tableSizeMask + 1);
1424 }
1425
1426#endif // ASSERT_DISABLED
1427
1428#if CHECK_HASHTABLE_ITERATORS
1429
1430 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1431 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
1432 {
1433 std::lock_guard<Lock> lock(*m_mutex);
1434 const_iterator* next;
1435 for (const_iterator* p = m_iterators; p; p = next) {
1436 next = p->m_next;
1437 p->m_table = 0;
1438 p->m_next = 0;
1439 p->m_previous = 0;
1440 }
1441 m_iterators = 0;
1442 }
1443
1444 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1445 void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
1446 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1447 {
1448 it->m_table = table;
1449 it->m_previous = 0;
1450
1451 // Insert iterator at head of doubly-linked list of iterators.
1452 if (!table) {
1453 it->m_next = 0;
1454 } else {
1455 std::lock_guard<Lock> lock(*table->m_mutex);
1456 ASSERT(table->m_iterators != it);
1457 it->m_next = table->m_iterators;
1458 table->m_iterators = it;
1459 if (it->m_next) {
1460 ASSERT(!it->m_next->m_previous);
1461 it->m_next->m_previous = it;
1462 }
1463 }
1464 }
1465
1466 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1467 void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1468 {
1469 // Delete iterator from doubly-linked list of iterators.
1470 if (!it->m_table) {
1471 ASSERT(!it->m_next);
1472 ASSERT(!it->m_previous);
1473 } else {
1474 std::lock_guard<Lock> lock(*it->m_table->m_mutex);
1475 if (it->m_next) {
1476 ASSERT(it->m_next->m_previous == it);
1477 it->m_next->m_previous = it->m_previous;
1478 }
1479 if (it->m_previous) {
1480 ASSERT(it->m_table->m_iterators != it);
1481 ASSERT(it->m_previous->m_next == it);
1482 it->m_previous->m_next = it->m_next;
1483 } else {
1484 ASSERT(it->m_table->m_iterators == it);
1485 it->m_table->m_iterators = it->m_next;
1486 }
1487 }
1488
1489 it->m_table = 0;
1490 it->m_next = 0;
1491 it->m_previous = 0;
1492 }
1493
1494#endif // CHECK_HASHTABLE_ITERATORS
1495
1496 // iterator adapters
1497
1498 template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter : public std::iterator<std::forward_iterator_tag, ValueType, std::ptrdiff_t, const ValueType*, const ValueType&> {
1499 HashTableConstIteratorAdapter() {}
1500 HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
1501
1502 const ValueType* get() const { return (const ValueType*)m_impl.get(); }
1503 const ValueType& operator*() const { return *get(); }
1504 const ValueType* operator->() const { return get(); }
1505
1506 HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
1507 // postfix ++ intentionally omitted
1508
1509 typename HashTableType::const_iterator m_impl;
1510 };
1511
1512 template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter : public std::iterator<std::forward_iterator_tag, ValueType, std::ptrdiff_t, ValueType*, ValueType&> {
1513 HashTableIteratorAdapter() {}
1514 HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
1515
1516 ValueType* get() const { return (ValueType*)m_impl.get(); }
1517 ValueType& operator*() const { return *get(); }
1518 ValueType* operator->() const { return get(); }
1519
1520 HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
1521 // postfix ++ intentionally omitted
1522
1523 operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
1524 typename HashTableType::const_iterator i = m_impl;
1525 return i;
1526 }
1527
1528 typename HashTableType::iterator m_impl;
1529 };
1530
1531 template<typename T, typename U>
1532 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1533 {
1534 return a.m_impl == b.m_impl;
1535 }
1536
1537 template<typename T, typename U>
1538 inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1539 {
1540 return a.m_impl != b.m_impl;
1541 }
1542
1543 template<typename T, typename U>
1544 inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1545 {
1546 return a.m_impl == b.m_impl;
1547 }
1548
1549 template<typename T, typename U>
1550 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1551 {
1552 return a.m_impl != b.m_impl;
1553 }
1554
1555 // All 4 combinations of ==, != and Const,non const.
1556 template<typename T, typename U>
1557 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1558 {
1559 return a.m_impl == b.m_impl;
1560 }
1561
1562 template<typename T, typename U>
1563 inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1564 {
1565 return a.m_impl != b.m_impl;
1566 }
1567
1568 template<typename T, typename U>
1569 inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1570 {
1571 return a.m_impl == b.m_impl;
1572 }
1573
1574 template<typename T, typename U>
1575 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1576 {
1577 return a.m_impl != b.m_impl;
1578 }
1579
1580} // namespace WTF
1581
1582#include <wtf/HashIterators.h>
1583