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