wtf/HashTable.h

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