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