[CMake][Win] Use target oriented design for WebKitLegacy
[WebKit-https.git] / Source / WTF / wtf / HashTable.h
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
46 namespace 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         static constexpr unsigned computeBestTableSize(unsigned keyCount);
468         bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
469         bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
470         bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; }
471         ValueType* expand(ValueType* entry = nullptr);
472         void shrink() { rehash(m_tableSize / 2, nullptr); }
473         void shrinkToBestSize();
474     
475         void deleteReleasedWeakBuckets();
476
477         ValueType* rehash(unsigned newTableSize, ValueType* entry);
478         ValueType* reinsert(ValueType&&);
479
480         static void initializeBucket(ValueType& bucket);
481         static void deleteBucket(ValueType& bucket) { hashTraitsDeleteBucket<Traits>(bucket); }
482
483         FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
484             { return FullLookupType(LookupType(position, found), hash); }
485
486         iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
487         const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
488         iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
489         const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
490
491 #if !ASSERT_DISABLED
492         void checkTableConsistencyExceptSize() const;
493 #else
494         static void checkTableConsistencyExceptSize() { }
495 #endif
496
497 #if CHECK_HASHTABLE_ITERATORS
498         void invalidateIterators();
499 #else
500         static void invalidateIterators() { }
501 #endif
502
503         static const unsigned m_maxLoad = 2;
504         static const unsigned m_minLoad = 6;
505
506         ValueType* m_table;
507         unsigned m_tableSize;
508         unsigned m_tableSizeMask;
509         unsigned m_keyCount;
510         unsigned m_deletedCount;
511
512 #if CHECK_HASHTABLE_ITERATORS
513     public:
514         // All access to m_iterators should be guarded with m_mutex.
515         mutable const_iterator* m_iterators;
516         // Use std::unique_ptr so HashTable can still be memmove'd or memcpy'ed.
517         mutable std::unique_ptr<Lock> m_mutex;
518 #endif
519
520 #if DUMP_HASHTABLE_STATS_PER_TABLE
521     public:
522         mutable std::unique_ptr<Stats> m_stats;
523 #endif
524     };
525
526     // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
527     template<unsigned size> struct OneifyLowBits;
528     template<>
529     struct OneifyLowBits<0> {
530         static const unsigned value = 0;
531     };
532     template<unsigned number>
533     struct OneifyLowBits {
534         static const unsigned value = number | OneifyLowBits<(number >> 1)>::value;
535     };
536     // Compute the first power of two integer that is an upper bound of the parameter 'number'.
537     template<unsigned number>
538     struct UpperPowerOfTwoBound {
539         static const unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2;
540     };
541
542     // Because power of two numbers are the limit of maxLoad, their capacity is twice the
543     // UpperPowerOfTwoBound, or 4 times their values.
544     template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter;
545     template<unsigned size>
546     struct HashTableCapacityForSizeSplitter<size, true> {
547         static const unsigned value = size * 4;
548     };
549     template<unsigned size>
550     struct HashTableCapacityForSizeSplitter<size, false> {
551         static const unsigned value = UpperPowerOfTwoBound<size>::value;
552     };
553
554     // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter.
555     // This is done at compile time to initialize the HashTraits.
556     template<unsigned size>
557     struct HashTableCapacityForSize {
558         static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
559         COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
560         COMPILE_ASSERT(!static_cast<unsigned>(value >> 31), HashTableNoCapacityOverflow);
561         COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
562     };
563
564     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
565     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
566         : m_table(0)
567         , m_tableSize(0)
568         , m_tableSizeMask(0)
569         , m_keyCount(0)
570         , m_deletedCount(0)
571 #if CHECK_HASHTABLE_ITERATORS
572         , m_iterators(0)
573         , m_mutex(std::make_unique<Lock>())
574 #endif
575 #if DUMP_HASHTABLE_STATS_PER_TABLE
576         , m_stats(std::make_unique<Stats>())
577 #endif
578     {
579     }
580
581     inline unsigned doubleHash(unsigned key)
582     {
583         key = ~key + (key >> 23);
584         key ^= (key << 12);
585         key ^= (key >> 7);
586         key ^= (key << 2);
587         key ^= (key >> 20);
588         return key;
589     }
590
591 #if ASSERT_DISABLED
592
593     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
594     template<typename HashTranslator, typename T>
595     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
596     {
597     }
598
599 #else
600
601     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
602     template<typename HashTranslator, typename T>
603     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)
604     {
605         if (!HashFunctions::safeToCompareToEmptyOrDeleted)
606             return;
607         ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
608         typename std::aligned_storage<sizeof(ValueType), std::alignment_of<ValueType>::value>::type deletedValueBuffer;
609         ValueType* deletedValuePtr = reinterpret_cast_ptr<ValueType*>(&deletedValueBuffer);
610         ValueType& deletedValue = *deletedValuePtr;
611         Traits::constructDeletedValue(deletedValue);
612         ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
613     }
614
615 #endif
616
617     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
618     template<typename HashTranslator, typename T>
619     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key) -> ValueType*
620     {
621         return inlineLookup<HashTranslator>(key);
622     }
623
624     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
625     template<typename HashTranslator, typename T>
626     ALWAYS_INLINE auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::inlineLookup(const T& key) -> ValueType*
627     {
628         checkKey<HashTranslator>(key);
629
630         unsigned k = 0;
631         unsigned sizeMask = m_tableSizeMask;
632         ValueType* table = m_table;
633         unsigned h = HashTranslator::hash(key);
634         unsigned i = h & sizeMask;
635
636         if (!table)
637             return 0;
638
639 #if DUMP_HASHTABLE_STATS
640         ++HashTableStats::numAccesses;
641         unsigned probeCount = 0;
642 #endif
643
644 #if DUMP_HASHTABLE_STATS_PER_TABLE
645         ++m_stats->numAccesses;
646 #endif
647
648         while (1) {
649             ValueType* entry = table + i;
650                 
651             // we count on the compiler to optimize out this branch
652             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
653                 if (HashTranslator::equal(Extractor::extract(*entry), key))
654                     return entry;
655                 
656                 if (isEmptyBucket(*entry))
657                     return 0;
658             } else {
659                 if (isEmptyBucket(*entry))
660                     return 0;
661                 
662                 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
663                     return entry;
664             }
665 #if DUMP_HASHTABLE_STATS
666             ++probeCount;
667             HashTableStats::recordCollisionAtCount(probeCount);
668 #endif
669
670 #if DUMP_HASHTABLE_STATS_PER_TABLE
671             m_stats->recordCollisionAtCount(probeCount);
672 #endif
673
674             if (k == 0)
675                 k = 1 | doubleHash(h);
676             i = (i + k) & sizeMask;
677         }
678     }
679
680     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
681     template<typename HashTranslator, typename T>
682     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key) -> LookupType
683     {
684         ASSERT(m_table);
685         checkKey<HashTranslator>(key);
686
687         unsigned k = 0;
688         ValueType* table = m_table;
689         unsigned sizeMask = m_tableSizeMask;
690         unsigned h = HashTranslator::hash(key);
691         unsigned i = h & sizeMask;
692
693 #if DUMP_HASHTABLE_STATS
694         ++HashTableStats::numAccesses;
695         unsigned probeCount = 0;
696 #endif
697
698 #if DUMP_HASHTABLE_STATS_PER_TABLE
699         ++m_stats->numAccesses;
700 #endif
701
702         ValueType* deletedEntry = 0;
703
704         while (1) {
705             ValueType* entry = table + i;
706             
707             // we count on the compiler to optimize out this branch
708             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
709                 if (isEmptyBucket(*entry))
710                     return LookupType(deletedEntry ? deletedEntry : entry, false);
711                 
712                 if (HashTranslator::equal(Extractor::extract(*entry), key))
713                     return LookupType(entry, true);
714                 
715                 if (isDeletedBucket(*entry))
716                     deletedEntry = entry;
717             } else {
718                 if (isEmptyBucket(*entry))
719                     return LookupType(deletedEntry ? deletedEntry : entry, false);
720             
721                 if (isDeletedBucket(*entry))
722                     deletedEntry = entry;
723                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
724                     return LookupType(entry, true);
725             }
726 #if DUMP_HASHTABLE_STATS
727             ++probeCount;
728             HashTableStats::recordCollisionAtCount(probeCount);
729 #endif
730
731 #if DUMP_HASHTABLE_STATS_PER_TABLE
732             m_stats->recordCollisionAtCount(probeCount);
733 #endif
734
735             if (k == 0)
736                 k = 1 | doubleHash(h);
737             i = (i + k) & sizeMask;
738         }
739     }
740
741     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
742     template<typename HashTranslator, typename T>
743     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key) -> FullLookupType
744     {
745         ASSERT(m_table);
746         checkKey<HashTranslator>(key);
747
748         unsigned k = 0;
749         ValueType* table = m_table;
750         unsigned sizeMask = m_tableSizeMask;
751         unsigned h = HashTranslator::hash(key);
752         unsigned i = h & sizeMask;
753
754 #if DUMP_HASHTABLE_STATS
755         ++HashTableStats::numAccesses;
756         unsigned probeCount = 0;
757 #endif
758
759 #if DUMP_HASHTABLE_STATS_PER_TABLE
760         ++m_stats->numAccesses;
761 #endif
762
763         ValueType* deletedEntry = 0;
764
765         while (1) {
766             ValueType* entry = table + i;
767             
768             // we count on the compiler to optimize out this branch
769             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
770                 if (isEmptyBucket(*entry))
771                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
772                 
773                 if (HashTranslator::equal(Extractor::extract(*entry), key))
774                     return makeLookupResult(entry, true, h);
775                 
776                 if (isDeletedBucket(*entry))
777                     deletedEntry = entry;
778             } else {
779                 if (isEmptyBucket(*entry))
780                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
781             
782                 if (isDeletedBucket(*entry))
783                     deletedEntry = entry;
784                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
785                     return makeLookupResult(entry, true, h);
786             }
787 #if DUMP_HASHTABLE_STATS
788             ++probeCount;
789             HashTableStats::recordCollisionAtCount(probeCount);
790 #endif
791
792 #if DUMP_HASHTABLE_STATS_PER_TABLE
793             m_stats->recordCollisionAtCount(probeCount);
794 #endif
795
796             if (k == 0)
797                 k = 1 | doubleHash(h);
798             i = (i + k) & sizeMask;
799         }
800     }
801
802     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
803     template<typename HashTranslator, typename T, typename Extra>
804     ALWAYS_INLINE void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addUniqueForInitialization(T&& key, Extra&& extra)
805     {
806         ASSERT(m_table);
807
808         checkKey<HashTranslator>(key);
809
810         invalidateIterators();
811
812         internalCheckTableConsistency();
813
814         unsigned k = 0;
815         ValueType* table = m_table;
816         unsigned sizeMask = m_tableSizeMask;
817         unsigned h = HashTranslator::hash(key);
818         unsigned i = h & sizeMask;
819
820 #if DUMP_HASHTABLE_STATS
821         ++HashTableStats::numAccesses;
822         unsigned probeCount = 0;
823 #endif
824
825 #if DUMP_HASHTABLE_STATS_PER_TABLE
826         ++m_stats->numAccesses;
827 #endif
828
829         ValueType* entry;
830         while (1) {
831             entry = table + i;
832
833             if (isEmptyBucket(*entry))
834                 break;
835
836 #if DUMP_HASHTABLE_STATS
837             ++probeCount;
838             HashTableStats::recordCollisionAtCount(probeCount);
839 #endif
840
841 #if DUMP_HASHTABLE_STATS_PER_TABLE
842             m_stats->recordCollisionAtCount(probeCount);
843 #endif
844
845             if (k == 0)
846                 k = 1 | doubleHash(h);
847             i = (i + k) & sizeMask;
848         }
849
850         HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
851
852         internalCheckTableConsistency();
853     }
854
855     template<bool emptyValueIsZero> struct HashTableBucketInitializer;
856
857     template<> struct HashTableBucketInitializer<false> {
858         template<typename Traits, typename Value> static void initialize(Value& bucket)
859         {
860             Traits::template constructEmptyValue<Traits>(bucket);
861         }
862     };
863
864     template<> struct HashTableBucketInitializer<true> {
865         template<typename Traits, typename Value> static void initialize(Value& bucket)
866         {
867             // This initializes the bucket without copying the empty value.
868             // That makes it possible to use this with types that don't support copying.
869             // The memset to 0 looks like a slow operation but is optimized by the compilers.
870             memset(static_cast<void*>(std::addressof(bucket)), 0, sizeof(bucket));
871         }
872     };
873     
874     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
875     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::initializeBucket(ValueType& bucket)
876     {
877         HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket);
878     }
879
880     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
881     template<typename HashTranslator, typename T, typename Extra>
882     ALWAYS_INLINE auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(T&& key, Extra&& extra) -> AddResult
883     {
884         checkKey<HashTranslator>(key);
885
886         invalidateIterators();
887
888         if (!m_table)
889             expand(nullptr);
890
891         internalCheckTableConsistency();
892
893         ASSERT(m_table);
894
895         unsigned k = 0;
896         ValueType* table = m_table;
897         unsigned sizeMask = m_tableSizeMask;
898         unsigned h = HashTranslator::hash(key);
899         unsigned i = h & sizeMask;
900
901 #if DUMP_HASHTABLE_STATS
902         ++HashTableStats::numAccesses;
903         unsigned probeCount = 0;
904 #endif
905
906 #if DUMP_HASHTABLE_STATS_PER_TABLE
907         ++m_stats->numAccesses;
908 #endif
909
910         ValueType* deletedEntry = 0;
911         ValueType* entry;
912         while (1) {
913             entry = table + i;
914             
915             // we count on the compiler to optimize out this branch
916             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
917                 if (isEmptyBucket(*entry))
918                     break;
919                 
920                 if (HashTranslator::equal(Extractor::extract(*entry), key))
921                     return AddResult(makeKnownGoodIterator(entry), false);
922                 
923                 if (isDeletedBucket(*entry))
924                     deletedEntry = entry;
925             } else {
926                 if (isEmptyBucket(*entry))
927                     break;
928             
929                 if (isDeletedBucket(*entry))
930                     deletedEntry = entry;
931                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
932                     return AddResult(makeKnownGoodIterator(entry), false);
933             }
934 #if DUMP_HASHTABLE_STATS
935             ++probeCount;
936             HashTableStats::recordCollisionAtCount(probeCount);
937 #endif
938
939 #if DUMP_HASHTABLE_STATS_PER_TABLE
940             m_stats->recordCollisionAtCount(probeCount);
941 #endif
942
943             if (k == 0)
944                 k = 1 | doubleHash(h);
945             i = (i + k) & sizeMask;
946         }
947
948         if (deletedEntry) {
949             initializeBucket(*deletedEntry);
950             entry = deletedEntry;
951             --m_deletedCount; 
952         }
953
954         HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
955         ++m_keyCount;
956         
957         if (shouldExpand())
958             entry = expand(entry);
959
960         internalCheckTableConsistency();
961         
962         return AddResult(makeKnownGoodIterator(entry), true);
963     }
964
965     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
966     template<typename HashTranslator, typename T, typename Extra>
967     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addPassingHashCode(T&& key, Extra&& extra) -> AddResult
968     {
969         checkKey<HashTranslator>(key);
970
971         invalidateIterators();
972
973         if (!m_table)
974             expand();
975
976         internalCheckTableConsistency();
977
978         FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key);
979
980         ValueType* entry = lookupResult.first.first;
981         bool found = lookupResult.first.second;
982         unsigned h = lookupResult.second;
983         
984         if (found)
985             return AddResult(makeKnownGoodIterator(entry), false);
986         
987         if (isDeletedBucket(*entry)) {
988             initializeBucket(*entry);
989             --m_deletedCount;
990         }
991
992         HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra), h);
993         ++m_keyCount;
994
995         if (shouldExpand())
996             entry = expand(entry);
997
998         internalCheckTableConsistency();
999
1000         return AddResult(makeKnownGoodIterator(entry), true);
1001     }
1002
1003     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1004     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType&& entry) -> ValueType*
1005     {
1006         ASSERT(m_table);
1007         ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
1008         ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
1009 #if DUMP_HASHTABLE_STATS
1010         ++HashTableStats::numReinserts;
1011 #endif
1012 #if DUMP_HASHTABLE_STATS_PER_TABLE
1013         ++m_stats->numReinserts;
1014 #endif
1015
1016         Value* newEntry = lookupForWriting(Extractor::extract(entry)).first;
1017         newEntry->~Value();
1018         new (NotNull, newEntry) ValueType(WTFMove(entry));
1019
1020         return newEntry;
1021     }
1022
1023     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1024     template <typename HashTranslator, typename T> 
1025     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) -> iterator
1026     {
1027         if (!m_table)
1028             return end();
1029
1030         ValueType* entry = lookup<HashTranslator>(key);
1031         if (!entry)
1032             return end();
1033
1034         return makeKnownGoodIterator(entry);
1035     }
1036
1037     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1038     template <typename HashTranslator, typename T> 
1039     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const -> const_iterator
1040     {
1041         if (!m_table)
1042             return end();
1043
1044         ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
1045         if (!entry)
1046             return end();
1047
1048         return makeKnownGoodConstIterator(entry);
1049     }
1050
1051     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1052     template <typename HashTranslator, typename T> 
1053     bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const
1054     {
1055         if (!m_table)
1056             return false;
1057
1058         return const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
1059     }
1060
1061     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1062     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos)
1063     {
1064         invalidateIterators();
1065         remove(pos);
1066     }
1067
1068     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1069     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos)
1070     {
1071         invalidateIterators();
1072         internalCheckTableConsistency();
1073         remove(pos);
1074     }
1075
1076     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1077     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
1078     {
1079 #if DUMP_HASHTABLE_STATS
1080         ++HashTableStats::numRemoves;
1081 #endif
1082 #if DUMP_HASHTABLE_STATS_PER_TABLE
1083         ++m_stats->numRemoves;
1084 #endif
1085
1086         deleteBucket(*pos);
1087         ++m_deletedCount;
1088         --m_keyCount;
1089
1090         if (shouldShrink())
1091             shrink();
1092
1093         internalCheckTableConsistency();
1094     }
1095
1096     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1097     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
1098     {
1099         if (it == end())
1100             return;
1101
1102         removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position));
1103     }
1104
1105     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1106     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it)
1107     {
1108         if (it == end())
1109             return;
1110
1111         removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position));
1112     }
1113
1114     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1115     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(const_iterator it)
1116     {
1117         if (it == end())
1118             return;
1119
1120         removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_position));
1121     }
1122
1123     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1124     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
1125     {
1126         remove(find(key));
1127     }
1128
1129     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1130     template<typename Functor>
1131     inline bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeIf(const Functor& functor)
1132     {
1133         // We must use local copies in case "functor" or "deleteBucket"
1134         // make a function call, which prevents the compiler from keeping
1135         // the values in register.
1136         unsigned removedBucketCount = 0;
1137         ValueType* table = m_table;
1138
1139         for (unsigned i = m_tableSize; i--;) {
1140             ValueType& bucket = table[i];
1141             if (isEmptyOrDeletedBucket(bucket))
1142                 continue;
1143             
1144             if (!functor(bucket))
1145                 continue;
1146             
1147             deleteBucket(bucket);
1148             ++removedBucketCount;
1149         }
1150         m_deletedCount += removedBucketCount;
1151         m_keyCount -= removedBucketCount;
1152
1153         if (shouldShrink())
1154             shrinkToBestSize();
1155         
1156         internalCheckTableConsistency();
1157         return removedBucketCount;
1158     }
1159
1160     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1161     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(unsigned size) -> ValueType*
1162     {
1163         // would use a template member function with explicit specializations here, but
1164         // gcc doesn't appear to support that
1165         if (Traits::emptyValueIsZero)
1166             return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType)));
1167         ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
1168         for (unsigned i = 0; i < size; i++)
1169             initializeBucket(result[i]);
1170         return result;
1171     }
1172
1173     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1174     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, unsigned size)
1175     {
1176         for (unsigned i = 0; i < size; ++i) {
1177             if (!isDeletedBucket(table[i]))
1178                 table[i].~ValueType();
1179         }
1180         fastFree(table);
1181     }
1182
1183     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1184     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand(ValueType* entry) -> ValueType*
1185     {
1186         if (KeyTraits::hasIsReleasedWeakValueFunction)
1187             deleteReleasedWeakBuckets();
1188
1189         unsigned newSize;
1190         if (m_tableSize == 0)
1191             newSize = KeyTraits::minimumTableSize;
1192         else if (mustRehashInPlace())
1193             newSize = m_tableSize;
1194         else
1195             newSize = m_tableSize * 2;
1196
1197         return rehash(newSize, entry);
1198     }
1199
1200     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1201     constexpr unsigned HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::computeBestTableSize(unsigned keyCount)
1202     {
1203         unsigned bestTableSize = WTF::roundUpToPowerOfTwo(keyCount) * 2;
1204
1205         // With maxLoad at 1/2 and minLoad at 1/6, our average load is 2/6.
1206         // If we are getting halfway between 2/6 and 1/2 (past 5/12), we double the size to avoid being too close to
1207         // loadMax and bring the ratio close to 2/6. This give us a load in the bounds [3/12, 5/12).
1208         bool aboveThreeQuarterLoad = keyCount * 12 >= bestTableSize * 5;
1209         if (aboveThreeQuarterLoad)
1210             bestTableSize *= 2;
1211
1212         unsigned minimumTableSize = KeyTraits::minimumTableSize;
1213         return std::max<unsigned>(bestTableSize, minimumTableSize);
1214     }
1215
1216     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1217     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::shrinkToBestSize()
1218     {
1219         unsigned minimumTableSize = KeyTraits::minimumTableSize;
1220         rehash(std::max<unsigned>(minimumTableSize, computeBestTableSize(m_keyCount)), nullptr);
1221     }
1222
1223     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1224     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deleteReleasedWeakBuckets()
1225     {
1226         for (unsigned i = 0; i < m_tableSize; ++i) {
1227             auto& entry = m_table[i];
1228             if (isReleasedWeakBucket(entry)) {
1229                 deleteBucket(entry);
1230                 ++m_deletedCount;
1231                 --m_keyCount;
1232             }
1233         }
1234     }
1235
1236     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1237     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(unsigned newTableSize, ValueType* entry) -> ValueType*
1238     {
1239         internalCheckTableConsistencyExceptSize();
1240
1241         unsigned oldTableSize = m_tableSize;
1242         ValueType* oldTable = m_table;
1243
1244 #if DUMP_HASHTABLE_STATS
1245         if (oldTableSize != 0)
1246             ++HashTableStats::numRehashes;
1247 #endif
1248
1249 #if DUMP_HASHTABLE_STATS_PER_TABLE
1250         if (oldTableSize != 0)
1251             ++m_stats->numRehashes;
1252 #endif
1253
1254         m_tableSize = newTableSize;
1255         m_tableSizeMask = newTableSize - 1;
1256         m_table = allocateTable(newTableSize);
1257
1258         Value* newEntry = nullptr;
1259         for (unsigned i = 0; i != oldTableSize; ++i) {
1260             auto& oldEntry = oldTable[i];
1261             if (isDeletedBucket(oldEntry)) {
1262                 ASSERT(std::addressof(oldEntry) != entry);
1263                 continue;
1264             }
1265
1266             if (isEmptyBucket(oldEntry)) {
1267                 ASSERT(std::addressof(oldEntry) != entry);
1268                 oldTable[i].~ValueType();
1269                 continue;
1270             }
1271
1272             if (isReleasedWeakBucket(oldEntry)) {
1273                 ASSERT(std::addressof(oldEntry) != entry);
1274                 oldEntry.~ValueType();
1275                 --m_keyCount;
1276                 continue;
1277             }
1278
1279             Value* reinsertedEntry = reinsert(WTFMove(oldEntry));
1280             oldEntry.~ValueType();
1281             if (std::addressof(oldEntry) == entry) {
1282                 ASSERT(!newEntry);
1283                 newEntry = reinsertedEntry;
1284             }
1285         }
1286
1287         m_deletedCount = 0;
1288
1289         fastFree(oldTable);
1290
1291         internalCheckTableConsistency();
1292         return newEntry;
1293     }
1294
1295     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1296     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
1297     {
1298         invalidateIterators();
1299         if (!m_table)
1300             return;
1301
1302         deallocateTable(m_table, m_tableSize);
1303         m_table = 0;
1304         m_tableSize = 0;
1305         m_tableSizeMask = 0;
1306         m_keyCount = 0;
1307         m_deletedCount = 0;
1308     }
1309
1310     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1311     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
1312         : m_table(nullptr)
1313         , m_tableSize(0)
1314         , m_tableSizeMask(0)
1315         , m_keyCount(0)
1316         , m_deletedCount(0)
1317 #if CHECK_HASHTABLE_ITERATORS
1318         , m_iterators(nullptr)
1319         , m_mutex(std::make_unique<Lock>())
1320 #endif
1321 #if DUMP_HASHTABLE_STATS_PER_TABLE
1322         , m_stats(std::make_unique<Stats>(*other.m_stats))
1323 #endif
1324     {
1325         unsigned otherKeyCount = other.size();
1326         if (!otherKeyCount)
1327             return;
1328
1329         m_tableSize = computeBestTableSize(otherKeyCount);
1330         m_tableSizeMask = m_tableSize - 1;
1331         m_keyCount = otherKeyCount;
1332         m_table = allocateTable(m_tableSize);
1333
1334         for (const auto& otherValue : other)
1335             addUniqueForInitialization<IdentityTranslatorType>(Extractor::extract(otherValue), otherValue);
1336     }
1337
1338     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1339     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
1340     {
1341         invalidateIterators();
1342         other.invalidateIterators();
1343
1344         std::swap(m_table, other.m_table);
1345         std::swap(m_tableSize, other.m_tableSize);
1346         std::swap(m_tableSizeMask, other.m_tableSizeMask);
1347         std::swap(m_keyCount, other.m_keyCount);
1348         std::swap(m_deletedCount, other.m_deletedCount);
1349
1350 #if DUMP_HASHTABLE_STATS_PER_TABLE
1351         m_stats.swap(other.m_stats);
1352 #endif
1353     }
1354
1355     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1356     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other) -> HashTable&
1357     {
1358         HashTable tmp(other);
1359         swap(tmp);
1360         return *this;
1361     }
1362
1363     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1364     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(HashTable&& other)
1365 #if CHECK_HASHTABLE_ITERATORS
1366         : m_iterators(nullptr)
1367         , m_mutex(std::make_unique<Lock>())
1368 #endif
1369     {
1370         other.invalidateIterators();
1371
1372         m_table = other.m_table;
1373         m_tableSize = other.m_tableSize;
1374         m_tableSizeMask = other.m_tableSizeMask;
1375         m_keyCount = other.m_keyCount;
1376         m_deletedCount = other.m_deletedCount;
1377
1378         other.m_table = nullptr;
1379         other.m_tableSize = 0;
1380         other.m_tableSizeMask = 0;
1381         other.m_keyCount = 0;
1382         other.m_deletedCount = 0;
1383
1384 #if DUMP_HASHTABLE_STATS_PER_TABLE
1385         m_stats = WTFMove(other.m_stats);
1386         other.m_stats = nullptr;
1387 #endif
1388     }
1389
1390     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1391     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(HashTable&& other) -> HashTable&
1392     {
1393         HashTable temp = WTFMove(other);
1394         swap(temp);
1395         return *this;
1396     }
1397
1398 #if !ASSERT_DISABLED
1399
1400     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1401     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
1402     {
1403         checkTableConsistencyExceptSize();
1404         ASSERT(!m_table || !shouldExpand());
1405         ASSERT(!shouldShrink());
1406     }
1407
1408     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1409     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
1410     {
1411         if (!m_table)
1412             return;
1413
1414         unsigned count = 0;
1415         unsigned deletedCount = 0;
1416         for (unsigned j = 0; j < m_tableSize; ++j) {
1417             ValueType* entry = m_table + j;
1418             if (isEmptyBucket(*entry))
1419                 continue;
1420
1421             if (isDeletedBucket(*entry)) {
1422                 ++deletedCount;
1423                 continue;
1424             }
1425
1426             auto& key = Extractor::extract(*entry);
1427             const_iterator it = find(key);
1428             ASSERT(entry == it.m_position);
1429             ++count;
1430
1431             ValueCheck<Key>::checkConsistency(key);
1432         }
1433
1434         ASSERT(count == m_keyCount);
1435         ASSERT(deletedCount == m_deletedCount);
1436         ASSERT(m_tableSize >= KeyTraits::minimumTableSize);
1437         ASSERT(m_tableSizeMask);
1438         ASSERT(m_tableSize == m_tableSizeMask + 1);
1439     }
1440
1441 #endif // ASSERT_DISABLED
1442
1443 #if CHECK_HASHTABLE_ITERATORS
1444
1445     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1446     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
1447     {
1448         std::lock_guard<Lock> lock(*m_mutex);
1449         const_iterator* next;
1450         for (const_iterator* p = m_iterators; p; p = next) {
1451             next = p->m_next;
1452             p->m_table = 0;
1453             p->m_next = 0;
1454             p->m_previous = 0;
1455         }
1456         m_iterators = 0;
1457     }
1458
1459     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1460     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
1461         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1462     {
1463         it->m_table = table;
1464         it->m_previous = 0;
1465
1466         // Insert iterator at head of doubly-linked list of iterators.
1467         if (!table) {
1468             it->m_next = 0;
1469         } else {
1470             std::lock_guard<Lock> lock(*table->m_mutex);
1471             ASSERT(table->m_iterators != it);
1472             it->m_next = table->m_iterators;
1473             table->m_iterators = it;
1474             if (it->m_next) {
1475                 ASSERT(!it->m_next->m_previous);
1476                 it->m_next->m_previous = it;
1477             }
1478         }
1479     }
1480
1481     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1482     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1483     {
1484         // Delete iterator from doubly-linked list of iterators.
1485         if (!it->m_table) {
1486             ASSERT(!it->m_next);
1487             ASSERT(!it->m_previous);
1488         } else {
1489             std::lock_guard<Lock> lock(*it->m_table->m_mutex);
1490             if (it->m_next) {
1491                 ASSERT(it->m_next->m_previous == it);
1492                 it->m_next->m_previous = it->m_previous;
1493             }
1494             if (it->m_previous) {
1495                 ASSERT(it->m_table->m_iterators != it);
1496                 ASSERT(it->m_previous->m_next == it);
1497                 it->m_previous->m_next = it->m_next;
1498             } else {
1499                 ASSERT(it->m_table->m_iterators == it);
1500                 it->m_table->m_iterators = it->m_next;
1501             }
1502         }
1503
1504         it->m_table = 0;
1505         it->m_next = 0;
1506         it->m_previous = 0;
1507     }
1508
1509 #endif // CHECK_HASHTABLE_ITERATORS
1510
1511     // iterator adapters
1512
1513     template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter : public std::iterator<std::forward_iterator_tag, ValueType, std::ptrdiff_t, const ValueType*, const ValueType&> {
1514         HashTableConstIteratorAdapter() {}
1515         HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
1516
1517         const ValueType* get() const { return (const ValueType*)m_impl.get(); }
1518         const ValueType& operator*() const { return *get(); }
1519         const ValueType* operator->() const { return get(); }
1520
1521         HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
1522         // postfix ++ intentionally omitted
1523
1524         typename HashTableType::const_iterator m_impl;
1525     };
1526
1527     template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter : public std::iterator<std::forward_iterator_tag, ValueType, std::ptrdiff_t, ValueType*, ValueType&> {
1528         HashTableIteratorAdapter() {}
1529         HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
1530
1531         ValueType* get() const { return (ValueType*)m_impl.get(); }
1532         ValueType& operator*() const { return *get(); }
1533         ValueType* operator->() const { return get(); }
1534
1535         HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
1536         // postfix ++ intentionally omitted
1537
1538         operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
1539             typename HashTableType::const_iterator i = m_impl;
1540             return i;
1541         }
1542
1543         typename HashTableType::iterator m_impl;
1544     };
1545
1546     template<typename T, typename U>
1547     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1548     {
1549         return a.m_impl == b.m_impl;
1550     }
1551
1552     template<typename T, typename U>
1553     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1554     {
1555         return a.m_impl != b.m_impl;
1556     }
1557
1558     template<typename T, typename U>
1559     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1560     {
1561         return a.m_impl == b.m_impl;
1562     }
1563
1564     template<typename T, typename U>
1565     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1566     {
1567         return a.m_impl != b.m_impl;
1568     }
1569
1570     // All 4 combinations of ==, != and Const,non const.
1571     template<typename T, typename U>
1572     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1573     {
1574         return a.m_impl == b.m_impl;
1575     }
1576
1577     template<typename T, typename U>
1578     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1579     {
1580         return a.m_impl != b.m_impl;
1581     }
1582
1583     template<typename T, typename U>
1584     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1585     {
1586         return a.m_impl == b.m_impl;
1587     }
1588
1589     template<typename T, typename U>
1590     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1591     {
1592         return a.m_impl != b.m_impl;
1593     }
1594
1595 } // namespace WTF
1596
1597 #include <wtf/HashIterators.h>