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

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