• Skip to content
  • Skip to link menu
  • KDE API Reference
  • kdelibs-4.14.38 API Reference
  • KDE Home
  • Contact Us
 

WTF

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

KDE's Doxygen guidelines are available online.

WTF

Skip menu "WTF"
  • Main Page
  • Namespace List
  • Namespace Members
  • Alphabetical List
  • Class List
  • Class Hierarchy
  • Class Members
  • File List
  • File Members
  • Related Pages

kdelibs-4.14.38 API Reference

Skip menu "kdelibs-4.14.38 API Reference"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDEWebKit
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • KPty
  • Kross
  • KUnitConversion
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Report problems with this website to our bug tracking system.
Contact the specific authors with questions and comments about the page contents.

KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal