Source/JavaScriptCore/wtf/HashTable.h

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