Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(225)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: Source/WTF/wtf/HashTable.h

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

Powered by Google App Engine
This is Rietveld 408576698