1/*
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012, 2015 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 <atomic>
26#include <iterator>
27#include <mutex>
28#include <string.h>
29#include <type_traits>
30#include <utility>
31#include <wtf/Assertions.h>
32#include <wtf/FastMalloc.h>
33#include <wtf/HashTraits.h>
34#include <wtf/Lock.h>
35#include <wtf/MathExtras.h>
36#include <wtf/StdLibExtras.h>
37#include <wtf/ValueCheck.h>
38
39#define DUMP_HASHTABLE_STATS 0
40#define DUMP_HASHTABLE_STATS_PER_TABLE 0
41
42#if DUMP_HASHTABLE_STATS_PER_TABLE
43#include <wtf/DataLog.h>
44#endif
45
46namespace WTF {
47
48// Enables internal WTF consistency checks that are invoked automatically. Non-WTF callers can call checkTableConsistency() even if internal checks are disabled.
49#define CHECK_HASHTABLE_CONSISTENCY 0
50
51#ifdef NDEBUG
52#define CHECK_HASHTABLE_ITERATORS 0
53#define CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 0
54#else
55#define CHECK_HASHTABLE_ITERATORS 1
56#define CHECK_HASHTABLE_USE_AFTER_DESTRUCTION 1
57#endif
58
59#if DUMP_HASHTABLE_STATS
60
61 struct HashTableStats {
62 // The following variables are all atomically incremented when modified.
63 WTF_EXPORTDATA static std::atomic<unsigned> numAccesses;
64 WTF_EXPORTDATA static std::atomic<unsigned> numRehashes;
65 WTF_EXPORTDATA static std::atomic<unsigned> numRemoves;
66 WTF_EXPORTDATA static std::atomic<unsigned> numReinserts;
67
68 // The following variables are only modified in the recordCollisionAtCount method within a mutex.
69 WTF_EXPORTDATA static unsigned maxCollisions;
70 WTF_EXPORTDATA static unsigned numCollisions;
71 WTF_EXPORTDATA static unsigned collisionGraph[4096];
72
73 WTF_EXPORT_PRIVATE static void recordCollisionAtCount(unsigned count);
74 WTF_EXPORT_PRIVATE static void dumpStats();
75 };
76
77#endif
78
79 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
80 class HashTable;
81 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
82 class HashTableIterator;
83 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
84 class HashTableConstIterator;
85
86 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
87 void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
88 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
89
90 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
91 void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
92
93#if !CHECK_HASHTABLE_ITERATORS
94
95 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
96 inline void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
97 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
98
99 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
100 inline void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
101
102#endif
103
104 typedef enum { HashItemKnownGood } HashItemKnownGoodTag;
105
106 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
107 class HashTableConstIterator : public std::iterator<std::forward_iterator_tag, Value, std::ptrdiff_t, const Value*, const Value&> {
108 private:
109 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
110 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
111 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
112 typedef Value ValueType;
113 typedef const ValueType& ReferenceType;
114 typedef const ValueType* PointerType;
115
116 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
117 friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
118
119 void skipEmptyBuckets()
120 {
121 while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position))
122 ++m_position;
123 }
124
125 HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition)
126 : m_position(position), m_endPosition(endPosition)
127 {
128 addIterator(table, this);
129 skipEmptyBuckets();
130 }
131
132 HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition, HashItemKnownGoodTag)
133 : m_position(position), m_endPosition(endPosition)
134 {
135 addIterator(table, this);
136 }
137
138 public:
139 HashTableConstIterator()
140 {
141 addIterator(static_cast<const HashTableType*>(0), this);
142 }
143
144 // default copy, assignment and destructor are OK if CHECK_HASHTABLE_ITERATORS is 0
145
146#if CHECK_HASHTABLE_ITERATORS
147 ~HashTableConstIterator()
148 {
149 removeIterator(this);
150 }
151
152 HashTableConstIterator(const const_iterator& other)
153 : m_position(other.m_position), m_endPosition(other.m_endPosition)
154 {
155 addIterator(other.m_table, this);
156 }
157
158 const_iterator& operator=(const const_iterator& other)
159 {
160 m_position = other.m_position;
161 m_endPosition = other.m_endPosition;
162
163 removeIterator(this);
164 addIterator(other.m_table, this);
165
166 return *this;
167 }
168#endif
169
170 PointerType get() const
171 {
172 checkValidity();
173 return m_position;
174 }
175 ReferenceType operator*() const { return *get(); }
176 PointerType operator->() const { return get(); }
177
178 const_iterator& operator++()
179 {
180 checkValidity();
181 ASSERT(m_position != m_endPosition);
182 ++m_position;
183 skipEmptyBuckets();
184 return *this;
185 }
186
187 // postfix ++ intentionally omitted
188
189 // Comparison.
190 bool operator==(const const_iterator& other) const
191 {
192 checkValidity(other);
193 return m_position == other.m_position;
194 }
195 bool operator!=(const const_iterator& other) const
196 {
197 checkValidity(other);
198 return m_position != other.m_position;
199 }
200 bool operator==(const iterator& other) const
201 {
202 return *this == static_cast<const_iterator>(other);
203 }
204 bool operator!=(const iterator& other) const
205 {
206 return *this != static_cast<const_iterator>(other);
207 }
208
209 private:
210 void checkValidity() const
211 {
212#if CHECK_HASHTABLE_ITERATORS
213 ASSERT(m_table);
214#endif
215 }
216
217
218#if CHECK_HASHTABLE_ITERATORS
219 void checkValidity(const const_iterator& other) const
220 {
221 ASSERT(m_table);
222 ASSERT_UNUSED(other, other.m_table);
223 ASSERT(m_table == other.m_table);
224 }
225#else
226 void checkValidity(const const_iterator&) const { }
227#endif
228
229 PointerType m_position;
230 PointerType m_endPosition;
231
232#if CHECK_HASHTABLE_ITERATORS
233 public:
234 // Any modifications of the m_next or m_previous of an iterator that is in a linked list of a HashTable::m_iterator,
235 // should be guarded with m_table->m_mutex.
236 mutable const HashTableType* m_table;
237 mutable const_iterator* m_next;
238 mutable const_iterator* m_previous;
239#endif
240 };
241
242 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
243 class HashTableIterator : public std::iterator<std::forward_iterator_tag, Value, std::ptrdiff_t, Value*, Value&> {
244 private:
245 typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
246 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
247 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
248 typedef Value ValueType;
249 typedef ValueType& ReferenceType;
250 typedef ValueType* PointerType;
251
252 friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
253
254 HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { }
255 HashTableIterator(HashTableType* table, PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(table, pos, end, tag) { }
256
257 public:
258 HashTableIterator() { }
259
260 // default copy, assignment and destructor are OK
261
262 PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
263 ReferenceType operator*() const { return *get(); }
264 PointerType operator->() const { return get(); }
265
266 iterator& operator++() { ++m_iterator; return *this; }
267
268 // postfix ++ intentionally omitted
269
270 // Comparison.
271 bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
272 bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
273 bool operator==(const const_iterator& other) const { return m_iterator == other; }
274 bool operator!=(const const_iterator& other) const { return m_iterator != other; }
275
276 operator const_iterator() const { return m_iterator; }
277
278 private:
279 const_iterator m_iterator;
280 };
281
282 template<typename HashFunctions> class IdentityHashTranslator {
283 public:
284 template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
285 template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
286 template<typename T, typename U, typename V> static void translate(T& location, const U&, V&& value) { location = std::forward<V>(value); }
287 };
288
289 template<typename IteratorType> struct HashTableAddResult {
290 HashTableAddResult() : isNewEntry(false) { }
291 HashTableAddResult(IteratorType iter, bool isNewEntry) : iterator(iter), isNewEntry(isNewEntry) { }
292 IteratorType iterator;
293 bool isNewEntry;
294
295 explicit operator bool() const { return isNewEntry; }
296 };
297
298 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
299 class HashTable {
300 public:
301 typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
302 typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
303 typedef Traits ValueTraits;
304 typedef Key KeyType;
305 typedef Value ValueType;
306 typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType;
307 typedef HashTableAddResult<iterator> AddResult;
308
309#if DUMP_HASHTABLE_STATS_PER_TABLE
310 struct Stats {
311 Stats()
312 : numAccesses(0)
313 , numRehashes(0)
314 , numRemoves(0)
315 , numReinserts(0)
316 , maxCollisions(0)
317 , numCollisions(0)
318 , collisionGraph()
319 {
320 }
321
322 unsigned numAccesses;
323 unsigned numRehashes;
324 unsigned numRemoves;
325 unsigned numReinserts;
326
327 unsigned maxCollisions;
328 unsigned numCollisions;
329 unsigned collisionGraph[4096];
330
331 void recordCollisionAtCount(unsigned count)
332 {
333 if (count > maxCollisions)
334 maxCollisions = count;
335 numCollisions++;
336 collisionGraph[count]++;
337 }
338
339 void dumpStats()
340 {
341 dataLogF("\nWTF::HashTable::Stats dump\n\n");
342 dataLogF("%d accesses\n", numAccesses);
343 dataLogF("%d total collisions, average %.2f probes per access\n", numCollisions, 1.0 * (numAccesses + numCollisions) / numAccesses);
344 dataLogF("longest collision chain: %d\n", maxCollisions);
345 for (unsigned i = 1; i <= maxCollisions; i++) {
346 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);
347 }
348 dataLogF("%d rehashes\n", numRehashes);
349 dataLogF("%d reinserts\n", numReinserts);
350 }
351 };
352#endif
353
354 HashTable();
355 ~HashTable()
356 {
357 invalidateIterators();
358 if (m_table)
359 deallocateTable(m_table, m_tableSize);
360#if CHECK_HASHTABLE_USE_AFTER_DESTRUCTION
361 m_table = (ValueType*)(uintptr_t)0xbbadbeef;
362#endif
363 }
364
365 HashTable(const HashTable&);
366 void swap(HashTable&);
367 HashTable& operator=(const HashTable&);
368
369 HashTable(HashTable&&);
370 HashTable& operator=(HashTable&&);
371
372 // When the hash table is empty, just return the same iterator for end as for begin.
373 // This is more efficient because we don't have to skip all the empty and deleted
374 // buckets, and iterating an empty table is a common case that's worth optimizing.
375 iterator begin() { return isEmpty() ? end() : makeIterator(m_table); }
376 iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
377 const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); }
378 const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
379
380 unsigned size() const { return m_keyCount; }
381 unsigned capacity() const { return m_tableSize; }
382 bool isEmpty() const { return !m_keyCount; }
383
384 AddResult add(const ValueType& value) { return add<IdentityTranslatorType>(Extractor::extract(value), value); }
385 AddResult add(ValueType&& value) { return add<IdentityTranslatorType>(Extractor::extract(value), WTFMove(value)); }
386
387 // A special version of add() that finds the object by hashing and comparing
388 // with some other type, to avoid the cost of type conversion if the object is already
389 // in the table.
390 template<typename HashTranslator, typename T, typename Extra> AddResult add(T&& key, Extra&&);
391 template<typename HashTranslator, typename T, typename Extra> AddResult addPassingHashCode(T&& key, Extra&&);
392
393 iterator find(const KeyType& key) { return find<IdentityTranslatorType>(key); }
394 const_iterator find(const KeyType& key) const { return find<IdentityTranslatorType>(key); }
395 bool contains(const KeyType& key) const { return contains<IdentityTranslatorType>(key); }
396
397 template<typename HashTranslator, typename T> iterator find(const T&);
398 template<typename HashTranslator, typename T> const_iterator find(const T&) const;
399 template<typename HashTranslator, typename T> bool contains(const T&) const;
400
401 void remove(const KeyType&);
402 void remove(iterator);
403 void removeWithoutEntryConsistencyCheck(iterator);
404 void removeWithoutEntryConsistencyCheck(const_iterator);
405 template<typename Functor>
406 void removeIf(const Functor&);
407 void clear();
408
409 static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
410 static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
411 static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
412
413 ValueType* lookup(const Key& key) { return lookup<IdentityTranslatorType>(key); }
414 template<typename HashTranslator, typename T> ValueType* lookup(const T&);
415 template<typename HashTranslator, typename T> ValueType* inlineLookup(const T&);
416
417#if !ASSERT_DISABLED
418 void checkTableConsistency() const;
419#else
420 static void checkTableConsistency() { }
421#endif
422#if CHECK_HASHTABLE_CONSISTENCY
423 void internalCheckTableConsistency() const { checkTableConsistency(); }
424 void internalCheckTableConsistencyExceptSize() const { checkTableConsistencyExceptSize(); }
425#else
426 static void internalCheckTableConsistencyExceptSize() { }
427 static void internalCheckTableConsistency() { }
428#endif
429
430 private:
431 static ValueType* allocateTable(unsigned size);
432 static void deallocateTable(ValueType* table, unsigned size);
433
434 typedef std::pair<ValueType*, bool> LookupType;
435 typedef std::pair<LookupType, unsigned> FullLookupType;
436
437 LookupType lookupForWriting(const Key& key) { return lookupForWriting<IdentityTranslatorType>(key); };
438 template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&);
439 template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&);
440
441 template<typename HashTranslator, typename T, typename Extra> void addUniqueForInitialization(T&& key, Extra&&);
442
443 template<typename HashTranslator, typename T> void checkKey(const T&);
444
445 void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
446 void removeAndInvalidate(ValueType*);
447 void remove(ValueType*);
448
449 bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
450 bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
451 bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; }
452 ValueType* expand(ValueType* entry = nullptr);
453 void shrink() { rehash(m_tableSize / 2, nullptr); }
454
455 ValueType* rehash(unsigned newTableSize, ValueType* entry);
456 ValueType* reinsert(ValueType&&);
457
458 static void initializeBucket(ValueType& bucket);
459 static void deleteBucket(ValueType& bucket) { hashTraitsDeleteBucket<Traits>(bucket); }
460
461 FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
462 { return FullLookupType(LookupType(position, found), hash); }
463
464 iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
465 const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
466 iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
467 const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
468
469#if !ASSERT_DISABLED
470 void checkTableConsistencyExceptSize() const;
471#else
472 static void checkTableConsistencyExceptSize() { }
473#endif
474
475#if CHECK_HASHTABLE_ITERATORS
476 void invalidateIterators();
477#else
478 static void invalidateIterators() { }
479#endif
480
481 static const unsigned m_maxLoad = 2;
482 static const unsigned m_minLoad = 6;
483
484 ValueType* m_table;
485 unsigned m_tableSize;
486 unsigned m_tableSizeMask;
487 unsigned m_keyCount;
488 unsigned m_deletedCount;
489
490#if CHECK_HASHTABLE_ITERATORS
491 public:
492 // All access to m_iterators should be guarded with m_mutex.
493 mutable const_iterator* m_iterators;
494 // Use std::unique_ptr so HashTable can still be memmove'd or memcpy'ed.
495 mutable std::unique_ptr<Lock> m_mutex;
496#endif
497
498#if DUMP_HASHTABLE_STATS_PER_TABLE
499 public:
500 mutable std::unique_ptr<Stats> m_stats;
501#endif
502 };
503
504 // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
505 template<unsigned size> struct OneifyLowBits;
506 template<>
507 struct OneifyLowBits<0> {
508 static const unsigned value = 0;
509 };
510 template<unsigned number>
511 struct OneifyLowBits {
512 static const unsigned value = number | OneifyLowBits<(number >> 1)>::value;
513 };
514 // Compute the first power of two integer that is an upper bound of the parameter 'number'.
515 template<unsigned number>
516 struct UpperPowerOfTwoBound {
517 static const unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2;
518 };
519
520 // Because power of two numbers are the limit of maxLoad, their capacity is twice the
521 // UpperPowerOfTwoBound, or 4 times their values.
522 template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter;
523 template<unsigned size>
524 struct HashTableCapacityForSizeSplitter<size, true> {
525 static const unsigned value = size * 4;
526 };
527 template<unsigned size>
528 struct HashTableCapacityForSizeSplitter<size, false> {
529 static const unsigned value = UpperPowerOfTwoBound<size>::value;
530 };
531
532 // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter.
533 // This is done at compile time to initialize the HashTraits.
534 template<unsigned size>
535 struct HashTableCapacityForSize {
536 static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
537 COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
538 COMPILE_ASSERT(!static_cast<unsigned>(value >> 31), HashTableNoCapacityOverflow);
539 COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
540 };
541
542 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
543 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
544 : m_table(0)
545 , m_tableSize(0)
546 , m_tableSizeMask(0)
547 , m_keyCount(0)
548 , m_deletedCount(0)
549#if CHECK_HASHTABLE_ITERATORS
550 , m_iterators(0)
551 , m_mutex(std::make_unique<Lock>())
552#endif
553#if DUMP_HASHTABLE_STATS_PER_TABLE
554 , m_stats(std::make_unique<Stats>())
555#endif
556 {
557 }
558
559 inline unsigned doubleHash(unsigned key)
560 {
561 key = ~key + (key >> 23);
562 key ^= (key << 12);
563 key ^= (key >> 7);
564 key ^= (key << 2);
565 key ^= (key >> 20);
566 return key;
567 }
568
569#if ASSERT_DISABLED
570
571 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
572 template<typename HashTranslator, typename T>
573 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
574 {
575 }
576
577#else
578
579 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
580 template<typename HashTranslator, typename T>
581 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)
582 {
583 if (!HashFunctions::safeToCompareToEmptyOrDeleted)
584 return;
585 ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
586 typename std::aligned_storage<sizeof(ValueType), std::alignment_of<ValueType>::value>::type deletedValueBuffer;
587 ValueType* deletedValuePtr = reinterpret_cast_ptr<ValueType*>(&deletedValueBuffer);
588 ValueType& deletedValue = *deletedValuePtr;
589 Traits::constructDeletedValue(deletedValue);
590 ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
591 }
592
593#endif
594
595 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
596 template<typename HashTranslator, typename T>
597 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key) -> ValueType*
598 {
599 return inlineLookup<HashTranslator>(key);
600 }
601
602 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
603 template<typename HashTranslator, typename T>
604 ALWAYS_INLINE auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::inlineLookup(const T& key) -> ValueType*
605 {
606 checkKey<HashTranslator>(key);
607
608 unsigned k = 0;
609 unsigned sizeMask = m_tableSizeMask;
610 ValueType* table = m_table;
611 unsigned h = HashTranslator::hash(key);
612 unsigned i = h & sizeMask;
613
614 if (!table)
615 return 0;
616
617#if DUMP_HASHTABLE_STATS
618 ++HashTableStats::numAccesses;
619 unsigned probeCount = 0;
620#endif
621
622#if DUMP_HASHTABLE_STATS_PER_TABLE
623 ++m_stats->numAccesses;
624#endif
625
626 while (1) {
627 ValueType* entry = table + i;
628
629 // we count on the compiler to optimize out this branch
630 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
631 if (HashTranslator::equal(Extractor::extract(*entry), key))
632 return entry;
633
634 if (isEmptyBucket(*entry))
635 return 0;
636 } else {
637 if (isEmptyBucket(*entry))
638 return 0;
639
640 if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
641 return entry;
642 }
643#if DUMP_HASHTABLE_STATS
644 ++probeCount;
645 HashTableStats::recordCollisionAtCount(probeCount);
646#endif
647
648#if DUMP_HASHTABLE_STATS_PER_TABLE
649 m_stats->recordCollisionAtCount(probeCount);
650#endif
651
652 if (k == 0)
653 k = 1 | doubleHash(h);
654 i = (i + k) & sizeMask;
655 }
656 }
657
658 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
659 template<typename HashTranslator, typename T>
660 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key) -> LookupType
661 {
662 ASSERT(m_table);
663 checkKey<HashTranslator>(key);
664
665 unsigned k = 0;
666 ValueType* table = m_table;
667 unsigned sizeMask = m_tableSizeMask;
668 unsigned h = HashTranslator::hash(key);
669 unsigned i = h & sizeMask;
670
671#if DUMP_HASHTABLE_STATS
672 ++HashTableStats::numAccesses;
673 unsigned probeCount = 0;
674#endif
675
676#if DUMP_HASHTABLE_STATS_PER_TABLE
677 ++m_stats->numAccesses;
678#endif
679
680 ValueType* deletedEntry = 0;
681
682 while (1) {
683 ValueType* entry = table + i;
684
685 // we count on the compiler to optimize out this branch
686 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
687 if (isEmptyBucket(*entry))
688 return LookupType(deletedEntry ? deletedEntry : entry, false);
689
690 if (HashTranslator::equal(Extractor::extract(*entry), key))
691 return LookupType(entry, true);
692
693 if (isDeletedBucket(*entry))
694 deletedEntry = entry;
695 } else {
696 if (isEmptyBucket(*entry))
697 return LookupType(deletedEntry ? deletedEntry : entry, false);
698
699 if (isDeletedBucket(*entry))
700 deletedEntry = entry;
701 else if (HashTranslator::equal(Extractor::extract(*entry), key))
702 return LookupType(entry, true);
703 }
704#if DUMP_HASHTABLE_STATS
705 ++probeCount;
706 HashTableStats::recordCollisionAtCount(probeCount);
707#endif
708
709#if DUMP_HASHTABLE_STATS_PER_TABLE
710 m_stats->recordCollisionAtCount(probeCount);
711#endif
712
713 if (k == 0)
714 k = 1 | doubleHash(h);
715 i = (i + k) & sizeMask;
716 }
717 }
718
719 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
720 template<typename HashTranslator, typename T>
721 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key) -> FullLookupType
722 {
723 ASSERT(m_table);
724 checkKey<HashTranslator>(key);
725
726 unsigned k = 0;
727 ValueType* table = m_table;
728 unsigned sizeMask = m_tableSizeMask;
729 unsigned h = HashTranslator::hash(key);
730 unsigned i = h & sizeMask;
731
732#if DUMP_HASHTABLE_STATS
733 ++HashTableStats::numAccesses;
734 unsigned probeCount = 0;
735#endif
736
737#if DUMP_HASHTABLE_STATS_PER_TABLE
738 ++m_stats->numAccesses;
739#endif
740
741 ValueType* deletedEntry = 0;
742
743 while (1) {
744 ValueType* entry = table + i;
745
746 // we count on the compiler to optimize out this branch
747 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
748 if (isEmptyBucket(*entry))
749 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
750
751 if (HashTranslator::equal(Extractor::extract(*entry), key))
752 return makeLookupResult(entry, true, h);
753
754 if (isDeletedBucket(*entry))
755 deletedEntry = entry;
756 } else {
757 if (isEmptyBucket(*entry))
758 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
759
760 if (isDeletedBucket(*entry))
761 deletedEntry = entry;
762 else if (HashTranslator::equal(Extractor::extract(*entry), key))
763 return makeLookupResult(entry, true, h);
764 }
765#if DUMP_HASHTABLE_STATS
766 ++probeCount;
767 HashTableStats::recordCollisionAtCount(probeCount);
768#endif
769
770#if DUMP_HASHTABLE_STATS_PER_TABLE
771 m_stats->recordCollisionAtCount(probeCount);
772#endif
773
774 if (k == 0)
775 k = 1 | doubleHash(h);
776 i = (i + k) & sizeMask;
777 }
778 }
779
780 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
781 template<typename HashTranslator, typename T, typename Extra>
782 ALWAYS_INLINE void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addUniqueForInitialization(T&& key, Extra&& extra)
783 {
784 ASSERT(m_table);
785
786 checkKey<HashTranslator>(key);
787
788 invalidateIterators();
789
790 internalCheckTableConsistency();
791
792 unsigned k = 0;
793 ValueType* table = m_table;
794 unsigned sizeMask = m_tableSizeMask;
795 unsigned h = HashTranslator::hash(key);
796 unsigned i = h & sizeMask;
797
798#if DUMP_HASHTABLE_STATS
799 ++HashTableStats::numAccesses;
800 unsigned probeCount = 0;
801#endif
802
803#if DUMP_HASHTABLE_STATS_PER_TABLE
804 ++m_stats->numAccesses;
805#endif
806
807 ValueType* entry;
808 while (1) {
809 entry = table + i;
810
811 if (isEmptyBucket(*entry))
812 break;
813
814#if DUMP_HASHTABLE_STATS
815 ++probeCount;
816 HashTableStats::recordCollisionAtCount(probeCount);
817#endif
818
819#if DUMP_HASHTABLE_STATS_PER_TABLE
820 m_stats->recordCollisionAtCount(probeCount);
821#endif
822
823 if (k == 0)
824 k = 1 | doubleHash(h);
825 i = (i + k) & sizeMask;
826 }
827
828 HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
829
830 internalCheckTableConsistency();
831 }
832
833 template<bool emptyValueIsZero> struct HashTableBucketInitializer;
834
835 template<> struct HashTableBucketInitializer<false> {
836 template<typename Traits, typename Value> static void initialize(Value& bucket)
837 {
838 new (NotNull, std::addressof(bucket)) Value(Traits::emptyValue());
839 }
840 };
841
842 template<> struct HashTableBucketInitializer<true> {
843 template<typename Traits, typename Value> static void initialize(Value& bucket)
844 {
845 // This initializes the bucket without copying the empty value.
846 // That makes it possible to use this with types that don't support copying.
847 // The memset to 0 looks like a slow operation but is optimized by the compilers.
848 memset(&bucket, 0, sizeof(bucket));
849 }
850 };
851
852 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
853 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::initializeBucket(ValueType& bucket)
854 {
855 HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket);
856 }
857
858 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
859 template<typename HashTranslator, typename T, typename Extra>
860 ALWAYS_INLINE auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(T&& key, Extra&& extra) -> AddResult
861 {
862 checkKey<HashTranslator>(key);
863
864 invalidateIterators();
865
866 if (!m_table)
867 expand(nullptr);
868
869 internalCheckTableConsistency();
870
871 ASSERT(m_table);
872
873 unsigned k = 0;
874 ValueType* table = m_table;
875 unsigned sizeMask = m_tableSizeMask;
876 unsigned h = HashTranslator::hash(key);
877 unsigned i = h & sizeMask;
878
879#if DUMP_HASHTABLE_STATS
880 ++HashTableStats::numAccesses;
881 unsigned probeCount = 0;
882#endif
883
884#if DUMP_HASHTABLE_STATS_PER_TABLE
885 ++m_stats->numAccesses;
886#endif
887
888 ValueType* deletedEntry = 0;
889 ValueType* entry;
890 while (1) {
891 entry = table + i;
892
893 // we count on the compiler to optimize out this branch
894 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
895 if (isEmptyBucket(*entry))
896 break;
897
898 if (HashTranslator::equal(Extractor::extract(*entry), key))
899 return AddResult(makeKnownGoodIterator(entry), false);
900
901 if (isDeletedBucket(*entry))
902 deletedEntry = entry;
903 } else {
904 if (isEmptyBucket(*entry))
905 break;
906
907 if (isDeletedBucket(*entry))
908 deletedEntry = entry;
909 else if (HashTranslator::equal(Extractor::extract(*entry), key))
910 return AddResult(makeKnownGoodIterator(entry), false);
911 }
912#if DUMP_HASHTABLE_STATS
913 ++probeCount;
914 HashTableStats::recordCollisionAtCount(probeCount);
915#endif
916
917#if DUMP_HASHTABLE_STATS_PER_TABLE
918 m_stats->recordCollisionAtCount(probeCount);
919#endif
920
921 if (k == 0)
922 k = 1 | doubleHash(h);
923 i = (i + k) & sizeMask;
924 }
925
926 if (deletedEntry) {
927 initializeBucket(*deletedEntry);
928 entry = deletedEntry;
929 --m_deletedCount;
930 }
931
932 HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
933 ++m_keyCount;
934
935 if (shouldExpand())
936 entry = expand(entry);
937
938 internalCheckTableConsistency();
939
940 return AddResult(makeKnownGoodIterator(entry), true);
941 }
942
943 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
944 template<typename HashTranslator, typename T, typename Extra>
945 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addPassingHashCode(T&& key, Extra&& extra) -> AddResult
946 {
947 checkKey<HashTranslator>(key);
948
949 invalidateIterators();
950
951 if (!m_table)
952 expand();
953
954 internalCheckTableConsistency();
955
956 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key);
957
958 ValueType* entry = lookupResult.first.first;
959 bool found = lookupResult.first.second;
960 unsigned h = lookupResult.second;
961
962 if (found)
963 return AddResult(makeKnownGoodIterator(entry), false);
964
965 if (isDeletedBucket(*entry)) {
966 initializeBucket(*entry);
967 --m_deletedCount;
968 }
969
970 HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra), h);
971 ++m_keyCount;
972
973 if (shouldExpand())
974 entry = expand(entry);
975
976 internalCheckTableConsistency();
977
978 return AddResult(makeKnownGoodIterator(entry), true);
979 }
980
981 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
982 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType&& entry) -> ValueType*
983 {
984 ASSERT(m_table);
985 ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
986 ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
987#if DUMP_HASHTABLE_STATS
988 ++HashTableStats::numReinserts;
989#endif
990#if DUMP_HASHTABLE_STATS_PER_TABLE
991 ++m_stats->numReinserts;
992#endif
993
994 Value* newEntry = lookupForWriting(Extractor::extract(entry)).first;
995 newEntry->~Value();
996 new (NotNull, newEntry) ValueType(WTFMove(entry));
997
998 return newEntry;
999 }
1000
1001 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1002 template <typename HashTranslator, typename T>
1003 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) -> iterator
1004 {
1005 if (!m_table)
1006 return end();
1007
1008 ValueType* entry = lookup<HashTranslator>(key);
1009 if (!entry)
1010 return end();
1011
1012 return makeKnownGoodIterator(entry);
1013 }
1014
1015 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1016 template <typename HashTranslator, typename T>
1017 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const -> const_iterator
1018 {
1019 if (!m_table)
1020 return end();
1021
1022 ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
1023 if (!entry)
1024 return end();
1025
1026 return makeKnownGoodConstIterator(entry);
1027 }
1028
1029 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1030 template <typename HashTranslator, typename T>
1031 bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const
1032 {
1033 if (!m_table)
1034 return false;
1035
1036 return const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
1037 }
1038
1039 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1040 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos)
1041 {
1042 invalidateIterators();
1043 remove(pos);
1044 }
1045
1046 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1047 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos)
1048 {
1049 invalidateIterators();
1050 internalCheckTableConsistency();
1051 remove(pos);
1052 }
1053
1054 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1055 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
1056 {
1057#if DUMP_HASHTABLE_STATS
1058 ++HashTableStats::numRemoves;
1059#endif
1060#if DUMP_HASHTABLE_STATS_PER_TABLE
1061 ++m_stats->numRemoves;
1062#endif
1063
1064 deleteBucket(*pos);
1065 ++m_deletedCount;
1066 --m_keyCount;
1067
1068 if (shouldShrink())
1069 shrink();
1070
1071 internalCheckTableConsistency();
1072 }
1073
1074 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1075 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
1076 {
1077 if (it == end())
1078 return;
1079
1080 removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position));
1081 }
1082
1083 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1084 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it)
1085 {
1086 if (it == end())
1087 return;
1088
1089 removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position));
1090 }
1091
1092 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1093 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(const_iterator it)
1094 {
1095 if (it == end())
1096 return;
1097
1098 removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_position));
1099 }
1100
1101 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1102 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
1103 {
1104 remove(find(key));
1105 }
1106
1107 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1108 template<typename Functor>
1109 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeIf(const Functor& functor)
1110 {
1111 // We must use local copies in case "functor" or "deleteBucket"
1112 // make a function call, which prevents the compiler from keeping
1113 // the values in register.
1114 unsigned removedBucketCount = 0;
1115 ValueType* table = m_table;
1116
1117 for (unsigned i = m_tableSize; i--;) {
1118 ValueType& bucket = table[i];
1119 if (isEmptyOrDeletedBucket(bucket))
1120 continue;
1121
1122 if (!functor(bucket))
1123 continue;
1124
1125 deleteBucket(bucket);
1126 ++removedBucketCount;
1127 }
1128 m_deletedCount += removedBucketCount;
1129 m_keyCount -= removedBucketCount;
1130
1131 if (shouldShrink())
1132 shrink();
1133
1134 internalCheckTableConsistency();
1135 }
1136
1137 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1138 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(unsigned size) -> ValueType*
1139 {
1140 // would use a template member function with explicit specializations here, but
1141 // gcc doesn't appear to support that
1142 if (Traits::emptyValueIsZero)
1143 return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType)));
1144 ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
1145 for (unsigned i = 0; i < size; i++)
1146 initializeBucket(result[i]);
1147 return result;
1148 }
1149
1150 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1151 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, unsigned size)
1152 {
1153 for (unsigned i = 0; i < size; ++i) {
1154 if (!isDeletedBucket(table[i]))
1155 table[i].~ValueType();
1156 }
1157 fastFree(table);
1158 }
1159
1160 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1161 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand(ValueType* entry) -> ValueType*
1162 {
1163 unsigned newSize;
1164 if (m_tableSize == 0)
1165 newSize = KeyTraits::minimumTableSize;
1166 else if (mustRehashInPlace())
1167 newSize = m_tableSize;
1168 else
1169 newSize = m_tableSize * 2;
1170
1171 return rehash(newSize, entry);
1172 }
1173
1174 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1175 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(unsigned newTableSize, ValueType* entry) -> ValueType*
1176 {
1177 internalCheckTableConsistencyExceptSize();
1178
1179 unsigned oldTableSize = m_tableSize;
1180 ValueType* oldTable = m_table;
1181
1182#if DUMP_HASHTABLE_STATS
1183 if (oldTableSize != 0)
1184 ++HashTableStats::numRehashes;
1185#endif
1186
1187#if DUMP_HASHTABLE_STATS_PER_TABLE
1188 if (oldTableSize != 0)
1189 ++m_stats->numRehashes;
1190#endif
1191
1192 m_tableSize = newTableSize;
1193 m_tableSizeMask = newTableSize - 1;
1194 m_table = allocateTable(newTableSize);
1195
1196 Value* newEntry = nullptr;
1197 for (unsigned i = 0; i != oldTableSize; ++i) {
1198 if (isEmptyOrDeletedBucket(oldTable[i])) {
1199 ASSERT(&oldTable[i] != entry);
1200 continue;
1201 }
1202
1203 Value* reinsertedEntry = reinsert(WTFMove(oldTable[i]));
1204 if (&oldTable[i] == entry) {
1205 ASSERT(!newEntry);
1206 newEntry = reinsertedEntry;
1207 }
1208 }
1209
1210 m_deletedCount = 0;
1211
1212 deallocateTable(oldTable, oldTableSize);
1213
1214 internalCheckTableConsistency();
1215 return newEntry;
1216 }
1217
1218 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1219 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
1220 {
1221 invalidateIterators();
1222 if (!m_table)
1223 return;
1224
1225 deallocateTable(m_table, m_tableSize);
1226 m_table = 0;
1227 m_tableSize = 0;
1228 m_tableSizeMask = 0;
1229 m_keyCount = 0;
1230 m_deletedCount = 0;
1231 }
1232
1233 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1234 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
1235 : m_table(nullptr)
1236 , m_tableSize(0)
1237 , m_tableSizeMask(0)
1238 , m_keyCount(0)
1239 , m_deletedCount(0)
1240#if CHECK_HASHTABLE_ITERATORS
1241 , m_iterators(nullptr)
1242 , m_mutex(std::make_unique<Lock>())
1243#endif
1244#if DUMP_HASHTABLE_STATS_PER_TABLE
1245 , m_stats(std::make_unique<Stats>(*other.m_stats))
1246#endif
1247 {
1248 unsigned otherKeyCount = other.size();
1249 if (!otherKeyCount)
1250 return;
1251
1252 unsigned bestTableSize = WTF::roundUpToPowerOfTwo(otherKeyCount) * 2;
1253
1254 // With maxLoad at 1/2 and minLoad at 1/6, our average load is 2/6.
1255 // If we are getting halfway between 2/6 and 1/2 (past 5/12), we double the size to avoid being too close to
1256 // loadMax and bring the ratio close to 2/6. This give us a load in the bounds [3/12, 5/12).
1257 bool aboveThreeQuarterLoad = otherKeyCount * 12 >= bestTableSize * 5;
1258 if (aboveThreeQuarterLoad)
1259 bestTableSize *= 2;
1260
1261 unsigned minimumTableSize = KeyTraits::minimumTableSize;
1262 m_tableSize = std::max<unsigned>(bestTableSize, minimumTableSize);
1263 m_tableSizeMask = m_tableSize - 1;
1264 m_keyCount = otherKeyCount;
1265 m_table = allocateTable(m_tableSize);
1266
1267 for (const auto& otherValue : other)
1268 addUniqueForInitialization<IdentityTranslatorType>(Extractor::extract(otherValue), otherValue);
1269 }
1270
1271 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1272 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
1273 {
1274 invalidateIterators();
1275 other.invalidateIterators();
1276
1277 std::swap(m_table, other.m_table);
1278 std::swap(m_tableSize, other.m_tableSize);
1279 std::swap(m_tableSizeMask, other.m_tableSizeMask);
1280 std::swap(m_keyCount, other.m_keyCount);
1281 std::swap(m_deletedCount, other.m_deletedCount);
1282
1283#if DUMP_HASHTABLE_STATS_PER_TABLE
1284 m_stats.swap(other.m_stats);
1285#endif
1286 }
1287
1288 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1289 auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other) -> HashTable&
1290 {
1291 HashTable tmp(other);
1292 swap(tmp);
1293 return *this;
1294 }
1295
1296 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1297 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(HashTable&& other)
1298#if CHECK_HASHTABLE_ITERATORS
1299 : m_iterators(nullptr)
1300 , m_mutex(std::make_unique<Lock>())
1301#endif
1302 {
1303 other.invalidateIterators();
1304
1305 m_table = other.m_table;
1306 m_tableSize = other.m_tableSize;
1307 m_tableSizeMask = other.m_tableSizeMask;
1308 m_keyCount = other.m_keyCount;
1309 m_deletedCount = other.m_deletedCount;
1310
1311 other.m_table = nullptr;
1312 other.m_tableSize = 0;
1313 other.m_tableSizeMask = 0;
1314 other.m_keyCount = 0;
1315 other.m_deletedCount = 0;
1316
1317#if DUMP_HASHTABLE_STATS_PER_TABLE
1318 m_stats = WTFMove(other.m_stats);
1319 other.m_stats = nullptr;
1320#endif
1321 }
1322
1323 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1324 inline auto HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(HashTable&& other) -> HashTable&
1325 {
1326 HashTable temp = WTFMove(other);
1327 swap(temp);
1328 return *this;
1329 }
1330
1331#if !ASSERT_DISABLED
1332
1333 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1334 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
1335 {
1336 checkTableConsistencyExceptSize();
1337 ASSERT(!m_table || !shouldExpand());
1338 ASSERT(!shouldShrink());
1339 }
1340
1341 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1342 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
1343 {
1344 if (!m_table)
1345 return;
1346
1347 unsigned count = 0;
1348 unsigned deletedCount = 0;
1349 for (unsigned j = 0; j < m_tableSize; ++j) {
1350 ValueType* entry = m_table + j;
1351 if (isEmptyBucket(*entry))
1352 continue;
1353
1354 if (isDeletedBucket(*entry)) {
1355 ++deletedCount;
1356 continue;
1357 }
1358
1359 const_iterator it = find(Extractor::extract(*entry));
1360 ASSERT(entry == it.m_position);
1361 ++count;
1362
1363 ValueCheck<Key>::checkConsistency(it->key);
1364 }
1365
1366 ASSERT(count == m_keyCount);
1367 ASSERT(deletedCount == m_deletedCount);
1368 ASSERT(m_tableSize >= KeyTraits::minimumTableSize);
1369 ASSERT(m_tableSizeMask);
1370 ASSERT(m_tableSize == m_tableSizeMask + 1);
1371 }
1372
1373#endif // ASSERT_DISABLED
1374
1375#if CHECK_HASHTABLE_ITERATORS
1376
1377 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1378 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
1379 {
1380 std::lock_guard<Lock> lock(*m_mutex);
1381 const_iterator* next;
1382 for (const_iterator* p = m_iterators; p; p = next) {
1383 next = p->m_next;
1384 p->m_table = 0;
1385 p->m_next = 0;
1386 p->m_previous = 0;
1387 }
1388 m_iterators = 0;
1389 }
1390
1391 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1392 void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
1393 HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1394 {
1395 it->m_table = table;
1396 it->m_previous = 0;
1397
1398 // Insert iterator at head of doubly-linked list of iterators.
1399 if (!table) {
1400 it->m_next = 0;
1401 } else {
1402 std::lock_guard<Lock> lock(*table->m_mutex);
1403 ASSERT(table->m_iterators != it);
1404 it->m_next = table->m_iterators;
1405 table->m_iterators = it;
1406 if (it->m_next) {
1407 ASSERT(!it->m_next->m_previous);
1408 it->m_next->m_previous = it;
1409 }
1410 }
1411 }
1412
1413 template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1414 void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1415 {
1416 // Delete iterator from doubly-linked list of iterators.
1417 if (!it->m_table) {
1418 ASSERT(!it->m_next);
1419 ASSERT(!it->m_previous);
1420 } else {
1421 std::lock_guard<Lock> lock(*it->m_table->m_mutex);
1422 if (it->m_next) {
1423 ASSERT(it->m_next->m_previous == it);
1424 it->m_next->m_previous = it->m_previous;
1425 }
1426 if (it->m_previous) {
1427 ASSERT(it->m_table->m_iterators != it);
1428 ASSERT(it->m_previous->m_next == it);
1429 it->m_previous->m_next = it->m_next;
1430 } else {
1431 ASSERT(it->m_table->m_iterators == it);
1432 it->m_table->m_iterators = it->m_next;
1433 }
1434 }
1435
1436 it->m_table = 0;
1437 it->m_next = 0;
1438 it->m_previous = 0;
1439 }
1440
1441#endif // CHECK_HASHTABLE_ITERATORS
1442
1443 // iterator adapters
1444
1445 template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter : public std::iterator<std::forward_iterator_tag, ValueType, std::ptrdiff_t, const ValueType*, const ValueType&> {
1446 HashTableConstIteratorAdapter() {}
1447 HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
1448
1449 const ValueType* get() const { return (const ValueType*)m_impl.get(); }
1450 const ValueType& operator*() const { return *get(); }
1451 const ValueType* operator->() const { return get(); }
1452
1453 HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
1454 // postfix ++ intentionally omitted
1455
1456 typename HashTableType::const_iterator m_impl;
1457 };
1458
1459 template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter : public std::iterator<std::forward_iterator_tag, ValueType, std::ptrdiff_t, ValueType*, ValueType&> {
1460 HashTableIteratorAdapter() {}
1461 HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
1462
1463 ValueType* get() const { return (ValueType*)m_impl.get(); }
1464 ValueType& operator*() const { return *get(); }
1465 ValueType* operator->() const { return get(); }
1466
1467 HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
1468 // postfix ++ intentionally omitted
1469
1470 operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
1471 typename HashTableType::const_iterator i = m_impl;
1472 return i;
1473 }
1474
1475 typename HashTableType::iterator m_impl;
1476 };
1477
1478 template<typename T, typename U>
1479 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1480 {
1481 return a.m_impl == b.m_impl;
1482 }
1483
1484 template<typename T, typename U>
1485 inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1486 {
1487 return a.m_impl != b.m_impl;
1488 }
1489
1490 template<typename T, typename U>
1491 inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1492 {
1493 return a.m_impl == b.m_impl;
1494 }
1495
1496 template<typename T, typename U>
1497 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1498 {
1499 return a.m_impl != b.m_impl;
1500 }
1501
1502 // All 4 combinations of ==, != and Const,non const.
1503 template<typename T, typename U>
1504 inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1505 {
1506 return a.m_impl == b.m_impl;
1507 }
1508
1509 template<typename T, typename U>
1510 inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1511 {
1512 return a.m_impl != b.m_impl;
1513 }
1514
1515 template<typename T, typename U>
1516 inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1517 {
1518 return a.m_impl == b.m_impl;
1519 }
1520
1521 template<typename T, typename U>
1522 inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1523 {
1524 return a.m_impl != b.m_impl;
1525 }
1526
1527} // namespace WTF
1528
1529#include <wtf/HashIterators.h>
1530
1531#endif // WTF_HashTable_h
1532