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