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