1 /*

     2  * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.

     3  * Copyright (C) 2008 David Levin <levin@chromium.org>

     4  *

     5  * This library is free software; you can redistribute it and/or

     6  * modify it under the terms of the GNU Library General Public

     7  * License as published by the Free Software Foundation; either

     8  * version 2 of the License, or (at your option) any later version.

     9  *

    10  * This library is distributed in the hope that it will be useful,

    11  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    13  * Library General Public License for more details.

    14  *

    15  * You should have received a copy of the GNU Library General Public License

    16  * along with this library; see the file COPYING.LIB.  If not, write to

    17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

    18  * Boston, MA 02110-1301, USA.

    19  *

    20  */

    21 

    22 #ifndef WTF_HashTable_h

    23 #define WTF_HashTable_h

    24 

    25 #include "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 #if !COMPILER(MSVC)

   263     // Visual C++ has a swap for pairs defined.

   264 

   265     // swap pairs by component, in case of pair members that specialize swap

   266     template<typename T, typename U> inline void swap(pair<T, U>& a, pair<T, U>& b)

   267     {

   268         swap(a.first, b.first);

   269         swap(a.second, b.second);

   270     }

   271 #endif

   272 

   273     template<typename T, bool useSwap> struct Mover;

   274     template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { swap(from, to); } };

   275     template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } };

   276 

   277     template<typename Key, typename Value, typename HashFunctions> class IdentityHashTranslator {

   278     public:

   279         static unsigned hash(const Key& key) { return HashFunctions::hash(key); }

   280         static bool equal(const Key& a, const Key& b) { return HashFunctions::equal(a, b); }

   281         static void translate(Value& location, const Key&, const Value& value) { location = value; }

   282     };

   283 

   284     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   285     class HashTable {

   286     public:

   287         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;

   288         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;

   289         typedef Traits ValueTraits;

   290         typedef Key KeyType;

   291         typedef Value ValueType;

   292         typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType;

   293 

   294         HashTable();

   295         ~HashTable() 

   296         {

   297             invalidateIterators(); 

   298             deallocateTable(m_table, m_tableSize); 

   299 #if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION

   300             m_table = (ValueType*)(uintptr_t)0xbbadbeef;

   301 #endif

   302         }

   303 

   304         HashTable(const HashTable&);

   305         void swap(HashTable&);

   306         HashTable& operator=(const HashTable&);

   307 

   308         iterator begin() { return makeIterator(m_table); }

   309         iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }

   310         const_iterator begin() const { return makeConstIterator(m_table); }

   311         const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }

   312 

   313         int size() const { return m_keyCount; }

   314         int capacity() const { return m_tableSize; }

   315         bool isEmpty() const { return !m_keyCount; }

   316 

   317         pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }

   318 

   319         // A special version of add() that finds the object by hashing and comparing

   320         // with some other type, to avoid the cost of type conversion if the object is already

   321         // in the table.

   322         template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&);

   323         template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> addPassingHashCode(const T& key, const Extra&);

   324 

   325         iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); }

   326         const_iterator find(const KeyType& key) const { return find<KeyType, IdentityTranslatorType>(key); }

   327         bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); }

   328 

   329         template <typename T, typename HashTranslator> iterator find(const T&);

   330         template <typename T, typename HashTranslator> const_iterator find(const T&) const;

   331         template <typename T, typename HashTranslator> bool contains(const T&) const;

   332 

   333         void remove(const KeyType&);

   334         void remove(iterator);

   335         void removeWithoutEntryConsistencyCheck(iterator);

   336         void removeWithoutEntryConsistencyCheck(const_iterator);

   337         void clear();

   338 

   339         static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); }

   340         static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }

   341         static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }

   342 

   343         ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); }

   344         template<typename T, typename HashTranslator> ValueType* lookup(const T&);

   345 

   346 #if !ASSERT_DISABLED

   347         void checkTableConsistency() const;

   348 #else

   349         static void checkTableConsistency() { }

   350 #endif

   351 #if CHECK_HASHTABLE_CONSISTENCY

   352         void internalCheckTableConsistency() const { checkTableConsistency(); }

   353         void internalCheckTableConsistencyExceptSize() const { checkTableConsistencyExceptSize(); }

   354 #else

   355         static void internalCheckTableConsistencyExceptSize() { }

   356         static void internalCheckTableConsistency() { }

   357 #endif

   358 

   359     private:

   360         static ValueType* allocateTable(int size);

   361         static void deallocateTable(ValueType* table, int size);

   362 

   363         typedef pair<ValueType*, bool> LookupType;

   364         typedef pair<LookupType, unsigned> FullLookupType;

   365 

   366         LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); };

   367         template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&);

   368         template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&);

   369 

   370         template<typename T, typename HashTranslator> void checkKey(const T&);

   371 

   372         void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);

   373         void removeAndInvalidate(ValueType*);

   374         void remove(ValueType*);

   375 

   376         bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }

   377         bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }

   378         bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; }

   379         void expand();

   380         void shrink() { rehash(m_tableSize / 2); }

   381 

   382         void rehash(int newTableSize);

   383         void reinsert(ValueType&);

   384 

   385         static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }

   386         static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); }

   387 

   388         FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)

   389             { return FullLookupType(LookupType(position, found), hash); }

   390 

   391         iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }

   392         const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }

   393         iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }

   394         const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }

   395 

   396 #if !ASSERT_DISABLED

   397         void checkTableConsistencyExceptSize() const;

   398 #else

   399         static void checkTableConsistencyExceptSize() { }

   400 #endif

   401 

   402 #if CHECK_HASHTABLE_ITERATORS

   403         void invalidateIterators();

   404 #else

   405         static void invalidateIterators() { }

   406 #endif

   407 

   408         static const int m_minTableSize = 64;

   409         static const int m_maxLoad = 2;

   410         static const int m_minLoad = 6;

   411 

   412         ValueType* m_table;

   413         int m_tableSize;

   414         int m_tableSizeMask;

   415         int m_keyCount;

   416         int m_deletedCount;

   417 

   418 #if CHECK_HASHTABLE_ITERATORS

   419     public:

   420         // All access to m_iterators should be guarded with m_mutex.

   421         mutable const_iterator* m_iterators;

   422         mutable Mutex m_mutex;

   423 #endif

   424     };

   425 

   426     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   427     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()

   428         : m_table(0)

   429         , m_tableSize(0)

   430         , m_tableSizeMask(0)

   431         , m_keyCount(0)

   432         , m_deletedCount(0)

   433 #if CHECK_HASHTABLE_ITERATORS

   434         , m_iterators(0)

   435 #endif

   436     {

   437     }

   438 

   439     static inline unsigned doubleHash(unsigned key)

   440     {

   441         key = ~key + (key >> 23);

   442         key ^= (key << 12);

   443         key ^= (key >> 7);

   444         key ^= (key << 2);

   445         key ^= (key >> 20);

   446         return key;

   447     }

   448 

   449 #if ASSERT_DISABLED

   450 

   451     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   452     template<typename T, typename HashTranslator>

   453     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)

   454     {

   455     }

   456 

   457 #else

   458 

   459     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   460     template<typename T, typename HashTranslator>

   461     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)

   462     {

   463         if (!HashFunctions::safeToCompareToEmptyOrDeleted)

   464             return;

   465         ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));

   466         ValueType deletedValue = Traits::emptyValue();

   467         deletedValue.~ValueType();

   468         Traits::constructDeletedValue(deletedValue);

   469         ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));

   470         new (&deletedValue) ValueType(Traits::emptyValue());

   471     }

   472 

   473 #endif

   474 

   475     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   476     template<typename T, typename HashTranslator>

   477     inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)

   478     {

   479         checkKey<T, HashTranslator>(key);

   480 

   481         int k = 0;

   482         int sizeMask = m_tableSizeMask;

   483         ValueType* table = m_table;

   484         unsigned h = HashTranslator::hash(key);

   485         int i = h & sizeMask;

   486 

   487         if (!table)

   488             return 0;

   489 

   490 #if DUMP_HASHTABLE_STATS

   491         atomicIncrement(&HashTableStats::numAccesses);

   492         int probeCount = 0;

   493 #endif

   494 

   495         while (1) {

   496             ValueType* entry = table + i;

   497                 

   498             // we count on the compiler to optimize out this branch

   499             if (HashFunctions::safeToCompareToEmptyOrDeleted) {

   500                 if (HashTranslator::equal(Extractor::extract(*entry), key))

   501                     return entry;

   502                 

   503                 if (isEmptyBucket(*entry))

   504                     return 0;

   505             } else {

   506                 if (isEmptyBucket(*entry))

   507                     return 0;

   508                 

   509                 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))

   510                     return entry;

   511             }

   512 #if DUMP_HASHTABLE_STATS

   513             ++probeCount;

   514             HashTableStats::recordCollisionAtCount(probeCount);

   515 #endif

   516             if (k == 0)

   517                 k = 1 | doubleHash(h);

   518             i = (i + k) & sizeMask;

   519         }

   520     }

   521 

   522     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   523     template<typename T, typename HashTranslator>

   524     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key)

   525     {

   526         ASSERT(m_table);

   527         checkKey<T, HashTranslator>(key);

   528 

   529         int k = 0;

   530         ValueType* table = m_table;

   531         int sizeMask = m_tableSizeMask;

   532         unsigned h = HashTranslator::hash(key);

   533         int i = h & sizeMask;

   534 

   535 #if DUMP_HASHTABLE_STATS

   536         atomicIncrement(&HashTableStats::numAccesses);

   537         int probeCount = 0;

   538 #endif

   539 

   540         ValueType* deletedEntry = 0;

   541 

   542         while (1) {

   543             ValueType* entry = table + i;

   544             

   545             // we count on the compiler to optimize out this branch

   546             if (HashFunctions::safeToCompareToEmptyOrDeleted) {

   547                 if (isEmptyBucket(*entry))

   548                     return LookupType(deletedEntry ? deletedEntry : entry, false);

   549                 

   550                 if (HashTranslator::equal(Extractor::extract(*entry), key))

   551                     return LookupType(entry, true);

   552                 

   553                 if (isDeletedBucket(*entry))

   554                     deletedEntry = entry;

   555             } else {

   556                 if (isEmptyBucket(*entry))

   557                     return LookupType(deletedEntry ? deletedEntry : entry, false);

   558             

   559                 if (isDeletedBucket(*entry))

   560                     deletedEntry = entry;

   561                 else if (HashTranslator::equal(Extractor::extract(*entry), key))

   562                     return LookupType(entry, true);

   563             }

   564 #if DUMP_HASHTABLE_STATS

   565             ++probeCount;

   566             HashTableStats::recordCollisionAtCount(probeCount);

   567 #endif

   568             if (k == 0)

   569                 k = 1 | doubleHash(h);

   570             i = (i + k) & sizeMask;

   571         }

   572     }

   573 

   574     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   575     template<typename T, typename HashTranslator>

   576     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key)

   577     {

   578         ASSERT(m_table);

   579         checkKey<T, HashTranslator>(key);

   580 

   581         int k = 0;

   582         ValueType* table = m_table;

   583         int sizeMask = m_tableSizeMask;

   584         unsigned h = HashTranslator::hash(key);

   585         int i = h & sizeMask;

   586 

   587 #if DUMP_HASHTABLE_STATS

   588         atomicIncrement(&HashTableStats::numAccesses);

   589         int probeCount = 0;

   590 #endif

   591 

   592         ValueType* deletedEntry = 0;

   593 

   594         while (1) {

   595             ValueType* entry = table + i;

   596             

   597             // we count on the compiler to optimize out this branch

   598             if (HashFunctions::safeToCompareToEmptyOrDeleted) {

   599                 if (isEmptyBucket(*entry))

   600                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);

   601                 

   602                 if (HashTranslator::equal(Extractor::extract(*entry), key))

   603                     return makeLookupResult(entry, true, h);

   604                 

   605                 if (isDeletedBucket(*entry))

   606                     deletedEntry = entry;

   607             } else {

   608                 if (isEmptyBucket(*entry))

   609                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);

   610             

   611                 if (isDeletedBucket(*entry))

   612                     deletedEntry = entry;

   613                 else if (HashTranslator::equal(Extractor::extract(*entry), key))

   614                     return makeLookupResult(entry, true, h);

   615             }

   616 #if DUMP_HASHTABLE_STATS

   617             ++probeCount;

   618             HashTableStats::recordCollisionAtCount(probeCount);

   619 #endif

   620             if (k == 0)

   621                 k = 1 | doubleHash(h);

   622             i = (i + k) & sizeMask;

   623         }

   624     }

   625 

   626     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   627     template<typename T, typename Extra, typename HashTranslator>

   628     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)

   629     {

   630         checkKey<T, HashTranslator>(key);

   631 

   632         invalidateIterators();

   633 

   634         if (!m_table)

   635             expand();

   636 

   637         internalCheckTableConsistency();

   638 

   639         ASSERT(m_table);

   640 

   641         int k = 0;

   642         ValueType* table = m_table;

   643         int sizeMask = m_tableSizeMask;

   644         unsigned h = HashTranslator::hash(key);

   645         int i = h & sizeMask;

   646 

   647 #if DUMP_HASHTABLE_STATS

   648         atomicIncrement(&HashTableStats::numAccesses);

   649         int probeCount = 0;

   650 #endif

   651 

   652         ValueType* deletedEntry = 0;

   653         ValueType* entry;

   654         while (1) {

   655             entry = table + i;

   656             

   657             // we count on the compiler to optimize out this branch

   658             if (HashFunctions::safeToCompareToEmptyOrDeleted) {

   659                 if (isEmptyBucket(*entry))

   660                     break;

   661                 

   662                 if (HashTranslator::equal(Extractor::extract(*entry), key))

   663                     return std::make_pair(makeKnownGoodIterator(entry), false);

   664                 

   665                 if (isDeletedBucket(*entry))

   666                     deletedEntry = entry;

   667             } else {

   668                 if (isEmptyBucket(*entry))

   669                     break;

   670             

   671                 if (isDeletedBucket(*entry))

   672                     deletedEntry = entry;

   673                 else if (HashTranslator::equal(Extractor::extract(*entry), key))

   674                     return std::make_pair(makeKnownGoodIterator(entry), false);

   675             }

   676 #if DUMP_HASHTABLE_STATS

   677             ++probeCount;

   678             HashTableStats::recordCollisionAtCount(probeCount);

   679 #endif

   680             if (k == 0)

   681                 k = 1 | doubleHash(h);

   682             i = (i + k) & sizeMask;

   683         }

   684 

   685         if (deletedEntry) {

   686             initializeBucket(*deletedEntry);

   687             entry = deletedEntry;

   688             --m_deletedCount; 

   689         }

   690 

   691         HashTranslator::translate(*entry, key, extra);

   692 

   693         ++m_keyCount;

   694         

   695         if (shouldExpand()) {

   696             // FIXME: This makes an extra copy on expand. Probably not that bad since

   697             // expand is rare, but would be better to have a version of expand that can

   698             // follow a pivot entry and return the new position.

   699             KeyType enteredKey = Extractor::extract(*entry);

   700             expand();

   701             pair<iterator, bool> p = std::make_pair(find(enteredKey), true);

   702             ASSERT(p.first != end());

   703             return p;

   704         }

   705         

   706         internalCheckTableConsistency();

   707         

   708         return std::make_pair(makeKnownGoodIterator(entry), true);

   709     }

   710 

   711     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   712     template<typename T, typename Extra, typename HashTranslator>

   713     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)

   714     {

   715         checkKey<T, HashTranslator>(key);

   716 

   717         invalidateIterators();

   718 

   719         if (!m_table)

   720             expand();

   721 

   722         internalCheckTableConsistency();

   723 

   724         FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key);

   725 

   726         ValueType* entry = lookupResult.first.first;

   727         bool found = lookupResult.first.second;

   728         unsigned h = lookupResult.second;

   729         

   730         if (found)

   731             return std::make_pair(makeKnownGoodIterator(entry), false);

   732         

   733         if (isDeletedBucket(*entry)) {

   734             initializeBucket(*entry);

   735             --m_deletedCount;

   736         }

   737         

   738         HashTranslator::translate(*entry, key, extra, h);

   739         ++m_keyCount;

   740         if (shouldExpand()) {

   741             // FIXME: This makes an extra copy on expand. Probably not that bad since

   742             // expand is rare, but would be better to have a version of expand that can

   743             // follow a pivot entry and return the new position.

   744             KeyType enteredKey = Extractor::extract(*entry);

   745             expand();

   746             pair<iterator, bool> p = std::make_pair(find(enteredKey), true);

   747             ASSERT(p.first != end());

   748             return p;

   749         }

   750 

   751         internalCheckTableConsistency();

   752 

   753         return std::make_pair(makeKnownGoodIterator(entry), true);

   754     }

   755 

   756     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   757     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)

   758     {

   759         ASSERT(m_table);

   760         ASSERT(!lookupForWriting(Extractor::extract(entry)).second);

   761         ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));

   762 #if DUMP_HASHTABLE_STATS

   763         atomicIncrement(&HashTableStats::numReinserts);

   764 #endif

   765 

   766         Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first);

   767     }

   768 

   769     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   770     template <typename T, typename HashTranslator> 

   771     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key)

   772     {

   773         if (!m_table)

   774             return end();

   775 

   776         ValueType* entry = lookup<T, HashTranslator>(key);

   777         if (!entry)

   778             return end();

   779 

   780         return makeKnownGoodIterator(entry);

   781     }

   782 

   783     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   784     template <typename T, typename HashTranslator> 

   785     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const

   786     {

   787         if (!m_table)

   788             return end();

   789 

   790         ValueType* entry = const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);

   791         if (!entry)

   792             return end();

   793 

   794         return makeKnownGoodConstIterator(entry);

   795     }

   796 

   797     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   798     template <typename T, typename HashTranslator> 

   799     bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const

   800     {

   801         if (!m_table)

   802             return false;

   803 

   804         return const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);

   805     }

   806 

   807     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   808     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos)

   809     {

   810         invalidateIterators();

   811         remove(pos);

   812     }

   813 

   814     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   815     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos)

   816     {

   817         invalidateIterators();

   818         internalCheckTableConsistency();

   819         remove(pos);

   820     }

   821 

   822     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   823     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)

   824     {

   825 #if DUMP_HASHTABLE_STATS

   826         atomicIncrement(&HashTableStats::numRemoves);

   827 #endif

   828 

   829         deleteBucket(*pos);

   830         ++m_deletedCount;

   831         --m_keyCount;

   832 

   833         if (shouldShrink())

   834             shrink();

   835 

   836         internalCheckTableConsistency();

   837     }

   838 

   839     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   840     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)

   841     {

   842         if (it == end())

   843             return;

   844 

   845         removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position));

   846     }

   847 

   848     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   849     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it)

   850     {

   851         if (it == end())

   852             return;

   853 

   854         removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position));

   855     }

   856 

   857     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   858     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(const_iterator it)

   859     {

   860         if (it == end())

   861             return;

   862 

   863         removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_position));

   864     }

   865 

   866     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   867     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)

   868     {

   869         remove(find(key));

   870     }

   871 

   872     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   873     Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)

   874     {

   875         // would use a template member function with explicit specializations here, but

   876         // gcc doesn't appear to support that

   877         if (Traits::emptyValueIsZero)

   878             return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType)));

   879         ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));

   880         for (int i = 0; i < size; i++)

   881             initializeBucket(result[i]);

   882         return result;

   883     }

   884 

   885     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   886     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, int size)

   887     {

   888         if (Traits::needsDestruction) {

   889             for (int i = 0; i < size; ++i) {

   890                 if (!isDeletedBucket(table[i]))

   891                     table[i].~ValueType();

   892             }

   893         }

   894         fastFree(table);

   895     }

   896 

   897     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   898     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()

   899     {

   900         int newSize;

   901         if (m_tableSize == 0)

   902             newSize = m_minTableSize;

   903         else if (mustRehashInPlace())

   904             newSize = m_tableSize;

   905         else

   906             newSize = m_tableSize * 2;

   907 

   908         rehash(newSize);

   909     }

   910 

   911     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   912     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize)

   913     {

   914         internalCheckTableConsistencyExceptSize();

   915 

   916         int oldTableSize = m_tableSize;

   917         ValueType* oldTable = m_table;

   918 

   919 #if DUMP_HASHTABLE_STATS

   920         if (oldTableSize != 0)

   921             atomicIncrement(&HashTableStats::numRehashes);

   922 #endif

   923 

   924         m_tableSize = newTableSize;

   925         m_tableSizeMask = newTableSize - 1;

   926         m_table = allocateTable(newTableSize);

   927 

   928         for (int i = 0; i != oldTableSize; ++i)

   929             if (!isEmptyOrDeletedBucket(oldTable[i]))

   930                 reinsert(oldTable[i]);

   931 

   932         m_deletedCount = 0;

   933 

   934         deallocateTable(oldTable, oldTableSize);

   935 

   936         internalCheckTableConsistency();

   937     }

   938 

   939     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   940     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()

   941     {

   942         invalidateIterators();

   943         deallocateTable(m_table, m_tableSize);

   944         m_table = 0;

   945         m_tableSize = 0;

   946         m_tableSizeMask = 0;

   947         m_keyCount = 0;

   948     }

   949 

   950     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   951     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)

   952         : m_table(0)

   953         , m_tableSize(0)

   954         , m_tableSizeMask(0)

   955         , m_keyCount(0)

   956         , m_deletedCount(0)

   957 #if CHECK_HASHTABLE_ITERATORS

   958         , m_iterators(0)

   959 #endif

   960     {

   961         // Copy the hash table the dumb way, by adding each element to the new table.

   962         // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.

   963         const_iterator end = other.end();

   964         for (const_iterator it = other.begin(); it != end; ++it)

   965             add(*it);

   966     }

   967 

   968     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   969     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)

   970     {

   971         invalidateIterators();

   972         other.invalidateIterators();

   973 

   974         ValueType* tmp_table = m_table;

   975         m_table = other.m_table;

   976         other.m_table = tmp_table;

   977 

   978         int tmp_tableSize = m_tableSize;

   979         m_tableSize = other.m_tableSize;

   980         other.m_tableSize = tmp_tableSize;

   981 

   982         int tmp_tableSizeMask = m_tableSizeMask;

   983         m_tableSizeMask = other.m_tableSizeMask;

   984         other.m_tableSizeMask = tmp_tableSizeMask;

   985 

   986         int tmp_keyCount = m_keyCount;

   987         m_keyCount = other.m_keyCount;

   988         other.m_keyCount = tmp_keyCount;

   989 

   990         int tmp_deletedCount = m_deletedCount;

   991         m_deletedCount = other.m_deletedCount;

   992         other.m_deletedCount = tmp_deletedCount;

   993     }

   994 

   995     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

   996     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)

   997     {

   998         HashTable tmp(other);

   999         swap(tmp);

  1000         return *this;

  1001     }

  1002 

  1003 #if !ASSERT_DISABLED

  1004 

  1005     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

  1006     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const

  1007     {

  1008         checkTableConsistencyExceptSize();

  1009         ASSERT(!m_table || !shouldExpand());

  1010         ASSERT(!shouldShrink());

  1011     }

  1012 

  1013     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

  1014     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const

  1015     {

  1016         if (!m_table)

  1017             return;

  1018 

  1019         int count = 0;

  1020         int deletedCount = 0;

  1021         for (int j = 0; j < m_tableSize; ++j) {

  1022             ValueType* entry = m_table + j;

  1023             if (isEmptyBucket(*entry))

  1024                 continue;

  1025 

  1026             if (isDeletedBucket(*entry)) {

  1027                 ++deletedCount;

  1028                 continue;

  1029             }

  1030 

  1031             const_iterator it = find(Extractor::extract(*entry));

  1032             ASSERT(entry == it.m_position);

  1033             ++count;

  1034 

  1035             ValueCheck<Key>::checkConsistency(it->first);

  1036         }

  1037 

  1038         ASSERT(count == m_keyCount);

  1039         ASSERT(deletedCount == m_deletedCount);

  1040         ASSERT(m_tableSize >= m_minTableSize);

  1041         ASSERT(m_tableSizeMask);

  1042         ASSERT(m_tableSize == m_tableSizeMask + 1);

  1043     }

  1044 

  1045 #endif // ASSERT_DISABLED

  1046 

  1047 #if CHECK_HASHTABLE_ITERATORS

  1048 

  1049     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

  1050     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()

  1051     {

  1052         MutexLocker lock(m_mutex);

  1053         const_iterator* next;

  1054         for (const_iterator* p = m_iterators; p; p = next) {

  1055             next = p->m_next;

  1056             p->m_table = 0;

  1057             p->m_next = 0;

  1058             p->m_previous = 0;

  1059         }

  1060         m_iterators = 0;

  1061     }

  1062 

  1063     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

  1064     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,

  1065         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)

  1066     {

  1067         it->m_table = table;

  1068         it->m_previous = 0;

  1069 

  1070         // Insert iterator at head of doubly-linked list of iterators.

  1071         if (!table) {

  1072             it->m_next = 0;

  1073         } else {

  1074             MutexLocker lock(table->m_mutex);

  1075             ASSERT(table->m_iterators != it);

  1076             it->m_next = table->m_iterators;

  1077             table->m_iterators = it;

  1078             if (it->m_next) {

  1079                 ASSERT(!it->m_next->m_previous);

  1080                 it->m_next->m_previous = it;

  1081             }

  1082         }

  1083     }

  1084 

  1085     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>

  1086     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)

  1087     {

  1088         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;

  1089         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;

  1090 

  1091         // Delete iterator from doubly-linked list of iterators.

  1092         if (!it->m_table) {

  1093             ASSERT(!it->m_next);

  1094             ASSERT(!it->m_previous);

  1095         } else {

  1096             MutexLocker lock(it->m_table->m_mutex);

  1097             if (it->m_next) {

  1098                 ASSERT(it->m_next->m_previous == it);

  1099                 it->m_next->m_previous = it->m_previous;

  1100             }

  1101             if (it->m_previous) {

  1102                 ASSERT(it->m_table->m_iterators != it);

  1103                 ASSERT(it->m_previous->m_next == it);

  1104                 it->m_previous->m_next = it->m_next;

  1105             } else {

  1106                 ASSERT(it->m_table->m_iterators == it);

  1107                 it->m_table->m_iterators = it->m_next;

  1108             }

  1109         }

  1110 

  1111         it->m_table = 0;

  1112         it->m_next = 0;

  1113         it->m_previous = 0;

  1114     }

  1115 

  1116 #endif // CHECK_HASHTABLE_ITERATORS

  1117 

  1118     // iterator adapters

  1119 

  1120     template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {

  1121         HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}

  1122 

  1123         const ValueType* get() const { return (const ValueType*)m_impl.get(); }

  1124         const ValueType& operator*() const { return *get(); }

  1125         const ValueType* operator->() const { return get(); }

  1126 

  1127         HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }

  1128         // postfix ++ intentionally omitted

  1129 

  1130         typename HashTableType::const_iterator m_impl;

  1131     };

  1132 

  1133     template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {

  1134         HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}

  1135