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