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