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 | |
30 | namespace 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& ) |
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& ) |
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 | |