Add WTF::move()
[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             int numAccesses;
317             int numRehashes;
318             int numRemoves;
319             int numReinserts;
320
321             int maxCollisions;
322             int numCollisions;
323             int collisionGraph[4096];
324
325             void recordCollisionAtCount(int 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 (int 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         // When the hash table is empty, just return the same iterator for end as for begin.
364         // This is more efficient because we don't have to skip all the empty and deleted
365         // buckets, and iterating an empty table is a common case that's worth optimizing.
366         iterator begin() { return isEmpty() ? end() : makeIterator(m_table); }
367         iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
368         const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); }
369         const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
370
371         int size() const { return m_keyCount; }
372         int capacity() const { return m_tableSize; }
373         bool isEmpty() const { return !m_keyCount; }
374
375         AddResult add(const ValueType& value) { return add<IdentityTranslatorType>(Extractor::extract(value), value); }
376         AddResult add(ValueType&& value) { return add<IdentityTranslatorType>(Extractor::extract(value), WTF::move(value)); }
377
378         // A special version of add() that finds the object by hashing and comparing
379         // with some other type, to avoid the cost of type conversion if the object is already
380         // in the table.
381         template<typename HashTranslator, typename T, typename Extra> AddResult add(T&& key, Extra&&);
382         template<typename HashTranslator, typename T, typename Extra> AddResult addPassingHashCode(T&& key, Extra&&);
383
384         iterator find(const KeyType& key) { return find<IdentityTranslatorType>(key); }
385         const_iterator find(const KeyType& key) const { return find<IdentityTranslatorType>(key); }
386         bool contains(const KeyType& key) const { return contains<IdentityTranslatorType>(key); }
387
388         template<typename HashTranslator, typename T> iterator find(const T&);
389         template<typename HashTranslator, typename T> const_iterator find(const T&) const;
390         template<typename HashTranslator, typename T> bool contains(const T&) const;
391
392         void remove(const KeyType&);
393         void remove(iterator);
394         void removeWithoutEntryConsistencyCheck(iterator);
395         void removeWithoutEntryConsistencyCheck(const_iterator);
396         void clear();
397
398         static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
399         static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
400         static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
401
402         ValueType* lookup(const Key& key) { return lookup<IdentityTranslatorType>(key); }
403         template<typename HashTranslator, typename T> ValueType* lookup(const T&);
404
405 #if !ASSERT_DISABLED
406         void checkTableConsistency() const;
407 #else
408         static void checkTableConsistency() { }
409 #endif
410 #if CHECK_HASHTABLE_CONSISTENCY
411         void internalCheckTableConsistency() const { checkTableConsistency(); }
412         void internalCheckTableConsistencyExceptSize() const { checkTableConsistencyExceptSize(); }
413 #else
414         static void internalCheckTableConsistencyExceptSize() { }
415         static void internalCheckTableConsistency() { }
416 #endif
417
418     private:
419         static ValueType* allocateTable(int size);
420         static void deallocateTable(ValueType* table, int size);
421
422         typedef std::pair<ValueType*, bool> LookupType;
423         typedef std::pair<LookupType, unsigned> FullLookupType;
424
425         LookupType lookupForWriting(const Key& key) { return lookupForWriting<IdentityTranslatorType>(key); };
426         template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&);
427         template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&);
428
429         template<typename HashTranslator, typename T> void checkKey(const T&);
430
431         void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
432         void removeAndInvalidate(ValueType*);
433         void remove(ValueType*);
434
435         bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
436         bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
437         bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; }
438         ValueType* expand(ValueType* entry = nullptr);
439         void shrink() { rehash(m_tableSize / 2, nullptr); }
440
441         ValueType* rehash(int newTableSize, ValueType* entry);
442         ValueType* reinsert(ValueType&&);
443
444         static void initializeBucket(ValueType& bucket);
445         static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); }
446
447         FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
448             { return FullLookupType(LookupType(position, found), hash); }
449
450         iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
451         const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
452         iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
453         const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
454
455 #if !ASSERT_DISABLED
456         void checkTableConsistencyExceptSize() const;
457 #else
458         static void checkTableConsistencyExceptSize() { }
459 #endif
460
461 #if CHECK_HASHTABLE_ITERATORS
462         void invalidateIterators();
463 #else
464         static void invalidateIterators() { }
465 #endif
466
467         static const int m_maxLoad = 2;
468         static const int m_minLoad = 6;
469
470         ValueType* m_table;
471         int m_tableSize;
472         int m_tableSizeMask;
473         int m_keyCount;
474         int m_deletedCount;
475
476 #if CHECK_HASHTABLE_ITERATORS
477     public:
478         // All access to m_iterators should be guarded with m_mutex.
479         mutable const_iterator* m_iterators;
480         // Use OwnPtr so HashTable can still be memmove'd or memcpy'ed.
481         mutable std::unique_ptr<std::mutex> m_mutex;
482 #endif
483
484 #if DUMP_HASHTABLE_STATS_PER_TABLE
485     public:
486         mutable std::unique_ptr<Stats> m_stats;
487 #endif
488     };
489
490     // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
491     template<unsigned size> struct OneifyLowBits;
492     template<>
493     struct OneifyLowBits<0> {
494         static const unsigned value = 0;
495     };
496     template<unsigned number>
497     struct OneifyLowBits {
498         static const unsigned value = number | OneifyLowBits<(number >> 1)>::value;
499     };
500     // Compute the first power of two integer that is an upper bound of the parameter 'number'.
501     template<unsigned number>
502     struct UpperPowerOfTwoBound {
503         static const unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2;
504     };
505
506     // Because power of two numbers are the limit of maxLoad, their capacity is twice the
507     // UpperPowerOfTwoBound, or 4 times their values.
508     template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter;
509     template<unsigned size>
510     struct HashTableCapacityForSizeSplitter<size, true> {
511         static const unsigned value = size * 4;
512     };
513     template<unsigned size>
514     struct HashTableCapacityForSizeSplitter<size, false> {
515         static const unsigned value = UpperPowerOfTwoBound<size>::value;
516     };
517
518     // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter.
519     // This is done at compile time to initialize the HashTraits.
520     template<unsigned size>
521     struct HashTableCapacityForSize {
522         static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
523         COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
524         COMPILE_ASSERT(!static_cast<int>(value >> 31), HashTableNoCapacityOverflow);
525         COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
526     };
527
528     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
529     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
530         : m_table(0)
531         , m_tableSize(0)
532         , m_tableSizeMask(0)
533         , m_keyCount(0)
534         , m_deletedCount(0)
535 #if CHECK_HASHTABLE_ITERATORS
536         , m_iterators(0)
537         , m_mutex(std::make_unique<std::mutex>())
538 #endif
539 #if DUMP_HASHTABLE_STATS_PER_TABLE
540         , m_stats(std::make_unique<Stats>())
541 #endif
542     {
543     }
544
545     inline unsigned doubleHash(unsigned key)
546     {
547         key = ~key + (key >> 23);
548         key ^= (key << 12);
549         key ^= (key >> 7);
550         key ^= (key << 2);
551         key ^= (key >> 20);
552         return key;
553     }
554
555 #if ASSERT_DISABLED
556
557     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
558     template<typename HashTranslator, typename T>
559     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
560     {
561     }
562
563 #else
564
565     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
566     template<typename HashTranslator, typename T>
567     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)
568     {
569         if (!HashFunctions::safeToCompareToEmptyOrDeleted)
570             return;
571         ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
572         typename std::aligned_storage<sizeof(ValueType), std::alignment_of<ValueType>::value>::type deletedValueBuffer;
573         ValueType* deletedValuePtr = reinterpret_cast_ptr<ValueType*>(&deletedValueBuffer);
574         ValueType& deletedValue = *deletedValuePtr;
575         Traits::constructDeletedValue(deletedValue);
576         ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
577     }
578
579 #endif
580
581     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
582     template<typename HashTranslator, typename T>
583     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key) -> ValueType*
584     {
585         checkKey<HashTranslator>(key);
586
587         int k = 0;
588         int sizeMask = m_tableSizeMask;
589         ValueType* table = m_table;
590         unsigned h = HashTranslator::hash(key);
591         int i = h & sizeMask;
592
593         if (!table)
594             return 0;
595
596 #if DUMP_HASHTABLE_STATS
597         ++HashTableStats::numAccesses;
598         unsigned probeCount = 0;
599 #endif
600
601 #if DUMP_HASHTABLE_STATS_PER_TABLE
602         ++m_stats->numAccesses;
603 #endif
604
605         while (1) {
606             ValueType* entry = table + i;
607                 
608             // we count on the compiler to optimize out this branch
609             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
610                 if (HashTranslator::equal(Extractor::extract(*entry), key))
611                     return entry;
612                 
613                 if (isEmptyBucket(*entry))
614                     return 0;
615             } else {
616                 if (isEmptyBucket(*entry))
617                     return 0;
618                 
619                 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
620                     return entry;
621             }
622 #if DUMP_HASHTABLE_STATS
623             ++probeCount;
624             HashTableStats::recordCollisionAtCount(probeCount);
625 #endif
626
627 #if DUMP_HASHTABLE_STATS_PER_TABLE
628             m_stats->recordCollisionAtCount(probeCount);
629 #endif
630
631             if (k == 0)
632                 k = 1 | doubleHash(h);
633             i = (i + k) & sizeMask;
634         }
635     }
636
637     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
638     template<typename HashTranslator, typename T>
639     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key) -> LookupType
640     {
641         ASSERT(m_table);
642         checkKey<HashTranslator>(key);
643
644         int k = 0;
645         ValueType* table = m_table;
646         int sizeMask = m_tableSizeMask;
647         unsigned h = HashTranslator::hash(key);
648         int i = h & sizeMask;
649
650 #if DUMP_HASHTABLE_STATS
651         ++HashTableStats::numAccesses;
652         int probeCount = 0;
653 #endif
654
655 #if DUMP_HASHTABLE_STATS_PER_TABLE
656         ++m_stats->numAccesses;
657 #endif
658
659         ValueType* deletedEntry = 0;
660
661         while (1) {
662             ValueType* entry = table + i;
663             
664             // we count on the compiler to optimize out this branch
665             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
666                 if (isEmptyBucket(*entry))
667                     return LookupType(deletedEntry ? deletedEntry : entry, false);
668                 
669                 if (HashTranslator::equal(Extractor::extract(*entry), key))
670                     return LookupType(entry, true);
671                 
672                 if (isDeletedBucket(*entry))
673                     deletedEntry = entry;
674             } else {
675                 if (isEmptyBucket(*entry))
676                     return LookupType(deletedEntry ? deletedEntry : entry, false);
677             
678                 if (isDeletedBucket(*entry))
679                     deletedEntry = entry;
680                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
681                     return LookupType(entry, true);
682             }
683 #if DUMP_HASHTABLE_STATS
684             ++probeCount;
685             HashTableStats::recordCollisionAtCount(probeCount);
686 #endif
687
688 #if DUMP_HASHTABLE_STATS_PER_TABLE
689             m_stats->recordCollisionAtCount(probeCount);
690 #endif
691
692             if (k == 0)
693                 k = 1 | doubleHash(h);
694             i = (i + k) & sizeMask;
695         }
696     }
697
698     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
699     template<typename HashTranslator, typename T>
700     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key) -> FullLookupType
701     {
702         ASSERT(m_table);
703         checkKey<HashTranslator>(key);
704
705         int k = 0;
706         ValueType* table = m_table;
707         int sizeMask = m_tableSizeMask;
708         unsigned h = HashTranslator::hash(key);
709         int i = h & sizeMask;
710
711 #if DUMP_HASHTABLE_STATS
712         ++HashTableStats::numAccesses;
713         unsigned probeCount = 0;
714 #endif
715
716 #if DUMP_HASHTABLE_STATS_PER_TABLE
717         ++m_stats->numAccesses;
718 #endif
719
720         ValueType* deletedEntry = 0;
721
722         while (1) {
723             ValueType* entry = table + i;
724             
725             // we count on the compiler to optimize out this branch
726             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
727                 if (isEmptyBucket(*entry))
728                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
729                 
730                 if (HashTranslator::equal(Extractor::extract(*entry), key))
731                     return makeLookupResult(entry, true, h);
732                 
733                 if (isDeletedBucket(*entry))
734                     deletedEntry = entry;
735             } else {
736                 if (isEmptyBucket(*entry))
737                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
738             
739                 if (isDeletedBucket(*entry))
740                     deletedEntry = entry;
741                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
742                     return makeLookupResult(entry, true, h);
743             }
744 #if DUMP_HASHTABLE_STATS
745             ++probeCount;
746             HashTableStats::recordCollisionAtCount(probeCount);
747 #endif
748
749 #if DUMP_HASHTABLE_STATS_PER_TABLE
750             m_stats->recordCollisionAtCount(probeCount);
751 #endif
752
753             if (k == 0)
754                 k = 1 | doubleHash(h);
755             i = (i + k) & sizeMask;
756         }
757     }
758
759     template<bool emptyValueIsZero> struct HashTableBucketInitializer;
760
761     template<> struct HashTableBucketInitializer<false> {
762         template<typename Traits, typename Value> static void initialize(Value& bucket)
763         {
764             new (NotNull, &bucket) Value(Traits::emptyValue());
765         }
766     };
767
768     template<> struct HashTableBucketInitializer<true> {
769         template<typename Traits, typename Value> static void initialize(Value& bucket)
770         {
771             // This initializes the bucket without copying the empty value.
772             // That makes it possible to use this with types that don't support copying.
773             // The memset to 0 looks like a slow operation but is optimized by the compilers.
774             memset(&bucket, 0, sizeof(bucket));
775         }
776     };
777     
778     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
779     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::initializeBucket(ValueType& bucket)
780     {
781         HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket);
782     }
783
784     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
785     template<typename HashTranslator, typename T, typename Extra>
786     ALWAYS_INLINE auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(T&& key, Extra&& extra) -> AddResult
787     {
788         checkKey<HashTranslator>(key);
789
790         invalidateIterators();
791
792         if (!m_table)
793             expand(nullptr);
794
795         internalCheckTableConsistency();
796
797         ASSERT(m_table);
798
799         int k = 0;
800         ValueType* table = m_table;
801         int sizeMask = m_tableSizeMask;
802         unsigned h = HashTranslator::hash(key);
803         int i = h & sizeMask;
804
805 #if DUMP_HASHTABLE_STATS
806         ++HashTableStats::numAccesses;
807         unsigned probeCount = 0;
808 #endif
809
810 #if DUMP_HASHTABLE_STATS_PER_TABLE
811         ++m_stats->numAccesses;
812 #endif
813
814         ValueType* deletedEntry = 0;
815         ValueType* entry;
816         while (1) {
817             entry = table + i;
818             
819             // we count on the compiler to optimize out this branch
820             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
821                 if (isEmptyBucket(*entry))
822                     break;
823                 
824                 if (HashTranslator::equal(Extractor::extract(*entry), key))
825                     return AddResult(makeKnownGoodIterator(entry), false);
826                 
827                 if (isDeletedBucket(*entry))
828                     deletedEntry = entry;
829             } else {
830                 if (isEmptyBucket(*entry))
831                     break;
832             
833                 if (isDeletedBucket(*entry))
834                     deletedEntry = entry;
835                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
836                     return AddResult(makeKnownGoodIterator(entry), false);
837             }
838 #if DUMP_HASHTABLE_STATS
839             ++probeCount;
840             HashTableStats::recordCollisionAtCount(probeCount);
841 #endif
842
843 #if DUMP_HASHTABLE_STATS_PER_TABLE
844             m_stats->recordCollisionAtCount(probeCount);
845 #endif
846
847             if (k == 0)
848                 k = 1 | doubleHash(h);
849             i = (i + k) & sizeMask;
850         }
851
852         if (deletedEntry) {
853             initializeBucket(*deletedEntry);
854             entry = deletedEntry;
855             --m_deletedCount; 
856         }
857
858         HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
859         ++m_keyCount;
860         
861         if (shouldExpand())
862             entry = expand(entry);
863
864         internalCheckTableConsistency();
865         
866         return AddResult(makeKnownGoodIterator(entry), true);
867     }
868
869     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
870     template<typename HashTranslator, typename T, typename Extra>
871     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addPassingHashCode(T&& key, Extra&& extra) -> AddResult
872     {
873         checkKey<HashTranslator>(key);
874
875         invalidateIterators();
876
877         if (!m_table)
878             expand();
879
880         internalCheckTableConsistency();
881
882         FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key);
883
884         ValueType* entry = lookupResult.first.first;
885         bool found = lookupResult.first.second;
886         unsigned h = lookupResult.second;
887         
888         if (found)
889             return AddResult(makeKnownGoodIterator(entry), false);
890         
891         if (isDeletedBucket(*entry)) {
892             initializeBucket(*entry);
893             --m_deletedCount;
894         }
895
896         HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra), h);
897         ++m_keyCount;
898
899         if (shouldExpand())
900             entry = expand(entry);
901
902         internalCheckTableConsistency();
903
904         return AddResult(makeKnownGoodIterator(entry), true);
905     }
906
907     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
908     inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType&& entry) -> ValueType*
909     {
910         ASSERT(m_table);
911         ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
912         ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
913 #if DUMP_HASHTABLE_STATS
914         ++HashTableStats::numReinserts;
915 #endif
916 #if DUMP_HASHTABLE_STATS_PER_TABLE
917         ++m_stats->numReinserts;
918 #endif
919
920         Value* newEntry = lookupForWriting(Extractor::extract(entry)).first;
921         newEntry->~Value();
922         new (NotNull, newEntry) ValueType(WTF::move(entry));
923
924         return newEntry;
925     }
926
927     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
928     template <typename HashTranslator, typename T> 
929     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) -> iterator
930     {
931         if (!m_table)
932             return end();
933
934         ValueType* entry = lookup<HashTranslator>(key);
935         if (!entry)
936             return end();
937
938         return makeKnownGoodIterator(entry);
939     }
940
941     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
942     template <typename HashTranslator, typename T> 
943     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const -> const_iterator
944     {
945         if (!m_table)
946             return end();
947
948         ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
949         if (!entry)
950             return end();
951
952         return makeKnownGoodConstIterator(entry);
953     }
954
955     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
956     template <typename HashTranslator, typename T> 
957     bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const
958     {
959         if (!m_table)
960             return false;
961
962         return const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
963     }
964
965     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
966     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos)
967     {
968         invalidateIterators();
969         remove(pos);
970     }
971
972     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
973     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos)
974     {
975         invalidateIterators();
976         internalCheckTableConsistency();
977         remove(pos);
978     }
979
980     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
981     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
982     {
983 #if DUMP_HASHTABLE_STATS
984         ++HashTableStats::numRemoves;
985 #endif
986 #if DUMP_HASHTABLE_STATS_PER_TABLE
987         ++m_stats->numRemoves;
988 #endif
989
990         deleteBucket(*pos);
991         ++m_deletedCount;
992         --m_keyCount;
993
994         if (shouldShrink())
995             shrink();
996
997         internalCheckTableConsistency();
998     }
999
1000     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1001     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
1002     {
1003         if (it == end())
1004             return;
1005
1006         removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position));
1007     }
1008
1009     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1010     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it)
1011     {
1012         if (it == end())
1013             return;
1014
1015         removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position));
1016     }
1017
1018     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1019     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(const_iterator it)
1020     {
1021         if (it == end())
1022             return;
1023
1024         removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_position));
1025     }
1026
1027     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1028     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
1029     {
1030         remove(find(key));
1031     }
1032
1033     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1034     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size) -> ValueType*
1035     {
1036         // would use a template member function with explicit specializations here, but
1037         // gcc doesn't appear to support that
1038         if (Traits::emptyValueIsZero)
1039             return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType)));
1040         ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
1041         for (int i = 0; i < size; i++)
1042             initializeBucket(result[i]);
1043         return result;
1044     }
1045
1046     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1047     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, int size)
1048     {
1049         for (int i = 0; i < size; ++i) {
1050             if (!isDeletedBucket(table[i]))
1051                 table[i].~ValueType();
1052         }
1053         fastFree(table);
1054     }
1055
1056     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1057     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand(ValueType* entry) -> ValueType*
1058     {
1059         int newSize;
1060         if (m_tableSize == 0)
1061             newSize = KeyTraits::minimumTableSize;
1062         else if (mustRehashInPlace())
1063             newSize = m_tableSize;
1064         else
1065             newSize = m_tableSize * 2;
1066
1067         return rehash(newSize, entry);
1068     }
1069
1070     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1071     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize, ValueType* entry) -> ValueType*
1072     {
1073         internalCheckTableConsistencyExceptSize();
1074
1075         int oldTableSize = m_tableSize;
1076         ValueType* oldTable = m_table;
1077
1078 #if DUMP_HASHTABLE_STATS
1079         if (oldTableSize != 0)
1080             ++HashTableStats::numRehashes;
1081 #endif
1082
1083 #if DUMP_HASHTABLE_STATS_PER_TABLE
1084         if (oldTableSize != 0)
1085             ++m_stats->numRehashes;
1086 #endif
1087
1088         m_tableSize = newTableSize;
1089         m_tableSizeMask = newTableSize - 1;
1090         m_table = allocateTable(newTableSize);
1091
1092         Value* newEntry = nullptr;
1093         for (int i = 0; i != oldTableSize; ++i) {
1094             if (isEmptyOrDeletedBucket(oldTable[i])) {
1095                 ASSERT(&oldTable[i] != entry);
1096                 continue;
1097             }
1098
1099             Value* reinsertedEntry = reinsert(WTF::move(oldTable[i]));
1100             if (&oldTable[i] == entry) {
1101                 ASSERT(!newEntry);
1102                 newEntry = reinsertedEntry;
1103             }
1104         }
1105
1106         m_deletedCount = 0;
1107
1108         deallocateTable(oldTable, oldTableSize);
1109
1110         internalCheckTableConsistency();
1111         return newEntry;
1112     }
1113
1114     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1115     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
1116     {
1117         invalidateIterators();
1118         if (!m_table)
1119             return;
1120
1121         deallocateTable(m_table, m_tableSize);
1122         m_table = 0;
1123         m_tableSize = 0;
1124         m_tableSizeMask = 0;
1125         m_keyCount = 0;
1126     }
1127
1128     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1129     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
1130         : m_table(0)
1131         , m_tableSize(0)
1132         , m_tableSizeMask(0)
1133         , m_keyCount(0)
1134         , m_deletedCount(0)
1135 #if CHECK_HASHTABLE_ITERATORS
1136         , m_iterators(0)
1137         , m_mutex(std::make_unique<std::mutex>())
1138 #endif
1139 #if DUMP_HASHTABLE_STATS_PER_TABLE
1140         , m_stats(std::make_unique<Stats>(*other.m_stats))
1141 #endif
1142     {
1143         // Copy the hash table the dumb way, by adding each element to the new table.
1144         // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
1145         // FIXME: It's likely that this can be improved, for static analyses that use
1146         // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
1147         const_iterator end = other.end();
1148         for (const_iterator it = other.begin(); it != end; ++it)
1149             add(*it);
1150     }
1151
1152     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1153     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
1154     {
1155         invalidateIterators();
1156         other.invalidateIterators();
1157
1158         std::swap(m_table, other.m_table);
1159         std::swap(m_tableSize, other.m_tableSize);
1160         std::swap(m_tableSizeMask, other.m_tableSizeMask);
1161         std::swap(m_keyCount, other.m_keyCount);
1162         std::swap(m_deletedCount, other.m_deletedCount);
1163
1164 #if DUMP_HASHTABLE_STATS_PER_TABLE
1165         m_stats.swap(other.m_stats);
1166 #endif
1167     }
1168
1169     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1170     auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other) -> HashTable&
1171     {
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         HashTable tmp(other);
1175         swap(tmp);
1176         return *this;
1177     }
1178
1179 #if !ASSERT_DISABLED
1180
1181     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1182     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
1183     {
1184         checkTableConsistencyExceptSize();
1185         ASSERT(!m_table || !shouldExpand());
1186         ASSERT(!shouldShrink());
1187     }
1188
1189     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1190     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
1191     {
1192         if (!m_table)
1193             return;
1194
1195         int count = 0;
1196         int deletedCount = 0;
1197         for (int j = 0; j < m_tableSize; ++j) {
1198             ValueType* entry = m_table + j;
1199             if (isEmptyBucket(*entry))
1200                 continue;
1201
1202             if (isDeletedBucket(*entry)) {
1203                 ++deletedCount;
1204                 continue;
1205             }
1206
1207             const_iterator it = find(Extractor::extract(*entry));
1208             ASSERT(entry == it.m_position);
1209             ++count;
1210
1211             ValueCheck<Key>::checkConsistency(it->key);
1212         }
1213
1214         ASSERT(count == m_keyCount);
1215         ASSERT(deletedCount == m_deletedCount);
1216         ASSERT(m_tableSize >= KeyTraits::minimumTableSize);
1217         ASSERT(m_tableSizeMask);
1218         ASSERT(m_tableSize == m_tableSizeMask + 1);
1219     }
1220
1221 #endif // ASSERT_DISABLED
1222
1223 #if CHECK_HASHTABLE_ITERATORS
1224
1225     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1226     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
1227     {
1228         std::lock_guard<std::mutex> lock(*m_mutex);
1229         const_iterator* next;
1230         for (const_iterator* p = m_iterators; p; p = next) {
1231             next = p->m_next;
1232             p->m_table = 0;
1233             p->m_next = 0;
1234             p->m_previous = 0;
1235         }
1236         m_iterators = 0;
1237     }
1238
1239     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1240     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
1241         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1242     {
1243         it->m_table = table;
1244         it->m_previous = 0;
1245
1246         // Insert iterator at head of doubly-linked list of iterators.
1247         if (!table) {
1248             it->m_next = 0;
1249         } else {
1250             std::lock_guard<std::mutex> lock(*table->m_mutex);
1251             ASSERT(table->m_iterators != it);
1252             it->m_next = table->m_iterators;
1253             table->m_iterators = it;
1254             if (it->m_next) {
1255                 ASSERT(!it->m_next->m_previous);
1256                 it->m_next->m_previous = it;
1257             }
1258         }
1259     }
1260
1261     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1262     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1263     {
1264         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
1265         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
1266
1267         // Delete iterator from doubly-linked list of iterators.
1268         if (!it->m_table) {
1269             ASSERT(!it->m_next);
1270             ASSERT(!it->m_previous);
1271         } else {
1272             std::lock_guard<std::mutex> lock(*it->m_table->m_mutex);
1273             if (it->m_next) {
1274                 ASSERT(it->m_next->m_previous == it);
1275                 it->m_next->m_previous = it->m_previous;
1276             }
1277             if (it->m_previous) {
1278                 ASSERT(it->m_table->m_iterators != it);
1279                 ASSERT(it->m_previous->m_next == it);
1280                 it->m_previous->m_next = it->m_next;
1281             } else {
1282                 ASSERT(it->m_table->m_iterators == it);
1283                 it->m_table->m_iterators = it->m_next;
1284             }
1285         }
1286
1287         it->m_table = 0;
1288         it->m_next = 0;
1289         it->m_previous = 0;
1290     }
1291
1292 #endif // CHECK_HASHTABLE_ITERATORS
1293
1294     // iterator adapters
1295
1296     template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
1297         HashTableConstIteratorAdapter() {}
1298         HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
1299
1300         const ValueType* get() const { return (const ValueType*)m_impl.get(); }
1301         const ValueType& operator*() const { return *get(); }
1302         const ValueType* operator->() const { return get(); }
1303
1304         HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
1305         // postfix ++ intentionally omitted
1306
1307         typename HashTableType::const_iterator m_impl;
1308     };
1309
1310     template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
1311         HashTableIteratorAdapter() {}
1312         HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
1313
1314         ValueType* get() const { return (ValueType*)m_impl.get(); }
1315         ValueType& operator*() const { return *get(); }
1316         ValueType* operator->() const { return get(); }
1317
1318         HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
1319         // postfix ++ intentionally omitted
1320
1321         operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
1322             typename HashTableType::const_iterator i = m_impl;
1323             return i;
1324         }
1325
1326         typename HashTableType::iterator m_impl;
1327     };
1328
1329     template<typename T, typename U>
1330     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1331     {
1332         return a.m_impl == b.m_impl;
1333     }
1334
1335     template<typename T, typename U>
1336     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1337     {
1338         return a.m_impl != b.m_impl;
1339     }
1340
1341     template<typename T, typename U>
1342     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1343     {
1344         return a.m_impl == b.m_impl;
1345     }
1346
1347     template<typename T, typename U>
1348     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1349     {
1350         return a.m_impl != b.m_impl;
1351     }
1352
1353     // All 4 combinations of ==, != and Const,non const.
1354     template<typename T, typename U>
1355     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1356     {
1357         return a.m_impl == b.m_impl;
1358     }
1359
1360     template<typename T, typename U>
1361     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1362     {
1363         return a.m_impl != b.m_impl;
1364     }
1365
1366     template<typename T, typename U>
1367     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1368     {
1369         return a.m_impl == b.m_impl;
1370     }
1371
1372     template<typename T, typename U>
1373     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1374     {
1375         return a.m_impl != b.m_impl;
1376     }
1377
1378 } // namespace WTF
1379
1380 #include <wtf/HashIterators.h>
1381
1382 #endif // WTF_HashTable_h