Remove some stray uses of OwnPtr and PassOwnPtr in WTF (outside of the template defin...
[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(0)
536         , m_tableSize(0)
537         , m_tableSizeMask(0)
538         , m_keyCount(0)
539         , m_deletedCount(0)
540 #if CHECK_HASHTABLE_ITERATORS
541         , m_iterators(0)
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     }
1154
1155     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1156     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
1157         : m_table(0)
1158         , m_tableSize(0)
1159         , m_tableSizeMask(0)
1160         , m_keyCount(0)
1161         , m_deletedCount(0)
1162 #if CHECK_HASHTABLE_ITERATORS
1163         , m_iterators(0)
1164         , m_mutex(std::make_unique<std::mutex>())
1165 #endif
1166 #if DUMP_HASHTABLE_STATS_PER_TABLE
1167         , m_stats(std::make_unique<Stats>(*other.m_stats))
1168 #endif
1169     {
1170         // Copy the hash table the dumb way, by adding each element to the new table.
1171         // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
1172         // FIXME: It's likely that this can be improved, for static analyses that use
1173         // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
1174         const_iterator end = other.end();
1175         for (const_iterator it = other.begin(); it != end; ++it)
1176             add(*it);
1177     }
1178
1179     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1180     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
1181     {
1182         invalidateIterators();
1183         other.invalidateIterators();
1184
1185         std::swap(m_table, other.m_table);
1186         std::swap(m_tableSize, other.m_tableSize);
1187         std::swap(m_tableSizeMask, other.m_tableSizeMask);
1188         std::swap(m_keyCount, other.m_keyCount);
1189         std::swap(m_deletedCount, other.m_deletedCount);
1190
1191 #if DUMP_HASHTABLE_STATS_PER_TABLE
1192         m_stats.swap(other.m_stats);
1193 #endif
1194     }
1195
1196     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1197     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other) -> HashTable&
1198     {
1199         // FIXME: It's likely that this can be improved, for static analyses that use
1200         // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
1201         HashTable tmp(other);
1202         swap(tmp);
1203         return *this;
1204     }
1205
1206     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1207     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(HashTable&& other)
1208 #if CHECK_HASHTABLE_ITERATORS
1209         : m_iterators(nullptr)
1210         , m_mutex(std::make_unique<std::mutex>())
1211 #endif
1212     {
1213         other.invalidateIterators();
1214
1215         m_table = other.m_table;
1216         m_tableSize = other.m_tableSize;
1217         m_tableSizeMask = other.m_tableSizeMask;
1218         m_keyCount = other.m_keyCount;
1219         m_deletedCount = other.m_deletedCount;
1220
1221         other.m_table = nullptr;
1222         other.m_tableSize = 0;
1223         other.m_tableSizeMask = 0;
1224         other.m_keyCount = 0;
1225         other.m_deletedCount = 0;
1226
1227 #if DUMP_HASHTABLE_STATS_PER_TABLE
1228         m_stats = WTF::move(other.m_stats);
1229         other.m_stats = nullptr;
1230 #endif
1231     }
1232
1233     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1234     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(HashTable&& other) -> HashTable&
1235     {
1236         HashTable temp = WTF::move(other);
1237         swap(temp);
1238         return *this;
1239     }
1240
1241 #if !ASSERT_DISABLED
1242
1243     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1244     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
1245     {
1246         checkTableConsistencyExceptSize();
1247         ASSERT(!m_table || !shouldExpand());
1248         ASSERT(!shouldShrink());
1249     }
1250
1251     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1252     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
1253     {
1254         if (!m_table)
1255             return;
1256
1257         unsigned count = 0;
1258         unsigned deletedCount = 0;
1259         for (unsigned j = 0; j < m_tableSize; ++j) {
1260             ValueType* entry = m_table + j;
1261             if (isEmptyBucket(*entry))
1262                 continue;
1263
1264             if (isDeletedBucket(*entry)) {
1265                 ++deletedCount;
1266                 continue;
1267             }
1268
1269             const_iterator it = find(Extractor::extract(*entry));
1270             ASSERT(entry == it.m_position);
1271             ++count;
1272
1273             ValueCheck<Key>::checkConsistency(it->key);
1274         }
1275
1276         ASSERT(count == m_keyCount);
1277         ASSERT(deletedCount == m_deletedCount);
1278         ASSERT(m_tableSize >= KeyTraits::minimumTableSize);
1279         ASSERT(m_tableSizeMask);
1280         ASSERT(m_tableSize == m_tableSizeMask + 1);
1281     }
1282
1283 #endif // ASSERT_DISABLED
1284
1285 #if CHECK_HASHTABLE_ITERATORS
1286
1287     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1288     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
1289     {
1290         std::lock_guard<std::mutex> lock(*m_mutex);
1291         const_iterator* next;
1292         for (const_iterator* p = m_iterators; p; p = next) {
1293             next = p->m_next;
1294             p->m_table = 0;
1295             p->m_next = 0;
1296             p->m_previous = 0;
1297         }
1298         m_iterators = 0;
1299     }
1300
1301     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1302     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
1303         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1304     {
1305         it->m_table = table;
1306         it->m_previous = 0;
1307
1308         // Insert iterator at head of doubly-linked list of iterators.
1309         if (!table) {
1310             it->m_next = 0;
1311         } else {
1312             std::lock_guard<std::mutex> lock(*table->m_mutex);
1313             ASSERT(table->m_iterators != it);
1314             it->m_next = table->m_iterators;
1315             table->m_iterators = it;
1316             if (it->m_next) {
1317                 ASSERT(!it->m_next->m_previous);
1318                 it->m_next->m_previous = it;
1319             }
1320         }
1321     }
1322
1323     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1324     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1325     {
1326         // Delete iterator from doubly-linked list of iterators.
1327         if (!it->m_table) {
1328             ASSERT(!it->m_next);
1329             ASSERT(!it->m_previous);
1330         } else {
1331             std::lock_guard<std::mutex> lock(*it->m_table->m_mutex);
1332             if (it->m_next) {
1333                 ASSERT(it->m_next->m_previous == it);
1334                 it->m_next->m_previous = it->m_previous;
1335             }
1336             if (it->m_previous) {
1337                 ASSERT(it->m_table->m_iterators != it);
1338                 ASSERT(it->m_previous->m_next == it);
1339                 it->m_previous->m_next = it->m_next;
1340             } else {
1341                 ASSERT(it->m_table->m_iterators == it);
1342                 it->m_table->m_iterators = it->m_next;
1343             }
1344         }
1345
1346         it->m_table = 0;
1347         it->m_next = 0;
1348         it->m_previous = 0;
1349     }
1350
1351 #endif // CHECK_HASHTABLE_ITERATORS
1352
1353     // iterator adapters
1354
1355     template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
1356         HashTableConstIteratorAdapter() {}
1357         HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
1358
1359         const ValueType* get() const { return (const ValueType*)m_impl.get(); }
1360         const ValueType& operator*() const { return *get(); }
1361         const ValueType* operator->() const { return get(); }
1362
1363         HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
1364         // postfix ++ intentionally omitted
1365
1366         typename HashTableType::const_iterator m_impl;
1367     };
1368
1369     template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
1370         HashTableIteratorAdapter() {}
1371         HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
1372
1373         ValueType* get() const { return (ValueType*)m_impl.get(); }
1374         ValueType& operator*() const { return *get(); }
1375         ValueType* operator->() const { return get(); }
1376
1377         HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
1378         // postfix ++ intentionally omitted
1379
1380         operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
1381             typename HashTableType::const_iterator i = m_impl;
1382             return i;
1383         }
1384
1385         typename HashTableType::iterator m_impl;
1386     };
1387
1388     template<typename T, typename U>
1389     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1390     {
1391         return a.m_impl == b.m_impl;
1392     }
1393
1394     template<typename T, typename U>
1395     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1396     {
1397         return a.m_impl != b.m_impl;
1398     }
1399
1400     template<typename T, typename U>
1401     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1402     {
1403         return a.m_impl == b.m_impl;
1404     }
1405
1406     template<typename T, typename U>
1407     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1408     {
1409         return a.m_impl != b.m_impl;
1410     }
1411
1412     // All 4 combinations of ==, != and Const,non const.
1413     template<typename T, typename U>
1414     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1415     {
1416         return a.m_impl == b.m_impl;
1417     }
1418
1419     template<typename T, typename U>
1420     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1421     {
1422         return a.m_impl != b.m_impl;
1423     }
1424
1425     template<typename T, typename U>
1426     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1427     {
1428         return a.m_impl == b.m_impl;
1429     }
1430
1431     template<typename T, typename U>
1432     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1433     {
1434         return a.m_impl != b.m_impl;
1435     }
1436
1437 } // namespace WTF
1438
1439 #include <wtf/HashIterators.h>
1440
1441 #endif // WTF_HashTable_h