00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef WTF_HashTable_h
00023 #define WTF_HashTable_h
00024
00025 #include "FastMalloc.h"
00026 #include "HashTraits.h"
00027 #include <wtf/Assertions.h>
00028
00029 namespace WTF {
00030
00031 #define DUMP_HASHTABLE_STATS 0
00032 #define CHECK_HASHTABLE_CONSISTENCY 0
00033
00034
00035
00036 #define CHECK_HASHTABLE_ITERATORS 0
00037 #define CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 0
00038
00039 #if DUMP_HASHTABLE_STATS
00040
00041 struct HashTableStats {
00042 ~HashTableStats();
00043 static int numAccesses;
00044 static int numCollisions;
00045 static int collisionGraph[4096];
00046 static int maxCollisions;
00047 static int numRehashes;
00048 static int numRemoves;
00049 static int numReinserts;
00050 static void recordCollisionAtCount(int count);
00051 };
00052
00053 #endif
00054
00055 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00056 class HashTable;
00057 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00058 class HashTableIterator;
00059 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00060 class HashTableConstIterator;
00061
00062 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00063 void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
00064 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
00065
00066 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00067 void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
00068
00069 #if !CHECK_HASHTABLE_ITERATORS
00070
00071 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00072 inline void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
00073 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
00074
00075 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00076 inline void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
00077
00078 #endif
00079
00080 typedef enum { HashItemKnownGood } HashItemKnownGoodTag;
00081
00082 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00083 class HashTableConstIterator {
00084 private:
00085 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
00086 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
00087 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
00088 typedef Value ValueType;
00089 typedef const ValueType& ReferenceType;
00090 typedef const ValueType* PointerType;
00091
00092 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
00093 friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
00094
00095 void skipEmptyBuckets()
00096 {
00097 while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position))
00098 ++m_position;
00099 }
00100
00101 HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition)
00102 : m_position(position), m_endPosition(endPosition)
00103 {
00104 addIterator(table, this);
00105 skipEmptyBuckets();
00106 }
00107
00108 HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition, HashItemKnownGoodTag)
00109 : m_position(position), m_endPosition(endPosition)
00110 {
00111 addIterator(table, this);
00112 }
00113
00114 public:
00115 HashTableConstIterator()
00116 {
00117 addIterator(0, this);
00118 }
00119
00120
00121
00122 #if CHECK_HASHTABLE_ITERATORS
00123 ~HashTableConstIterator()
00124 {
00125 removeIterator(this);
00126 }
00127
00128 HashTableConstIterator(const const_iterator& other)
00129 : m_position(other.m_position), m_endPosition(other.m_endPosition)
00130 {
00131 addIterator(other.m_table, this);
00132 }
00133
00134 const_iterator& operator=(const const_iterator& other)
00135 {
00136 m_position = other.m_position;
00137 m_endPosition = other.m_endPosition;
00138
00139 removeIterator(this);
00140 addIterator(other.m_table, this);
00141
00142 return *this;
00143 }
00144 #endif
00145
00146 PointerType get() const
00147 {
00148 checkValidity();
00149 return m_position;
00150 }
00151 ReferenceType operator*() const { return *get(); }
00152 PointerType operator->() const { return get(); }
00153
00154 const_iterator& operator++()
00155 {
00156 checkValidity();
00157 ASSERT(m_position != m_endPosition);
00158 ++m_position;
00159 skipEmptyBuckets();
00160 return *this;
00161 }
00162
00163
00164
00165
00166 bool operator==(const const_iterator& other) const
00167 {
00168 checkValidity(other);
00169 return m_position == other.m_position;
00170 }
00171 bool operator!=(const const_iterator& other) const
00172 {
00173 checkValidity(other);
00174 return m_position != other.m_position;
00175 }
00176
00177 private:
00178 void checkValidity() const
00179 {
00180 #if CHECK_HASHTABLE_ITERATORS
00181 ASSERT(m_table);
00182 #endif
00183 }
00184
00185
00186 #if CHECK_HASHTABLE_ITERATORS
00187 void checkValidity(const const_iterator& other) const
00188 {
00189 ASSERT(m_table);
00190 ASSERT(other.m_table);
00191 ASSERT(m_table == other.m_table);
00192 }
00193 #else
00194 void checkValidity(const const_iterator&) const { }
00195 #endif
00196
00197 PointerType m_position;
00198 PointerType m_endPosition;
00199
00200 #if CHECK_HASHTABLE_ITERATORS
00201 public:
00202 mutable const HashTableType* m_table;
00203 mutable const_iterator* m_next;
00204 mutable const_iterator* m_previous;
00205 #endif
00206 };
00207
00208 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00209 class HashTableIterator {
00210 private:
00211 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
00212 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
00213 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
00214 typedef Value ValueType;
00215 typedef ValueType& ReferenceType;
00216 typedef ValueType* PointerType;
00217
00218 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
00219
00220 HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { }
00221 HashTableIterator(HashTableType* table, PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(table, pos, end, tag) { }
00222
00223 public:
00224 HashTableIterator() { }
00225
00226
00227
00228 PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
00229 ReferenceType operator*() const { return *get(); }
00230 PointerType operator->() const { return get(); }
00231
00232 iterator& operator++() { ++m_iterator; return *this; }
00233
00234
00235
00236
00237 bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
00238 bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
00239
00240 operator const_iterator() const { return m_iterator; }
00241
00242 private:
00243 const_iterator m_iterator;
00244 };
00245
00246 using std::swap;
00247
00248 #if !COMPILER(MSVC)
00249
00250
00251
00252 template<typename T, typename U> inline void swap(pair<T, U>& a, pair<T, U>& b)
00253 {
00254 swap(a.first, b.first);
00255 swap(a.second, b.second);
00256 }
00257 #endif
00258
00259 template<typename T, bool useSwap> struct Mover;
00260 template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { swap(from, to); } };
00261 template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } };
00262
00263 template<typename Key, typename Value, typename HashFunctions> class IdentityHashTranslator {
00264 public:
00265 static unsigned hash(const Key& key) { return HashFunctions::hash(key); }
00266 static bool equal(const Key& a, const Key& b) { return HashFunctions::equal(a, b); }
00267 static void translate(Value& location, const Key&, const Value& value) { location = value; }
00268 };
00269
00270 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00271 class HashTable {
00272 public:
00273 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
00274 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
00275 typedef Traits ValueTraits;
00276 typedef Key KeyType;
00277 typedef Value ValueType;
00278 typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType;
00279
00280 HashTable();
00281 ~HashTable()
00282 {
00283 invalidateIterators();
00284 deallocateTable(m_table, m_tableSize);
00285 #if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION
00286 m_table = (ValueType*)(uintptr_t)0xbbadbeef;
00287 #endif
00288 }
00289
00290 HashTable(const HashTable&);
00291 void swap(HashTable&);
00292 HashTable& operator=(const HashTable&);
00293
00294 iterator begin() { return makeIterator(m_table); }
00295 iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
00296 const_iterator begin() const { return makeConstIterator(m_table); }
00297 const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
00298
00299 int size() const { return m_keyCount; }
00300 int capacity() const { return m_tableSize; }
00301 bool isEmpty() const { return !m_keyCount; }
00302
00303 pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }
00304
00305
00306
00307
00308 template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&);
00309 template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> addPassingHashCode(const T& key, const Extra&);
00310
00311 iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); }
00312 const_iterator find(const KeyType& key) const { return find<KeyType, IdentityTranslatorType>(key); }
00313 bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); }
00314
00315 template <typename T, typename HashTranslator> iterator find(const T&);
00316 template <typename T, typename HashTranslator> const_iterator find(const T&) const;
00317 template <typename T, typename HashTranslator> bool contains(const T&) const;
00318
00319 void remove(const KeyType&);
00320 void remove(iterator);
00321 void removeWithoutEntryConsistencyCheck(iterator);
00322 void clear();
00323
00324 static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); }
00325 static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
00326 static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
00327
00328 ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); }
00329 template<typename T, typename HashTranslator> ValueType* lookup(const T&);
00330
00331 #if CHECK_HASHTABLE_CONSISTENCY
00332 void checkTableConsistency() const;
00333 #else
00334 static void checkTableConsistency() { }
00335 #endif
00336
00337 private:
00338 static ValueType* allocateTable(int size);
00339 static void deallocateTable(ValueType* table, int size);
00340
00341 typedef pair<ValueType*, bool> LookupType;
00342 typedef pair<LookupType, unsigned> FullLookupType;
00343
00344 LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); };
00345 template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&);
00346 template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&);
00347
00348 template<typename T, typename HashTranslator> void checkKey(const T&);
00349
00350 void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
00351 void removeAndInvalidate(ValueType*);
00352 void remove(ValueType*);
00353
00354 bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
00355 bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
00356 bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; }
00357 void expand();
00358 void shrink() { rehash(m_tableSize / 2); }
00359
00360 void rehash(int newTableSize);
00361 void reinsert(ValueType&);
00362
00363 static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }
00364 static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(&bucket); }
00365
00366 FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
00367 { return FullLookupType(LookupType(position, found), hash); }
00368
00369 iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
00370 const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
00371 iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
00372 const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
00373
00374 #if CHECK_HASHTABLE_CONSISTENCY
00375 void checkTableConsistencyExceptSize() const;
00376 #else
00377 static void checkTableConsistencyExceptSize() { }
00378 #endif
00379
00380 #if CHECK_HASHTABLE_ITERATORS
00381 void invalidateIterators();
00382 #else
00383 static void invalidateIterators() { }
00384 #endif
00385
00386 static const int m_minTableSize = 64;
00387 static const int m_maxLoad = 2;
00388 static const int m_minLoad = 6;
00389
00390 ValueType* m_table;
00391 int m_tableSize;
00392 int m_tableSizeMask;
00393 int m_keyCount;
00394 int m_deletedCount;
00395
00396 #if CHECK_HASHTABLE_ITERATORS
00397 public:
00398 mutable const_iterator* m_iterators;
00399 #endif
00400 };
00401
00402 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00403 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
00404 : m_table(0)
00405 , m_tableSize(0)
00406 , m_tableSizeMask(0)
00407 , m_keyCount(0)
00408 , m_deletedCount(0)
00409 #if CHECK_HASHTABLE_ITERATORS
00410 , m_iterators(0)
00411 #endif
00412 {
00413 }
00414
00415 static inline unsigned doubleHash(unsigned key)
00416 {
00417 key = ~key + (key >> 23);
00418 key ^= (key << 12);
00419 key ^= (key >> 7);
00420 key ^= (key << 2);
00421 key ^= (key >> 20);
00422 return key;
00423 }
00424
00425 #if ASSERT_DISABLED
00426
00427 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00428 template<typename T, typename HashTranslator>
00429 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
00430 {
00431 }
00432
00433 #else
00434
00435 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00436 template<typename T, typename HashTranslator>
00437 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)
00438 {
00439 if (!HashFunctions::safeToCompareToEmptyOrDeleted)
00440 return;
00441 ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
00442 ValueType deletedValue = Traits::emptyValue();
00443 deletedValue.~ValueType();
00444 Traits::constructDeletedValue(&deletedValue);
00445 ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
00446 new (&deletedValue) ValueType(Traits::emptyValue());
00447 }
00448
00449 #endif
00450
00451 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00452 template<typename T, typename HashTranslator>
00453 inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
00454 {
00455 checkKey<T, HashTranslator>(key);
00456
00457 int k = 0;
00458 int sizeMask = m_tableSizeMask;
00459 ValueType* table = m_table;
00460 unsigned h = HashTranslator::hash(key);
00461 int i = h & sizeMask;
00462
00463 if (!table)
00464 return 0;
00465
00466 #if DUMP_HASHTABLE_STATS
00467 ++HashTableStats::numAccesses;
00468 int probeCount = 0;
00469 #endif
00470
00471 while (1) {
00472 ValueType* entry = table + i;
00473
00474
00475 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
00476 if (HashTranslator::equal(Extractor::extract(*entry), key))
00477 return entry;
00478
00479 if (isEmptyBucket(*entry))
00480 return 0;
00481 } else {
00482 if (isEmptyBucket(*entry))
00483 return 0;
00484
00485 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
00486 return entry;
00487 }
00488 #if DUMP_HASHTABLE_STATS
00489 ++probeCount;
00490 HashTableStats::recordCollisionAtCount(probeCount);
00491 #endif
00492 if (k == 0)
00493 k = 1 | doubleHash(h);
00494 i = (i + k) & sizeMask;
00495 }
00496 }
00497
00498 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00499 template<typename T, typename HashTranslator>
00500 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key)
00501 {
00502 ASSERT(m_table);
00503 checkKey<T, HashTranslator>(key);
00504
00505 int k = 0;
00506 ValueType* table = m_table;
00507 int sizeMask = m_tableSizeMask;
00508 unsigned h = HashTranslator::hash(key);
00509 int i = h & sizeMask;
00510
00511 #if DUMP_HASHTABLE_STATS
00512 ++HashTableStats::numAccesses;
00513 int probeCount = 0;
00514 #endif
00515
00516 ValueType* deletedEntry = 0;
00517
00518 while (1) {
00519 ValueType* entry = table + i;
00520
00521
00522 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
00523 if (isEmptyBucket(*entry))
00524 return LookupType(deletedEntry ? deletedEntry : entry, false);
00525
00526 if (HashTranslator::equal(Extractor::extract(*entry), key))
00527 return LookupType(entry, true);
00528
00529 if (isDeletedBucket(*entry))
00530 deletedEntry = entry;
00531 } else {
00532 if (isEmptyBucket(*entry))
00533 return LookupType(deletedEntry ? deletedEntry : entry, false);
00534
00535 if (isDeletedBucket(*entry))
00536 deletedEntry = entry;
00537 else if (HashTranslator::equal(Extractor::extract(*entry), key))
00538 return LookupType(entry, true);
00539 }
00540 #if DUMP_HASHTABLE_STATS
00541 ++probeCount;
00542 HashTableStats::recordCollisionAtCount(probeCount);
00543 #endif
00544 if (k == 0)
00545 k = 1 | doubleHash(h);
00546 i = (i + k) & sizeMask;
00547 }
00548 }
00549
00550 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00551 template<typename T, typename HashTranslator>
00552 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key)
00553 {
00554 ASSERT(m_table);
00555 checkKey<T, HashTranslator>(key);
00556
00557 int k = 0;
00558 ValueType* table = m_table;
00559 int sizeMask = m_tableSizeMask;
00560 unsigned h = HashTranslator::hash(key);
00561 int i = h & sizeMask;
00562
00563 #if DUMP_HASHTABLE_STATS
00564 ++HashTableStats::numAccesses;
00565 int probeCount = 0;
00566 #endif
00567
00568 ValueType* deletedEntry = 0;
00569
00570 while (1) {
00571 ValueType* entry = table + i;
00572
00573
00574 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
00575 if (isEmptyBucket(*entry))
00576 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
00577
00578 if (HashTranslator::equal(Extractor::extract(*entry), key))
00579 return makeLookupResult(entry, true, h);
00580
00581 if (isDeletedBucket(*entry))
00582 deletedEntry = entry;
00583 } else {
00584 if (isEmptyBucket(*entry))
00585 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
00586
00587 if (isDeletedBucket(*entry))
00588 deletedEntry = entry;
00589 else if (HashTranslator::equal(Extractor::extract(*entry), key))
00590 return makeLookupResult(entry, true, h);
00591 }
00592 #if DUMP_HASHTABLE_STATS
00593 ++probeCount;
00594 HashTableStats::recordCollisionAtCount(probeCount);
00595 #endif
00596 if (k == 0)
00597 k = 1 | doubleHash(h);
00598 i = (i + k) & sizeMask;
00599 }
00600 }
00601
00602 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00603 template<typename T, typename Extra, typename HashTranslator>
00604 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)
00605 {
00606 checkKey<T, HashTranslator>(key);
00607
00608 invalidateIterators();
00609
00610 if (!m_table)
00611 expand();
00612
00613 checkTableConsistency();
00614
00615 ASSERT(m_table);
00616
00617 int k = 0;
00618 ValueType* table = m_table;
00619 int sizeMask = m_tableSizeMask;
00620 unsigned h = HashTranslator::hash(key);
00621 int i = h & sizeMask;
00622
00623 #if DUMP_HASHTABLE_STATS
00624 ++HashTableStats::numAccesses;
00625 int probeCount = 0;
00626 #endif
00627
00628 ValueType* deletedEntry = 0;
00629 ValueType* entry;
00630 while (1) {
00631 entry = table + i;
00632
00633
00634 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
00635 if (isEmptyBucket(*entry))
00636 break;
00637
00638 if (HashTranslator::equal(Extractor::extract(*entry), key))
00639 return std::make_pair(makeKnownGoodIterator(entry), false);
00640
00641 if (isDeletedBucket(*entry))
00642 deletedEntry = entry;
00643 } else {
00644 if (isEmptyBucket(*entry))
00645 break;
00646
00647 if (isDeletedBucket(*entry))
00648 deletedEntry = entry;
00649 else if (HashTranslator::equal(Extractor::extract(*entry), key))
00650 return std::make_pair(makeKnownGoodIterator(entry), false);
00651 }
00652 #if DUMP_HASHTABLE_STATS
00653 ++probeCount;
00654 HashTableStats::recordCollisionAtCount(probeCount);
00655 #endif
00656 if (k == 0)
00657 k = 1 | doubleHash(h);
00658 i = (i + k) & sizeMask;
00659 }
00660
00661 if (deletedEntry) {
00662 initializeBucket(*deletedEntry);
00663 entry = deletedEntry;
00664 --m_deletedCount;
00665 }
00666
00667 HashTranslator::translate(*entry, key, extra);
00668
00669 ++m_keyCount;
00670
00671 if (shouldExpand()) {
00672
00673
00674
00675 KeyType enteredKey = Extractor::extract(*entry);
00676 expand();
00677 return std::make_pair(find(enteredKey), true);
00678 }
00679
00680 checkTableConsistency();
00681
00682 return std::make_pair(makeKnownGoodIterator(entry), true);
00683 }
00684
00685 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00686 template<typename T, typename Extra, typename HashTranslator>
00687 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)
00688 {
00689 checkKey<T, HashTranslator>(key);
00690
00691 invalidateIterators();
00692
00693 if (!m_table)
00694 expand();
00695
00696 checkTableConsistency();
00697
00698 FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key);
00699
00700 ValueType* entry = lookupResult.first.first;
00701 bool found = lookupResult.first.second;
00702 unsigned h = lookupResult.second;
00703
00704 if (found)
00705 return std::make_pair(makeKnownGoodIterator(entry), false);
00706
00707 if (isDeletedBucket(*entry)) {
00708 initializeBucket(*entry);
00709 --m_deletedCount;
00710 }
00711
00712 HashTranslator::translate(*entry, key, extra, h);
00713 ++m_keyCount;
00714 if (shouldExpand()) {
00715
00716
00717
00718 KeyType enteredKey = Extractor::extract(*entry);
00719 expand();
00720 return std::make_pair(find(enteredKey), true);
00721 }
00722
00723 checkTableConsistency();
00724
00725 return std::make_pair(makeKnownGoodIterator(entry), true);
00726 }
00727
00728 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00729 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)
00730 {
00731 ASSERT(m_table);
00732 ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
00733 ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
00734 #if DUMP_HASHTABLE_STATS
00735 ++HashTableStats::numReinserts;
00736 #endif
00737
00738 Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first);
00739 }
00740
00741 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00742 template <typename T, typename HashTranslator>
00743 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key)
00744 {
00745 if (!m_table)
00746 return end();
00747
00748 ValueType* entry = lookup<T, HashTranslator>(key);
00749 if (!entry)
00750 return end();
00751
00752 return makeKnownGoodIterator(entry);
00753 }
00754
00755 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00756 template <typename T, typename HashTranslator>
00757 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const
00758 {
00759 if (!m_table)
00760 return end();
00761
00762 ValueType* entry = const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);
00763 if (!entry)
00764 return end();
00765
00766 return makeKnownGoodConstIterator(entry);
00767 }
00768
00769 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00770 template <typename T, typename HashTranslator>
00771 bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const
00772 {
00773 if (!m_table)
00774 return false;
00775
00776 return const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);
00777 }
00778
00779 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00780 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos)
00781 {
00782 invalidateIterators();
00783 remove(pos);
00784 }
00785
00786 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00787 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos)
00788 {
00789 invalidateIterators();
00790 checkTableConsistency();
00791 remove(pos);
00792 }
00793
00794 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00795 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
00796 {
00797 #if DUMP_HASHTABLE_STATS
00798 ++HashTableStats::numRemoves;
00799 #endif
00800
00801 deleteBucket(*pos);
00802 ++m_deletedCount;
00803 --m_keyCount;
00804
00805 if (shouldShrink())
00806 shrink();
00807
00808 checkTableConsistency();
00809 }
00810
00811 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00812 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
00813 {
00814 if (it == end())
00815 return;
00816
00817 removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position));
00818 }
00819
00820 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00821 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it)
00822 {
00823 if (it == end())
00824 return;
00825
00826 removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position));
00827 }
00828
00829 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00830 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
00831 {
00832 remove(find(key));
00833 }
00834
00835 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00836 Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
00837 {
00838
00839
00840 if (Traits::emptyValueIsZero)
00841 return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType)));
00842 ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
00843 for (int i = 0; i < size; i++)
00844 initializeBucket(result[i]);
00845 return result;
00846 }
00847
00848 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00849 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, int size)
00850 {
00851 if (Traits::needsDestruction) {
00852 for (int i = 0; i < size; ++i) {
00853 if (!isDeletedBucket(table[i]))
00854 table[i].~ValueType();
00855 }
00856 }
00857 fastFree(table);
00858 }
00859
00860 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00861 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
00862 {
00863 int newSize;
00864 if (m_tableSize == 0)
00865 newSize = m_minTableSize;
00866 else if (mustRehashInPlace())
00867 newSize = m_tableSize;
00868 else
00869 newSize = m_tableSize * 2;
00870
00871 rehash(newSize);
00872 }
00873
00874 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00875 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize)
00876 {
00877 checkTableConsistencyExceptSize();
00878
00879 int oldTableSize = m_tableSize;
00880 ValueType* oldTable = m_table;
00881
00882 #if DUMP_HASHTABLE_STATS
00883 if (oldTableSize != 0)
00884 ++HashTableStats::numRehashes;
00885 #endif
00886
00887 m_tableSize = newTableSize;
00888 m_tableSizeMask = newTableSize - 1;
00889 m_table = allocateTable(newTableSize);
00890
00891 for (int i = 0; i != oldTableSize; ++i)
00892 if (!isEmptyOrDeletedBucket(oldTable[i]))
00893 reinsert(oldTable[i]);
00894
00895 m_deletedCount = 0;
00896
00897 deallocateTable(oldTable, oldTableSize);
00898
00899 checkTableConsistency();
00900 }
00901
00902 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00903 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
00904 {
00905 invalidateIterators();
00906 deallocateTable(m_table, m_tableSize);
00907 m_table = 0;
00908 m_tableSize = 0;
00909 m_tableSizeMask = 0;
00910 m_keyCount = 0;
00911 }
00912
00913 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00914 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
00915 : m_table(0)
00916 , m_tableSize(0)
00917 , m_tableSizeMask(0)
00918 , m_keyCount(0)
00919 , m_deletedCount(0)
00920 #if CHECK_HASHTABLE_ITERATORS
00921 , m_iterators(0)
00922 #endif
00923 {
00924
00925
00926 const_iterator end = other.end();
00927 for (const_iterator it = other.begin(); it != end; ++it)
00928 add(*it);
00929 }
00930
00931 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00932 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
00933 {
00934 invalidateIterators();
00935 other.invalidateIterators();
00936
00937 ValueType* tmp_table = m_table;
00938 m_table = other.m_table;
00939 other.m_table = tmp_table;
00940
00941 int tmp_tableSize = m_tableSize;
00942 m_tableSize = other.m_tableSize;
00943 other.m_tableSize = tmp_tableSize;
00944
00945 int tmp_tableSizeMask = m_tableSizeMask;
00946 m_tableSizeMask = other.m_tableSizeMask;
00947 other.m_tableSizeMask = tmp_tableSizeMask;
00948
00949 int tmp_keyCount = m_keyCount;
00950 m_keyCount = other.m_keyCount;
00951 other.m_keyCount = tmp_keyCount;
00952
00953 int tmp_deletedCount = m_deletedCount;
00954 m_deletedCount = other.m_deletedCount;
00955 other.m_deletedCount = tmp_deletedCount;
00956 }
00957
00958 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00959 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)
00960 {
00961 HashTable tmp(other);
00962 swap(tmp);
00963 return *this;
00964 }
00965
00966 #if CHECK_HASHTABLE_CONSISTENCY
00967
00968 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00969 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
00970 {
00971 checkTableConsistencyExceptSize();
00972 ASSERT(!shouldExpand());
00973 ASSERT(!shouldShrink());
00974 }
00975
00976 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00977 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
00978 {
00979 if (!m_table)
00980 return;
00981
00982 int count = 0;
00983 int deletedCount = 0;
00984 for (int j = 0; j < m_tableSize; ++j) {
00985 ValueType* entry = m_table + j;
00986 if (isEmptyBucket(*entry))
00987 continue;
00988
00989 if (isDeletedBucket(*entry)) {
00990 ++deletedCount;
00991 continue;
00992 }
00993
00994 const_iterator it = find(Extractor::extract(*entry));
00995 ASSERT(entry == it.m_position);
00996 ++count;
00997 }
00998
00999 ASSERT(count == m_keyCount);
01000 ASSERT(deletedCount == m_deletedCount);
01001 ASSERT(m_tableSize >= m_minTableSize);
01002 ASSERT(m_tableSizeMask);
01003 ASSERT(m_tableSize == m_tableSizeMask + 1);
01004 }
01005
01006 #endif // CHECK_HASHTABLE_CONSISTENCY
01007
01008 #if CHECK_HASHTABLE_ITERATORS
01009
01010 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
01011 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
01012 {
01013 const_iterator* next;
01014 for (const_iterator* p = m_iterators; p; p = next) {
01015 next = p->m_next;
01016 p->m_table = 0;
01017 p->m_next = 0;
01018 p->m_previous = 0;
01019 }
01020 m_iterators = 0;
01021 }
01022
01023 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
01024 void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
01025 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
01026 {
01027 it->m_table = table;
01028 it->m_previous = 0;
01029
01030
01031 if (!table) {
01032 it->m_next = 0;
01033 } else {
01034 ASSERT(table->m_iterators != it);
01035 it->m_next = table->m_iterators;
01036 table->m_iterators = it;
01037 if (it->m_next) {
01038 ASSERT(!it->m_next->m_previous);
01039 it->m_next->m_previous = it;
01040 }
01041 }
01042 }
01043
01044 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
01045 void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
01046 {
01047 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
01048 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
01049
01050
01051 if (!it->m_table) {
01052 ASSERT(!it->m_next);
01053 ASSERT(!it->m_previous);
01054 } else {
01055 if (it->m_next) {
01056 ASSERT(it->m_next->m_previous == it);
01057 it->m_next->m_previous = it->m_previous;
01058 }
01059 if (it->m_previous) {
01060 ASSERT(it->m_table->m_iterators != it);
01061 ASSERT(it->m_previous->m_next == it);
01062 it->m_previous->m_next = it->m_next;
01063 } else {
01064 ASSERT(it->m_table->m_iterators == it);
01065 it->m_table->m_iterators = it->m_next;
01066 }
01067 }
01068
01069 it->m_table = 0;
01070 it->m_next = 0;
01071 it->m_previous = 0;
01072 }
01073
01074 #endif // CHECK_HASHTABLE_ITERATORS
01075
01076
01077
01078 template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
01079 HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
01080
01081 const ValueType* get() const { return (const ValueType*)m_impl.get(); }
01082 const ValueType& operator*() const { return *get(); }
01083 const ValueType* operator->() const { return get(); }
01084
01085 HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
01086
01087
01088 typename HashTableType::const_iterator m_impl;
01089 };
01090
01091 template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
01092 HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
01093
01094 ValueType* get() const { return (ValueType*)m_impl.get(); }
01095 ValueType& operator*() const { return *get(); }
01096 ValueType* operator->() const { return get(); }
01097
01098 HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
01099
01100
01101 operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
01102 typename HashTableType::const_iterator i = m_impl;
01103 return i;
01104 }
01105
01106 typename HashTableType::iterator m_impl;
01107 };
01108
01109 template<typename T, typename U>
01110 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
01111 {
01112 return a.m_impl == b.m_impl;
01113 }
01114
01115 template<typename T, typename U>
01116 inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
01117 {
01118 return a.m_impl != b.m_impl;
01119 }
01120
01121 template<typename T, typename U>
01122 inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
01123 {
01124 return a.m_impl == b.m_impl;
01125 }
01126
01127 template<typename T, typename U>
01128 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
01129 {
01130 return a.m_impl != b.m_impl;
01131 }
01132
01133 }
01134
01135 #include "HashIterators.h"
01136
01137 #endif // WTF_HashTable_h