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