2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
3 * Copyright (C) 2008 David Levin <levin@chromium.org>
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.
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Library General Public License for more details.
13 * You should have received a copy of the GNU Library General Public License
14 * along with this library; see the file COPYING.LIB. If not, write to
15 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
16 * Boston, MA 02110-1301, USA.
20 #ifndef WTF_HashTable_h
21 #define WTF_HashTable_h
23 #include "wtf/Alignment.h"
24 #include "wtf/Assertions.h"
25 #include "wtf/DefaultAllocator.h"
26 #include "wtf/HashTraits.h"
29 #define DUMP_HASHTABLE_STATS 0
30 #define DUMP_HASHTABLE_STATS_PER_TABLE 0
32 #if DUMP_HASHTABLE_STATS_PER_TABLE
33 #include "wtf/DataLog.h"
36 #if DUMP_HASHTABLE_STATS
37 #if DUMP_HASHTABLE_STATS_PER_TABLE
38 #define UPDATE_PROBE_COUNTS() \
40 HashTableStats::recordCollisionAtCount(probeCount); \
41 ++perTableProbeCount; \
42 m_stats->recordCollisionAtCount(perTableProbeCount)
43 #define UPDATE_ACCESS_COUNTS() \
44 atomicIncrement(&HashTableStats::numAccesses); \
46 ++m_stats->numAccesses; \
47 int perTableProbeCount = 0
49 #define UPDATE_PROBE_COUNTS() \
51 HashTableStats::recordCollisionAtCount(probeCount)
52 #define UPDATE_ACCESS_COUNTS() \
53 atomicIncrement(&HashTableStats::numAccesses); \
57 #if DUMP_HASHTABLE_STATS_PER_TABLE
58 #define UPDATE_PROBE_COUNTS() \
59 ++perTableProbeCount; \
60 m_stats->recordCollisionAtCount(perTableProbeCount)
61 #define UPDATE_ACCESS_COUNTS() \
62 ++m_stats->numAccesses; \
63 int perTableProbeCount = 0
65 #define UPDATE_PROBE_COUNTS() do { } while (0)
66 #define UPDATE_ACCESS_COUNTS() do { } while (0)
72 #if DUMP_HASHTABLE_STATS
74 struct HashTableStats {
75 // The following variables are all atomically incremented when modified.
76 static int numAccesses;
77 static int numRehashes;
78 static int numRemoves;
79 static int numReinserts;
81 // The following variables are only modified in the recordCollisionAtCount method within a mutex.
82 static int maxCollisions;
83 static int numCollisions;
84 static int collisionGraph[4096];
86 static void recordCollisionAtCount(int count);
87 static void dumpStats();
92 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
94 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
95 class HashTableIterator;
96 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
97 class HashTableConstIterator;
98 template<typename Value, typename HashFunctions, typename HashTraits, typename Allocator>
100 template<WeakHandlingFlag x, typename T, typename U, typename V, typename W, typename X, typename Y, typename Z>
101 struct WeakProcessingHashTableHelper;
103 typedef enum { HashItemKnownGood } HashItemKnownGoodTag;
105 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
106 class HashTableConstIterator {
108 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> HashTableType;
109 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
110 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> const_iterator;
111 typedef Value ValueType;
112 typedef typename Traits::IteratorConstGetType GetType;
113 typedef const ValueType* PointerType;
115 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
116 friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
118 void skipEmptyBuckets()
120 while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position))
124 HashTableConstIterator(PointerType position, PointerType endPosition, const HashTableType* container)
125 : m_position(position)
126 , m_endPosition(endPosition)
127 #ifdef ASSERT_ENABLED
128 , m_container(container)
129 , m_containerModifications(container->modifications())
135 HashTableConstIterator(PointerType position, PointerType endPosition, const HashTableType* container, HashItemKnownGoodTag)
136 : m_position(position)
137 , m_endPosition(endPosition)
138 #ifdef ASSERT_ENABLED
139 , m_container(container)
140 , m_containerModifications(container->modifications())
143 ASSERT(m_containerModifications == m_container->modifications());
146 void checkModifications() const
148 // HashTable and collections that build on it do not support
149 // modifications while there is an iterator in use. The exception
150 // is ListHashSet, which has its own iterators that tolerate
151 // modification of the underlying set.
152 ASSERT(m_containerModifications == m_container->modifications());
156 HashTableConstIterator()
162 checkModifications();
165 typename Traits::IteratorConstReferenceType operator*() const { return Traits::getToReferenceConstConversion(get()); }
166 GetType operator->() const { return get(); }
168 const_iterator& operator++()
170 ASSERT(m_position != m_endPosition);
171 checkModifications();
177 // postfix ++ intentionally omitted
180 bool operator==(const const_iterator& other) const
182 return m_position == other.m_position;
184 bool operator!=(const const_iterator& other) const
186 return m_position != other.m_position;
188 bool operator==(const iterator& other) const
190 return *this == static_cast<const_iterator>(other);
192 bool operator!=(const iterator& other) const
194 return *this != static_cast<const_iterator>(other);
198 PointerType m_position;
199 PointerType m_endPosition;
200 #ifdef ASSERT_ENABLED
201 const HashTableType* m_container;
202 int64_t m_containerModifications;
206 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
207 class HashTableIterator {
209 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> HashTableType;
210 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
211 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> const_iterator;
212 typedef Value ValueType;
213 typedef typename Traits::IteratorGetType GetType;
214 typedef ValueType* PointerType;
216 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
218 HashTableIterator(PointerType pos, PointerType end, const HashTableType* container) : m_iterator(pos, end, container) { }
219 HashTableIterator(PointerType pos, PointerType end, const HashTableType* container, HashItemKnownGoodTag tag) : m_iterator(pos, end, container, tag) { }
222 HashTableIterator() { }
224 // default copy, assignment and destructor are OK
226 GetType get() const { return const_cast<GetType>(m_iterator.get()); }
227 typename Traits::IteratorReferenceType operator*() const { return Traits::getToReferenceConversion(get()); }
228 GetType operator->() const { return get(); }
230 iterator& operator++() { ++m_iterator; return *this; }
232 // postfix ++ intentionally omitted
235 bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
236 bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
237 bool operator==(const const_iterator& other) const { return m_iterator == other; }
238 bool operator!=(const const_iterator& other) const { return m_iterator != other; }
240 operator const_iterator() const { return m_iterator; }
243 const_iterator m_iterator;
248 // Work around MSVC's standard library, whose swap for pairs does not swap by component.
249 template<typename T> inline void hashTableSwap(T& a, T& b)
254 template<typename T, typename U> inline void hashTableSwap(KeyValuePair<T, U>& a, KeyValuePair<T, U>& b)
257 swap(a.value, b.value);
260 template<typename T, bool useSwap> struct Mover;
261 template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { hashTableSwap(from, to); } };
262 template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } };
264 template<typename HashFunctions> class IdentityHashTranslator {
266 template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
267 template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
268 template<typename T, typename U, typename V> static void translate(T& location, const U&, const V& value) { location = value; }
271 template<typename HashTableType, typename ValueType> struct HashTableAddResult {
272 HashTableAddResult(const HashTableType* container, ValueType* storedValue, bool isNewEntry)
273 : storedValue(storedValue)
274 , isNewEntry(isNewEntry)
275 #if SECURITY_ASSERT_ENABLED
276 , m_container(container)
277 , m_containerModifications(container->modifications())
280 ASSERT_UNUSED(container, container);
283 ~HashTableAddResult()
285 // If rehash happened before accessing storedValue, it's
286 // use-after-free. Any modification may cause a rehash, so we check
287 // for modifications here.
288 // Rehash after accessing storedValue is harmless but will assert if
289 // the AddResult destructor takes place after a modification. You
290 // may need to limit the scope of the AddResult.
291 ASSERT_WITH_SECURITY_IMPLICATION(m_containerModifications == m_container->modifications());
294 ValueType* storedValue;
297 #if SECURITY_ASSERT_ENABLED
299 const HashTableType* m_container;
300 const int64_t m_containerModifications;
304 template<typename Value, typename Extractor, typename KeyTraits>
305 struct HashTableHelper {
306 static bool isEmptyBucket(const Value& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
307 static bool isDeletedBucket(const Value& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
308 static bool isEmptyOrDeletedBucket(const Value& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
311 template<typename HashTranslator, typename KeyTraits, bool safeToCompareToEmptyOrDeleted>
312 struct HashTableKeyChecker {
313 // There's no simple generic way to make this check if safeToCompareToEmptyOrDeleted is false,
314 // so the check always passes.
315 template <typename T>
316 static bool checkKey(const T&) { return true; }
319 template<typename HashTranslator, typename KeyTraits>
320 struct HashTableKeyChecker<HashTranslator, KeyTraits, true> {
321 template <typename T>
322 static bool checkKey(const T& key)
324 // FIXME : Check also equality to the deleted value.
325 return !HashTranslator::equal(KeyTraits::emptyValue(), key);
329 // Don't declare a destructor for HeapAllocated hash tables.
330 template<typename Derived, bool isGarbageCollected>
331 class HashTableDestructorBase;
333 template<typename Derived>
334 class HashTableDestructorBase<Derived, true> { };
336 template<typename Derived>
337 class HashTableDestructorBase<Derived, false> {
339 ~HashTableDestructorBase() { static_cast<Derived*>(this)->finalize(); }
342 // Note: empty or deleted key values are not allowed, using them may lead to undefined behavior.
343 // For pointer keys this means that null pointers are not allowed unless you supply custom key traits.
344 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
345 class HashTable : public HashTableDestructorBase<HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>, Allocator::isGarbageCollected> {
347 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
348 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> const_iterator;
349 typedef Traits ValueTraits;
351 typedef typename KeyTraits::PeekInType KeyPeekInType;
352 typedef typename KeyTraits::PassInType KeyPassInType;
353 typedef Value ValueType;
354 typedef Extractor ExtractorType;
355 typedef KeyTraits KeyTraitsType;
356 typedef typename Traits::PassInType ValuePassInType;
357 typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType;
358 typedef HashTableAddResult<HashTable, ValueType> AddResult;
360 #if DUMP_HASHTABLE_STATS_PER_TABLE
380 int collisionGraph[4096];
382 void recordCollisionAtCount(int count)
384 if (count > maxCollisions)
385 maxCollisions = count;
387 collisionGraph[count]++;
392 dataLogF("\nWTF::HashTable::Stats dump\n\n");
393 dataLogF("%d accesses\n", numAccesses);
394 dataLogF("%d total collisions, average %.2f probes per access\n", numCollisions, 1.0 * (numAccesses + numCollisions) / numAccesses);
395 dataLogF("longest collision chain: %d\n", maxCollisions);
396 for (int i = 1; i <= maxCollisions; i++) {
397 dataLogF(" %d lookups with exactly %d collisions (%.2f%% , %.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses);
399 dataLogF("%d rehashes\n", numRehashes);
400 dataLogF("%d reinserts\n", numReinserts);
408 ASSERT(!Allocator::isGarbageCollected);
409 if (LIKELY(!m_table))
411 deleteAllBucketsAndDeallocate(m_table, m_tableSize);
415 HashTable(const HashTable&);
416 void swap(HashTable&);
417 HashTable& operator=(const HashTable&);
419 // When the hash table is empty, just return the same iterator for end as for begin.
420 // This is more efficient because we don't have to skip all the empty and deleted
421 // buckets, and iterating an empty table is a common case that's worth optimizing.
422 iterator begin() { return isEmpty() ? end() : makeIterator(m_table); }
423 iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
424 const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); }
425 const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
427 unsigned size() const { return m_keyCount; }
428 unsigned capacity() const { return m_tableSize; }
429 bool isEmpty() const { return !m_keyCount; }
431 AddResult add(ValuePassInType value)
433 return add<IdentityTranslatorType>(Extractor::extract(value), value);
436 // A special version of add() that finds the object by hashing and comparing
437 // with some other type, to avoid the cost of type conversion if the object is already
439 template<typename HashTranslator, typename T, typename Extra> AddResult add(const T& key, const Extra&);
440 template<typename HashTranslator, typename T, typename Extra> AddResult addPassingHashCode(const T& key, const Extra&);
442 iterator find(KeyPeekInType key) { return find<IdentityTranslatorType>(key); }
443 const_iterator find(KeyPeekInType key) const { return find<IdentityTranslatorType>(key); }
444 bool contains(KeyPeekInType key) const { return contains<IdentityTranslatorType>(key); }
446 template<typename HashTranslator, typename T> iterator find(const T&);
447 template<typename HashTranslator, typename T> const_iterator find(const T&) const;
448 template<typename HashTranslator, typename T> bool contains(const T&) const;
450 void remove(KeyPeekInType);
451 void remove(iterator);
452 void remove(const_iterator);
455 static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
456 static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
457 static bool isEmptyOrDeletedBucket(const ValueType& value) { return HashTableHelper<ValueType, Extractor, KeyTraits>:: isEmptyOrDeletedBucket(value); }
459 ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorType, KeyPeekInType>(key); }
460 template<typename HashTranslator, typename T> ValueType* lookup(T);
461 template<typename HashTranslator, typename T> const ValueType* lookup(T) const;
463 void trace(typename Allocator::Visitor*);
465 #ifdef ASSERT_ENABLED
466 int64_t modifications() const { return m_modifications; }
467 void registerModification() { m_modifications++; }
468 // HashTable and collections that build on it do not support
469 // modifications while there is an iterator in use. The exception is
470 // ListHashSet, which has its own iterators that tolerate modification
471 // of the underlying set.
472 void checkModifications(int64_t mods) const { ASSERT(mods == m_modifications); }
474 int64_t modifications() const { return 0; }
475 void registerModification() { }
476 void checkModifications(int64_t mods) const { }
480 static ValueType* allocateTable(unsigned size);
481 static void deleteAllBucketsAndDeallocate(ValueType* table, unsigned size);
483 typedef std::pair<ValueType*, bool> LookupType;
484 typedef std::pair<LookupType, unsigned> FullLookupType;
486 LookupType lookupForWriting(const Key& key) { return lookupForWriting<IdentityTranslatorType>(key); };
487 template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&);
488 template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&);
490 void remove(ValueType*);
492 bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
493 bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
494 bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; }
495 ValueType* expand(ValueType* entry = 0);
496 void shrink() { rehash(m_tableSize / 2, 0); }
498 ValueType* rehash(unsigned newTableSize, ValueType* entry);
499 ValueType* reinsert(ValueType&);
501 static void initializeBucket(ValueType& bucket);
502 static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); }
504 FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
505 { return FullLookupType(LookupType(position, found), hash); }
507 iterator makeIterator(ValueType* pos) { return iterator(pos, m_table + m_tableSize, this); }
508 const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(pos, m_table + m_tableSize, this); }
509 iterator makeKnownGoodIterator(ValueType* pos) { return iterator(pos, m_table + m_tableSize, this, HashItemKnownGood); }
510 const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(pos, m_table + m_tableSize, this, HashItemKnownGood); }
512 static const unsigned m_maxLoad = 2;
513 static const unsigned m_minLoad = 6;
515 unsigned tableSizeMask() const
517 size_t mask = m_tableSize - 1;
518 ASSERT((mask & m_tableSize) == 0);
523 unsigned m_tableSize;
525 unsigned m_deletedCount;
526 #ifdef ASSERT_ENABLED
527 unsigned m_modifications;
530 #if DUMP_HASHTABLE_STATS_PER_TABLE
532 mutable OwnPtr<Stats> m_stats;
535 template<WeakHandlingFlag x, typename T, typename U, typename V, typename W, typename X, typename Y, typename Z> friend struct WeakProcessingHashTableHelper;
536 template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
539 // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
540 template<unsigned size> struct OneifyLowBits;
542 struct OneifyLowBits<0> {
543 static const unsigned value = 0;
545 template<unsigned number>
546 struct OneifyLowBits {
547 static const unsigned value = number | OneifyLowBits<(number >> 1)>::value;
549 // Compute the first power of two integer that is an upper bound of the parameter 'number'.
550 template<unsigned number>
551 struct UpperPowerOfTwoBound {
552 static const unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2;
555 // Because power of two numbers are the limit of maxLoad, their capacity is twice the
556 // UpperPowerOfTwoBound, or 4 times their values.
557 template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter;
558 template<unsigned size>
559 struct HashTableCapacityForSizeSplitter<size, true> {
560 static const unsigned value = size * 4;
562 template<unsigned size>
563 struct HashTableCapacityForSizeSplitter<size, false> {
564 static const unsigned value = UpperPowerOfTwoBound<size>::value;
567 // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter.
568 // This is done at compile time to initialize the HashTraits.
569 template<unsigned size>
570 struct HashTableCapacityForSize {
571 static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
572 COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
573 COMPILE_ASSERT(!static_cast<int>(value >> 31), HashTableNoCapacityOverflow);
574 COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
577 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
578 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::HashTable()
583 #ifdef ASSERT_ENABLED
586 #if DUMP_HASHTABLE_STATS_PER_TABLE
587 , m_stats(adoptPtr(new Stats))
592 inline unsigned doubleHash(unsigned key)
594 key = ~key + (key >> 23);
602 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
603 template<typename HashTranslator, typename T>
604 inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key)
606 return const_cast<Value*>(const_cast<const HashTable*>(this)->lookup<HashTranslator, T>(key));
609 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
610 template<typename HashTranslator, typename T>
611 inline const Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key) const
613 ASSERT((HashTableKeyChecker<HashTranslator, KeyTraits, HashFunctions::safeToCompareToEmptyOrDeleted>::checkKey(key)));
614 const ValueType* table = m_table;
619 size_t sizeMask = tableSizeMask();
620 unsigned h = HashTranslator::hash(key);
621 size_t i = h & sizeMask;
623 UPDATE_ACCESS_COUNTS();
626 const ValueType* entry = table + i;
628 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
629 if (HashTranslator::equal(Extractor::extract(*entry), key))
632 if (isEmptyBucket(*entry))
635 if (isEmptyBucket(*entry))
638 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
641 UPDATE_PROBE_COUNTS();
643 k = 1 | doubleHash(h);
644 i = (i + k) & sizeMask;
648 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
649 template<typename HashTranslator, typename T>
650 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookupForWriting(const T& key)
653 registerModification();
655 ValueType* table = m_table;
657 size_t sizeMask = tableSizeMask();
658 unsigned h = HashTranslator::hash(key);
659 size_t i = h & sizeMask;
661 UPDATE_ACCESS_COUNTS();
663 ValueType* deletedEntry = 0;
666 ValueType* entry = table + i;
668 if (isEmptyBucket(*entry))
669 return LookupType(deletedEntry ? deletedEntry : entry, false);
671 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
672 if (HashTranslator::equal(Extractor::extract(*entry), key))
673 return LookupType(entry, true);
675 if (isDeletedBucket(*entry))
676 deletedEntry = entry;
678 if (isDeletedBucket(*entry))
679 deletedEntry = entry;
680 else if (HashTranslator::equal(Extractor::extract(*entry), key))
681 return LookupType(entry, true);
683 UPDATE_PROBE_COUNTS();
685 k = 1 | doubleHash(h);
686 i = (i + k) & sizeMask;
690 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
691 template<typename HashTranslator, typename T>
692 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::fullLookupForWriting(const T& key)
695 registerModification();
697 ValueType* table = m_table;
699 size_t sizeMask = tableSizeMask();
700 unsigned h = HashTranslator::hash(key);
701 size_t i = h & sizeMask;
703 UPDATE_ACCESS_COUNTS();
705 ValueType* deletedEntry = 0;
708 ValueType* entry = table + i;
710 if (isEmptyBucket(*entry))
711 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
713 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
714 if (HashTranslator::equal(Extractor::extract(*entry), key))
715 return makeLookupResult(entry, true, h);
717 if (isDeletedBucket(*entry))
718 deletedEntry = entry;
720 if (isDeletedBucket(*entry))
721 deletedEntry = entry;
722 else if (HashTranslator::equal(Extractor::extract(*entry), key))
723 return makeLookupResult(entry, true, h);
725 UPDATE_PROBE_COUNTS();
727 k = 1 | doubleHash(h);
728 i = (i + k) & sizeMask;
732 template<bool emptyValueIsZero> struct HashTableBucketInitializer;
734 template<> struct HashTableBucketInitializer<false> {
735 template<typename Traits, typename Value> static void initialize(Value& bucket)
737 new (NotNull, &bucket) Value(Traits::emptyValue());
741 template<> struct HashTableBucketInitializer<true> {
742 template<typename Traits, typename Value> static void initialize(Value& bucket)
744 // This initializes the bucket without copying the empty value.
745 // That makes it possible to use this with types that don't support copying.
746 // The memset to 0 looks like a slow operation but is optimized by the compilers.
747 memset(&bucket, 0, sizeof(bucket));
751 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
752 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::initializeBucket(ValueType& bucket)
754 HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket);
757 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
758 template<typename HashTranslator, typename T, typename Extra>
759 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::add(const T& key, const Extra& extra)
766 ValueType* table = m_table;
768 size_t sizeMask = tableSizeMask();
769 unsigned h = HashTranslator::hash(key);
770 size_t i = h & sizeMask;
772 UPDATE_ACCESS_COUNTS();
774 ValueType* deletedEntry = 0;
779 if (isEmptyBucket(*entry))
782 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
783 if (HashTranslator::equal(Extractor::extract(*entry), key))
784 return AddResult(this, entry, false);
786 if (isDeletedBucket(*entry))
787 deletedEntry = entry;
789 if (isDeletedBucket(*entry))
790 deletedEntry = entry;
791 else if (HashTranslator::equal(Extractor::extract(*entry), key))
792 return AddResult(this, entry, false);
794 UPDATE_PROBE_COUNTS();
796 k = 1 | doubleHash(h);
797 i = (i + k) & sizeMask;
800 registerModification();
803 initializeBucket(*deletedEntry);
804 entry = deletedEntry;
808 HashTranslator::translate(*entry, key, extra);
809 ASSERT(!isEmptyOrDeletedBucket(*entry));
814 entry = expand(entry);
816 return AddResult(this, entry, true);
819 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
820 template<typename HashTranslator, typename T, typename Extra>
821 typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::addPassingHashCode(const T& key, const Extra& extra)
826 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key);
828 ValueType* entry = lookupResult.first.first;
829 bool found = lookupResult.first.second;
830 unsigned h = lookupResult.second;
833 return AddResult(this, entry, false);
835 registerModification();
837 if (isDeletedBucket(*entry)) {
838 initializeBucket(*entry);
842 HashTranslator::translate(*entry, key, extra, h);
843 ASSERT(!isEmptyOrDeletedBucket(*entry));
847 entry = expand(entry);
849 return AddResult(this, entry, true);
852 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
853 Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::reinsert(ValueType& entry)
856 registerModification();
857 ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
858 ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
859 #if DUMP_HASHTABLE_STATS
860 atomicIncrement(&HashTableStats::numReinserts);
862 #if DUMP_HASHTABLE_STATS_PER_TABLE
863 ++m_stats->numReinserts;
865 Value* newEntry = lookupForWriting(Extractor::extract(entry)).first;
866 Mover<ValueType, Traits::needsDestruction>::move(entry, *newEntry);
871 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
872 template <typename HashTranslator, typename T>
873 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::find(const T& key)
875 ValueType* entry = lookup<HashTranslator>(key);
879 return makeKnownGoodIterator(entry);
882 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
883 template <typename HashTranslator, typename T>
884 inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::find(const T& key) const
886 ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
890 return makeKnownGoodConstIterator(entry);
893 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
894 template <typename HashTranslator, typename T>
895 bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::contains(const T& key) const
897 return const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
900 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
901 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(ValueType* pos)
903 registerModification();
904 #if DUMP_HASHTABLE_STATS
905 atomicIncrement(&HashTableStats::numRemoves);
907 #if DUMP_HASHTABLE_STATS_PER_TABLE
908 ++m_stats->numRemoves;
919 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
920 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(iterator it)
925 remove(const_cast<ValueType*>(it.m_iterator.m_position));
928 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
929 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(const_iterator it)
934 remove(const_cast<ValueType*>(it.m_position));
937 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
938 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(KeyPeekInType key)
943 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
944 Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::allocateTable(unsigned size)
946 typedef typename Allocator::template HashTableBackingHelper<HashTable>::Type HashTableBacking;
948 size_t allocSize = size * sizeof(ValueType);
950 COMPILE_ASSERT(!Traits::emptyValueIsZero || !IsPolymorphic<ValueType>::value, EmptyValueCannotBeZeroForThingsWithAVtable);
951 if (Traits::emptyValueIsZero) {
952 result = Allocator::template zeroedBackingMalloc<ValueType*, HashTableBacking>(allocSize);
954 result = Allocator::template backingMalloc<ValueType*, HashTableBacking>(allocSize);
955 for (unsigned i = 0; i < size; i++)
956 initializeBucket(result[i]);
961 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
962 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::deleteAllBucketsAndDeallocate(ValueType* table, unsigned size)
964 if (Traits::needsDestruction) {
965 for (unsigned i = 0; i < size; ++i) {
966 // This code is called when the hash table is cleared or
967 // resized. We have allocated a new backing store and we need
968 // to run the destructors on the old backing store, as it is
969 // being freed. If we are GCing we need to both call the
970 // destructor and mark the bucket as deleted, otherwise the
971 // destructor gets called again when the GC finds the backing
972 // store. With the default allocator it's enough to call the
973 // destructor, since we will free the memory explicitly and
974 // we won't see the memory with the bucket again.
975 if (!isEmptyOrDeletedBucket(table[i])) {
976 if (Allocator::isGarbageCollected)
977 deleteBucket(table[i]);
979 table[i].~ValueType();
983 Allocator::backingFree(table);
986 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
987 Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::expand(Value* entry)
991 newSize = KeyTraits::minimumTableSize;
992 } else if (mustRehashInPlace()) {
993 newSize = m_tableSize;
995 newSize = m_tableSize * 2;
996 RELEASE_ASSERT(newSize > m_tableSize);
999 return rehash(newSize, entry);
1002 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1003 Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::rehash(unsigned newTableSize, Value* entry)
1005 unsigned oldTableSize = m_tableSize;
1006 ValueType* oldTable = m_table;
1008 #if DUMP_HASHTABLE_STATS
1009 if (oldTableSize != 0)
1010 atomicIncrement(&HashTableStats::numRehashes);
1013 #if DUMP_HASHTABLE_STATS_PER_TABLE
1014 if (oldTableSize != 0)
1015 ++m_stats->numRehashes;
1018 m_table = allocateTable(newTableSize);
1019 m_tableSize = newTableSize;
1021 Value* newEntry = 0;
1022 for (unsigned i = 0; i != oldTableSize; ++i) {
1023 if (isEmptyOrDeletedBucket(oldTable[i])) {
1024 ASSERT(&oldTable[i] != entry);
1028 Value* reinsertedEntry = reinsert(oldTable[i]);
1029 if (&oldTable[i] == entry) {
1031 newEntry = reinsertedEntry;
1037 deleteAllBucketsAndDeallocate(oldTable, oldTableSize);
1042 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1043 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::clear()
1045 registerModification();
1049 deleteAllBucketsAndDeallocate(m_table, m_tableSize);
1055 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1056 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::HashTable(const HashTable& other)
1061 #ifdef ASSERT_ENABLED
1062 , m_modifications(0)
1064 #if DUMP_HASHTABLE_STATS_PER_TABLE
1065 , m_stats(adoptPtr(new Stats(*other.m_stats)))
1068 // Copy the hash table the dumb way, by adding each element to the new table.
1069 // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
1070 const_iterator end = other.end();
1071 for (const_iterator it = other.begin(); it != end; ++it)
1075 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1076 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::swap(HashTable& other)
1078 std::swap(m_table, other.m_table);
1079 std::swap(m_tableSize, other.m_tableSize);
1080 std::swap(m_keyCount, other.m_keyCount);
1081 std::swap(m_deletedCount, other.m_deletedCount);
1083 #ifdef ASSERT_ENABLED
1084 std::swap(m_modifications, other.m_modifications);
1087 #if DUMP_HASHTABLE_STATS_PER_TABLE
1088 m_stats.swap(other.m_stats);
1092 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1093 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::operator=(const HashTable& other)
1095 HashTable tmp(other);
1100 template<WeakHandlingFlag weakHandlingFlag, typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1101 struct WeakProcessingHashTableHelper;
1103 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1104 struct WeakProcessingHashTableHelper<NoWeakHandlingInCollections, Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> {
1105 static void process(typename Allocator::Visitor* visitor, void* closure) { }
1108 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1109 struct WeakProcessingHashTableHelper<WeakHandlingInCollections, Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> {
1110 static void process(typename Allocator::Visitor* visitor, void* closure)
1112 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> HashTableType;
1113 HashTableType* table = reinterpret_cast<HashTableType*>(closure);
1114 if (table->m_table) {
1115 // This just marks it live and does not push anything onto the
1117 Allocator::markNoTracing(visitor, table->m_table);
1118 // Now perform weak processing (this is a no-op if the backing
1119 // was accessible through an iterator and was already marked
1121 for (typename HashTableType::ValueType* element = table->m_table + table->m_tableSize - 1; element >= table->m_table; element--) {
1122 if (!HashTableType::isEmptyOrDeletedBucket(*element)) {
1123 if (Traits::shouldRemoveFromCollection(visitor, *element)) {
1124 table->registerModification();
1125 HashTableType::deleteBucket(*element); // Also calls the destructor.
1126 table->m_deletedCount++;
1127 table->m_keyCount--;
1128 // We don't rehash the backing until the next add
1129 // or delete, because that would cause allocation
1138 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1139 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::trace(typename Allocator::Visitor* visitor)
1141 // If someone else already marked the backing and queued up the trace
1142 // and/or weak callback then we are done. This optimization does not
1143 // happen for ListHashSet since its iterator does not point at the
1145 if (!m_table || visitor->isAlive(m_table))
1147 // Normally, we mark the backing store without performing trace. This
1148 // means it is marked live, but the pointers inside it are not marked.
1149 // Instead we will mark the pointers below. However, for backing
1150 // stores that contain weak pointers the handling is rather different.
1151 // We don't mark the backing store here, so the marking GC will leave
1152 // the backing unmarked. If the backing is found in any other way than
1153 // through its HashTable (ie from an iterator) then the mark bit will
1154 // be set and the pointers will be marked strongly, avoiding problems
1155 // with iterating over things that disappear due to weak processing
1156 // while we are iterating over them. The weakProcessing callback will
1157 // mark the backing as a void pointer, and will perform weak processing
1159 if (Traits::weakHandlingFlag == NoWeakHandlingInCollections)
1160 Allocator::markNoTracing(visitor, m_table);
1162 Allocator::registerWeakMembers(visitor, this, m_table, WeakProcessingHashTableHelper<Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::process);
1163 if (ShouldBeTraced<Traits>::value) {
1164 for (ValueType* element = m_table + m_tableSize - 1; element >= m_table; element--) {
1165 if (!isEmptyOrDeletedBucket(*element))
1166 Allocator::template trace<ValueType, Traits>(visitor, *element);
1171 // iterator adapters
1173 template<typename HashTableType, typename Traits> struct HashTableConstIteratorAdapter {
1174 HashTableConstIteratorAdapter() {}
1175 HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
1176 typedef typename Traits::IteratorConstGetType GetType;
1177 typedef typename HashTableType::ValueTraits::IteratorConstGetType SourceGetType;
1179 GetType get() const { return const_cast<GetType>(SourceGetType(m_impl.get())); }
1180 typename Traits::IteratorConstReferenceType operator*() const { return Traits::getToReferenceConstConversion(get()); }
1181 GetType operator->() const { return get(); }
1183 HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
1184 // postfix ++ intentionally omitted
1186 typename HashTableType::const_iterator m_impl;
1189 template<typename HashTableType, typename Traits> struct HashTableIteratorAdapter {
1190 typedef typename Traits::IteratorGetType GetType;
1191 typedef typename HashTableType::ValueTraits::IteratorGetType SourceGetType;
1193 HashTableIteratorAdapter() {}
1194 HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
1196 GetType get() const { return const_cast<GetType>(SourceGetType(m_impl.get())); }
1197 typename Traits::IteratorReferenceType operator*() const { return Traits::getToReferenceConversion(get()); }
1198 GetType operator->() const { return get(); }
1200 HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
1201 // postfix ++ intentionally omitted
1203 operator HashTableConstIteratorAdapter<HashTableType, Traits>()
1205 typename HashTableType::const_iterator i = m_impl;
1209 typename HashTableType::iterator m_impl;
1212 template<typename T, typename U>
1213 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1215 return a.m_impl == b.m_impl;
1218 template<typename T, typename U>
1219 inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1221 return a.m_impl != b.m_impl;
1224 template<typename T, typename U>
1225 inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1227 return a.m_impl == b.m_impl;
1230 template<typename T, typename U>
1231 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1233 return a.m_impl != b.m_impl;
1236 // All 4 combinations of ==, != and Const,non const.
1237 template<typename T, typename U>
1238 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1240 return a.m_impl == b.m_impl;
1243 template<typename T, typename U>
1244 inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1246 return a.m_impl != b.m_impl;
1249 template<typename T, typename U>
1250 inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1252 return a.m_impl == b.m_impl;
1255 template<typename T, typename U>
1256 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1258 return a.m_impl != b.m_impl;
1261 template<typename Collection1, typename Collection2>
1262 inline void removeAll(Collection1& collection, const Collection2& toBeRemoved)
1264 if (collection.isEmpty() || toBeRemoved.isEmpty())
1266 typedef typename Collection2::const_iterator CollectionIterator;
1267 CollectionIterator end(toBeRemoved.end());
1268 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it)
1269 collection.remove(*it);
1274 #include "wtf/HashIterators.h"
1276 #endif // WTF_HashTable_h