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