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