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