1/* 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved. 3 * Copyright (C) 2008 David Levin <levin@chromium.org> 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Library General Public 7 * License as published by the Free Software Foundation; either 8 * version 2 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Library General Public License for more details. 14 * 15 * You should have received a copy of the GNU Library General Public License 16 * along with this library; see the file COPYING.LIB. If not, write to 17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 18 * Boston, MA 02110-1301, USA. 19 * 20 */ 21 22#ifndef WTF_HashTable_h 23#define WTF_HashTable_h 24 25#include <atomic> 26#include <mutex> 27#include <string.h> 28#include <type_traits> 29#include <utility> 30#include <wtf/Assertions.h> 31#include <wtf/FastMalloc.h> 32#include <wtf/HashTraits.h> 33#include <wtf/StdLibExtras.h> 34#include <wtf/ValueCheck.h> 35 36#define DUMP_HASHTABLE_STATS 0 37#define DUMP_HASHTABLE_STATS_PER_TABLE 0 38 39#if DUMP_HASHTABLE_STATS_PER_TABLE 40#include <wtf/DataLog.h> 41#endif 42 43namespace WTF { 44 45// Enables internal WTF consistency checks that are invoked automatically. Non-WTF callers can call checkTableConsistency() even if internal checks are disabled. 46#define CHECK_HASHTABLE_CONSISTENCY 0 47 48#ifdef NDEBUG 49#define CHECK_HASHTABLE_ITERATORS 0 50#define CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 0 51#else 52#define CHECK_HASHTABLE_ITERATORS 1 53#define CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 1 54#endif 55 56#if DUMP_HASHTABLE_STATS 57 58 struct HashTableStats { 59 // The following variables are all atomically incremented when modified. 60 WTF_EXPORTDATA static std::atomic<unsigned> numAccesses; 61 WTF_EXPORTDATA static std::atomic<unsigned> numRehashes; 62 WTF_EXPORTDATA static std::atomic<unsigned> numRemoves; 63 WTF_EXPORTDATA static std::atomic<unsigned> numReinserts; 64 65 // The following variables are only modified in the recordCollisionAtCount method within a mutex. 66 WTF_EXPORTDATA static unsigned maxCollisions; 67 WTF_EXPORTDATA static unsigned numCollisions; 68 WTF_EXPORTDATA static unsigned collisionGraph[4096]; 69 70 WTF_EXPORT_PRIVATE static void recordCollisionAtCount(unsigned count); 71 WTF_EXPORT_PRIVATE static void dumpStats(); 72 }; 73 74#endif 75 76 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 77 class HashTable; 78 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 79 class HashTableIterator; 80 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 81 class HashTableConstIterator; 82 83 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 84 void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*, 85 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*); 86 87 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 88 void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*); 89 90#if !CHECK_HASHTABLE_ITERATORS 91 92 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 93 inline void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*, 94 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { } 95 96 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 97 inline void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { } 98 99#endif 100 101 typedef enum { HashItemKnownGood } HashItemKnownGoodTag; 102 103 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 104 class HashTableConstIterator { 105 private: 106 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType; 107 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator; 108 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 109 typedef Value ValueType; 110 typedef const ValueType& ReferenceType; 111 typedef const ValueType* PointerType; 112 113 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>; 114 friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>; 115 116 void skipEmptyBuckets() 117 { 118 while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position)) 119 ++m_position; 120 } 121 122 HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition) 123 : m_position(position), m_endPosition(endPosition) 124 { 125 addIterator(table, this); 126 skipEmptyBuckets(); 127 } 128 129 HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition, HashItemKnownGoodTag) 130 : m_position(position), m_endPosition(endPosition) 131 { 132 addIterator(table, this); 133 } 134 135 public: 136 HashTableConstIterator() 137 { 138 addIterator(static_cast<const HashTableType*>(0), this); 139 } 140 141 // default copy, assignment and destructor are OK if CHECK_HASHTABLE_ITERATORS is 0 142 143#if CHECK_HASHTABLE_ITERATORS 144 ~HashTableConstIterator() 145 { 146 removeIterator(this); 147 } 148 149 HashTableConstIterator(const const_iterator& other) 150 : m_position(other.m_position), m_endPosition(other.m_endPosition) 151 { 152 addIterator(other.m_table, this); 153 } 154 155 const_iterator& operator=(const const_iterator& other) 156 { 157 m_position = other.m_position; 158 m_endPosition = other.m_endPosition; 159 160 removeIterator(this); 161 addIterator(other.m_table, this); 162 163 return *this; 164 } 165#endif 166 167 PointerType get() const 168 { 169 checkValidity(); 170 return m_position; 171 } 172 ReferenceType operator*() const { return *get(); } 173 PointerType operator->() const { return get(); } 174 175 const_iterator& operator++() 176 { 177 checkValidity(); 178 ASSERT(m_position != m_endPosition); 179 ++m_position; 180 skipEmptyBuckets(); 181 return *this; 182 } 183 184 // postfix ++ intentionally omitted 185 186 // Comparison. 187 bool operator==(const const_iterator& other) const 188 { 189 checkValidity(other); 190 return m_position == other.m_position; 191 } 192 bool operator!=(const const_iterator& other) const 193 { 194 checkValidity(other); 195 return m_position != other.m_position; 196 } 197 bool operator==(const iterator& other) const 198 { 199 return *this == static_cast<const_iterator>(other); 200 } 201 bool operator!=(const iterator& other) const 202 { 203 return *this != static_cast<const_iterator>(other); 204 } 205 206 private: 207 void checkValidity() const 208 { 209#if CHECK_HASHTABLE_ITERATORS 210 ASSERT(m_table); 211#endif 212 } 213 214 215#if CHECK_HASHTABLE_ITERATORS 216 void checkValidity(const const_iterator& other) const 217 { 218 ASSERT(m_table); 219 ASSERT_UNUSED(other, other.m_table); 220 ASSERT(m_table == other.m_table); 221 } 222#else 223 void checkValidity(const const_iterator&) const { } 224#endif 225 226 PointerType m_position; 227 PointerType m_endPosition; 228 229#if CHECK_HASHTABLE_ITERATORS 230 public: 231 // Any modifications of the m_next or m_previous of an iterator that is in a linked list of a HashTable::m_iterator, 232 // should be guarded with m_table->m_mutex. 233 mutable const HashTableType* m_table; 234 mutable const_iterator* m_next; 235 mutable const_iterator* m_previous; 236#endif 237 }; 238 239 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 240 class HashTableIterator { 241 private: 242 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType; 243 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator; 244 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 245 typedef Value ValueType; 246 typedef ValueType& ReferenceType; 247 typedef ValueType* PointerType; 248 249 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>; 250 251 HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { } 252 HashTableIterator(HashTableType* table, PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(table, pos, end, tag) { } 253 254 public: 255 HashTableIterator() { } 256 257 // default copy, assignment and destructor are OK 258 259 PointerType get() const { return const_cast<PointerType>(m_iterator.get()); } 260 ReferenceType operator*() const { return *get(); } 261 PointerType operator->() const { return get(); } 262 263 iterator& operator++() { ++m_iterator; return *this; } 264 265 // postfix ++ intentionally omitted 266 267 // Comparison. 268 bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; } 269 bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; } 270 bool operator==(const const_iterator& other) const { return m_iterator == other; } 271 bool operator!=(const const_iterator& other) const { return m_iterator != other; } 272 273 operator const_iterator() const { return m_iterator; } 274 275 private: 276 const_iterator m_iterator; 277 }; 278 279 template<typename HashFunctions> class IdentityHashTranslator { 280 public: 281 template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); } 282 template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); } 283 template<typename T, typename U, typename V> static void translate(T& location, const U&, V&& value) { location = std::forward<V>(value); } 284 }; 285 286 template<typename IteratorType> struct HashTableAddResult { 287 HashTableAddResult(IteratorType iter, bool isNewEntry) : iterator(iter), isNewEntry(isNewEntry) { } 288 IteratorType iterator; 289 bool isNewEntry; 290 }; 291 292 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 293 class HashTable { 294 public: 295 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator; 296 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 297 typedef Traits ValueTraits; 298 typedef Key KeyType; 299 typedef Value ValueType; 300 typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType; 301 typedef HashTableAddResult<iterator> AddResult; 302 303#if DUMP_HASHTABLE_STATS_PER_TABLE 304 struct Stats { 305 Stats() 306 : numAccesses(0) 307 , numRehashes(0) 308 , numRemoves(0) 309 , numReinserts(0) 310 , maxCollisions(0) 311 , numCollisions(0) 312 , collisionGraph() 313 { 314 } 315 316 int numAccesses; 317 int numRehashes; 318 int numRemoves; 319 int numReinserts; 320 321 int maxCollisions; 322 int numCollisions; 323 int collisionGraph[4096]; 324 325 void recordCollisionAtCount(int count) 326 { 327 if (count > maxCollisions) 328 maxCollisions = count; 329 numCollisions++; 330 collisionGraph[count]++; 331 } 332 333 void dumpStats() 334 { 335 dataLogF("\nWTF::HashTable::Stats dump\n\n"); 336 dataLogF("%d accesses\n", numAccesses); 337 dataLogF("%d total collisions, average %.2f probes per access\n", numCollisions, 1.0 * (numAccesses + numCollisions) / numAccesses); 338 dataLogF("longest collision chain: %d\n", maxCollisions); 339 for (int i = 1; i <= maxCollisions; i++) { 340 dataLogF(" %d lookups with exactly %d collisions (%.2f%% , %.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses); 341 } 342 dataLogF("%d rehashes\n", numRehashes); 343 dataLogF("%d reinserts\n", numReinserts); 344 } 345 }; 346#endif 347 348 HashTable(); 349 ~HashTable() 350 { 351 invalidateIterators(); 352 if (m_table) 353 deallocateTable(m_table, m_tableSize); 354#if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 355 m_table = (ValueType*)(uintptr_t)0xbbadbeef; 356#endif 357 } 358 359 HashTable(const HashTable&); 360 void swap(HashTable&); 361 HashTable& operator=(const HashTable&); 362 363 // When the hash table is empty, just return the same iterator for end as for begin. 364 // This is more efficient because we don't have to skip all the empty and deleted 365 // buckets, and iterating an empty table is a common case that's worth optimizing. 366 iterator begin() { return isEmpty() ? end() : makeIterator(m_table); } 367 iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); } 368 const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); } 369 const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); } 370 371 int size() const { return m_keyCount; } 372 int capacity() const { return m_tableSize; } 373 bool isEmpty() const { return !m_keyCount; } 374 375 AddResult add(const ValueType& value) { return add<IdentityTranslatorType>(Extractor::extract(value), value); } 376 AddResult add(ValueType&& value) { return add<IdentityTranslatorType>(Extractor::extract(value), WTF::move(value)); } 377 378 // A special version of add() that finds the object by hashing and comparing 379 // with some other type, to avoid the cost of type conversion if the object is already 380 // in the table. 381 template<typename HashTranslator, typename T, typename Extra> AddResult add(T&& key, Extra&&); 382 template<typename HashTranslator, typename T, typename Extra> AddResult addPassingHashCode(T&& key, Extra&&); 383 384 iterator find(const KeyType& key) { return find<IdentityTranslatorType>(key); } 385 const_iterator find(const KeyType& key) const { return find<IdentityTranslatorType>(key); } 386 bool contains(const KeyType& key) const { return contains<IdentityTranslatorType>(key); } 387 388 template<typename HashTranslator, typename T> iterator find(const T&); 389 template<typename HashTranslator, typename T> const_iterator find(const T&) const; 390 template<typename HashTranslator, typename T> bool contains(const T&) const; 391 392 void remove(const KeyType&); 393 void remove(iterator); 394 void removeWithoutEntryConsistencyCheck(iterator); 395 void removeWithoutEntryConsistencyCheck(const_iterator); 396 template<typename Functor> 397 void removeIf(const Functor&); 398 void clear(); 399 400 static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); } 401 static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); } 402 static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); } 403 404 ValueType* lookup(const Key& key) { return lookup<IdentityTranslatorType>(key); } 405 template<typename HashTranslator, typename T> ValueType* lookup(const T&); 406 407#if !ASSERT_DISABLED 408 void checkTableConsistency() const; 409#else 410 static void checkTableConsistency() { } 411#endif 412#if CHECK_HASHTABLE_CONSISTENCY 413 void internalCheckTableConsistency() const { checkTableConsistency(); } 414 void internalCheckTableConsistencyExceptSize() const { checkTableConsistencyExceptSize(); } 415#else 416 static void internalCheckTableConsistencyExceptSize() { } 417 static void internalCheckTableConsistency() { } 418#endif 419 420 private: 421 static ValueType* allocateTable(int size); 422 static void deallocateTable(ValueType* table, int size); 423 424 typedef std::pair<ValueType*, bool> LookupType; 425 typedef std::pair<LookupType, unsigned> FullLookupType; 426 427 LookupType lookupForWriting(const Key& key) { return lookupForWriting<IdentityTranslatorType>(key); }; 428 template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&); 429 template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&); 430 431 template<typename HashTranslator, typename T> void checkKey(const T&); 432 433 void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*); 434 void removeAndInvalidate(ValueType*); 435 void remove(ValueType*); 436 437 bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; } 438 bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; } 439 bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; } 440 ValueType* expand(ValueType* entry = nullptr); 441 void shrink() { rehash(m_tableSize / 2, nullptr); } 442 443 ValueType* rehash(int newTableSize, ValueType* entry); 444 ValueType* reinsert(ValueType&&); 445 446 static void initializeBucket(ValueType& bucket); 447 static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); } 448 449 FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash) 450 { return FullLookupType(LookupType(position, found), hash); } 451 452 iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); } 453 const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); } 454 iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); } 455 const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); } 456 457#if !ASSERT_DISABLED 458 void checkTableConsistencyExceptSize() const; 459#else 460 static void checkTableConsistencyExceptSize() { } 461#endif 462 463#if CHECK_HASHTABLE_ITERATORS 464 void invalidateIterators(); 465#else 466 static void invalidateIterators() { } 467#endif 468 469 static const int m_maxLoad = 2; 470 static const int m_minLoad = 6; 471 472 ValueType* m_table; 473 int m_tableSize; 474 int m_tableSizeMask; 475 int m_keyCount; 476 int m_deletedCount; 477 478#if CHECK_HASHTABLE_ITERATORS 479 public: 480 // All access to m_iterators should be guarded with m_mutex. 481 mutable const_iterator* m_iterators; 482 // Use OwnPtr so HashTable can still be memmove'd or memcpy'ed. 483 mutable std::unique_ptr<std::mutex> m_mutex; 484#endif 485 486#if DUMP_HASHTABLE_STATS_PER_TABLE 487 public: 488 mutable std::unique_ptr<Stats> m_stats; 489#endif 490 }; 491 492 // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111. 493 template<unsigned size> struct OneifyLowBits; 494 template<> 495 struct OneifyLowBits<0> { 496 static const unsigned value = 0; 497 }; 498 template<unsigned number> 499 struct OneifyLowBits { 500 static const unsigned value = number | OneifyLowBits<(number >> 1)>::value; 501 }; 502 // Compute the first power of two integer that is an upper bound of the parameter 'number'. 503 template<unsigned number> 504 struct UpperPowerOfTwoBound { 505 static const unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2; 506 }; 507 508 // Because power of two numbers are the limit of maxLoad, their capacity is twice the 509 // UpperPowerOfTwoBound, or 4 times their values. 510 template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter; 511 template<unsigned size> 512 struct HashTableCapacityForSizeSplitter<size, true> { 513 static const unsigned value = size * 4; 514 }; 515 template<unsigned size> 516 struct HashTableCapacityForSizeSplitter<size, false> { 517 static const unsigned value = UpperPowerOfTwoBound<size>::value; 518 }; 519 520 // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter. 521 // This is done at compile time to initialize the HashTraits. 522 template<unsigned size> 523 struct HashTableCapacityForSize { 524 static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value; 525 COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity); 526 COMPILE_ASSERT(!static_cast<int>(value >> 31), HashTableNoCapacityOverflow); 527 COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize); 528 }; 529 530 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 531 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable() 532 : m_table(0) 533 , m_tableSize(0) 534 , m_tableSizeMask(0) 535 , m_keyCount(0) 536 , m_deletedCount(0) 537#if CHECK_HASHTABLE_ITERATORS 538 , m_iterators(0) 539 , m_mutex(std::make_unique<std::mutex>()) 540#endif 541#if DUMP_HASHTABLE_STATS_PER_TABLE 542 , m_stats(std::make_unique<Stats>()) 543#endif 544 { 545 } 546 547 inline unsigned doubleHash(unsigned key) 548 { 549 key = ~key + (key >> 23); 550 key ^= (key << 12); 551 key ^= (key >> 7); 552 key ^= (key << 2); 553 key ^= (key >> 20); 554 return key; 555 } 556 557#if ASSERT_DISABLED 558 559 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 560 template<typename HashTranslator, typename T> 561 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&) 562 { 563 } 564 565#else 566 567 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 568 template<typename HashTranslator, typename T> 569 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key) 570 { 571 if (!HashFunctions::safeToCompareToEmptyOrDeleted) 572 return; 573 ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key)); 574 typename std::aligned_storage<sizeof(ValueType), std::alignment_of<ValueType>::value>::type deletedValueBuffer; 575 ValueType* deletedValuePtr = reinterpret_cast_ptr<ValueType*>(&deletedValueBuffer); 576 ValueType& deletedValue = *deletedValuePtr; 577 Traits::constructDeletedValue(deletedValue); 578 ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key)); 579 } 580 581#endif 582 583 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 584 template<typename HashTranslator, typename T> 585 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key) -> ValueType* 586 { 587 checkKey<HashTranslator>(key); 588 589 int k = 0; 590 int sizeMask = m_tableSizeMask; 591 ValueType* table = m_table; 592 unsigned h = HashTranslator::hash(key); 593 int i = h & sizeMask; 594 595 if (!table) 596 return 0; 597 598#if DUMP_HASHTABLE_STATS 599 ++HashTableStats::numAccesses; 600 unsigned probeCount = 0; 601#endif 602 603#if DUMP_HASHTABLE_STATS_PER_TABLE 604 ++m_stats->numAccesses; 605#endif 606 607 while (1) { 608 ValueType* entry = table + i; 609 610 // we count on the compiler to optimize out this branch 611 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 612 if (HashTranslator::equal(Extractor::extract(*entry), key)) 613 return entry; 614 615 if (isEmptyBucket(*entry)) 616 return 0; 617 } else { 618 if (isEmptyBucket(*entry)) 619 return 0; 620 621 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key)) 622 return entry; 623 } 624#if DUMP_HASHTABLE_STATS 625 ++probeCount; 626 HashTableStats::recordCollisionAtCount(probeCount); 627#endif 628 629#if DUMP_HASHTABLE_STATS_PER_TABLE 630 m_stats->recordCollisionAtCount(probeCount); 631#endif 632 633 if (k == 0) 634 k = 1 | doubleHash(h); 635 i = (i + k) & sizeMask; 636 } 637 } 638 639 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 640 template<typename HashTranslator, typename T> 641 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key) -> LookupType 642 { 643 ASSERT(m_table); 644 checkKey<HashTranslator>(key); 645 646 int k = 0; 647 ValueType* table = m_table; 648 int sizeMask = m_tableSizeMask; 649 unsigned h = HashTranslator::hash(key); 650 int i = h & sizeMask; 651 652#if DUMP_HASHTABLE_STATS 653 ++HashTableStats::numAccesses; 654 int probeCount = 0; 655#endif 656 657#if DUMP_HASHTABLE_STATS_PER_TABLE 658 ++m_stats->numAccesses; 659#endif 660 661 ValueType* deletedEntry = 0; 662 663 while (1) { 664 ValueType* entry = table + i; 665 666 // we count on the compiler to optimize out this branch 667 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 668 if (isEmptyBucket(*entry)) 669 return LookupType(deletedEntry ? deletedEntry : entry, false); 670 671 if (HashTranslator::equal(Extractor::extract(*entry), key)) 672 return LookupType(entry, true); 673 674 if (isDeletedBucket(*entry)) 675 deletedEntry = entry; 676 } else { 677 if (isEmptyBucket(*entry)) 678 return LookupType(deletedEntry ? deletedEntry : entry, false); 679 680 if (isDeletedBucket(*entry)) 681 deletedEntry = entry; 682 else if (HashTranslator::equal(Extractor::extract(*entry), key)) 683 return LookupType(entry, true); 684 } 685#if DUMP_HASHTABLE_STATS 686 ++probeCount; 687 HashTableStats::recordCollisionAtCount(probeCount); 688#endif 689 690#if DUMP_HASHTABLE_STATS_PER_TABLE 691 m_stats->recordCollisionAtCount(probeCount); 692#endif 693 694 if (k == 0) 695 k = 1 | doubleHash(h); 696 i = (i + k) & sizeMask; 697 } 698 } 699 700 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 701 template<typename HashTranslator, typename T> 702 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key) -> FullLookupType 703 { 704 ASSERT(m_table); 705 checkKey<HashTranslator>(key); 706 707 int k = 0; 708 ValueType* table = m_table; 709 int sizeMask = m_tableSizeMask; 710 unsigned h = HashTranslator::hash(key); 711 int i = h & sizeMask; 712 713#if DUMP_HASHTABLE_STATS 714 ++HashTableStats::numAccesses; 715 unsigned probeCount = 0; 716#endif 717 718#if DUMP_HASHTABLE_STATS_PER_TABLE 719 ++m_stats->numAccesses; 720#endif 721 722 ValueType* deletedEntry = 0; 723 724 while (1) { 725 ValueType* entry = table + i; 726 727 // we count on the compiler to optimize out this branch 728 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 729 if (isEmptyBucket(*entry)) 730 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h); 731 732 if (HashTranslator::equal(Extractor::extract(*entry), key)) 733 return makeLookupResult(entry, true, h); 734 735 if (isDeletedBucket(*entry)) 736 deletedEntry = entry; 737 } else { 738 if (isEmptyBucket(*entry)) 739 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h); 740 741 if (isDeletedBucket(*entry)) 742 deletedEntry = entry; 743 else if (HashTranslator::equal(Extractor::extract(*entry), key)) 744 return makeLookupResult(entry, true, h); 745 } 746#if DUMP_HASHTABLE_STATS 747 ++probeCount; 748 HashTableStats::recordCollisionAtCount(probeCount); 749#endif 750 751#if DUMP_HASHTABLE_STATS_PER_TABLE 752 m_stats->recordCollisionAtCount(probeCount); 753#endif 754 755 if (k == 0) 756 k = 1 | doubleHash(h); 757 i = (i + k) & sizeMask; 758 } 759 } 760 761 template<bool emptyValueIsZero> struct HashTableBucketInitializer; 762 763 template<> struct HashTableBucketInitializer<false> { 764 template<typename Traits, typename Value> static void initialize(Value& bucket) 765 { 766 new (NotNull, &bucket) Value(Traits::emptyValue()); 767 } 768 }; 769 770 template<> struct HashTableBucketInitializer<true> { 771 template<typename Traits, typename Value> static void initialize(Value& bucket) 772 { 773 // This initializes the bucket without copying the empty value. 774 // That makes it possible to use this with types that don't support copying. 775 // The memset to 0 looks like a slow operation but is optimized by the compilers. 776 memset(&bucket, 0, sizeof(bucket)); 777 } 778 }; 779 780 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 781 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::initializeBucket(ValueType& bucket) 782 { 783 HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket); 784 } 785 786 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 787 template<typename HashTranslator, typename T, typename Extra> 788 ALWAYS_INLINE auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(T&& key, Extra&& extra) -> AddResult 789 { 790 checkKey<HashTranslator>(key); 791 792 invalidateIterators(); 793 794 if (!m_table) 795 expand(nullptr); 796 797 internalCheckTableConsistency(); 798 799 ASSERT(m_table); 800 801 int k = 0; 802 ValueType* table = m_table; 803 int sizeMask = m_tableSizeMask; 804 unsigned h = HashTranslator::hash(key); 805 int i = h & sizeMask; 806 807#if DUMP_HASHTABLE_STATS 808 ++HashTableStats::numAccesses; 809 unsigned probeCount = 0; 810#endif 811 812#if DUMP_HASHTABLE_STATS_PER_TABLE 813 ++m_stats->numAccesses; 814#endif 815 816 ValueType* deletedEntry = 0; 817 ValueType* entry; 818 while (1) { 819 entry = table + i; 820 821 // we count on the compiler to optimize out this branch 822 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 823 if (isEmptyBucket(*entry)) 824 break; 825 826 if (HashTranslator::equal(Extractor::extract(*entry), key)) 827 return AddResult(makeKnownGoodIterator(entry), false); 828 829 if (isDeletedBucket(*entry)) 830 deletedEntry = entry; 831 } else { 832 if (isEmptyBucket(*entry)) 833 break; 834 835 if (isDeletedBucket(*entry)) 836 deletedEntry = entry; 837 else if (HashTranslator::equal(Extractor::extract(*entry), key)) 838 return AddResult(makeKnownGoodIterator(entry), false); 839 } 840#if DUMP_HASHTABLE_STATS 841 ++probeCount; 842 HashTableStats::recordCollisionAtCount(probeCount); 843#endif 844 845#if DUMP_HASHTABLE_STATS_PER_TABLE 846 m_stats->recordCollisionAtCount(probeCount); 847#endif 848 849 if (k == 0) 850 k = 1 | doubleHash(h); 851 i = (i + k) & sizeMask; 852 } 853 854 if (deletedEntry) { 855 initializeBucket(*deletedEntry); 856 entry = deletedEntry; 857 --m_deletedCount; 858 } 859 860 HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra)); 861 ++m_keyCount; 862 863 if (shouldExpand()) 864 entry = expand(entry); 865 866 internalCheckTableConsistency(); 867 868 return AddResult(makeKnownGoodIterator(entry), true); 869 } 870 871 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 872 template<typename HashTranslator, typename T, typename Extra> 873 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addPassingHashCode(T&& key, Extra&& extra) -> AddResult 874 { 875 checkKey<HashTranslator>(key); 876 877 invalidateIterators(); 878 879 if (!m_table) 880 expand(); 881 882 internalCheckTableConsistency(); 883 884 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key); 885 886 ValueType* entry = lookupResult.first.first; 887 bool found = lookupResult.first.second; 888 unsigned h = lookupResult.second; 889 890 if (found) 891 return AddResult(makeKnownGoodIterator(entry), false); 892 893 if (isDeletedBucket(*entry)) { 894 initializeBucket(*entry); 895 --m_deletedCount; 896 } 897 898 HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra), h); 899 ++m_keyCount; 900 901 if (shouldExpand()) 902 entry = expand(entry); 903 904 internalCheckTableConsistency(); 905 906 return AddResult(makeKnownGoodIterator(entry), true); 907 } 908 909 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 910 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType&& entry) -> ValueType* 911 { 912 ASSERT(m_table); 913 ASSERT(!lookupForWriting(Extractor::extract(entry)).second); 914 ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first))); 915#if DUMP_HASHTABLE_STATS 916 ++HashTableStats::numReinserts; 917#endif 918#if DUMP_HASHTABLE_STATS_PER_TABLE 919 ++m_stats->numReinserts; 920#endif 921 922 Value* newEntry = lookupForWriting(Extractor::extract(entry)).first; 923 newEntry->~Value(); 924 new (NotNull, newEntry) ValueType(WTF::move(entry)); 925 926 return newEntry; 927 } 928 929 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 930 template <typename HashTranslator, typename T> 931 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) -> iterator 932 { 933 if (!m_table) 934 return end(); 935 936 ValueType* entry = lookup<HashTranslator>(key); 937 if (!entry) 938 return end(); 939 940 return makeKnownGoodIterator(entry); 941 } 942 943 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 944 template <typename HashTranslator, typename T> 945 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const -> const_iterator 946 { 947 if (!m_table) 948 return end(); 949 950 ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(key); 951 if (!entry) 952 return end(); 953 954 return makeKnownGoodConstIterator(entry); 955 } 956 957 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 958 template <typename HashTranslator, typename T> 959 bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const 960 { 961 if (!m_table) 962 return false; 963 964 return const_cast<HashTable*>(this)->lookup<HashTranslator>(key); 965 } 966 967 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 968 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos) 969 { 970 invalidateIterators(); 971 remove(pos); 972 } 973 974 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 975 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos) 976 { 977 invalidateIterators(); 978 internalCheckTableConsistency(); 979 remove(pos); 980 } 981 982 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 983 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos) 984 { 985#if DUMP_HASHTABLE_STATS 986 ++HashTableStats::numRemoves; 987#endif 988#if DUMP_HASHTABLE_STATS_PER_TABLE 989 ++m_stats->numRemoves; 990#endif 991 992 deleteBucket(*pos); 993 ++m_deletedCount; 994 --m_keyCount; 995 996 if (shouldShrink()) 997 shrink(); 998 999 internalCheckTableConsistency(); 1000 } 1001 1002 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1003 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it) 1004 { 1005 if (it == end()) 1006 return; 1007 1008 removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position)); 1009 } 1010 1011 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1012 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it) 1013 { 1014 if (it == end()) 1015 return; 1016 1017 removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position)); 1018 } 1019 1020 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1021 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(const_iterator it) 1022 { 1023 if (it == end()) 1024 return; 1025 1026 removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_position)); 1027 } 1028 1029 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1030 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key) 1031 { 1032 remove(find(key)); 1033 } 1034 1035 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1036 template<typename Functor> 1037 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeIf(const Functor& functor) 1038 { 1039 for (unsigned i = m_tableSize; i--;) { 1040 if (isEmptyOrDeletedBucket(m_table[i])) 1041 continue; 1042 1043 if (!functor(m_table[i])) 1044 continue; 1045 1046 deleteBucket(m_table[i]); 1047 ++m_deletedCount; 1048 --m_keyCount; 1049 } 1050 1051 if (shouldShrink()) 1052 shrink(); 1053 1054 internalCheckTableConsistency(); 1055 } 1056 1057 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1058 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size) -> ValueType* 1059 { 1060 // would use a template member function with explicit specializations here, but 1061 // gcc doesn't appear to support that 1062 if (Traits::emptyValueIsZero) 1063 return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType))); 1064 ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType))); 1065 for (int i = 0; i < size; i++) 1066 initializeBucket(result[i]); 1067 return result; 1068 } 1069 1070 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1071 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, int size) 1072 { 1073 for (int i = 0; i < size; ++i) { 1074 if (!isDeletedBucket(table[i])) 1075 table[i].~ValueType(); 1076 } 1077 fastFree(table); 1078 } 1079 1080 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1081 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand(ValueType* entry) -> ValueType* 1082 { 1083 int newSize; 1084 if (m_tableSize == 0) 1085 newSize = KeyTraits::minimumTableSize; 1086 else if (mustRehashInPlace()) 1087 newSize = m_tableSize; 1088 else 1089 newSize = m_tableSize * 2; 1090 1091 return rehash(newSize, entry); 1092 } 1093 1094 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1095 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize, ValueType* entry) -> ValueType* 1096 { 1097 internalCheckTableConsistencyExceptSize(); 1098 1099 int oldTableSize = m_tableSize; 1100 ValueType* oldTable = m_table; 1101 1102#if DUMP_HASHTABLE_STATS 1103 if (oldTableSize != 0) 1104 ++HashTableStats::numRehashes; 1105#endif 1106 1107#if DUMP_HASHTABLE_STATS_PER_TABLE 1108 if (oldTableSize != 0) 1109 ++m_stats->numRehashes; 1110#endif 1111 1112 m_tableSize = newTableSize; 1113 m_tableSizeMask = newTableSize - 1; 1114 m_table = allocateTable(newTableSize); 1115 1116 Value* newEntry = nullptr; 1117 for (int i = 0; i != oldTableSize; ++i) { 1118 if (isEmptyOrDeletedBucket(oldTable[i])) { 1119 ASSERT(&oldTable[i] != entry); 1120 continue; 1121 } 1122 1123 Value* reinsertedEntry = reinsert(WTF::move(oldTable[i])); 1124 if (&oldTable[i] == entry) { 1125 ASSERT(!newEntry); 1126 newEntry = reinsertedEntry; 1127 } 1128 } 1129 1130 m_deletedCount = 0; 1131 1132 deallocateTable(oldTable, oldTableSize); 1133 1134 internalCheckTableConsistency(); 1135 return newEntry; 1136 } 1137 1138 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1139 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear() 1140 { 1141 invalidateIterators(); 1142 if (!m_table) 1143 return; 1144 1145 deallocateTable(m_table, m_tableSize); 1146 m_table = 0; 1147 m_tableSize = 0; 1148 m_tableSizeMask = 0; 1149 m_keyCount = 0; 1150 } 1151 1152 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1153 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other) 1154 : m_table(0) 1155 , m_tableSize(0) 1156 , m_tableSizeMask(0) 1157 , m_keyCount(0) 1158 , m_deletedCount(0) 1159#if CHECK_HASHTABLE_ITERATORS 1160 , m_iterators(0) 1161 , m_mutex(std::make_unique<std::mutex>()) 1162#endif 1163#if DUMP_HASHTABLE_STATS_PER_TABLE 1164 , m_stats(std::make_unique<Stats>(*other.m_stats)) 1165#endif 1166 { 1167 // Copy the hash table the dumb way, by adding each element to the new table. 1168 // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed. 1169 // FIXME: It's likely that this can be improved, for static analyses that use 1170 // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455 1171 const_iterator end = other.end(); 1172 for (const_iterator it = other.begin(); it != end; ++it) 1173 add(*it); 1174 } 1175 1176 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1177 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other) 1178 { 1179 invalidateIterators(); 1180 other.invalidateIterators(); 1181 1182 std::swap(m_table, other.m_table); 1183 std::swap(m_tableSize, other.m_tableSize); 1184 std::swap(m_tableSizeMask, other.m_tableSizeMask); 1185 std::swap(m_keyCount, other.m_keyCount); 1186 std::swap(m_deletedCount, other.m_deletedCount); 1187 1188#if DUMP_HASHTABLE_STATS_PER_TABLE 1189 m_stats.swap(other.m_stats); 1190#endif 1191 } 1192 1193 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1194 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other) -> HashTable& 1195 { 1196 // FIXME: It's likely that this can be improved, for static analyses that use 1197 // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455 1198 HashTable tmp(other); 1199 swap(tmp); 1200 return *this; 1201 } 1202 1203#if !ASSERT_DISABLED 1204 1205 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1206 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const 1207 { 1208 checkTableConsistencyExceptSize(); 1209 ASSERT(!m_table || !shouldExpand()); 1210 ASSERT(!shouldShrink()); 1211 } 1212 1213 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1214 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const 1215 { 1216 if (!m_table) 1217 return; 1218 1219 int count = 0; 1220 int deletedCount = 0; 1221 for (int j = 0; j < m_tableSize; ++j) { 1222 ValueType* entry = m_table + j; 1223 if (isEmptyBucket(*entry)) 1224 continue; 1225 1226 if (isDeletedBucket(*entry)) { 1227 ++deletedCount; 1228 continue; 1229 } 1230 1231 const_iterator it = find(Extractor::extract(*entry)); 1232 ASSERT(entry == it.m_position); 1233 ++count; 1234 1235 ValueCheck<Key>::checkConsistency(it->key); 1236 } 1237 1238 ASSERT(count == m_keyCount); 1239 ASSERT(deletedCount == m_deletedCount); 1240 ASSERT(m_tableSize >= KeyTraits::minimumTableSize); 1241 ASSERT(m_tableSizeMask); 1242 ASSERT(m_tableSize == m_tableSizeMask + 1); 1243 } 1244 1245#endif // ASSERT_DISABLED 1246 1247#if CHECK_HASHTABLE_ITERATORS 1248 1249 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1250 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators() 1251 { 1252 std::lock_guard<std::mutex> lock(*m_mutex); 1253 const_iterator* next; 1254 for (const_iterator* p = m_iterators; p; p = next) { 1255 next = p->m_next; 1256 p->m_table = 0; 1257 p->m_next = 0; 1258 p->m_previous = 0; 1259 } 1260 m_iterators = 0; 1261 } 1262 1263 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1264 void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table, 1265 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it) 1266 { 1267 it->m_table = table; 1268 it->m_previous = 0; 1269 1270 // Insert iterator at head of doubly-linked list of iterators. 1271 if (!table) { 1272 it->m_next = 0; 1273 } else { 1274 std::lock_guard<std::mutex> lock(*table->m_mutex); 1275 ASSERT(table->m_iterators != it); 1276 it->m_next = table->m_iterators; 1277 table->m_iterators = it; 1278 if (it->m_next) { 1279 ASSERT(!it->m_next->m_previous); 1280 it->m_next->m_previous = it; 1281 } 1282 } 1283 } 1284 1285 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1286 void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it) 1287 { 1288 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType; 1289 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 1290 1291 // Delete iterator from doubly-linked list of iterators. 1292 if (!it->m_table) { 1293 ASSERT(!it->m_next); 1294 ASSERT(!it->m_previous); 1295 } else { 1296 std::lock_guard<std::mutex> lock(*it->m_table->m_mutex); 1297 if (it->m_next) { 1298 ASSERT(it->m_next->m_previous == it); 1299 it->m_next->m_previous = it->m_previous; 1300 } 1301 if (it->m_previous) { 1302 ASSERT(it->m_table->m_iterators != it); 1303 ASSERT(it->m_previous->m_next == it); 1304 it->m_previous->m_next = it->m_next; 1305 } else { 1306 ASSERT(it->m_table->m_iterators == it); 1307 it->m_table->m_iterators = it->m_next; 1308 } 1309 } 1310 1311 it->m_table = 0; 1312 it->m_next = 0; 1313 it->m_previous = 0; 1314 } 1315 1316#endif // CHECK_HASHTABLE_ITERATORS 1317 1318 // iterator adapters 1319 1320 template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter { 1321 HashTableConstIteratorAdapter() {} 1322 HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {} 1323 1324 const ValueType* get() const { return (const ValueType*)m_impl.get(); } 1325 const ValueType& operator*() const { return *get(); } 1326 const ValueType* operator->() const { return get(); } 1327 1328 HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; } 1329 // postfix ++ intentionally omitted 1330 1331 typename HashTableType::const_iterator m_impl; 1332 }; 1333 1334 template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter { 1335 HashTableIteratorAdapter() {} 1336 HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {} 1337 1338 ValueType* get() const { return (ValueType*)m_impl.get(); } 1339 ValueType& operator*() const { return *get(); } 1340 ValueType* operator->() const { return get(); } 1341 1342 HashTableIteratorAdapter& operator++() { ++m_impl; return *this; } 1343 // postfix ++ intentionally omitted 1344 1345 operator HashTableConstIteratorAdapter<HashTableType, ValueType>() { 1346 typename HashTableType::const_iterator i = m_impl; 1347 return i; 1348 } 1349 1350 typename HashTableType::iterator m_impl; 1351 }; 1352 1353 template<typename T, typename U> 1354 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) 1355 { 1356 return a.m_impl == b.m_impl; 1357 } 1358 1359 template<typename T, typename U> 1360 inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) 1361 { 1362 return a.m_impl != b.m_impl; 1363 } 1364 1365 template<typename T, typename U> 1366 inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 1367 { 1368 return a.m_impl == b.m_impl; 1369 } 1370 1371 template<typename T, typename U> 1372 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 1373 { 1374 return a.m_impl != b.m_impl; 1375 } 1376 1377 // All 4 combinations of ==, != and Const,non const. 1378 template<typename T, typename U> 1379 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 1380 { 1381 return a.m_impl == b.m_impl; 1382 } 1383 1384 template<typename T, typename U> 1385 inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 1386 { 1387 return a.m_impl != b.m_impl; 1388 } 1389 1390 template<typename T, typename U> 1391 inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) 1392 { 1393 return a.m_impl == b.m_impl; 1394 } 1395 1396 template<typename T, typename U> 1397 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) 1398 { 1399 return a.m_impl != b.m_impl; 1400 } 1401 1402} // namespace WTF 1403 1404#include <wtf/HashIterators.h> 1405 1406#endif // WTF_HashTable_h 1407