• Skip to content
  • Skip to link menu
  • KDE API Reference
  • kdelibs-4.10.5 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 
29 namespace 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  iterator begin() { return makeIterator(m_table); }
296  iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
297  const_iterator begin() const { return makeConstIterator(m_table); }
298  const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
299 
300  int size() const { return m_keyCount; }
301  int capacity() const { return m_tableSize; }
302  bool isEmpty() const { return !m_keyCount; }
303 
304  pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }
305 
306  // A special version of add() that finds the object by hashing and comparing
307  // with some other type, to avoid the cost of type conversion if the object is already
308  // in the table.
309  template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&);
310  template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> addPassingHashCode(const T& key, const Extra&);
311 
312  iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); }
313  const_iterator find(const KeyType& key) const { return find<KeyType, IdentityTranslatorType>(key); }
314  bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); }
315 
316  template <typename T, typename HashTranslator> iterator find(const T&);
317  template <typename T, typename HashTranslator> const_iterator find(const T&) const;
318  template <typename T, typename HashTranslator> bool contains(const T&) const;
319 
320  void remove(const KeyType&);
321  void remove(iterator);
322  void removeWithoutEntryConsistencyCheck(iterator);
323  void clear();
324 
325  static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); }
326  static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
327  static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
328 
329  ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); }
330  template<typename T, typename HashTranslator> ValueType* lookup(const T&);
331 
332 #if CHECK_HASHTABLE_CONSISTENCY
333  void checkTableConsistency() const;
334 #else
335  static void checkTableConsistency() { }
336 #endif
337 
338  private:
339  static ValueType* allocateTable(int size);
340  static void deallocateTable(ValueType* table, int size);
341 
342  typedef pair<ValueType*, bool> LookupType;
343  typedef pair<LookupType, unsigned> FullLookupType;
344 
345  LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); };
346  template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&);
347  template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&);
348 
349  template<typename T, typename HashTranslator> void checkKey(const T&);
350 
351  void removeAndInvalidateWithoutEntryConsistencyCheck(ValueType*);
352  void removeAndInvalidate(ValueType*);
353  void remove(ValueType*);
354 
355  bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
356  bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
357  bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; }
358  void expand();
359  void shrink() { rehash(m_tableSize / 2); }
360 
361  void rehash(int newTableSize);
362  void reinsert(ValueType&);
363 
364  static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }
365  static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(&bucket); }
366 
367  FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
368  { return FullLookupType(LookupType(position, found), hash); }
369 
370  iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
371  const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
372  iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
373  const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
374 
375 #if CHECK_HASHTABLE_CONSISTENCY
376  void checkTableConsistencyExceptSize() const;
377 #else
378  static void checkTableConsistencyExceptSize() { }
379 #endif
380 
381 #if CHECK_HASHTABLE_ITERATORS
382  void invalidateIterators();
383 #else
384  static void invalidateIterators() { }
385 #endif
386 
387  static const int m_minTableSize = 64;
388  static const int m_maxLoad = 2;
389  static const int m_minLoad = 6;
390 
391  ValueType* m_table;
392  int m_tableSize;
393  int m_tableSizeMask;
394  int m_keyCount;
395  int m_deletedCount;
396 
397 #if CHECK_HASHTABLE_ITERATORS
398  public:
399  mutable const_iterator* m_iterators;
400 #endif
401  };
402 
403  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
404  inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
405  : m_table(0)
406  , m_tableSize(0)
407  , m_tableSizeMask(0)
408  , m_keyCount(0)
409  , m_deletedCount(0)
410 #if CHECK_HASHTABLE_ITERATORS
411  , m_iterators(0)
412 #endif
413  {
414  }
415 
416  static inline unsigned doubleHash(unsigned key)
417  {
418  key = ~key + (key >> 23);
419  key ^= (key << 12);
420  key ^= (key >> 7);
421  key ^= (key << 2);
422  key ^= (key >> 20);
423  return key;
424  }
425 
426 #if ASSERT_DISABLED
427 
428  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
429  template<typename T, typename HashTranslator>
430  inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
431  {
432  }
433 
434 #else
435 
436  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
437  template<typename T, typename HashTranslator>
438  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)
439  {
440  if (!HashFunctions::safeToCompareToEmptyOrDeleted)
441  return;
442  ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
443  ValueType deletedValue = Traits::emptyValue();
444  deletedValue.~ValueType();
445  Traits::constructDeletedValue(&deletedValue);
446  ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
447  new (&deletedValue) ValueType(Traits::emptyValue());
448  }
449 
450 #endif
451 
452  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
453  template<typename T, typename HashTranslator>
454  inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
455  {
456  checkKey<T, HashTranslator>(key);
457 
458  int k = 0;
459  int sizeMask = m_tableSizeMask;
460  ValueType* table = m_table;
461  unsigned h = HashTranslator::hash(key);
462  int i = h & sizeMask;
463 
464  if (!table)
465  return 0;
466 
467 #if DUMP_HASHTABLE_STATS
468  ++HashTableStats::numAccesses;
469  int probeCount = 0;
470 #endif
471 
472  while (1) {
473  ValueType* entry = table + i;
474 
475  // we count on the compiler to optimize out this branch
476  if (HashFunctions::safeToCompareToEmptyOrDeleted) {
477  if (HashTranslator::equal(Extractor::extract(*entry), key))
478  return entry;
479 
480  if (isEmptyBucket(*entry))
481  return 0;
482  } else {
483  if (isEmptyBucket(*entry))
484  return 0;
485 
486  if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
487  return entry;
488  }
489 #if DUMP_HASHTABLE_STATS
490  ++probeCount;
491  HashTableStats::recordCollisionAtCount(probeCount);
492 #endif
493  if (k == 0)
494  k = 1 | doubleHash(h);
495  i = (i + k) & sizeMask;
496  }
497  }
498 
499  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
500  template<typename T, typename HashTranslator>
501  inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key)
502  {
503  ASSERT(m_table);
504  checkKey<T, HashTranslator>(key);
505 
506  int k = 0;
507  ValueType* table = m_table;
508  int sizeMask = m_tableSizeMask;
509  unsigned h = HashTranslator::hash(key);
510  int i = h & sizeMask;
511 
512 #if DUMP_HASHTABLE_STATS
513  ++HashTableStats::numAccesses;
514  int probeCount = 0;
515 #endif
516 
517  ValueType* deletedEntry = 0;
518 
519  while (1) {
520  ValueType* entry = table + i;
521 
522  // we count on the compiler to optimize out this branch
523  if (HashFunctions::safeToCompareToEmptyOrDeleted) {
524  if (isEmptyBucket(*entry))
525  return LookupType(deletedEntry ? deletedEntry : entry, false);
526 
527  if (HashTranslator::equal(Extractor::extract(*entry), key))
528  return LookupType(entry, true);
529 
530  if (isDeletedBucket(*entry))
531  deletedEntry = entry;
532  } else {
533  if (isEmptyBucket(*entry))
534  return LookupType(deletedEntry ? deletedEntry : entry, false);
535 
536  if (isDeletedBucket(*entry))
537  deletedEntry = entry;
538  else if (HashTranslator::equal(Extractor::extract(*entry), key))
539  return LookupType(entry, true);
540  }
541 #if DUMP_HASHTABLE_STATS
542  ++probeCount;
543  HashTableStats::recordCollisionAtCount(probeCount);
544 #endif
545  if (k == 0)
546  k = 1 | doubleHash(h);
547  i = (i + k) & sizeMask;
548  }
549  }
550 
551  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
552  template<typename T, typename HashTranslator>
553  inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key)
554  {
555  ASSERT(m_table);
556  checkKey<T, HashTranslator>(key);
557 
558  int k = 0;
559  ValueType* table = m_table;
560  int sizeMask = m_tableSizeMask;
561  unsigned h = HashTranslator::hash(key);
562  int i = h & sizeMask;
563 
564 #if DUMP_HASHTABLE_STATS
565  ++HashTableStats::numAccesses;
566  int probeCount = 0;
567 #endif
568 
569  ValueType* deletedEntry = 0;
570 
571  while (1) {
572  ValueType* entry = table + i;
573 
574  // we count on the compiler to optimize out this branch
575  if (HashFunctions::safeToCompareToEmptyOrDeleted) {
576  if (isEmptyBucket(*entry))
577  return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
578 
579  if (HashTranslator::equal(Extractor::extract(*entry), key))
580  return makeLookupResult(entry, true, h);
581 
582  if (isDeletedBucket(*entry))
583  deletedEntry = entry;
584  } else {
585  if (isEmptyBucket(*entry))
586  return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
587 
588  if (isDeletedBucket(*entry))
589  deletedEntry = entry;
590  else if (HashTranslator::equal(Extractor::extract(*entry), key))
591  return makeLookupResult(entry, true, h);
592  }
593 #if DUMP_HASHTABLE_STATS
594  ++probeCount;
595  HashTableStats::recordCollisionAtCount(probeCount);
596 #endif
597  if (k == 0)
598  k = 1 | doubleHash(h);
599  i = (i + k) & sizeMask;
600  }
601  }
602 
603  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
604  template<typename T, typename Extra, typename HashTranslator>
605  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)
606  {
607  checkKey<T, HashTranslator>(key);
608 
609  invalidateIterators();
610 
611  if (!m_table)
612  expand();
613 
614  checkTableConsistency();
615 
616  ASSERT(m_table);
617 
618  int k = 0;
619  ValueType* table = m_table;
620  int sizeMask = m_tableSizeMask;
621  unsigned h = HashTranslator::hash(key);
622  int i = h & sizeMask;
623 
624 #if DUMP_HASHTABLE_STATS
625  ++HashTableStats::numAccesses;
626  int probeCount = 0;
627 #endif
628 
629  ValueType* deletedEntry = 0;
630  ValueType* entry;
631  while (1) {
632  entry = table + i;
633 
634  // we count on the compiler to optimize out this branch
635  if (HashFunctions::safeToCompareToEmptyOrDeleted) {
636  if (isEmptyBucket(*entry))
637  break;
638 
639  if (HashTranslator::equal(Extractor::extract(*entry), key))
640  return std::make_pair(makeKnownGoodIterator(entry), false);
641 
642  if (isDeletedBucket(*entry))
643  deletedEntry = entry;
644  } else {
645  if (isEmptyBucket(*entry))
646  break;
647 
648  if (isDeletedBucket(*entry))
649  deletedEntry = entry;
650  else if (HashTranslator::equal(Extractor::extract(*entry), key))
651  return std::make_pair(makeKnownGoodIterator(entry), false);
652  }
653 #if DUMP_HASHTABLE_STATS
654  ++probeCount;
655  HashTableStats::recordCollisionAtCount(probeCount);
656 #endif
657  if (k == 0)
658  k = 1 | doubleHash(h);
659  i = (i + k) & sizeMask;
660  }
661 
662  if (deletedEntry) {
663  initializeBucket(*deletedEntry);
664  entry = deletedEntry;
665  --m_deletedCount;
666  }
667 
668  HashTranslator::translate(*entry, key, extra);
669 
670  ++m_keyCount;
671 
672  if (shouldExpand()) {
673  // FIXME: This makes an extra copy on expand. Probably not that bad since
674  // expand is rare, but would be better to have a version of expand that can
675  // follow a pivot entry and return the new position.
676  KeyType enteredKey = Extractor::extract(*entry);
677  expand();
678  return std::make_pair(find(enteredKey), true);
679  }
680 
681  checkTableConsistency();
682 
683  return std::make_pair(makeKnownGoodIterator(entry), true);
684  }
685 
686  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
687  template<typename T, typename Extra, typename HashTranslator>
688  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)
689  {
690  checkKey<T, HashTranslator>(key);
691 
692  invalidateIterators();
693 
694  if (!m_table)
695  expand();
696 
697  checkTableConsistency();
698 
699  FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key);
700 
701  ValueType* entry = lookupResult.first.first;
702  bool found = lookupResult.first.second;
703  unsigned h = lookupResult.second;
704 
705  if (found)
706  return std::make_pair(makeKnownGoodIterator(entry), false);
707 
708  if (isDeletedBucket(*entry)) {
709  initializeBucket(*entry);
710  --m_deletedCount;
711  }
712 
713  HashTranslator::translate(*entry, key, extra, h);
714  ++m_keyCount;
715  if (shouldExpand()) {
716  // FIXME: This makes an extra copy on expand. Probably not that bad since
717  // expand is rare, but would be better to have a version of expand that can
718  // follow a pivot entry and return the new position.
719  KeyType enteredKey = Extractor::extract(*entry);
720  expand();
721  return std::make_pair(find(enteredKey), true);
722  }
723 
724  checkTableConsistency();
725 
726  return std::make_pair(makeKnownGoodIterator(entry), true);
727  }
728 
729  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
730  inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)
731  {
732  ASSERT(m_table);
733  ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
734  ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
735 #if DUMP_HASHTABLE_STATS
736  ++HashTableStats::numReinserts;
737 #endif
738 
739  Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first);
740  }
741 
742  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
743  template <typename T, typename HashTranslator>
744  typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key)
745  {
746  if (!m_table)
747  return end();
748 
749  ValueType* entry = lookup<T, HashTranslator>(key);
750  if (!entry)
751  return end();
752 
753  return makeKnownGoodIterator(entry);
754  }
755 
756  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
757  template <typename T, typename HashTranslator>
758  typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const
759  {
760  if (!m_table)
761  return end();
762 
763  ValueType* entry = const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);
764  if (!entry)
765  return end();
766 
767  return makeKnownGoodConstIterator(entry);
768  }
769 
770  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
771  template <typename T, typename HashTranslator>
772  bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const
773  {
774  if (!m_table)
775  return false;
776 
777  return const_cast<HashTable*>(this)->lookup<T, HashTranslator>(key);
778  }
779 
780  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
781  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidateWithoutEntryConsistencyCheck(ValueType* pos)
782  {
783  invalidateIterators();
784  remove(pos);
785  }
786 
787  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
788  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeAndInvalidate(ValueType* pos)
789  {
790  invalidateIterators();
791  checkTableConsistency();
792  remove(pos);
793  }
794 
795  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
796  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
797  {
798 #if DUMP_HASHTABLE_STATS
799  ++HashTableStats::numRemoves;
800 #endif
801 
802  deleteBucket(*pos);
803  ++m_deletedCount;
804  --m_keyCount;
805 
806  if (shouldShrink())
807  shrink();
808 
809  checkTableConsistency();
810  }
811 
812  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
813  inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
814  {
815  if (it == end())
816  return;
817 
818  removeAndInvalidate(const_cast<ValueType*>(it.m_iterator.m_position));
819  }
820 
821  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
822  inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeWithoutEntryConsistencyCheck(iterator it)
823  {
824  if (it == end())
825  return;
826 
827  removeAndInvalidateWithoutEntryConsistencyCheck(const_cast<ValueType*>(it.m_iterator.m_position));
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(const KeyType& key)
832  {
833  remove(find(key));
834  }
835 
836  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
837  Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
838  {
839  // would use a template member function with explicit specializations here, but
840  // gcc doesn't appear to support that
841  if (Traits::emptyValueIsZero)
842  return static_cast<ValueType*>(fastZeroedMalloc(size * sizeof(ValueType)));
843  ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
844  for (int i = 0; i < size; i++)
845  initializeBucket(result[i]);
846  return result;
847  }
848 
849  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
850  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType* table, int size)
851  {
852  if (Traits::needsDestruction) {
853  for (int i = 0; i < size; ++i) {
854  if (!isDeletedBucket(table[i]))
855  table[i].~ValueType();
856  }
857  }
858  fastFree(table);
859  }
860 
861  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
862  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
863  {
864  int newSize;
865  if (m_tableSize == 0)
866  newSize = m_minTableSize;
867  else if (mustRehashInPlace())
868  newSize = m_tableSize;
869  else
870  newSize = m_tableSize * 2;
871 
872  rehash(newSize);
873  }
874 
875  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
876  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize)
877  {
878  checkTableConsistencyExceptSize();
879 
880  int oldTableSize = m_tableSize;
881  ValueType* oldTable = m_table;
882 
883 #if DUMP_HASHTABLE_STATS
884  if (oldTableSize != 0)
885  ++HashTableStats::numRehashes;
886 #endif
887 
888  m_tableSize = newTableSize;
889  m_tableSizeMask = newTableSize - 1;
890  m_table = allocateTable(newTableSize);
891 
892  for (int i = 0; i != oldTableSize; ++i)
893  if (!isEmptyOrDeletedBucket(oldTable[i]))
894  reinsert(oldTable[i]);
895 
896  m_deletedCount = 0;
897 
898  deallocateTable(oldTable, oldTableSize);
899 
900  checkTableConsistency();
901  }
902 
903  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
904  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
905  {
906  invalidateIterators();
907  deallocateTable(m_table, m_tableSize);
908  m_table = 0;
909  m_tableSize = 0;
910  m_tableSizeMask = 0;
911  m_keyCount = 0;
912  }
913 
914  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
915  HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
916  : m_table(0)
917  , m_tableSize(0)
918  , m_tableSizeMask(0)
919  , m_keyCount(0)
920  , m_deletedCount(0)
921 #if CHECK_HASHTABLE_ITERATORS
922  , m_iterators(0)
923 #endif
924  {
925  // Copy the hash table the dumb way, by adding each element to the new table.
926  // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
927  const_iterator end = other.end();
928  for (const_iterator it = other.begin(); it != end; ++it)
929  add(*it);
930  }
931 
932  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
933  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
934  {
935  invalidateIterators();
936  other.invalidateIterators();
937 
938  ValueType* tmp_table = m_table;
939  m_table = other.m_table;
940  other.m_table = tmp_table;
941 
942  int tmp_tableSize = m_tableSize;
943  m_tableSize = other.m_tableSize;
944  other.m_tableSize = tmp_tableSize;
945 
946  int tmp_tableSizeMask = m_tableSizeMask;
947  m_tableSizeMask = other.m_tableSizeMask;
948  other.m_tableSizeMask = tmp_tableSizeMask;
949 
950  int tmp_keyCount = m_keyCount;
951  m_keyCount = other.m_keyCount;
952  other.m_keyCount = tmp_keyCount;
953 
954  int tmp_deletedCount = m_deletedCount;
955  m_deletedCount = other.m_deletedCount;
956  other.m_deletedCount = tmp_deletedCount;
957  }
958 
959  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
960  HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)
961  {
962  HashTable tmp(other);
963  swap(tmp);
964  return *this;
965  }
966 
967 #if CHECK_HASHTABLE_CONSISTENCY
968 
969  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
970  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
971  {
972  checkTableConsistencyExceptSize();
973  ASSERT(!shouldExpand());
974  ASSERT(!shouldShrink());
975  }
976 
977  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
978  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
979  {
980  if (!m_table)
981  return;
982 
983  int count = 0;
984  int deletedCount = 0;
985  for (int j = 0; j < m_tableSize; ++j) {
986  ValueType* entry = m_table + j;
987  if (isEmptyBucket(*entry))
988  continue;
989 
990  if (isDeletedBucket(*entry)) {
991  ++deletedCount;
992  continue;
993  }
994 
995  const_iterator it = find(Extractor::extract(*entry));
996  ASSERT(entry == it.m_position);
997  ++count;
998  }
999 
1000  ASSERT(count == m_keyCount);
1001  ASSERT(deletedCount == m_deletedCount);
1002  ASSERT(m_tableSize >= m_minTableSize);
1003  ASSERT(m_tableSizeMask);
1004  ASSERT(m_tableSize == m_tableSizeMask + 1);
1005  }
1006 
1007 #endif // CHECK_HASHTABLE_CONSISTENCY
1008 
1009 #if CHECK_HASHTABLE_ITERATORS
1010 
1011  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1012  void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
1013  {
1014  const_iterator* next;
1015  for (const_iterator* p = m_iterators; p; p = next) {
1016  next = p->m_next;
1017  p->m_table = 0;
1018  p->m_next = 0;
1019  p->m_previous = 0;
1020  }
1021  m_iterators = 0;
1022  }
1023 
1024  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1025  void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
1026  HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1027  {
1028  it->m_table = table;
1029  it->m_previous = 0;
1030 
1031  // Insert iterator at head of doubly-linked list of iterators.
1032  if (!table) {
1033  it->m_next = 0;
1034  } else {
1035  ASSERT(table->m_iterators != it);
1036  it->m_next = table->m_iterators;
1037  table->m_iterators = it;
1038  if (it->m_next) {
1039  ASSERT(!it->m_next->m_previous);
1040  it->m_next->m_previous = it;
1041  }
1042  }
1043  }
1044 
1045  template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
1046  void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
1047  {
1048  typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
1049  typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
1050 
1051  // Delete iterator from doubly-linked list of iterators.
1052  if (!it->m_table) {
1053  ASSERT(!it->m_next);
1054  ASSERT(!it->m_previous);
1055  } else {
1056  if (it->m_next) {
1057  ASSERT(it->m_next->m_previous == it);
1058  it->m_next->m_previous = it->m_previous;
1059  }
1060  if (it->m_previous) {
1061  ASSERT(it->m_table->m_iterators != it);
1062  ASSERT(it->m_previous->m_next == it);
1063  it->m_previous->m_next = it->m_next;
1064  } else {
1065  ASSERT(it->m_table->m_iterators == it);
1066  it->m_table->m_iterators = it->m_next;
1067  }
1068  }
1069 
1070  it->m_table = 0;
1071  it->m_next = 0;
1072  it->m_previous = 0;
1073  }
1074 
1075 #endif // CHECK_HASHTABLE_ITERATORS
1076 
1077  // iterator adapters
1078 
1079  template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
1080  HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
1081 
1082  const ValueType* get() const { return (const ValueType*)m_impl.get(); }
1083  const ValueType& operator*() const { return *get(); }
1084  const ValueType* operator->() const { return get(); }
1085 
1086  HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
1087  // postfix ++ intentionally omitted
1088 
1089  typename HashTableType::const_iterator m_impl;
1090  };
1091 
1092  template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
1093  HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
1094 
1095  ValueType* get() const { return (ValueType*)m_impl.get(); }
1096  ValueType& operator*() const { return *get(); }
1097  ValueType* operator->() const { return get(); }
1098 
1099  HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
1100  // postfix ++ intentionally omitted
1101 
1102  operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
1103  typename HashTableType::const_iterator i = m_impl;
1104  return i;
1105  }
1106 
1107  typename HashTableType::iterator m_impl;
1108  };
1109 
1110  template<typename T, typename U>
1111  inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1112  {
1113  return a.m_impl == b.m_impl;
1114  }
1115 
1116  template<typename T, typename U>
1117  inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1118  {
1119  return a.m_impl != b.m_impl;
1120  }
1121 
1122  template<typename T, typename U>
1123  inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1124  {
1125  return a.m_impl == b.m_impl;
1126  }
1127 
1128  template<typename T, typename U>
1129  inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1130  {
1131  return a.m_impl != b.m_impl;
1132  }
1133 
1134 } // namespace WTF
1135 
1136 #include "HashIterators.h"
1137 
1138 #endif // WTF_HashTable_h
WTF::HashTable::contains
bool contains(const KeyType &key) const
Definition: HashTable.h:314
WTF::HashTable::begin
const_iterator begin() const
Definition: HashTable.h:297
WTF::HashTable::add
pair< iterator, bool > add(const ValueType &value)
Definition: HashTable.h:304
WTF::HashTable::size
int size() const
Definition: HashTable.h:300
WTF::HashTableIterator::operator*
ReferenceType operator*() const
Definition: HashTable.h:229
WTF::removeIterator
void removeIterator(HashTableConstIterator< Key, Value, Extractor, HashFunctions, Traits, KeyTraits > *)
Definition: HashTable.h:76
WTF::HashItemKnownGoodTag
HashItemKnownGoodTag
Definition: HashTable.h:80
CHECK_HASHTABLE_ITERATORS
#define CHECK_HASHTABLE_ITERATORS
Definition: HashTable.h:36
WTF::HashTableConstIterator::HashTableConstIterator
HashTableConstIterator()
Definition: HashTable.h:115
WTF::HashTable::clear
void clear()
Definition: HashTable.h:904
WTF::HashTableConstIteratorAdapter::operator++
HashTableConstIteratorAdapter & operator++()
Definition: HashTable.h:1086
WTF::IdentityHashTranslator
Definition: HashTable.h:264
WTF::HashTableConstIterator::HashTableIterator< Key, Value, Extractor, HashFunctions, Traits, KeyTraits >
friend class HashTableIterator< Key, Value, Extractor, HashFunctions, Traits, KeyTraits >
Definition: HashTable.h:93
HashTraits.h
WTF::HashTableConstIteratorAdapter
Definition: HashTable.h:1079
WTF::HashTableConstIterator::operator->
PointerType operator->() const
Definition: HashTable.h:152
WTF::HashTable::IdentityTranslatorType
IdentityHashTranslator< Key, Value, HashFunctions > IdentityTranslatorType
Definition: HashTable.h:279
WTF::HashItemKnownGood
Definition: HashTable.h:80
WTF::swap
void swap(OwnArrayPtr< T > &a, OwnArrayPtr< T > &b)
Definition: OwnArrayPtr.h:61
WTF::HashTable::ValueType
Value ValueType
Definition: HashTable.h:278
WTF::HashTable::checkTableConsistency
static void checkTableConsistency()
Definition: HashTable.h:335
WTF::HashTableIterator::operator++
iterator & operator++()
Definition: HashTable.h:232
WTF::HashTable::~HashTable
~HashTable()
Definition: HashTable.h:282
WTF::HashTable::HashTable
HashTable()
Definition: HashTable.h:404
Assertions.h
WTF::HashTableIteratorAdapter::operator*
ValueType & operator*() const
Definition: HashTable.h:1096
WTF::HashTableIterator::HashTable< Key, Value, Extractor, HashFunctions, Traits, KeyTraits >
friend class HashTable< Key, Value, Extractor, HashFunctions, Traits, KeyTraits >
Definition: HashTable.h:218
WTF::HashTableConstIterator::operator==
bool operator==(const const_iterator &other) const
Definition: HashTable.h:166
WTF::fastFree
void fastFree(void *p)
Definition: FastMalloc.h:44
WTF::HashTable::isEmptyOrDeletedBucket
static bool isEmptyOrDeletedBucket(const ValueType &value)
Definition: HashTable.h:327
WTF::HashTable::capacity
int capacity() const
Definition: HashTable.h:301
WTF::IdentityHashTranslator::translate
static void translate(Value &location, const Key &, const Value &value)
Definition: HashTable.h:268
WTF::HashTable::ValueTraits
Traits ValueTraits
Definition: HashTable.h:276
WTF::HashTableConstIteratorAdapter::m_impl
HashTableType::const_iterator m_impl
Definition: HashTable.h:1089
WTF::HashTable::KeyType
Key KeyType
Definition: HashTable.h:277
WTF::HashTable::swap
void swap(HashTable &)
Definition: HashTable.h:933
WTF::HashTableIterator::operator->
PointerType operator->() const
Definition: HashTable.h:230
WTF::HashTable::find
const_iterator find(const KeyType &key) const
Definition: HashTable.h:313
WTF::HashTable::find
iterator find(const KeyType &key)
Definition: HashTable.h:312
WTF::HashTableIteratorAdapter::operator->
ValueType * operator->() const
Definition: HashTable.h:1097
WTF::HashTable::addPassingHashCode
pair< iterator, bool > addPassingHashCode(const T &key, const Extra &)
WTF::HashTable::remove
void remove(const KeyType &)
Definition: HashTable.h:831
WTF::HashTableIterator::operator!=
bool operator!=(const iterator &other) const
Definition: HashTable.h:238
WTF::HashTableConstIterator
Definition: HashTable.h:60
WTF::HashTableConstIterator::HashTable< Key, Value, Extractor, HashFunctions, Traits, KeyTraits >
friend class HashTable< Key, Value, Extractor, HashFunctions, Traits, KeyTraits >
Definition: HashTable.h:92
WTF::HashTableIterator::HashTableIterator
HashTableIterator()
Definition: HashTable.h:224
WTF::HashTableConstIterator::operator*
ReferenceType operator*() const
Definition: HashTable.h:151
WTF::HashTableIterator::operator==
bool operator==(const iterator &other) const
Definition: HashTable.h:237
WTF::operator==
bool operator==(const HashTableConstKeysIterator< T, U, V > &a, const HashTableConstKeysIterator< T, U, V > &b)
Definition: HashIterators.h:167
WTF::HashTable::removeWithoutEntryConsistencyCheck
void removeWithoutEntryConsistencyCheck(iterator)
Definition: HashTable.h:822
WTF::HashTable::isEmptyBucket
static bool isEmptyBucket(const ValueType &value)
Definition: HashTable.h:325
WTF::fastMalloc
void * fastMalloc(size_t n)
Definition: FastMalloc.h:36
WTF::Mover
Definition: HashTable.h:260
WTF::Mover< T, false >::move
static void move(T &from, T &to)
Definition: HashTable.h:262
WTF::HashTable::operator=
HashTable & operator=(const HashTable &)
Definition: HashTable.h:960
WTF::fastZeroedMalloc
void * fastZeroedMalloc(size_t n)
Definition: FastMalloc.h:48
WTF::HashTable::lookup
ValueType * lookup(const Key &key)
Definition: HashTable.h:329
WTF::Mover< T, true >::move
static void move(T &from, T &to)
Definition: HashTable.h:261
WTF::HashTableIteratorAdapter
Definition: HashTable.h:1092
WTF::HashTableIterator
Definition: HashTable.h:58
FastMalloc.h
WTF::HashTableIteratorAdapter::HashTableIteratorAdapter
HashTableIteratorAdapter(const typename HashTableType::iterator &impl)
Definition: HashTable.h:1093
WTF::doubleHash
static unsigned doubleHash(unsigned key)
Definition: HashTable.h:416
WTF::addIterator
void addIterator(const HashTable< Key, Value, Extractor, HashFunctions, Traits, KeyTraits > *, HashTableConstIterator< Key, Value, Extractor, HashFunctions, Traits, KeyTraits > *)
Definition: HashTable.h:72
WTF::HashTable::isDeletedBucket
static bool isDeletedBucket(const ValueType &value)
Definition: HashTable.h:326
WTF::HashTable::end
iterator end()
Definition: HashTable.h:296
WTF::HashTableIteratorAdapter::operator++
HashTableIteratorAdapter & operator++()
Definition: HashTable.h:1099
WTF::operator!=
bool operator!=(const HashTableConstKeysIterator< T, U, V > &a, const HashTableConstKeysIterator< T, U, V > &b)
Definition: HashIterators.h:173
WTF::HashTable
Definition: HashTable.h:56
WTF::HashTableConstIterator::operator!=
bool operator!=(const const_iterator &other) const
Definition: HashTable.h:171
WTF::hashTableSwap
void hashTableSwap(T &a, T &b)
Definition: HashTable.h:249
WTF::HashTableConstIterator::operator++
const_iterator & operator++()
Definition: HashTable.h:154
WTF::HashTableIteratorAdapter::m_impl
HashTableType::iterator m_impl
Definition: HashTable.h:1107
WTF::HashTable::end
const_iterator end() const
Definition: HashTable.h:298
WTF::HashTable::isEmpty
bool isEmpty() const
Definition: HashTable.h:302
WTF::HashTable::begin
iterator begin()
Definition: HashTable.h:295
WTF::IdentityHashTranslator::equal
static bool equal(const Key &a, const Key &b)
Definition: HashTable.h:267
ASSERT
#define ASSERT(x)
Definition: Assertions.h:33
WTF::HashTableConstIteratorAdapter::operator*
const ValueType & operator*() const
Definition: HashTable.h:1083
HashIterators.h
WTF::HashTableConstIteratorAdapter::HashTableConstIteratorAdapter
HashTableConstIteratorAdapter(const typename HashTableType::const_iterator &impl)
Definition: HashTable.h:1080
WTF::HashTableConstIteratorAdapter::operator->
const ValueType * operator->() const
Definition: HashTable.h:1084
WTF::IdentityHashTranslator::hash
static unsigned hash(const Key &key)
Definition: HashTable.h:266
This file is part of the KDE documentation.
Documentation copyright © 1996-2014 The KDE developers.
Generated on Tue Jun 17 2014 17:08:07 by doxygen 1.8.5 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.10.5 API Reference

Skip menu "kdelibs-4.10.5 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