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