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