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