src/third_party/WebKit/Source/wtf/HashTable.h

   1 /*
   2  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 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 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU * Library General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Library General Public License
  14  * along with this library; see the file COPYING.LIB.  If not, write to
  15  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  16  * Boston, MA 02110-1301, USA.
  17  *
  18  */
  19
  20 #ifndef WTF_HashTable_h
  21 #define WTF_HashTable_h
  22
  23 #include "wtf/Alignment.h"
  24 #include "wtf/Assertions.h"
  25 #include "wtf/DefaultAllocator.h"
  26 #include "wtf/HashTraits.h"
  27 #include "wtf/WTF.h"
  28
  29 #define DUMP_HASHTABLE_STATS 0
  30 #define DUMP_HASHTABLE_STATS_PER_TABLE 0
  31
  32 #if DUMP_HASHTABLE_STATS_PER_TABLE
  33 #include "wtf/DataLog.h"
  34 #endif
  35
  36 namespace WTF {
  37
  38 #if DUMP_HASHTABLE_STATS
  39
  40     struct HashTableStats {
  41         // The following variables are all atomically incremented when modified.
  42         static int numAccesses;
  43         static int numRehashes;
  44         static int numRemoves;
  45         static int numReinserts;
  46
  47         // The following variables are only modified in the recordCollisionAtCount method within a mutex.
  48         static int maxCollisions;
  49         static int numCollisions;
  50         static int collisionGraph[4096];
  51
  52         static void recordCollisionAtCount(int count);
  53         static void dumpStats();
  54     };
  55
  56 #endif
  57
  58     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
  59     class HashTable;
  60     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
  61     class HashTableIterator;
  62     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
  63     class HashTableConstIterator;
  64     template<bool x, typename T, typename U, typename V, typename W, typename X, typename Y, typename Z>
  65     struct WeakProcessingHashTableHelper;
  66
  67     typedef enum { HashItemKnownGood } HashItemKnownGoodTag;
  68
  69     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
  70     class HashTableConstIterator {
  71     private:
  72         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> HashTableType;
  73         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
  74         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> const_iterator;
  75         typedef Value ValueType;
  76         typedef const ValueType& ReferenceType;
  77         typedef const ValueType* PointerType;
  78
  79         friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
  80         friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
  81
  82         void skipEmptyBuckets()
  83         {
  84             while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position))
  85                 ++m_position;
  86         }
  87
  88         HashTableConstIterator(PointerType position, PointerType endPosition)
  89             : m_position(position), m_endPosition(endPosition)
  90         {
  91             skipEmptyBuckets();
  92         }
  93
  94         HashTableConstIterator(PointerType position, PointerType endPosition, HashItemKnownGoodTag)
  95             : m_position(position), m_endPosition(endPosition)
  96         {
  97         }
  98
  99     public:
 100         HashTableConstIterator()
 101         {
 102         }
 103
 104         PointerType get() const
 105         {
 106             return m_position;
 107         }
 108         ReferenceType operator*() const { return *get(); }
 109         PointerType operator->() const { return get(); }
 110
 111         const_iterator& operator++()
 112         {
 113             ASSERT(m_position != m_endPosition);
 114             ++m_position;
 115             skipEmptyBuckets();
 116             return *this;
 117         }
 118
 119         // postfix ++ intentionally omitted
 120
 121         // Comparison.
 122         bool operator==(const const_iterator& other) const
 123         {
 124             return m_position == other.m_position;
 125         }
 126         bool operator!=(const const_iterator& other) const
 127         {
 128             return m_position != other.m_position;
 129         }
 130         bool operator==(const iterator& other) const
 131         {
 132             return *this == static_cast<const_iterator>(other);
 133         }
 134         bool operator!=(const iterator& other) const
 135         {
 136             return *this != static_cast<const_iterator>(other);
 137         }
 138
 139     private:
 140         PointerType m_position;
 141         PointerType m_endPosition;
 142     };
 143
 144     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 145     class HashTableIterator {
 146     private:
 147         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
 148         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> const_iterator;
 149         typedef Value ValueType;
 150         typedef typename Traits::IteratorGetType GetType;
 151         typedef ValueType* PointerType;
 152
 153         friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
 154
 155         HashTableIterator(PointerType pos, PointerType end) : m_iterator(pos, end) { }
 156         HashTableIterator(PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(pos, end, tag) { }
 157
 158     public:
 159         HashTableIterator() { }
 160
 161         // default copy, assignment and destructor are OK
 162
 163         GetType get() const { return const_cast<GetType>(m_iterator.get()); }
 164         typename Traits::IteratorReferenceType operator*() const { return Traits::getToReferenceConversion(get()); }
 165         GetType operator->() const { return get(); }
 166
 167         iterator& operator++() { ++m_iterator; return *this; }
 168
 169         // postfix ++ intentionally omitted
 170
 171         // Comparison.
 172         bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
 173         bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
 174         bool operator==(const const_iterator& other) const { return m_iterator == other; }
 175         bool operator!=(const const_iterator& other) const { return m_iterator != other; }
 176
 177         operator const_iterator() const { return m_iterator; }
 178
 179     private:
 180         const_iterator m_iterator;
 181     };
 182
 183     using std::swap;
 184
 185     // Work around MSVC's standard library, whose swap for pairs does not swap by component.
 186     template<typename T> inline void hashTableSwap(T& a, T& b)
 187     {
 188         swap(a, b);
 189     }
 190
 191     template<typename T, typename U> inline void hashTableSwap(KeyValuePair<T, U>& a, KeyValuePair<T, U>& b)
 192     {
 193         swap(a.key, b.key);
 194         swap(a.value, b.value);
 195     }
 196
 197     template<typename T, bool useSwap> struct Mover;
 198     template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { hashTableSwap(from, to); } };
 199     template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } };
 200
 201     template<typename HashFunctions> class IdentityHashTranslator {
 202     public:
 203         template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
 204         template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
 205         template<typename T, typename U, typename V> static void translate(T& location, const U&, const V& value) { location = value; }
 206     };
 207
 208     template<typename ValueType> struct HashTableAddResult {
 209         HashTableAddResult(ValueType* storedValue, bool isNewEntry) : storedValue(storedValue), isNewEntry(isNewEntry) { }
 210         ValueType* storedValue;
 211         bool isNewEntry;
 212     };
 213
 214     template<typename Value, typename Extractor, typename KeyTraits>
 215     struct HashTableHelper {
 216         static bool isEmptyBucket(const Value& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
 217         static bool isDeletedBucket(const Value& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
 218         static bool isEmptyOrDeletedBucket(const Value& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
 219     };
 220
 221     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 222     class HashTable {
 223     public:
 224         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
 225         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> const_iterator;
 226         typedef Traits ValueTraits;
 227         typedef Key KeyType;
 228         typedef typename KeyTraits::PeekInType KeyPeekInType;
 229         typedef typename KeyTraits::PassInType KeyPassInType;
 230         typedef Value ValueType;
 231         typedef typename Traits::PeekInType ValuePeekInType;
 232         typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType;
 233         typedef HashTableAddResult<ValueType> AddResult;
 234
 235 #if DUMP_HASHTABLE_STATS_PER_TABLE
 236         struct Stats {
 237             Stats()
 238                 : numAccesses(0)
 239                 , numRehashes(0)
 240                 , numRemoves(0)
 241                 , numReinserts(0)
 242                 , maxCollisions(0)
 243                 , numCollisions(0)
 244                 , collisionGraph()
 245             {
 246             }
 247
 248             int numAccesses;
 249             int numRehashes;
 250             int numRemoves;
 251             int numReinserts;
 252
 253             int maxCollisions;
 254             int numCollisions;
 255             int collisionGraph[4096];
 256
 257             void recordCollisionAtCount(int count)
 258             {
 259                 if (count > maxCollisions)
 260                     maxCollisions = count;
 261                 numCollisions++;
 262                 collisionGraph[count]++;
 263             }
 264
 265             void dumpStats()
 266             {
 267                 dataLogF("\nWTF::HashTable::Stats dump\n\n");
 268                 dataLogF("%d accesses\n", numAccesses);
 269                 dataLogF("%d total collisions, average %.2f probes per access\n", numCollisions, 1.0 * (numAccesses + numCollisions) / numAccesses);
 270                 dataLogF("longest collision chain: %d\n", maxCollisions);
 271                 for (int i = 1; i <= maxCollisions; i++) {
 272                     dataLogF("  %d lookups with exactly %d collisions (%.2f%% , %.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses);
 273                 }
 274                 dataLogF("%d rehashes\n", numRehashes);
 275                 dataLogF("%d reinserts\n", numReinserts);
 276             }
 277         };
 278 #endif
 279
 280         HashTable();
 281         ~HashTable()
 282         {
 283             if (LIKELY(!m_table))
 284                 return;
 285             deallocateTable(m_table, m_tableSize);
 286             m_table = 0;
 287         }
 288
 289         HashTable(const HashTable&);
 290         void swap(HashTable&);
 291         HashTable& operator=(const HashTable&);
 292
 293         // When the hash table is empty, just return the same iterator for end as for begin.
 294         // This is more efficient because we don't have to skip all the empty and deleted
 295         // buckets, and iterating an empty table is a common case that's worth optimizing.
 296         iterator begin() { return isEmpty() ? end() : makeIterator(m_table); }
 297         iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
 298         const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); }
 299         const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
 300
 301         unsigned size() const { return m_keyCount; }
 302         unsigned capacity() const { return m_tableSize; }
 303         bool isEmpty() const { return !m_keyCount; }
 304
 305         AddResult add(ValuePeekInType value)
 306         {
 307             return add<IdentityTranslatorType>(Extractor::extract(value), value);
 308         }
 309
 310         // A special version of add() that finds the object by hashing and comparing
 311         // with some other type, to avoid the cost of type conversion if the object is already
 312         // in the table.
 313         template<typename HashTranslator, typename T, typename Extra> AddResult add(const T& key, const Extra&);
 314         template<typename HashTranslator, typename T, typename Extra> AddResult addPassingHashCode(const T& key, const Extra&);
 315
 316         iterator find(KeyPeekInType key) { return find<IdentityTranslatorType>(key); }
 317         const_iterator find(KeyPeekInType key) const { return find<IdentityTranslatorType>(key); }
 318         bool contains(KeyPeekInType key) const { return contains<IdentityTranslatorType>(key); }
 319
 320         template<typename HashTranslator, typename T> iterator find(const T&);
 321         template<typename HashTranslator, typename T> const_iterator find(const T&) const;
 322         template<typename HashTranslator, typename T> bool contains(const T&) const;
 323
 324         void remove(KeyPeekInType);
 325         void remove(iterator);
 326         void remove(const_iterator);
 327         void clear();
 328
 329         static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
 330         static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
 331         static bool isEmptyOrDeletedBucket(const ValueType& value) { return HashTableHelper<ValueType, Extractor, KeyTraits>:: isEmptyOrDeletedBucket(value); }
 332
 333         ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorType>(key); }
 334         template<typename HashTranslator, typename T> ValueType* lookup(const T&);
 335
 336         void trace(typename Allocator::Visitor*);
 337
 338     private:
 339         static ValueType* allocateTable(unsigned size);
 340         static void deallocateTable(ValueType* table, unsigned size);
 341
 342         typedef std::pair<ValueType*, bool> LookupType;
 343         typedef std::pair<LookupType, unsigned> FullLookupType;
 344
 345         LookupType lookupForWriting(const Key& key) { return lookupForWriting<IdentityTranslatorType>(key); };
 346         template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&);
 347         template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&);
 348
 349         void remove(ValueType*);
 350
 351         bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
 352         bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
 353         bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; }
 354         void expand();
 355         void shrink() { rehash(m_tableSize / 2); }
 356
 357         void rehash(unsigned newTableSize);
 358         void reinsert(ValueType&);
 359
 360         static void initializeBucket(ValueType& bucket);
 361         static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); }
 362
 363         FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
 364             { return FullLookupType(LookupType(position, found), hash); }
 365
 366         iterator makeIterator(ValueType* pos) { return iterator(pos, m_table + m_tableSize); }
 367         const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(pos, m_table + m_tableSize); }
 368         iterator makeKnownGoodIterator(ValueType* pos) { return iterator(pos, m_table + m_tableSize, HashItemKnownGood); }
 369         const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(pos, m_table + m_tableSize, HashItemKnownGood); }
 370
 371         static const unsigned m_maxLoad = 2;
 372         static const unsigned m_minLoad = 6;
 373
 374         ValueType* m_table;
 375         unsigned m_tableSize;
 376         unsigned m_tableSizeMask;
 377         unsigned m_keyCount;
 378         unsigned m_deletedCount;
 379
 380 #if DUMP_HASHTABLE_STATS_PER_TABLE
 381     public:
 382         mutable OwnPtr<Stats> m_stats;
 383 #endif
 384
 385         template<bool x, typename T, typename U, typename V, typename W, typename X, typename Y, typename Z> friend struct WeakProcessingHashTableHelper;
 386     };
 387
 388     // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
 389     template<unsigned size> struct OneifyLowBits;
 390     template<>
 391     struct OneifyLowBits<0> {
 392         static const unsigned value = 0;
 393     };
 394     template<unsigned number>
 395     struct OneifyLowBits {
 396         static const unsigned value = number | OneifyLowBits<(number >> 1)>::value;
 397     };
 398     // Compute the first power of two integer that is an upper bound of the parameter 'number'.
 399     template<unsigned number>
 400     struct UpperPowerOfTwoBound {
 401         static const unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2;
 402     };
 403
 404     // Because power of two numbers are the limit of maxLoad, their capacity is twice the
 405     // UpperPowerOfTwoBound, or 4 times their values.
 406     template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter;
 407     template<unsigned size>
 408     struct HashTableCapacityForSizeSplitter<size, true> {
 409         static const unsigned value = size * 4;
 410     };
 411     template<unsigned size>
 412     struct HashTableCapacityForSizeSplitter<size, false> {
 413         static const unsigned value = UpperPowerOfTwoBound<size>::value;
 414     };
 415
 416     // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter.
 417     // This is done at compile time to initialize the HashTraits.
 418     template<unsigned size>
 419     struct HashTableCapacityForSize {
 420         static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
 421         COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
 422         COMPILE_ASSERT(!static_cast<int>(value >> 31), HashTableNoCapacityOverflow);
 423         COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
 424     };
 425
 426     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 427     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::HashTable()
 428         : m_table(0)
 429         , m_tableSize(0)
 430         , m_tableSizeMask(0)
 431         , m_keyCount(0)
 432         , m_deletedCount(0)
 433 #if DUMP_HASHTABLE_STATS_PER_TABLE
 434         , m_stats(adoptPtr(new Stats))
 435 #endif
 436     {
 437     }
 438
 439     inline unsigned doubleHash(unsigned key)
 440     {
 441         key = ~key + (key >> 23);
 442         key ^= (key << 12);
 443         key ^= (key >> 7);
 444         key ^= (key << 2);
 445         key ^= (key >> 20);
 446         return key;
 447     }
 448
 449     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 450     template<typename HashTranslator, typename T>
 451     inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(const T& key)
 452     {
 453         ValueType* table = m_table;
 454         if (!table)
 455             return 0;
 456
 457         size_t k = 0;
 458         size_t sizeMask = m_tableSizeMask;
 459         unsigned h = HashTranslator::hash(key);
 460         size_t i = h & sizeMask;
 461
 462 #if DUMP_HASHTABLE_STATS
 463         atomicIncrement(&HashTableStats::numAccesses);
 464         int probeCount = 0;
 465 #endif
 466
 467 #if DUMP_HASHTABLE_STATS_PER_TABLE
 468         ++m_stats->numAccesses;
 469         int perTableProbeCount = 0;
 470 #endif
 471
 472         while (1) {
 473             ValueType* entry = table + i;
 474
 475             // we count on the compiler to optimize out this branch
 476             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
 477                 if (HashTranslator::equal(Extractor::extract(*entry), key))
 478                     return entry;
 479
 480                 if (isEmptyBucket(*entry))
 481                     return 0;
 482             } else {
 483                 if (isEmptyBucket(*entry))
 484                     return 0;
 485
 486                 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
 487                     return entry;
 488             }
 489 #if DUMP_HASHTABLE_STATS
 490             ++probeCount;
 491             HashTableStats::recordCollisionAtCount(probeCount);
 492 #endif
 493
 494 #if DUMP_HASHTABLE_STATS_PER_TABLE
 495             ++perTableProbeCount;
 496             m_stats->recordCollisionAtCount(perTableProbeCount);
 497 #endif
 498
 499             if (!k)
 500                 k = 1 | doubleHash(h);
 501             i = (i + k) & sizeMask;
 502         }
 503     }
 504
 505     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 506     template<typename HashTranslator, typename T>
 507     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookupForWriting(const T& key)
 508     {
 509         ASSERT(m_table);
 510
 511         size_t k = 0;
 512         ValueType* table = m_table;
 513         size_t sizeMask = m_tableSizeMask;
 514         unsigned h = HashTranslator::hash(key);
 515         size_t i = h & sizeMask;
 516
 517 #if DUMP_HASHTABLE_STATS
 518         atomicIncrement(&HashTableStats::numAccesses);
 519         int probeCount = 0;
 520 #endif
 521
 522 #if DUMP_HASHTABLE_STATS_PER_TABLE
 523         ++m_stats->numAccesses;
 524         int perTableProbeCount = 0;
 525 #endif
 526
 527         ValueType* deletedEntry = 0;
 528
 529         while (1) {
 530             ValueType* entry = table + i;
 531
 532             // we count on the compiler to optimize out this branch
 533             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
 534                 if (isEmptyBucket(*entry))
 535                     return LookupType(deletedEntry ? deletedEntry : entry, false);
 536
 537                 if (HashTranslator::equal(Extractor::extract(*entry), key))
 538                     return LookupType(entry, true);
 539
 540                 if (isDeletedBucket(*entry))
 541                     deletedEntry = entry;
 542             } else {
 543                 if (isEmptyBucket(*entry))
 544                     return LookupType(deletedEntry ? deletedEntry : entry, false);
 545
 546                 if (isDeletedBucket(*entry))
 547                     deletedEntry = entry;
 548                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
 549                     return LookupType(entry, true);
 550             }
 551 #if DUMP_HASHTABLE_STATS
 552             ++probeCount;
 553             HashTableStats::recordCollisionAtCount(probeCount);
 554 #endif
 555
 556 #if DUMP_HASHTABLE_STATS_PER_TABLE
 557             ++perTableProbeCount;
 558             m_stats->recordCollisionAtCount(perTableProbeCount);
 559 #endif
 560
 561             if (!k)
 562                 k = 1 | doubleHash(h);
 563             i = (i + k) & sizeMask;
 564         }
 565     }
 566
 567     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 568     template<typename HashTranslator, typename T>
 569     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::fullLookupForWriting(const T& key)
 570     {
 571         ASSERT(m_table);
 572
 573         size_t k = 0;
 574         ValueType* table = m_table;
 575         size_t sizeMask = m_tableSizeMask;
 576         unsigned h = HashTranslator::hash(key);
 577         size_t i = h & sizeMask;
 578
 579 #if DUMP_HASHTABLE_STATS
 580         atomicIncrement(&HashTableStats::numAccesses);
 581         int probeCount = 0;
 582 #endif
 583
 584 #if DUMP_HASHTABLE_STATS_PER_TABLE
 585         ++m_stats->numAccesses;
 586         int perTableProbeCount = 0;
 587 #endif
 588
 589         ValueType* deletedEntry = 0;
 590
 591         while (1) {
 592             ValueType* entry = table + i;
 593
 594             // we count on the compiler to optimize out this branch
 595             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
 596                 if (isEmptyBucket(*entry))
 597                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
 598
 599                 if (HashTranslator::equal(Extractor::extract(*entry), key))
 600                     return makeLookupResult(entry, true, h);
 601
 602                 if (isDeletedBucket(*entry))
 603                     deletedEntry = entry;
 604             } else {
 605                 if (isEmptyBucket(*entry))
 606                     return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
 607
 608                 if (isDeletedBucket(*entry))
 609                     deletedEntry = entry;
 610                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
 611                     return makeLookupResult(entry, true, h);
 612             }
 613 #if DUMP_HASHTABLE_STATS
 614             ++probeCount;
 615             HashTableStats::recordCollisionAtCount(probeCount);
 616 #endif
 617
 618 #if DUMP_HASHTABLE_STATS_PER_TABLE
 619             ++perTableProbeCount;
 620             m_stats->recordCollisionAtCount(perTableProbeCount);
 621 #endif
 622
 623             if (!k)
 624                 k = 1 | doubleHash(h);
 625             i = (i + k) & sizeMask;
 626         }
 627     }
 628
 629     template<bool emptyValueIsZero> struct HashTableBucketInitializer;
 630
 631     template<> struct HashTableBucketInitializer<false> {
 632         template<typename Traits, typename Value> static void initialize(Value& bucket)
 633         {
 634             new (NotNull, &bucket) Value(Traits::emptyValue());
 635         }
 636     };
 637
 638     template<> struct HashTableBucketInitializer<true> {
 639         template<typename Traits, typename Value> static void initialize(Value& bucket)
 640         {
 641             // This initializes the bucket without copying the empty value.
 642             // That makes it possible to use this with types that don't support copying.
 643             // The memset to 0 looks like a slow operation but is optimized by the compilers.
 644             memset(&bucket, 0, sizeof(bucket));
 645         }
 646     };
 647
 648     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 649     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::initializeBucket(ValueType& bucket)
 650     {
 651         HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket);
 652     }
 653
 654     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 655     template<typename HashTranslator, typename T, typename Extra>
 656     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::add(const T& key, const Extra& extra)
 657     {
 658         if (!m_table)
 659             expand();
 660
 661         ASSERT(m_table);
 662
 663         size_t k = 0;
 664         ValueType* table = m_table;
 665         size_t sizeMask = m_tableSizeMask;
 666         unsigned h = HashTranslator::hash(key);
 667         size_t i = h & sizeMask;
 668
 669 #if DUMP_HASHTABLE_STATS
 670         atomicIncrement(&HashTableStats::numAccesses);
 671         int probeCount = 0;
 672 #endif
 673
 674 #if DUMP_HASHTABLE_STATS_PER_TABLE
 675         ++m_stats->numAccesses;
 676         int perTableProbeCount = 0;
 677 #endif
 678
 679         ValueType* deletedEntry = 0;
 680         ValueType* entry;
 681         while (1) {
 682             entry = table + i;
 683
 684             // we count on the compiler to optimize out this branch
 685             if (HashFunctions::safeToCompareToEmptyOrDeleted) {
 686                 if (isEmptyBucket(*entry))
 687                     break;
 688
 689                 if (HashTranslator::equal(Extractor::extract(*entry), key))
 690                     return AddResult(entry, false);
 691
 692                 if (isDeletedBucket(*entry))
 693                     deletedEntry = entry;
 694             } else {
 695                 if (isEmptyBucket(*entry))
 696                     break;
 697
 698                 if (isDeletedBucket(*entry))
 699                     deletedEntry = entry;
 700                 else if (HashTranslator::equal(Extractor::extract(*entry), key))
 701                     return AddResult(entry, false);
 702             }
 703 #if DUMP_HASHTABLE_STATS
 704             ++probeCount;
 705             HashTableStats::recordCollisionAtCount(probeCount);
 706 #endif
 707
 708 #if DUMP_HASHTABLE_STATS_PER_TABLE
 709             ++perTableProbeCount;
 710             m_stats->recordCollisionAtCount(perTableProbeCount);
 711 #endif
 712
 713             if (!k)
 714                 k = 1 | doubleHash(h);
 715             i = (i + k) & sizeMask;
 716         }
 717
 718         if (deletedEntry) {
 719             initializeBucket(*deletedEntry);
 720             entry = deletedEntry;
 721             --m_deletedCount;
 722         }
 723
 724         HashTranslator::translate(*entry, key, extra);
 725
 726         ++m_keyCount;
 727
 728         if (shouldExpand()) {
 729             // FIXME: This makes an extra copy on expand. Probably not that bad since
 730             // expand is rare, but would be better to have a version of expand that can
 731             // follow a pivot entry and return the new position.
 732             typename WTF::RemoveReference<KeyPassInType>::Type enteredKey = Extractor::extract(*entry);
 733             expand();
 734             iterator findResult = find(enteredKey);
 735             ASSERT(findResult != end());
 736             ValueType* resultValue = findResult.get();
 737             AddResult result(resultValue, true);
 738             return result;
 739         }
 740
 741         return AddResult(entry, true);
 742     }
 743
 744     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 745     template<typename HashTranslator, typename T, typename Extra>
 746     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::addPassingHashCode(const T& key, const Extra& extra)
 747     {
 748         if (!m_table)
 749             expand();
 750
 751         FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key);
 752
 753         ValueType* entry = lookupResult.first.first;
 754         bool found = lookupResult.first.second;
 755         unsigned h = lookupResult.second;
 756
 757         if (found)
 758             return AddResult(entry, false);
 759
 760         if (isDeletedBucket(*entry)) {
 761             initializeBucket(*entry);
 762             --m_deletedCount;
 763         }
 764
 765         HashTranslator::translate(*entry, key, extra, h);
 766         ++m_keyCount;
 767         if (shouldExpand()) {
 768             // FIXME: This makes an extra copy on expand. Probably not that bad since
 769             // expand is rare, but would be better to have a version of expand that can
 770             // follow a pivot entry and return the new position.
 771             typename WTF::RemoveReference<KeyPassInType>::Type enteredKey = Extractor::extract(*entry);
 772             expand();
 773             iterator findResult = find(enteredKey);
 774             ASSERT(findResult != end());
 775             ValueType* resultValue = findResult.get();
 776             AddResult result(resultValue, true);
 777             return result;
 778         }
 779
 780         return AddResult(entry, true);
 781     }
 782
 783     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 784     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::reinsert(ValueType& entry)
 785     {
 786         ASSERT(m_table);
 787         ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
 788         ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
 789 #if DUMP_HASHTABLE_STATS
 790         atomicIncrement(&HashTableStats::numReinserts);
 791 #endif
 792 #if DUMP_HASHTABLE_STATS_PER_TABLE
 793         ++m_stats->numReinserts;
 794 #endif
 795
 796         Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first);
 797     }
 798
 799     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 800     template <typename HashTranslator, typename T>
 801     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::find(const T& key)
 802     {
 803         ValueType* entry = lookup<HashTranslator>(key);
 804         if (!entry)
 805             return end();
 806
 807         return makeKnownGoodIterator(entry);
 808     }
 809
 810     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 811     template <typename HashTranslator, typename T>
 812     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::find(const T& key) const
 813     {
 814         ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
 815         if (!entry)
 816             return end();
 817
 818         return makeKnownGoodConstIterator(entry);
 819     }
 820
 821     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 822     template <typename HashTranslator, typename T>
 823     bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::contains(const T& key) const
 824     {
 825         return const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
 826     }
 827
 828     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 829     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(ValueType* pos)
 830     {
 831 #if DUMP_HASHTABLE_STATS
 832         atomicIncrement(&HashTableStats::numRemoves);
 833 #endif
 834 #if DUMP_HASHTABLE_STATS_PER_TABLE
 835         ++m_stats->numRemoves;
 836 #endif
 837
 838         deleteBucket(*pos);
 839         ++m_deletedCount;
 840         --m_keyCount;
 841
 842         if (shouldShrink())
 843             shrink();
 844     }
 845
 846     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 847     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(iterator it)
 848     {
 849         if (it == end())
 850             return;
 851
 852         remove(const_cast<ValueType*>(it.m_iterator.m_position));
 853     }
 854
 855     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 856     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(const_iterator it)
 857     {
 858         if (it == end())
 859             return;
 860
 861         remove(const_cast<ValueType*>(it.m_position));
 862     }
 863
 864     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 865     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(KeyPeekInType key)
 866     {
 867         remove(find(key));
 868     }
 869
 870     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 871     Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::allocateTable(unsigned size)
 872     {
 873         typedef typename Allocator::template HashTableBackingHelper<Key, Value, Extractor, Traits, KeyTraits>::Type HashTableBacking;
 874
 875         size_t allocSize = size * sizeof(ValueType);
 876         ValueType* result;
 877         if (Traits::emptyValueIsZero) {
 878             result = Allocator::template zeroedBackingMalloc<ValueType*, HashTableBacking>(allocSize);
 879         } else {
 880             result = Allocator::template backingMalloc<ValueType*, HashTableBacking>(allocSize);
 881             for (unsigned i = 0; i < size; i++)
 882                 initializeBucket(result[i]);
 883         }
 884         return result;
 885     }
 886
 887     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 888     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::deallocateTable(ValueType* table, unsigned size)
 889     {
 890         if (Traits::needsDestruction) {
 891             for (unsigned i = 0; i < size; ++i) {
 892                 if (!isDeletedBucket(table[i]))
 893                     table[i].~ValueType();
 894             }
 895         }
 896         Allocator::backingFree(table);
 897     }
 898
 899     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 900     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::expand()
 901     {
 902         unsigned newSize;
 903         if (!m_tableSize) {
 904             newSize = KeyTraits::minimumTableSize;
 905         } else if (mustRehashInPlace()) {
 906             newSize = m_tableSize;
 907         } else {
 908             newSize = m_tableSize * 2;
 909             RELEASE_ASSERT(newSize > m_tableSize);
 910         }
 911
 912         rehash(newSize);
 913     }
 914
 915     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 916     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::rehash(unsigned newTableSize)
 917     {
 918         unsigned 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 #if DUMP_HASHTABLE_STATS_PER_TABLE
 927         if (oldTableSize != 0)
 928             ++m_stats->numRehashes;
 929 #endif
 930
 931         m_table = allocateTable(newTableSize);
 932         m_tableSize = newTableSize;
 933         m_tableSizeMask = newTableSize - 1;
 934
 935         for (unsigned i = 0; i != oldTableSize; ++i)
 936             if (!isEmptyOrDeletedBucket(oldTable[i]))
 937                 reinsert(oldTable[i]);
 938
 939         m_deletedCount = 0;
 940
 941         deallocateTable(oldTable, oldTableSize);
 942     }
 943
 944     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 945     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::clear()
 946     {
 947         if (!m_table)
 948             return;
 949
 950         deallocateTable(m_table, m_tableSize);
 951         m_table = 0;
 952         m_tableSize = 0;
 953         m_tableSizeMask = 0;
 954         m_keyCount = 0;
 955     }
 956
 957     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 958     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::HashTable(const HashTable& other)
 959         : m_table(0)
 960         , m_tableSize(0)
 961         , m_tableSizeMask(0)
 962         , m_keyCount(0)
 963         , m_deletedCount(0)
 964 #if DUMP_HASHTABLE_STATS_PER_TABLE
 965         , m_stats(adoptPtr(new Stats(*other.m_stats)))
 966 #endif
 967     {
 968         // Copy the hash table the dumb way, by adding each element to the new table.
 969         // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
 970         const_iterator end = other.end();
 971         for (const_iterator it = other.begin(); it != end; ++it)
 972             add(*it);
 973     }
 974
 975     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 976     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::swap(HashTable& other)
 977     {
 978         ValueType* tmpTable = m_table;
 979         m_table = other.m_table;
 980         other.m_table = tmpTable;
 981
 982         size_t tmpTableSize = m_tableSize;
 983         m_tableSize = other.m_tableSize;
 984         other.m_tableSize = tmpTableSize;
 985
 986         size_t tmpTableSizeMask = m_tableSizeMask;
 987         m_tableSizeMask = other.m_tableSizeMask;
 988         other.m_tableSizeMask = tmpTableSizeMask;
 989
 990         size_t tmpKeyCount = m_keyCount;
 991         m_keyCount = other.m_keyCount;
 992         other.m_keyCount = tmpKeyCount;
 993
 994         size_t tmpDeletedCount = m_deletedCount;
 995         m_deletedCount = other.m_deletedCount;
 996         other.m_deletedCount = tmpDeletedCount;
 997
 998 #if DUMP_HASHTABLE_STATS_PER_TABLE
 999         m_stats.swap(other.m_stats);
1000 #endif
1001     }
1002
1003     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1004     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::operator=(const HashTable& other)
1005     {
1006         HashTable tmp(other);
1007         swap(tmp);
1008         return *this;
1009     }
1010
1011     template<bool isWeak, typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1012     struct WeakProcessingHashTableHelper;
1013
1014     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1015     struct WeakProcessingHashTableHelper<false, Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> {
1016         static void process(typename Allocator::Visitor* visitor, void* closure) { }
1017     };
1018
1019     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1020     struct WeakProcessingHashTableHelper<true, Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> {
1021         static void process(typename Allocator::Visitor* visitor, void* closure)
1022         {
1023             typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> HashTableType;
1024             HashTableType* table = reinterpret_cast<HashTableType*>(closure);
1025             if (table->m_table) {
1026                 // This just marks it live and does not push anything onto the
1027                 // marking stack.
1028                 Allocator::markNoTracing(visitor, table->m_table);
1029                 // Now perform weak processing (this is a no-op if the backing
1030                 // was accessible through an iterator and was already marked
1031                 // strongly).
1032                 for (typename HashTableType::ValueType* element = table->m_table + table->m_tableSize - 1; element >= table->m_table; element--) {
1033                     if (!HashTableType::isEmptyOrDeletedBucket(*element)) {
1034                         if (Allocator::hasDeadMember(visitor, *element)) {
1035                             HashTableType::deleteBucket(*element); // Also calls the destructor.
1036                             table->m_deletedCount++;
1037                             table->m_keyCount--;
1038                             // We don't rehash the backing until the next add
1039                             // or delete, because that would cause allocation
1040                             // during GC.
1041                         }
1042                     }
1043                 }
1044             }
1045         }
1046     };
1047
1048     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1049     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::trace(typename Allocator::Visitor* visitor)
1050     {
1051         // If someone else already marked the backing and queued up the trace
1052         // and/or weak callback then we are done.
1053         if (!m_table || visitor->isAlive(m_table))
1054             return;
1055         // Normally, we mark the backing store without performing trace. This
1056         // means it is marked live, but the pointers inside it are not marked.
1057         // Instead we will mark the pointers below. However, for backing
1058         // stores that contain weak pointers the handling is rather different.
1059         // We don't mark the backing store here, so the marking GC will leave
1060         // the backing unmarked. If the backing is found in any other way than
1061         // through its HashTable (ie from an iterator) then the mark bit will
1062         // be set and the pointers will be marked strongly, avoiding problems
1063         // with iterating over things that disappear due to weak processing
1064         // while we are iterating over them. The weakProcessing callback will
1065         // mark the backing as a void pointer, and will perform weak processing
1066         // if needed.
1067         if (!Traits::isWeak)
1068             Allocator::markNoTracing(visitor, m_table);
1069         else
1070             Allocator::registerWeakMembers(visitor, this, WeakProcessingHashTableHelper<Traits::isWeak, Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::process);
1071         if (Traits::needsTracing) {
1072             for (ValueType* element = m_table + m_tableSize - 1; element >= m_table; element--) {
1073                 if (!isEmptyOrDeletedBucket(*element))
1074                     Allocator::template trace<ValueType, Traits>(visitor, *element);
1075             }
1076         }
1077     }
1078
1079     // iterator adapters
1080
1081     template<typename HashTableType, typename Traits> struct HashTableConstIteratorAdapter {
1082         HashTableConstIteratorAdapter() {}
1083         HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
1084         typedef typename Traits::IteratorConstGetType GetType;
1085         typedef typename HashTableType::ValueTraits::IteratorConstGetType SourceGetType;
1086
1087         GetType get() const { return const_cast<GetType>(SourceGetType(m_impl.get())); }
1088         typename Traits::IteratorConstReferenceType operator*() const { return Traits::getToReferenceConstConversion(get()); }
1089         GetType operator->() const { return get(); }
1090
1091         HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
1092         // postfix ++ intentionally omitted
1093
1094         typename HashTableType::const_iterator m_impl;
1095     };
1096
1097     template<typename HashTableType, typename Traits> struct HashTableIteratorAdapter {
1098         typedef typename Traits::IteratorGetType GetType;
1099         typedef typename HashTableType::ValueTraits::IteratorGetType SourceGetType;
1100
1101         HashTableIteratorAdapter() {}
1102         HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
1103
1104         GetType get() const { return const_cast<GetType>(SourceGetType(m_impl.get())); }
1105         typename Traits::IteratorReferenceType operator*() const { return Traits::getToReferenceConversion(get()); }
1106         GetType operator->() const { return get(); }
1107
1108         HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
1109         // postfix ++ intentionally omitted
1110
1111         operator HashTableConstIteratorAdapter<HashTableType, Traits>()
1112         {
1113             typename HashTableType::const_iterator i = m_impl;
1114             return i;
1115         }
1116
1117         typename HashTableType::iterator m_impl;
1118     };
1119
1120     template<typename T, typename U>
1121     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1122     {
1123         return a.m_impl == b.m_impl;
1124     }
1125
1126     template<typename T, typename U>
1127     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1128     {
1129         return a.m_impl != b.m_impl;
1130     }
1131
1132     template<typename T, typename U>
1133     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1134     {
1135         return a.m_impl == b.m_impl;
1136     }
1137
1138     template<typename T, typename U>
1139     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1140     {
1141         return a.m_impl != b.m_impl;
1142     }
1143
1144     // All 4 combinations of ==, != and Const,non const.
1145     template<typename T, typename U>
1146     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1147     {
1148         return a.m_impl == b.m_impl;
1149     }
1150
1151     template<typename T, typename U>
1152     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1153     {
1154         return a.m_impl != b.m_impl;
1155     }
1156
1157     template<typename T, typename U>
1158     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1159     {
1160         return a.m_impl == b.m_impl;
1161     }
1162
1163     template<typename T, typename U>
1164     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1165     {
1166         return a.m_impl != b.m_impl;
1167     }
1168
1169 } // namespace WTF
1170
1171 #include "wtf/HashIterators.h"
1172
1173 #endif // WTF_HashTable_h