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 "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 clear();
 337
 338         static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); }
 339         static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
 340         static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
 341
 342         ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); }
 343         template<typename T, typename HashTranslator> ValueType* lookup(const T&);
 344
 345 #if !ASSERT_DISABLED
 346         void checkTableConsistency() const;
 347 #else
 348         static void checkTableConsistency() { }
 349 #endif
 350 #if CHECK_HASHTABLE_CONSISTENCY
 351         void internalCheckTableConsistency() const { checkTableConsistency(); }
 352         void internalCheckTableConsistencyExceptSize() const { checkTableConsistencyExceptSize(); }
 353 #else
 354         static void internalCheckTableConsistencyExceptSize() { }
 355         static void internalCheckTableConsistency() { }
 356 #endif
 357
 358     private:
 359         static ValueType* allocateTable(int size);
 360         static void deallocateTable(ValueType* table, int size);
 361
 362         typedef pair<ValueType*, bool> LookupType;
 363         typedef pair<LookupType, unsigned> FullLookupType;
 364
 365         LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); };
 366         template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&);
 367         template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&);
 368
 369         template<typename T, typename HashTranslator> void checkKey(const T&);
 370
 371         void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
 372         void removeAndInvalidate(ValueType*);
 373         void remove(ValueType*);
 374
 375         bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
 376         bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
 377         bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; }
 378         void expand();
 379         void shrink() { rehash(m_tableSize / 2); }
 380
 381         void rehash(int newTableSize);
 382         void reinsert(ValueType&);
 383
 384         static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }
 385         static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); }
 386
 387         FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
 388             { return FullLookupType(LookupType(position, found), hash); }
 389
 390         iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
 391         const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
 392         iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
 393         const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
 394
 395 #if !ASSERT_DISABLED
 396         void checkTableConsistencyExceptSize() const;
 397 #else
 398         static void checkTableConsistencyExceptSize() { }
 399 #endif
 400
 401 #if CHECK_HASHTABLE_ITERATORS
 402         void invalidateIterators();
 403 #else
 404         static void invalidateIterators() { }
 405 #endif
 406
 407         static const int m_minTableSize = 64;
 408         static const int m_maxLoad = 2;
 409         static const int m_minLoad = 6;
 410
 411         ValueType* m_table;
 412         int m_tableSize;
 413         int m_tableSizeMask;
 414         int m_keyCount;
 415         int m_deletedCount;
 416
 417 #if CHECK_HASHTABLE_ITERATORS
 418     public:
 419         // All access to m_iterators should be guarded with m_mutex.
 420         mutable const_iterator* m_iterators;
 421         mutable Mutex m_mutex;
 422 #endif
 423     };
 424
 425     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 426     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
 427         : m_table(0)
 428         , m_tableSize(0)
 429         , m_tableSizeMask(0)
 430         , m_keyCount(0)
 431         , m_deletedCount(0)
 432 #if CHECK_HASHTABLE_ITERATORS
 433         , m_iterators(0)
 434 #endif
 435     {
 436     }
 437
 438     static inline unsigned doubleHash(unsigned key)
 439     {
 440         key = ~key + (key >> 23);
 441         key ^= (key << 12);
 442         key ^= (key >> 7);
 443         key ^= (key << 2);
 444         key ^= (key >> 20);
 445         return key;
 446     }
 447
 448 #if ASSERT_DISABLED
 449
 450     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 451     template<typename T, typename HashTranslator>
 452     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
 453     {
 454     }
 455
 456 #else
 457
 458     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 459     template<typename T, typename HashTranslator>
 460     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)
 461     {
 462         if (!HashFunctions::safeToCompareToEmptyOrDeleted)
 463             return;
 464         ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
 465         ValueType deletedValue = Traits::emptyValue();
 466         deletedValue.~ValueType();
 467         Traits::constructDeletedValue(deletedValue);
 468         ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
 469         new (&deletedValue) ValueType(Traits::emptyValue());
 470     }
 471
 472 #endif
 473
 474     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 475     template<typename T, typename HashTranslator>
 476     inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
 477     {
 478         checkKey<T, HashTranslator>(key);
 479
 480         int k = 0;
 481         int sizeMask = m_tableSizeMask;
 482         ValueType* table = m_table;
 483         unsigned h = HashTranslator::hash(key);
 484         int i = h & sizeMask;
 485
 486         if (!table)
 487             return 0;
 488
 489 #if DUMP_HASHTABLE_STATS
 490         atomicIncrement(&HashTableStats::numAccesses);
 491         int probeCount = 0;
 492 #endif
 493
 494         while (1) {
 495             ValueType* entry = table + i;
 496
 497             // we count on the compiler to optimize out this branch
 498             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
 499                 if (HashTranslator::equal(Extractor::extract(*entry), key))
 500                     return entry;
 501
 502                 if (isEmptyBucket(*entry))
 503                     return 0;
 504             } else {
 505                 if (isEmptyBucket(*entry))
 506                     return 0;
 507
 508                 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
 509                     return entry;
 510             }
 511 #if DUMP_HASHTABLE_STATS
 512             ++probeCount;
 513             HashTableStats::recordCollisionAtCount(probeCount);
 514 #endif
 515             if (k == 0)
 516                 k = 1 | doubleHash(h);
 517             i = (i + k) & sizeMask;
 518         }
 519     }
 520
 521     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 522     template<typename T, typename HashTranslator>
 523     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key)
 524     {
 525         ASSERT(m_table);
 526         checkKey<T, HashTranslator>(key);
 527
 528         int k = 0;
 529         ValueType* table = m_table;
 530         int sizeMask = m_tableSizeMask;
 531         unsigned h = HashTranslator::hash(key);
 532         int i = h & sizeMask;
 533
 534 #if DUMP_HASHTABLE_STATS
 535         atomicIncrement(&HashTableStats::numAccesses);
 536         int probeCount = 0;
 537 #endif
 538
 539         ValueType* deletedEntry = 0;
 540
 541         while (1) {
 542             ValueType* entry = table + i;
 543
 544             // we count on the compiler to optimize out this branch
 545             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
 546                 if (isEmptyBucket(*entry))
 547                     return LookupType(deletedEntry ? deletedEntry : entry, false);
 548
 549                 if (HashTranslator::equal(Extractor::extract(*entry), key))
 550                     return LookupType(entry, true);
 551
 552                 if (isDeletedBucket(*entry))
 553                     deletedEntry = entry;
 554             } else {
 555                 if (isEmptyBucket(*entry))
 556                     return LookupType(deletedEntry ? deletedEntry : entry, false);
 557
 558                 if (isDeletedBucket(*entry))
 559                     deletedEntry = entry;
 560                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
 561                     return LookupType(entry, true);
 562             }
 563 #if DUMP_HASHTABLE_STATS
 564             ++probeCount;
 565             HashTableStats::recordCollisionAtCount(probeCount);
 566 #endif
 567             if (k == 0)
 568                 k = 1 | doubleHash(h);
 569             i = (i + k) & sizeMask;
 570         }
 571     }
 572
 573     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 574     template<typename T, typename HashTranslator>
 575     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key)
 576     {
 577         ASSERT(m_table);
 578         checkKey<T, HashTranslator>(key);
 579
 580         int k = 0;
 581         ValueType* table = m_table;
 582         int sizeMask = m_tableSizeMask;
 583         unsigned h = HashTranslator::hash(key);
 584         int i = h & sizeMask;
 585
 586 #if DUMP_HASHTABLE_STATS
 587         atomicIncrement(&HashTableStats::numAccesses);
 588         int probeCount = 0;
 589 #endif
 590
 591         ValueType* deletedEntry = 0;
 592
 593         while (1) {
 594             ValueType* entry = table + i;
 595
 596             // we count on the compiler to optimize out this branch
 597             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
 598                 if (isEmptyBucket(*entry))
 599                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
 600
 601                 if (HashTranslator::equal(Extractor::extract(*entry), key))
 602                     return makeLookupResult(entry, true, h);
 603
 604                 if (isDeletedBucket(*entry))
 605                     deletedEntry = entry;
 606             } else {
 607                 if (isEmptyBucket(*entry))
 608                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
 609
 610                 if (isDeletedBucket(*entry))
 611                     deletedEntry = entry;
 612                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
 613                     return makeLookupResult(entry, true, h);
 614             }
 615 #if DUMP_HASHTABLE_STATS
 616             ++probeCount;
 617             HashTableStats::recordCollisionAtCount(probeCount);
 618 #endif
 619             if (k == 0)
 620                 k = 1 | doubleHash(h);
 621             i = (i + k) & sizeMask;
 622         }
 623     }
 624
 625     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 626     template<typename T, typename Extra, typename HashTranslator>
 627     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)
 628     {
 629         checkKey<T, HashTranslator>(key);
 630
 631         invalidateIterators();
 632
 633         if (!m_table)
 634             expand();
 635
 636         internalCheckTableConsistency();
 637
 638         ASSERT(m_table);
 639
 640         int k = 0;
 641         ValueType* table = m_table;
 642         int sizeMask = m_tableSizeMask;
 643         unsigned h = HashTranslator::hash(key);
 644         int i = h & sizeMask;
 645
 646 #if DUMP_HASHTABLE_STATS
 647         atomicIncrement(&HashTableStats::numAccesses);
 648         int probeCount = 0;
 649 #endif
 650
 651         ValueType* deletedEntry = 0;
 652         ValueType* entry;
 653         while (1) {
 654             entry = table + i;
 655
 656             // we count on the compiler to optimize out this branch
 657             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
 658                 if (isEmptyBucket(*entry))
 659                     break;
 660
 661                 if (HashTranslator::equal(Extractor::extract(*entry), key))
 662                     return std::make_pair(makeKnownGoodIterator(entry), false);
 663
 664                 if (isDeletedBucket(*entry))
 665                     deletedEntry = entry;
 666             } else {
 667                 if (isEmptyBucket(*entry))
 668                     break;
 669
 670                 if (isDeletedBucket(*entry))
 671                     deletedEntry = entry;
 672                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
 673                     return std::make_pair(makeKnownGoodIterator(entry), false);
 674             }
 675 #if DUMP_HASHTABLE_STATS
 676             ++probeCount;
 677             HashTableStats::recordCollisionAtCount(probeCount);
 678 #endif
 679             if (k == 0)
 680                 k = 1 | doubleHash(h);
 681             i = (i + k) & sizeMask;
 682         }
 683
 684         if (deletedEntry) {
 685             initializeBucket(*deletedEntry);
 686             entry = deletedEntry;
 687             --m_deletedCount;
 688         }
 689
 690         HashTranslator::translate(*entry, key, extra);
 691
 692         ++m_keyCount;
 693
 694         if (shouldExpand()) {
 695             // FIXME: This makes an extra copy on expand. Probably not that bad since
 696             // expand is rare, but would be better to have a version of expand that can
 697             // follow a pivot entry and return the new position.
 698             KeyType enteredKey = Extractor::extract(*entry);
 699             expand();
 700             pair<iterator, bool> p = std::make_pair(find(enteredKey), true);
 701             ASSERT(p.first != end());
 702             return p;
 703         }
 704
 705         internalCheckTableConsistency();
 706
 707         return std::make_pair(makeKnownGoodIterator(entry), true);
 708     }
 709
 710     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 711     template<typename T, typename Extra, typename HashTranslator>
 712     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)
 713     {
 714         checkKey<T, HashTranslator>(key);
 715
 716         invalidateIterators();
 717
 718         if (!m_table)
 719             expand();
 720
 721         internalCheckTableConsistency();
 722
 723         FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key);
 724
 725         ValueType* entry = lookupResult.first.first;
 726         bool found = lookupResult.first.second;
 727         unsigned h = lookupResult.second;
 728
 729         if (found)
 730             return std::make_pair(makeKnownGoodIterator(entry), false);
 731
 732         if (isDeletedBucket(*entry)) {
 733             initializeBucket(*entry);
 734             --m_deletedCount;
 735         }
 736
 737         HashTranslator::translate(*entry, key, extra, h);
 738         ++m_keyCount;
 739         if (shouldExpand()) {
 740             // FIXME: This makes an extra copy on expand. Probably not that bad since
 741             // expand is rare, but would be better to have a version of expand that can
 742             // follow a pivot entry and return the new position.
 743             KeyType enteredKey = Extractor::extract(*entry);
 744             expand();
 745             pair<iterator, bool> p = std::make_pair(find(enteredKey), true);
 746             ASSERT(p.first != end());
 747             return p;
 748         }
 749
 750         internalCheckTableConsistency();
 751
 752         return std::make_pair(makeKnownGoodIterator(entry), true);
 753     }
 754
 755     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 756     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)
 757     {
 758         ASSERT(m_table);
 759         ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
 760         ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
 761 #if DUMP_HASHTABLE_STATS
 762         atomicIncrement(&HashTableStats::numReinserts);
 763 #endif
 764
 765         Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first);
 766     }
 767
 768     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 769     template <typename T, typename HashTranslator>
 770     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key)
 771     {
 772         if (!m_table)
 773             return end();
 774
 775         ValueType* entry = lookup<T, HashTranslator>(key);
 776         if (!entry)
 777             return end();
 778
 779         return makeKnownGoodIterator(entry);
 780     }
 781
 782     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 783     template <typename T, typename HashTranslator>
 784     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const
 785     {
 786         if (!m_table)
 787             return end();
 788
 789         ValueType* entry = const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);
 790         if (!entry)
 791             return end();
 792
 793         return makeKnownGoodConstIterator(entry);
 794     }
 795
 796     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 797     template <typename T, typename HashTranslator>
 798     bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const
 799     {
 800         if (!m_table)
 801             return false;
 802
 803         return const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);
 804     }
 805
 806     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 807     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos)
 808     {
 809         invalidateIterators();
 810         remove(pos);
 811     }
 812
 813     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 814     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos)
 815     {
 816         invalidateIterators();
 817         internalCheckTableConsistency();
 818         remove(pos);
 819     }
 820
 821     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 822     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
 823     {
 824 #if DUMP_HASHTABLE_STATS
 825         atomicIncrement(&HashTableStats::numRemoves);
 826 #endif
 827
 828         deleteBucket(*pos);
 829         ++m_deletedCount;
 830         --m_keyCount;
 831
 832         if (shouldShrink())
 833             shrink();
 834
 835         internalCheckTableConsistency();
 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>::remove(iterator it)
 840     {
 841         if (it == end())
 842             return;
 843
 844         removeAndInvalidate(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>::removeWithoutEntryConsistencyCheck(iterator it)
 849     {
 850         if (it == end())
 851             return;
 852
 853         removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position));
 854     }
 855
 856     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 857     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
 858     {
 859         remove(find(key));
 860     }
 861
 862     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 863     Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
 864     {
 865         // would use a template member function with explicit specializations here, but
 866         // gcc doesn't appear to support that
 867         if (Traits::emptyValueIsZero)
 868             return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType)));
 869         ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
 870         for (int i = 0; i < size; i++)
 871             initializeBucket(result[i]);
 872         return result;
 873     }
 874
 875     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 876     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, int size)
 877     {
 878         if (Traits::needsDestruction) {
 879             for (int i = 0; i < size; ++i) {
 880                 if (!isDeletedBucket(table[i]))
 881                     table[i].~ValueType();
 882             }
 883         }
 884         fastFree(table);
 885     }
 886
 887     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 888     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
 889     {
 890         int newSize;
 891         if (m_tableSize == 0)
 892             newSize = m_minTableSize;
 893         else if (mustRehashInPlace())
 894             newSize = m_tableSize;
 895         else
 896             newSize = m_tableSize * 2;
 897
 898         rehash(newSize);
 899     }
 900
 901     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 902     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize)
 903     {
 904         internalCheckTableConsistencyExceptSize();
 905
 906         int oldTableSize = m_tableSize;
 907         ValueType* oldTable = m_table;
 908
 909 #if DUMP_HASHTABLE_STATS
 910         if (oldTableSize != 0)
 911             atomicIncrement(&HashTableStats::numRehashes);
 912 #endif
 913
 914         m_tableSize = newTableSize;
 915         m_tableSizeMask = newTableSize - 1;
 916         m_table = allocateTable(newTableSize);
 917
 918         for (int i = 0; i != oldTableSize; ++i)
 919             if (!isEmptyOrDeletedBucket(oldTable[i]))
 920                 reinsert(oldTable[i]);
 921
 922         m_deletedCount = 0;
 923
 924         deallocateTable(oldTable, oldTableSize);
 925
 926         internalCheckTableConsistency();
 927     }
 928
 929     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 930     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
 931     {
 932         invalidateIterators();
 933         deallocateTable(m_table, m_tableSize);
 934         m_table = 0;
 935         m_tableSize = 0;
 936         m_tableSizeMask = 0;
 937         m_keyCount = 0;
 938     }
 939
 940     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 941     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
 942         : m_table(0)
 943         , m_tableSize(0)
 944         , m_tableSizeMask(0)
 945         , m_keyCount(0)
 946         , m_deletedCount(0)
 947 #if CHECK_HASHTABLE_ITERATORS
 948         , m_iterators(0)
 949 #endif
 950     {
 951         // Copy the hash table the dumb way, by adding each element to the new table.
 952         // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
 953         const_iterator end = other.end();
 954         for (const_iterator it = other.begin(); it != end; ++it)
 955             add(*it);
 956     }
 957
 958     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 959     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
 960     {
 961         invalidateIterators();
 962         other.invalidateIterators();
 963
 964         ValueType* tmp_table = m_table;
 965         m_table = other.m_table;
 966         other.m_table = tmp_table;
 967
 968         int tmp_tableSize = m_tableSize;
 969         m_tableSize = other.m_tableSize;
 970         other.m_tableSize = tmp_tableSize;
 971
 972         int tmp_tableSizeMask = m_tableSizeMask;
 973         m_tableSizeMask = other.m_tableSizeMask;
 974         other.m_tableSizeMask = tmp_tableSizeMask;
 975
 976         int tmp_keyCount = m_keyCount;
 977         m_keyCount = other.m_keyCount;
 978         other.m_keyCount = tmp_keyCount;
 979
 980         int tmp_deletedCount = m_deletedCount;
 981         m_deletedCount = other.m_deletedCount;
 982         other.m_deletedCount = tmp_deletedCount;
 983     }
 984
 985     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 986     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)
 987     {
 988         HashTable tmp(other);
 989         swap(tmp);
 990         return *this;
 991     }
 992
 993 #if !ASSERT_DISABLED
 994
 995     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 996     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
 997     {
 998         checkTableConsistencyExceptSize();
 999         ASSERT(!m_table || !shouldExpand());
1000         ASSERT(!shouldShrink());
1001     }
1002
1003     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1004     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
1005     {
1006         if (!m_table)
1007             return;
1008
1009         int count = 0;
1010         int deletedCount = 0;
1011         for (int j = 0; j < m_tableSize; ++j) {
1012             ValueType* entry = m_table + j;
1013             if (isEmptyBucket(*entry))
1014                 continue;
1015
1016             if (isDeletedBucket(*entry)) {
1017                 ++deletedCount;
1018                 continue;
1019             }
1020
1021             const_iterator it = find(Extractor::extract(*entry));
1022             ASSERT(entry == it.m_position);
1023             ++count;
1024
1025             ValueCheck<Key>::checkConsistency(it->first);
1026         }
1027
1028         ASSERT(count == m_keyCount);
1029         ASSERT(deletedCount == m_deletedCount);
1030         ASSERT(m_tableSize >= m_minTableSize);
1031         ASSERT(m_tableSizeMask);
1032         ASSERT(m_tableSize == m_tableSizeMask + 1);
1033     }
1034
1035 #endif // ASSERT_DISABLED
1036
1037 #if CHECK_HASHTABLE_ITERATORS
1038
1039     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1040     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
1041     {
1042         MutexLocker lock(m_mutex);
1043         const_iterator* next;
1044         for (const_iterator* p = m_iterators; p; p = next) {
1045             next = p->m_next;
1046             p->m_table = 0;
1047             p->m_next = 0;
1048             p->m_previous = 0;
1049         }
1050         m_iterators = 0;
1051     }
1052
1053     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1054     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
1055         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1056     {
1057         it->m_table = table;
1058         it->m_previous = 0;
1059
1060         // Insert iterator at head of doubly-linked list of iterators.
1061         if (!table) {
1062             it->m_next = 0;
1063         } else {
1064             MutexLocker lock(table->m_mutex);
1065             ASSERT(table->m_iterators != it);
1066             it->m_next = table->m_iterators;
1067             table->m_iterators = it;
1068             if (it->m_next) {
1069                 ASSERT(!it->m_next->m_previous);
1070                 it->m_next->m_previous = it;
1071             }
1072         }
1073     }
1074
1075     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1076     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1077     {
1078         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
1079         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
1080
1081         // Delete iterator from doubly-linked list of iterators.
1082         if (!it->m_table) {
1083             ASSERT(!it->m_next);
1084             ASSERT(!it->m_previous);
1085         } else {
1086             MutexLocker lock(it->m_table->m_mutex);
1087             if (it->m_next) {
1088                 ASSERT(it->m_next->m_previous == it);
1089                 it->m_next->m_previous = it->m_previous;
1090             }
1091             if (it->m_previous) {
1092                 ASSERT(it->m_table->m_iterators != it);
1093                 ASSERT(it->m_previous->m_next == it);
1094                 it->m_previous->m_next = it->m_next;
1095             } else {
1096                 ASSERT(it->m_table->m_iterators == it);
1097                 it->m_table->m_iterators = it->m_next;
1098             }
1099         }
1100
1101         it->m_table = 0;
1102         it->m_next = 0;
1103         it->m_previous = 0;
1104     }
1105
1106 #endif // CHECK_HASHTABLE_ITERATORS
1107
1108     // iterator adapters
1109
1110     template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
1111         HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
1112
1113         const ValueType* get() const { return (const ValueType*)m_impl.get(); }
1114         const ValueType& operator*() const { return *get(); }
1115         const ValueType* operator->() const { return get(); }
1116
1117         HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
1118         // postfix ++ intentionally omitted
1119
1120         typename HashTableType::const_iterator m_impl;
1121     };
1122
1123     template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
1124         HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
1125
1126         ValueType* get() const { return (ValueType*)m_impl.get(); }
1127         ValueType& operator*() const { return *get(); }
1128         ValueType* operator->() const { return get(); }
1129
1130         HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
1131         // postfix ++ intentionally omitted
1132
1133         operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
1134             typename HashTableType::const_iterator i = m_impl;
1135             return i;
1136         }
1137
1138         typename HashTableType::iterator m_impl;
1139     };
1140
1141     template<typename T, typename U>
1142     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1143     {
1144         return a.m_impl == b.m_impl;
1145     }
1146
1147     template<typename T, typename U>
1148     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1149     {
1150         return a.m_impl != b.m_impl;
1151     }
1152
1153     template<typename T, typename U>
1154     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1155     {
1156         return a.m_impl == b.m_impl;
1157     }
1158
1159     template<typename T, typename U>
1160     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1161     {
1162         return a.m_impl != b.m_impl;
1163     }
1164
1165 } // namespace WTF
1166
1167 #include "HashIterators.h"
1168
1169 #endif // WTF_HashTable_h