wtf/HashTable.h

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