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