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

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/wtf/HashTable.h