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