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(static_cast<const HashTableType*>(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     // Work around MSVC's standard library, whose swap for pairs does not swap by component.
 263     template<typename T> inline void hashTableSwap(T& a, T& b)
 264     {
 265         swap(a, b);
 266     }
 267
 268     // Swap pairs by component, in case of pair members that specialize swap.
 269     template<typename T, typename U> inline void hashTableSwap(pair<T, U>& a, pair<T, U>& b)
 270     {
 271         swap(a.first, b.first);
 272         swap(a.second, b.second);
 273     }
 274
 275     template<typename T, bool useSwap> struct Mover;
 276     template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { hashTableSwap(from, to); } };
 277     template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } };
 278
 279     template<typename Key, typename Value, typename HashFunctions> class IdentityHashTranslator {
 280     public:
 281         static unsigned hash(const Key& key) { return HashFunctions::hash(key); }
 282         static bool equal(const Key& a, const Key& b) { return HashFunctions::equal(a, b); }
 283         static void translate(Value& location, const Key&, const Value& value) { location = value; }
 284     };
 285
 286     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 287     class HashTable {
 288     public:
 289         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
 290         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
 291         typedef Traits ValueTraits;
 292         typedef Key KeyType;
 293         typedef Value ValueType;
 294         typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType;
 295
 296         HashTable();
 297         ~HashTable()
 298         {
 299             invalidateIterators();
 300             deallocateTable(m_table, m_tableSize);
 301 #if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION
 302             m_table = (ValueType*)(uintptr_t)0xbbadbeef;
 303 #endif
 304         }
 305
 306         HashTable(const HashTable&);
 307         void swap(HashTable&);
 308         HashTable& operator=(const HashTable&);
 309
 310         iterator begin() { return makeIterator(m_table); }
 311         iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
 312         const_iterator begin() const { return makeConstIterator(m_table); }
 313         const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
 314
 315         int size() const { return m_keyCount; }
 316         int capacity() const { return m_tableSize; }
 317         bool isEmpty() const { return !m_keyCount; }
 318
 319         pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }
 320
 321         // A special version of add() that finds the object by hashing and comparing
 322         // with some other type, to avoid the cost of type conversion if the object is already
 323         // in the table.
 324         template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&);
 325         template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> addPassingHashCode(const T& key, const Extra&);
 326
 327         iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); }
 328         const_iterator find(const KeyType& key) const { return find<KeyType, IdentityTranslatorType>(key); }
 329         bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); }
 330
 331         template <typename T, typename HashTranslator> iterator find(const T&);
 332         template <typename T, typename HashTranslator> const_iterator find(const T&) const;
 333         template <typename T, typename HashTranslator> bool contains(const T&) const;
 334
 335         void remove(const KeyType&);
 336         void remove(iterator);
 337         void removeWithoutEntryConsistencyCheck(iterator);
 338         void removeWithoutEntryConsistencyCheck(const_iterator);
 339         void clear();
 340
 341         static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); }
 342         static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
 343         static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
 344
 345         ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); }
 346         template<typename T, typename HashTranslator> ValueType* lookup(const T&);
 347
 348 #if !ASSERT_DISABLED
 349         void checkTableConsistency() const;
 350 #else
 351         static void checkTableConsistency() { }
 352 #endif
 353 #if CHECK_HASHTABLE_CONSISTENCY
 354         void internalCheckTableConsistency() const { checkTableConsistency(); }
 355         void internalCheckTableConsistencyExceptSize() const { checkTableConsistencyExceptSize(); }
 356 #else
 357         static void internalCheckTableConsistencyExceptSize() { }
 358         static void internalCheckTableConsistency() { }
 359 #endif
 360
 361     private:
 362         static ValueType* allocateTable(int size);
 363         static void deallocateTable(ValueType* table, int size);
 364
 365         typedef pair<ValueType*, bool> LookupType;
 366         typedef pair<LookupType, unsigned> FullLookupType;
 367
 368         LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); };
 369         template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&);
 370         template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&);
 371
 372         template<typename T, typename HashTranslator> void checkKey(const T&);
 373
 374         void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
 375         void removeAndInvalidate(ValueType*);
 376         void remove(ValueType*);
 377
 378         bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
 379         bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
 380         bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; }
 381         void expand();
 382         void shrink() { rehash(m_tableSize / 2); }
 383
 384         void rehash(int newTableSize);
 385         void reinsert(ValueType&);
 386
 387         static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }
 388         static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); }
 389
 390         FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
 391             { return FullLookupType(LookupType(position, found), hash); }
 392
 393         iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
 394         const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
 395         iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
 396         const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
 397
 398 #if !ASSERT_DISABLED
 399         void checkTableConsistencyExceptSize() const;
 400 #else
 401         static void checkTableConsistencyExceptSize() { }
 402 #endif
 403
 404 #if CHECK_HASHTABLE_ITERATORS
 405         void invalidateIterators();
 406 #else
 407         static void invalidateIterators() { }
 408 #endif
 409
 410         static const int m_minTableSize = 64;
 411         static const int m_maxLoad = 2;
 412         static const int m_minLoad = 6;
 413
 414         ValueType* m_table;
 415         int m_tableSize;
 416         int m_tableSizeMask;
 417         int m_keyCount;
 418         int m_deletedCount;
 419
 420 #if CHECK_HASHTABLE_ITERATORS
 421     public:
 422         // All access to m_iterators should be guarded with m_mutex.
 423         mutable const_iterator* m_iterators;
 424         mutable Mutex m_mutex;
 425 #endif
 426     };
 427
 428     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 429     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
 430         : m_table(0)
 431         , m_tableSize(0)
 432         , m_tableSizeMask(0)
 433         , m_keyCount(0)
 434         , m_deletedCount(0)
 435 #if CHECK_HASHTABLE_ITERATORS
 436         , m_iterators(0)
 437 #endif
 438     {
 439     }
 440
 441     static inline unsigned doubleHash(unsigned key)
 442     {
 443         key = ~key + (key >> 23);
 444         key ^= (key << 12);
 445         key ^= (key >> 7);
 446         key ^= (key << 2);
 447         key ^= (key >> 20);
 448         return key;
 449     }
 450
 451 #if ASSERT_DISABLED
 452
 453     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 454     template<typename T, typename HashTranslator>
 455     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
 456     {
 457     }
 458
 459 #else
 460
 461     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 462     template<typename T, typename HashTranslator>
 463     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)
 464     {
 465         if (!HashFunctions::safeToCompareToEmptyOrDeleted)
 466             return;
 467         ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
 468         ValueType deletedValue = Traits::emptyValue();
 469         deletedValue.~ValueType();
 470         Traits::constructDeletedValue(deletedValue);
 471         ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
 472         new (&deletedValue) ValueType(Traits::emptyValue());
 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<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 629     template<typename T, typename Extra, typename HashTranslator>
 630     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)
 631     {
 632         checkKey<T, HashTranslator>(key);
 633
 634         invalidateIterators();
 635
 636         if (!m_table)
 637             expand();
 638
 639         internalCheckTableConsistency();
 640
 641         ASSERT(m_table);
 642
 643         int k = 0;
 644         ValueType* table = m_table;
 645         int sizeMask = m_tableSizeMask;
 646         unsigned h = HashTranslator::hash(key);
 647         int i = h & sizeMask;
 648
 649 #if DUMP_HASHTABLE_STATS
 650         atomicIncrement(&HashTableStats::numAccesses);
 651         int probeCount = 0;
 652 #endif
 653
 654         ValueType* deletedEntry = 0;
 655         ValueType* entry;
 656         while (1) {
 657             entry = table + i;
 658
 659             // we count on the compiler to optimize out this branch
 660             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
 661                 if (isEmptyBucket(*entry))
 662                     break;
 663
 664                 if (HashTranslator::equal(Extractor::extract(*entry), key))
 665                     return std::make_pair(makeKnownGoodIterator(entry), false);
 666
 667                 if (isDeletedBucket(*entry))
 668                     deletedEntry = entry;
 669             } else {
 670                 if (isEmptyBucket(*entry))
 671                     break;
 672
 673                 if (isDeletedBucket(*entry))
 674                     deletedEntry = entry;
 675                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
 676                     return std::make_pair(makeKnownGoodIterator(entry), false);
 677             }
 678 #if DUMP_HASHTABLE_STATS
 679             ++probeCount;
 680             HashTableStats::recordCollisionAtCount(probeCount);
 681 #endif
 682             if (k == 0)
 683                 k = 1 | doubleHash(h);
 684             i = (i + k) & sizeMask;
 685         }
 686
 687         if (deletedEntry) {
 688             initializeBucket(*deletedEntry);
 689             entry = deletedEntry;
 690             --m_deletedCount;
 691         }
 692
 693         HashTranslator::translate(*entry, key, extra);
 694
 695         ++m_keyCount;
 696
 697         if (shouldExpand()) {
 698             // FIXME: This makes an extra copy on expand. Probably not that bad since
 699             // expand is rare, but would be better to have a version of expand that can
 700             // follow a pivot entry and return the new position.
 701             KeyType enteredKey = Extractor::extract(*entry);
 702             expand();
 703             pair<iterator, bool> p = std::make_pair(find(enteredKey), true);
 704             ASSERT(p.first != end());
 705             return p;
 706         }
 707
 708         internalCheckTableConsistency();
 709
 710         return std::make_pair(makeKnownGoodIterator(entry), true);
 711     }
 712
 713     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 714     template<typename T, typename Extra, typename HashTranslator>
 715     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)
 716     {
 717         checkKey<T, HashTranslator>(key);
 718
 719         invalidateIterators();
 720
 721         if (!m_table)
 722             expand();
 723
 724         internalCheckTableConsistency();
 725
 726         FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key);
 727
 728         ValueType* entry = lookupResult.first.first;
 729         bool found = lookupResult.first.second;
 730         unsigned h = lookupResult.second;
 731
 732         if (found)
 733             return std::make_pair(makeKnownGoodIterator(entry), false);
 734
 735         if (isDeletedBucket(*entry)) {
 736             initializeBucket(*entry);
 737             --m_deletedCount;
 738         }
 739
 740         HashTranslator::translate(*entry, key, extra, h);
 741         ++m_keyCount;
 742         if (shouldExpand()) {
 743             // FIXME: This makes an extra copy on expand. Probably not that bad since
 744             // expand is rare, but would be better to have a version of expand that can
 745             // follow a pivot entry and return the new position.
 746             KeyType enteredKey = Extractor::extract(*entry);
 747             expand();
 748             pair<iterator, bool> p = std::make_pair(find(enteredKey), true);
 749             ASSERT(p.first != end());
 750             return p;
 751         }
 752
 753         internalCheckTableConsistency();
 754
 755         return std::make_pair(makeKnownGoodIterator(entry), true);
 756     }
 757
 758     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 759     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)
 760     {
 761         ASSERT(m_table);
 762         ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
 763         ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
 764 #if DUMP_HASHTABLE_STATS
 765         atomicIncrement(&HashTableStats::numReinserts);
 766 #endif
 767
 768         Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first);
 769     }
 770
 771     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 772     template <typename T, typename HashTranslator>
 773     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key)
 774     {
 775         if (!m_table)
 776             return end();
 777
 778         ValueType* entry = lookup<T, HashTranslator>(key);
 779         if (!entry)
 780             return end();
 781
 782         return makeKnownGoodIterator(entry);
 783     }
 784
 785     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 786     template <typename T, typename HashTranslator>
 787     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const
 788     {
 789         if (!m_table)
 790             return end();
 791
 792         ValueType* entry = const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);
 793         if (!entry)
 794             return end();
 795
 796         return makeKnownGoodConstIterator(entry);
 797     }
 798
 799     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 800     template <typename T, typename HashTranslator>
 801     bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const
 802     {
 803         if (!m_table)
 804             return false;
 805
 806         return const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);
 807     }
 808
 809     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 810     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos)
 811     {
 812         invalidateIterators();
 813         remove(pos);
 814     }
 815
 816     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 817     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos)
 818     {
 819         invalidateIterators();
 820         internalCheckTableConsistency();
 821         remove(pos);
 822     }
 823
 824     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 825     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
 826     {
 827 #if DUMP_HASHTABLE_STATS
 828         atomicIncrement(&HashTableStats::numRemoves);
 829 #endif
 830
 831         deleteBucket(*pos);
 832         ++m_deletedCount;
 833         --m_keyCount;
 834
 835         if (shouldShrink())
 836             shrink();
 837
 838         internalCheckTableConsistency();
 839     }
 840
 841     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 842     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
 843     {
 844         if (it == end())
 845             return;
 846
 847         removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position));
 848     }
 849
 850     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 851     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it)
 852     {
 853         if (it == end())
 854             return;
 855
 856         removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position));
 857     }
 858
 859     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 860     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(const_iterator it)
 861     {
 862         if (it == end())
 863             return;
 864
 865         removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_position));
 866     }
 867
 868     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 869     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
 870     {
 871         remove(find(key));
 872     }
 873
 874     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 875     Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
 876     {
 877         // would use a template member function with explicit specializations here, but
 878         // gcc doesn't appear to support that
 879         if (Traits::emptyValueIsZero)
 880             return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType)));
 881         ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
 882         for (int i = 0; i < size; i++)
 883             initializeBucket(result[i]);
 884         return result;
 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>::deallocateTable(ValueType* table, int size)
 889     {
 890         if (Traits::needsDestruction) {
 891             for (int i = 0; i < size; ++i) {
 892                 if (!isDeletedBucket(table[i]))
 893                     table[i].~ValueType();
 894             }
 895         }
 896         fastFree(table);
 897     }
 898
 899     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 900     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
 901     {
 902         int newSize;
 903         if (m_tableSize == 0)
 904             newSize = m_minTableSize;
 905         else if (mustRehashInPlace())
 906             newSize = m_tableSize;
 907         else
 908             newSize = m_tableSize * 2;
 909
 910         rehash(newSize);
 911     }
 912
 913     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 914     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize)
 915     {
 916         internalCheckTableConsistencyExceptSize();
 917
 918         int oldTableSize = m_tableSize;
 919         ValueType* oldTable = m_table;
 920
 921 #if DUMP_HASHTABLE_STATS
 922         if (oldTableSize != 0)
 923             atomicIncrement(&HashTableStats::numRehashes);
 924 #endif
 925
 926         m_tableSize = newTableSize;
 927         m_tableSizeMask = newTableSize - 1;
 928         m_table = allocateTable(newTableSize);
 929
 930         for (int i = 0; i != oldTableSize; ++i)
 931             if (!isEmptyOrDeletedBucket(oldTable[i]))
 932                 reinsert(oldTable[i]);
 933
 934         m_deletedCount = 0;
 935
 936         deallocateTable(oldTable, oldTableSize);
 937
 938         internalCheckTableConsistency();
 939     }
 940
 941     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 942     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
 943     {
 944         invalidateIterators();
 945         deallocateTable(m_table, m_tableSize);
 946         m_table = 0;
 947         m_tableSize = 0;
 948         m_tableSizeMask = 0;
 949         m_keyCount = 0;
 950     }
 951
 952     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 953     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
 954         : m_table(0)
 955         , m_tableSize(0)
 956         , m_tableSizeMask(0)
 957         , m_keyCount(0)
 958         , m_deletedCount(0)
 959 #if CHECK_HASHTABLE_ITERATORS
 960         , m_iterators(0)
 961 #endif
 962     {
 963         // Copy the hash table the dumb way, by adding each element to the new table.
 964         // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
 965         const_iterator end = other.end();
 966         for (const_iterator it = other.begin(); it != end; ++it)
 967             add(*it);
 968     }
 969
 970     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 971     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
 972     {
 973         invalidateIterators();
 974         other.invalidateIterators();
 975
 976         ValueType* tmp_table = m_table;
 977         m_table = other.m_table;
 978         other.m_table = tmp_table;
 979
 980         int tmp_tableSize = m_tableSize;
 981         m_tableSize = other.m_tableSize;
 982         other.m_tableSize = tmp_tableSize;
 983
 984         int tmp_tableSizeMask = m_tableSizeMask;
 985         m_tableSizeMask = other.m_tableSizeMask;
 986         other.m_tableSizeMask = tmp_tableSizeMask;
 987
 988         int tmp_keyCount = m_keyCount;
 989         m_keyCount = other.m_keyCount;
 990         other.m_keyCount = tmp_keyCount;
 991
 992         int tmp_deletedCount = m_deletedCount;
 993         m_deletedCount = other.m_deletedCount;
 994         other.m_deletedCount = tmp_deletedCount;
 995     }
 996
 997     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
 998     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)
 999     {
1000         HashTable tmp(other);
1001         swap(tmp);
1002         return *this;
1003     }
1004
1005 #if !ASSERT_DISABLED
1006
1007     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1008     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
1009     {
1010         checkTableConsistencyExceptSize();
1011         ASSERT(!m_table || !shouldExpand());
1012         ASSERT(!shouldShrink());
1013     }
1014
1015     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1016     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
1017     {
1018         if (!m_table)
1019             return;
1020
1021         int count = 0;
1022         int deletedCount = 0;
1023         for (int j = 0; j < m_tableSize; ++j) {
1024             ValueType* entry = m_table + j;
1025             if (isEmptyBucket(*entry))
1026                 continue;
1027
1028             if (isDeletedBucket(*entry)) {
1029                 ++deletedCount;
1030                 continue;
1031             }
1032
1033             const_iterator it = find(Extractor::extract(*entry));
1034             ASSERT(entry == it.m_position);
1035             ++count;
1036
1037             ValueCheck<Key>::checkConsistency(it->first);
1038         }
1039
1040         ASSERT(count == m_keyCount);
1041         ASSERT(deletedCount == m_deletedCount);
1042         ASSERT(m_tableSize >= m_minTableSize);
1043         ASSERT(m_tableSizeMask);
1044         ASSERT(m_tableSize == m_tableSizeMask + 1);
1045     }
1046
1047 #endif // ASSERT_DISABLED
1048
1049 #if CHECK_HASHTABLE_ITERATORS
1050
1051     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1052     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
1053     {
1054         MutexLocker lock(m_mutex);
1055         const_iterator* next;
1056         for (const_iterator* p = m_iterators; p; p = next) {
1057             next = p->m_next;
1058             p->m_table = 0;
1059             p->m_next = 0;
1060             p->m_previous = 0;
1061         }
1062         m_iterators = 0;
1063     }
1064
1065     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1066     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
1067         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1068     {
1069         it->m_table = table;
1070         it->m_previous = 0;
1071
1072         // Insert iterator at head of doubly-linked list of iterators.
1073         if (!table) {
1074             it->m_next = 0;
1075         } else {
1076             MutexLocker lock(table->m_mutex);
1077             ASSERT(table->m_iterators != it);
1078             it->m_next = table->m_iterators;
1079             table->m_iterators = it;
1080             if (it->m_next) {
1081                 ASSERT(!it->m_next->m_previous);
1082                 it->m_next->m_previous = it;
1083             }
1084         }
1085     }
1086
1087     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1088     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1089     {
1090         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
1091         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
1092
1093         // Delete iterator from doubly-linked list of iterators.
1094         if (!it->m_table) {
1095             ASSERT(!it->m_next);
1096             ASSERT(!it->m_previous);
1097         } else {
1098             MutexLocker lock(it->m_table->m_mutex);
1099             if (it->m_next) {
1100                 ASSERT(it->m_next->m_previous == it);
1101                 it->m_next->m_previous = it->m_previous;
1102             }
1103             if (it->m_previous) {
1104                 ASSERT(it->m_table->m_iterators != it);
1105                 ASSERT(it->m_previous->m_next == it);
1106                 it->m_previous->m_next = it->m_next;
1107             } else {
1108                 ASSERT(it->m_table->m_iterators == it);
1109                 it->m_table->m_iterators = it->m_next;
1110             }
1111         }
1112
1113         it->m_table = 0;
1114         it->m_next = 0;
1115         it->m_previous = 0;
1116     }
1117
1118 #endif // CHECK_HASHTABLE_ITERATORS
1119
1120     // iterator adapters
1121
1122     template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
1123         HashTableConstIteratorAdapter() {}
1124         HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
1125
1126         const ValueType* get() const { return (const ValueType*)m_impl.get(); }
1127         const ValueType& operator*() const { return *get(); }
1128         const ValueType* operator->() const { return get(); }
1129
1130         HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
1131         // postfix ++ intentionally omitted
1132
1133         typename HashTableType::const_iterator m_impl;
1134     };
1135
1136     template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
1137         HashTableIteratorAdapter() {}
1138         HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
1139
1140         ValueType* get() const { return (ValueType*)m_impl.get(); }
1141         ValueType& operator*() const { return *get(); }
1142         ValueType* operator->() const { return get(); }
1143
1144         HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
1145         // postfix ++ intentionally omitted
1146
1147         operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
1148             typename HashTableType::const_iterator i = m_impl;
1149             return i;
1150         }
1151
1152         typename HashTableType::iterator m_impl;
1153     };
1154
1155     template<typename T, typename U>
1156     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1157     {
1158         return a.m_impl == b.m_impl;
1159     }
1160
1161     template<typename T, typename U>
1162     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1163     {
1164         return a.m_impl != b.m_impl;
1165     }
1166
1167     template<typename T, typename U>
1168     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1169     {
1170         return a.m_impl == b.m_impl;
1171     }
1172
1173     template<typename T, typename U>
1174     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1175     {
1176         return a.m_impl != b.m_impl;
1177     }
1178
1179 } // namespace WTF
1180
1181 #include "HashIterators.h"
1182
1183 #endif // WTF_HashTable_h