1 /* 2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. 3 * Copyright (C) 2008 David Levin <levin@chromium.org> 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Library General Public 7 * License as published by the Free Software Foundation; either 8 * version 2 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Library General Public License for more details. 14 * 15 * You should have received a copy of the GNU Library General Public License 16 * along with this library; see the file COPYING.LIB. If not, write to 17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 18 * Boston, MA 02110-1301, USA. 19 * 20 */ 21 22 #ifndef WTF_HashTable_h 23 #define WTF_HashTable_h 24 25 #include "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> addIterator(const HashTable<Key,Value,Extractor,HashFunctions,Traits,KeyTraits> *,HashTableConstIterator<Key,Value,Extractor,HashFunctions,Traits,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> removeIterator(HashTableConstIterator<Key,Value,Extractor,HashFunctions,Traits,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 skipEmptyBuckets()107 void skipEmptyBuckets() 108 { 109 while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position)) 110 ++m_position; 111 } 112 HashTableConstIterator(const HashTableType * table,PointerType position,PointerType endPosition)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 HashTableConstIterator(const HashTableType * table,PointerType position,PointerType endPosition,HashItemKnownGoodTag)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: HashTableConstIterator()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 ~HashTableConstIterator()135 ~HashTableConstIterator() 136 { 137 removeIterator(this); 138 } 139 HashTableConstIterator(const const_iterator & other)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 get()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: checkValidity()190 void checkValidity() const 191 { 192 #if CHECK_HASHTABLE_ITERATORS 193 ASSERT(m_table); 194 #endif 195 } 196 197 198 #if CHECK_HASHTABLE_ITERATORS checkValidity(const const_iterator & other)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 checkValidity(const const_iterator &)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 HashTableIterator(HashTableType * table,PointerType pos,PointerType end)234 HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { } HashTableIterator(HashTableType * table,PointerType pos,PointerType end,HashItemKnownGoodTag tag)235 HashTableIterator(HashTableType* table, PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(table, pos, end, tag) { } 236 237 public: HashTableIterator()238 HashTableIterator() { } 239 240 // default copy, assignment and destructor are OK 241 get()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 const_iterator()254 operator const_iterator() const { return m_iterator; } 255 256 private: 257 const_iterator m_iterator; 258 }; 259 260 using std::swap; 261 262 // Work around MSVC's standard library, whose swap for pairs does not swap by component. hashTableSwap(T & a,T & b)263 template<typename T> inline void hashTableSwap(T& a, T& b) 264 { 265 swap(a, b); 266 } 267 268 // Swap pairs by component, in case of pair members that specialize swap. hashTableSwap(pair<T,U> & a,pair<T,U> & b)269 template<typename T, typename U> inline void hashTableSwap(pair<T, U>& a, pair<T, U>& b) 270 { 271 swap(a.first, b.first); 272 swap(a.second, b.second); 273 } 274 275 template<typename T, bool useSwap> struct Mover; 276 template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { hashTableSwap(from, to); } }; 277 template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } }; 278 279 template<typename Key, typename Value, typename HashFunctions> class IdentityHashTranslator { 280 public: 281 static unsigned hash(const Key& key) { return HashFunctions::hash(key); } 282 static bool equal(const Key& a, const Key& b) { return HashFunctions::equal(a, b); } 283 static void translate(Value& location, const Key&, const Value& value) { location = value; } 284 }; 285 286 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 287 class HashTable { 288 public: 289 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator; 290 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 291 typedef Traits ValueTraits; 292 typedef Key KeyType; 293 typedef Value ValueType; 294 typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType; 295 296 HashTable(); 297 ~HashTable() 298 { 299 invalidateIterators(); 300 deallocateTable(m_table, m_tableSize); 301 #if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 302 m_table = (ValueType*)(uintptr_t)0xbbadbeef; 303 #endif 304 } 305 306 HashTable(const HashTable&); 307 void swap(HashTable&); 308 HashTable& operator=(const HashTable&); 309 310 iterator begin() { return makeIterator(m_table); } 311 iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); } 312 const_iterator begin() const { return makeConstIterator(m_table); } 313 const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); } 314 315 int size() const { return m_keyCount; } 316 int capacity() const { return m_tableSize; } 317 bool isEmpty() const { return !m_keyCount; } 318 319 pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); } 320 321 // A special version of add() that finds the object by hashing and comparing 322 // with some other type, to avoid the cost of type conversion if the object is already 323 // in the table. 324 template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&); 325 template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> addPassingHashCode(const T& key, const Extra&); 326 327 iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); } 328 const_iterator find(const KeyType& key) const { return find<KeyType, IdentityTranslatorType>(key); } 329 bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); } 330 331 template <typename T, typename HashTranslator> iterator find(const T&); 332 template <typename T, typename HashTranslator> const_iterator find(const T&) const; 333 template <typename T, typename HashTranslator> bool contains(const T&) const; 334 335 void remove(const KeyType&); 336 void remove(iterator); 337 void removeWithoutEntryConsistencyCheck(iterator); 338 void removeWithoutEntryConsistencyCheck(const_iterator); 339 void clear(); 340 341 static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); } 342 static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); } 343 static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); } 344 345 ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); } 346 template<typename T, typename HashTranslator> ValueType* lookup(const T&); 347 348 #if !ASSERT_DISABLED 349 void checkTableConsistency() const; 350 #else 351 static void checkTableConsistency() { } 352 #endif 353 #if CHECK_HASHTABLE_CONSISTENCY 354 void internalCheckTableConsistency() const { checkTableConsistency(); } 355 void internalCheckTableConsistencyExceptSize() const { checkTableConsistencyExceptSize(); } 356 #else 357 static void internalCheckTableConsistencyExceptSize() { } 358 static void internalCheckTableConsistency() { } 359 #endif 360 361 private: 362 static ValueType* allocateTable(int size); 363 static void deallocateTable(ValueType* table, int size); 364 365 typedef pair<ValueType*, bool> LookupType; 366 typedef pair<LookupType, unsigned> FullLookupType; 367 368 LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); }; 369 template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&); 370 template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&); 371 372 template<typename T, typename HashTranslator> void checkKey(const T&); 373 374 void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*); 375 void removeAndInvalidate(ValueType*); 376 void remove(ValueType*); 377 378 bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; } 379 bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; } 380 bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; } 381 void expand(); 382 void shrink() { rehash(m_tableSize / 2); } 383 384 void rehash(int newTableSize); 385 void reinsert(ValueType&); 386 387 static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); } 388 static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); } 389 390 FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash) 391 { return FullLookupType(LookupType(position, found), hash); } 392 393 iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); } 394 const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); } 395 iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); } 396 const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); } 397 398 #if !ASSERT_DISABLED 399 void checkTableConsistencyExceptSize() const; 400 #else 401 static void checkTableConsistencyExceptSize() { } 402 #endif 403 404 #if CHECK_HASHTABLE_ITERATORS 405 void invalidateIterators(); 406 #else 407 static void invalidateIterators() { } 408 #endif 409 410 static const int m_minTableSize = 64; 411 static const int m_maxLoad = 2; 412 static const int m_minLoad = 6; 413 414 ValueType* m_table; 415 int m_tableSize; 416 int m_tableSizeMask; 417 int m_keyCount; 418 int m_deletedCount; 419 420 #if CHECK_HASHTABLE_ITERATORS 421 public: 422 // All access to m_iterators should be guarded with m_mutex. 423 mutable const_iterator* m_iterators; 424 mutable Mutex m_mutex; 425 #endif 426 }; 427 428 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 429 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable() 430 : m_table(0) 431 , m_tableSize(0) 432 , m_tableSizeMask(0) 433 , m_keyCount(0) 434 , m_deletedCount(0) 435 #if CHECK_HASHTABLE_ITERATORS 436 , m_iterators(0) 437 #endif 438 { 439 } 440 441 static inline unsigned doubleHash(unsigned key) 442 { 443 key = ~key + (key >> 23); 444 key ^= (key << 12); 445 key ^= (key >> 7); 446 key ^= (key << 2); 447 key ^= (key >> 20); 448 return key; 449 } 450 451 #if ASSERT_DISABLED 452 453 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 454 template<typename T, typename HashTranslator> 455 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&) 456 { 457 } 458 459 #else 460 461 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 462 template<typename T, typename HashTranslator> 463 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key) 464 { 465 if (!HashFunctions::safeToCompareToEmptyOrDeleted) 466 return; 467 ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key)); 468 ValueType deletedValue = Traits::emptyValue(); 469 deletedValue.~ValueType(); 470 Traits::constructDeletedValue(deletedValue); 471 ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key)); 472 new (&deletedValue) ValueType(Traits::emptyValue()); 473 } 474 475 #endif 476 477 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 478 template<typename T, typename HashTranslator> 479 inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key) 480 { 481 checkKey<T, HashTranslator>(key); 482 483 int k = 0; 484 int sizeMask = m_tableSizeMask; 485 ValueType* table = m_table; 486 unsigned h = HashTranslator::hash(key); 487 int i = h & sizeMask; 488 489 if (!table) 490 return 0; 491 492 #if DUMP_HASHTABLE_STATS 493 atomicIncrement(&HashTableStats::numAccesses); 494 int probeCount = 0; 495 #endif 496 497 while (1) { 498 ValueType* entry = table + i; 499 500 // we count on the compiler to optimize out this branch 501 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 502 if (HashTranslator::equal(Extractor::extract(*entry), key)) 503 return entry; 504 505 if (isEmptyBucket(*entry)) 506 return 0; 507 } else { 508 if (isEmptyBucket(*entry)) 509 return 0; 510 511 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key)) 512 return entry; 513 } 514 #if DUMP_HASHTABLE_STATS 515 ++probeCount; 516 HashTableStats::recordCollisionAtCount(probeCount); 517 #endif 518 if (k == 0) 519 k = 1 | doubleHash(h); 520 i = (i + k) & sizeMask; 521 } 522 } 523 524 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 525 template<typename T, typename HashTranslator> 526 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key) 527 { 528 ASSERT(m_table); 529 checkKey<T, HashTranslator>(key); 530 531 int k = 0; 532 ValueType* table = m_table; 533 int sizeMask = m_tableSizeMask; 534 unsigned h = HashTranslator::hash(key); 535 int i = h & sizeMask; 536 537 #if DUMP_HASHTABLE_STATS 538 atomicIncrement(&HashTableStats::numAccesses); 539 int probeCount = 0; 540 #endif 541 542 ValueType* deletedEntry = 0; 543 544 while (1) { 545 ValueType* entry = table + i; 546 547 // we count on the compiler to optimize out this branch 548 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 549 if (isEmptyBucket(*entry)) 550 return LookupType(deletedEntry ? deletedEntry : entry, false); 551 552 if (HashTranslator::equal(Extractor::extract(*entry), key)) 553 return LookupType(entry, true); 554 555 if (isDeletedBucket(*entry)) 556 deletedEntry = entry; 557 } else { 558 if (isEmptyBucket(*entry)) 559 return LookupType(deletedEntry ? deletedEntry : entry, false); 560 561 if (isDeletedBucket(*entry)) 562 deletedEntry = entry; 563 else if (HashTranslator::equal(Extractor::extract(*entry), key)) 564 return LookupType(entry, true); 565 } 566 #if DUMP_HASHTABLE_STATS 567 ++probeCount; 568 HashTableStats::recordCollisionAtCount(probeCount); 569 #endif 570 if (k == 0) 571 k = 1 | doubleHash(h); 572 i = (i + k) & sizeMask; 573 } 574 } 575 576 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 577 template<typename T, typename HashTranslator> 578 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key) 579 { 580 ASSERT(m_table); 581 checkKey<T, HashTranslator>(key); 582 583 int k = 0; 584 ValueType* table = m_table; 585 int sizeMask = m_tableSizeMask; 586 unsigned h = HashTranslator::hash(key); 587 int i = h & sizeMask; 588 589 #if DUMP_HASHTABLE_STATS 590 atomicIncrement(&HashTableStats::numAccesses); 591 int probeCount = 0; 592 #endif 593 594 ValueType* deletedEntry = 0; 595 596 while (1) { 597 ValueType* entry = table + i; 598 599 // we count on the compiler to optimize out this branch 600 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 601 if (isEmptyBucket(*entry)) 602 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h); 603 604 if (HashTranslator::equal(Extractor::extract(*entry), key)) 605 return makeLookupResult(entry, true, h); 606 607 if (isDeletedBucket(*entry)) 608 deletedEntry = entry; 609 } else { 610 if (isEmptyBucket(*entry)) 611 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h); 612 613 if (isDeletedBucket(*entry)) 614 deletedEntry = entry; 615 else if (HashTranslator::equal(Extractor::extract(*entry), key)) 616 return makeLookupResult(entry, true, h); 617 } 618 #if DUMP_HASHTABLE_STATS 619 ++probeCount; 620 HashTableStats::recordCollisionAtCount(probeCount); 621 #endif 622 if (k == 0) 623 k = 1 | doubleHash(h); 624 i = (i + k) & sizeMask; 625 } 626 } 627 628 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 629 template<typename T, typename Extra, typename HashTranslator> 630 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) 631 { 632 checkKey<T, HashTranslator>(key); 633 634 invalidateIterators(); 635 636 if (!m_table) 637 expand(); 638 639 internalCheckTableConsistency(); 640 641 ASSERT(m_table); 642 643 int k = 0; 644 ValueType* table = m_table; 645 int sizeMask = m_tableSizeMask; 646 unsigned h = HashTranslator::hash(key); 647 int i = h & sizeMask; 648 649 #if DUMP_HASHTABLE_STATS 650 atomicIncrement(&HashTableStats::numAccesses); 651 int probeCount = 0; 652 #endif 653 654 ValueType* deletedEntry = 0; 655 ValueType* entry; 656 while (1) { 657 entry = table + i; 658 659 // we count on the compiler to optimize out this branch 660 if (HashFunctions::safeToCompareToEmptyOrDeleted) { 661 if (isEmptyBucket(*entry)) 662 break; 663 664 if (HashTranslator::equal(Extractor::extract(*entry), key)) 665 return std::make_pair(makeKnownGoodIterator(entry), false); 666 667 if (isDeletedBucket(*entry)) 668 deletedEntry = entry; 669 } else { 670 if (isEmptyBucket(*entry)) 671 break; 672 673 if (isDeletedBucket(*entry)) 674 deletedEntry = entry; 675 else if (HashTranslator::equal(Extractor::extract(*entry), key)) 676 return std::make_pair(makeKnownGoodIterator(entry), false); 677 } 678 #if DUMP_HASHTABLE_STATS 679 ++probeCount; 680 HashTableStats::recordCollisionAtCount(probeCount); 681 #endif 682 if (k == 0) 683 k = 1 | doubleHash(h); 684 i = (i + k) & sizeMask; 685 } 686 687 if (deletedEntry) { 688 initializeBucket(*deletedEntry); 689 entry = deletedEntry; 690 --m_deletedCount; 691 } 692 693 HashTranslator::translate(*entry, key, extra); 694 695 ++m_keyCount; 696 697 if (shouldExpand()) { 698 // FIXME: This makes an extra copy on expand. Probably not that bad since 699 // expand is rare, but would be better to have a version of expand that can 700 // follow a pivot entry and return the new position. 701 KeyType enteredKey = Extractor::extract(*entry); 702 expand(); 703 pair<iterator, bool> p = std::make_pair(find(enteredKey), true); 704 ASSERT(p.first != end()); 705 return p; 706 } 707 708 internalCheckTableConsistency(); 709 710 return std::make_pair(makeKnownGoodIterator(entry), true); 711 } 712 713 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 714 template<typename T, typename Extra, typename HashTranslator> 715 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) 716 { 717 checkKey<T, HashTranslator>(key); 718 719 invalidateIterators(); 720 721 if (!m_table) 722 expand(); 723 724 internalCheckTableConsistency(); 725 726 FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key); 727 728 ValueType* entry = lookupResult.first.first; 729 bool found = lookupResult.first.second; 730 unsigned h = lookupResult.second; 731 732 if (found) 733 return std::make_pair(makeKnownGoodIterator(entry), false); 734 735 if (isDeletedBucket(*entry)) { 736 initializeBucket(*entry); 737 --m_deletedCount; 738 } 739 740 HashTranslator::translate(*entry, key, extra, h); 741 ++m_keyCount; 742 if (shouldExpand()) { 743 // FIXME: This makes an extra copy on expand. Probably not that bad since 744 // expand is rare, but would be better to have a version of expand that can 745 // follow a pivot entry and return the new position. 746 KeyType enteredKey = Extractor::extract(*entry); 747 expand(); 748 pair<iterator, bool> p = std::make_pair(find(enteredKey), true); 749 ASSERT(p.first != end()); 750 return p; 751 } 752 753 internalCheckTableConsistency(); 754 755 return std::make_pair(makeKnownGoodIterator(entry), true); 756 } 757 758 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 759 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry) 760 { 761 ASSERT(m_table); 762 ASSERT(!lookupForWriting(Extractor::extract(entry)).second); 763 ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first))); 764 #if DUMP_HASHTABLE_STATS 765 atomicIncrement(&HashTableStats::numReinserts); 766 #endif 767 768 Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first); 769 } 770 771 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 772 template <typename T, typename HashTranslator> 773 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) 774 { 775 if (!m_table) 776 return end(); 777 778 ValueType* entry = lookup<T, HashTranslator>(key); 779 if (!entry) 780 return end(); 781 782 return makeKnownGoodIterator(entry); 783 } 784 785 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 786 template <typename T, typename HashTranslator> 787 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const 788 { 789 if (!m_table) 790 return end(); 791 792 ValueType* entry = const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key); 793 if (!entry) 794 return end(); 795 796 return makeKnownGoodConstIterator(entry); 797 } 798 799 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 800 template <typename T, typename HashTranslator> 801 bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const 802 { 803 if (!m_table) 804 return false; 805 806 return const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key); 807 } 808 809 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 810 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos) 811 { 812 invalidateIterators(); 813 remove(pos); 814 } 815 816 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 817 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos) 818 { 819 invalidateIterators(); 820 internalCheckTableConsistency(); 821 remove(pos); 822 } 823 824 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 825 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos) 826 { 827 #if DUMP_HASHTABLE_STATS 828 atomicIncrement(&HashTableStats::numRemoves); 829 #endif 830 831 deleteBucket(*pos); 832 ++m_deletedCount; 833 --m_keyCount; 834 835 if (shouldShrink()) 836 shrink(); 837 838 internalCheckTableConsistency(); 839 } 840 841 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 842 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it) 843 { 844 if (it == end()) 845 return; 846 847 removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position)); 848 } 849 850 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 851 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it) 852 { 853 if (it == end()) 854 return; 855 856 removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position)); 857 } 858 859 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 860 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(const_iterator it) 861 { 862 if (it == end()) 863 return; 864 865 removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_position)); 866 } 867 868 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 869 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key) 870 { 871 remove(find(key)); 872 } 873 874 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 875 Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size) 876 { 877 // would use a template member function with explicit specializations here, but 878 // gcc doesn't appear to support that 879 if (Traits::emptyValueIsZero) 880 return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType))); 881 ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType))); 882 for (int i = 0; i < size; i++) 883 initializeBucket(result[i]); 884 return result; 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>::deallocateTable(ValueType* table, int size) 889 { 890 if (Traits::needsDestruction) { 891 for (int i = 0; i < size; ++i) { 892 if (!isDeletedBucket(table[i])) 893 table[i].~ValueType(); 894 } 895 } 896 fastFree(table); 897 } 898 899 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 900 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand() 901 { 902 int newSize; 903 if (m_tableSize == 0) 904 newSize = m_minTableSize; 905 else if (mustRehashInPlace()) 906 newSize = m_tableSize; 907 else 908 newSize = m_tableSize * 2; 909 910 rehash(newSize); 911 } 912 913 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 914 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize) 915 { 916 internalCheckTableConsistencyExceptSize(); 917 918 int oldTableSize = m_tableSize; 919 ValueType* oldTable = m_table; 920 921 #if DUMP_HASHTABLE_STATS 922 if (oldTableSize != 0) 923 atomicIncrement(&HashTableStats::numRehashes); 924 #endif 925 926 m_tableSize = newTableSize; 927 m_tableSizeMask = newTableSize - 1; 928 m_table = allocateTable(newTableSize); 929 930 for (int i = 0; i != oldTableSize; ++i) 931 if (!isEmptyOrDeletedBucket(oldTable[i])) 932 reinsert(oldTable[i]); 933 934 m_deletedCount = 0; 935 936 deallocateTable(oldTable, oldTableSize); 937 938 internalCheckTableConsistency(); 939 } 940 941 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 942 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear() 943 { 944 invalidateIterators(); 945 deallocateTable(m_table, m_tableSize); 946 m_table = 0; 947 m_tableSize = 0; 948 m_tableSizeMask = 0; 949 m_keyCount = 0; 950 } 951 952 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 953 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other) 954 : m_table(0) 955 , m_tableSize(0) 956 , m_tableSizeMask(0) 957 , m_keyCount(0) 958 , m_deletedCount(0) 959 #if CHECK_HASHTABLE_ITERATORS 960 , m_iterators(0) 961 #endif 962 { 963 // Copy the hash table the dumb way, by adding each element to the new table. 964 // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed. 965 const_iterator end = other.end(); 966 for (const_iterator it = other.begin(); it != end; ++it) 967 add(*it); 968 } 969 970 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 971 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other) 972 { 973 invalidateIterators(); 974 other.invalidateIterators(); 975 976 ValueType* tmp_table = m_table; 977 m_table = other.m_table; 978 other.m_table = tmp_table; 979 980 int tmp_tableSize = m_tableSize; 981 m_tableSize = other.m_tableSize; 982 other.m_tableSize = tmp_tableSize; 983 984 int tmp_tableSizeMask = m_tableSizeMask; 985 m_tableSizeMask = other.m_tableSizeMask; 986 other.m_tableSizeMask = tmp_tableSizeMask; 987 988 int tmp_keyCount = m_keyCount; 989 m_keyCount = other.m_keyCount; 990 other.m_keyCount = tmp_keyCount; 991 992 int tmp_deletedCount = m_deletedCount; 993 m_deletedCount = other.m_deletedCount; 994 other.m_deletedCount = tmp_deletedCount; 995 } 996 997 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 998 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other) 999 { 1000 HashTable tmp(other); 1001 swap(tmp); 1002 return *this; 1003 } 1004 1005 #if !ASSERT_DISABLED 1006 1007 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1008 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const 1009 { 1010 checkTableConsistencyExceptSize(); 1011 ASSERT(!m_table || !shouldExpand()); 1012 ASSERT(!shouldShrink()); 1013 } 1014 1015 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1016 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const 1017 { 1018 if (!m_table) 1019 return; 1020 1021 int count = 0; 1022 int deletedCount = 0; 1023 for (int j = 0; j < m_tableSize; ++j) { 1024 ValueType* entry = m_table + j; 1025 if (isEmptyBucket(*entry)) 1026 continue; 1027 1028 if (isDeletedBucket(*entry)) { 1029 ++deletedCount; 1030 continue; 1031 } 1032 1033 const_iterator it = find(Extractor::extract(*entry)); 1034 ASSERT(entry == it.m_position); 1035 ++count; 1036 1037 ValueCheck<Key>::checkConsistency(it->first); 1038 } 1039 1040 ASSERT(count == m_keyCount); 1041 ASSERT(deletedCount == m_deletedCount); 1042 ASSERT(m_tableSize >= m_minTableSize); 1043 ASSERT(m_tableSizeMask); 1044 ASSERT(m_tableSize == m_tableSizeMask + 1); 1045 } 1046 1047 #endif // ASSERT_DISABLED 1048 1049 #if CHECK_HASHTABLE_ITERATORS 1050 1051 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1052 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators() 1053 { 1054 MutexLocker lock(m_mutex); 1055 const_iterator* next; 1056 for (const_iterator* p = m_iterators; p; p = next) { 1057 next = p->m_next; 1058 p->m_table = 0; 1059 p->m_next = 0; 1060 p->m_previous = 0; 1061 } 1062 m_iterators = 0; 1063 } 1064 1065 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1066 void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table, 1067 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it) 1068 { 1069 it->m_table = table; 1070 it->m_previous = 0; 1071 1072 // Insert iterator at head of doubly-linked list of iterators. 1073 if (!table) { 1074 it->m_next = 0; 1075 } else { 1076 MutexLocker lock(table->m_mutex); 1077 ASSERT(table->m_iterators != it); 1078 it->m_next = table->m_iterators; 1079 table->m_iterators = it; 1080 if (it->m_next) { 1081 ASSERT(!it->m_next->m_previous); 1082 it->m_next->m_previous = it; 1083 } 1084 } 1085 } 1086 1087 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits> 1088 void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it) 1089 { 1090 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType; 1091 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator; 1092 1093 // Delete iterator from doubly-linked list of iterators. 1094 if (!it->m_table) { 1095 ASSERT(!it->m_next); 1096 ASSERT(!it->m_previous); 1097 } else { 1098 MutexLocker lock(it->m_table->m_mutex); 1099 if (it->m_next) { 1100 ASSERT(it->m_next->m_previous == it); 1101 it->m_next->m_previous = it->m_previous; 1102 } 1103 if (it->m_previous) { 1104 ASSERT(it->m_table->m_iterators != it); 1105 ASSERT(it->m_previous->m_next == it); 1106 it->m_previous->m_next = it->m_next; 1107 } else { 1108 ASSERT(it->m_table->m_iterators == it); 1109 it->m_table->m_iterators = it->m_next; 1110 } 1111 } 1112 1113 it->m_table = 0; 1114 it->m_next = 0; 1115 it->m_previous = 0; 1116 } 1117 1118 #endif // CHECK_HASHTABLE_ITERATORS 1119 1120 // iterator adapters 1121 1122 template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter { 1123 HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {} 1124 1125 const ValueType* get() const { return (const ValueType*)m_impl.get(); } 1126 const ValueType& operator*() const { return *get(); } 1127 const ValueType* operator->() const { return get(); } 1128 1129 HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; } 1130 // postfix ++ intentionally omitted 1131 1132 typename HashTableType::const_iterator m_impl; 1133 }; 1134 1135 template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter { 1136 HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {} 1137 1138 ValueType* get() const { return (ValueType*)m_impl.get(); } 1139 ValueType& operator*() const { return *get(); } 1140 ValueType* operator->() const { return get(); } 1141 1142 HashTableIteratorAdapter& operator++() { ++m_impl; return *this; } 1143 // postfix ++ intentionally omitted 1144 1145 operator HashTableConstIteratorAdapter<HashTableType, ValueType>() { 1146 typename HashTableType::const_iterator i = m_impl; 1147 return i; 1148 } 1149 1150 typename HashTableType::iterator m_impl; 1151 }; 1152 1153 template<typename T, typename U> 1154 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<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 HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b) 1161 { 1162 return a.m_impl != b.m_impl; 1163 } 1164 1165 template<typename T, typename U> 1166 inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 1167 { 1168 return a.m_impl == b.m_impl; 1169 } 1170 1171 template<typename T, typename U> 1172 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b) 1173 { 1174 return a.m_impl != b.m_impl; 1175 } 1176 1177 } // namespace WTF 1178 1179 #include "HashIterators.h" 1180 1181 #endif // WTF_HashTable_h 1182