source: webkit/trunk/JavaScriptCore/wtf/HashTable.h@ 27402

Last change on this file since 27402 was 27359, checked in by ggaren, 18 years ago

JavaScriptCore:

Reviewed by Maciej Stachowiak.

Fixed ​http://bugs.webkit.org/show_bug.cgi?id=15785
REGRESSION(r27344): Crash on load at finance.yahoo.com


Reverted a small portion of my last check-in. (The speedup and the List
removal are still there, though.)


ActivationImp needs to hold a pointer to its function, and mark that
pointer (rather than accessing its function through its ExecState, and
counting on the active scope to mark its function) because a closure
can cause an ActivationImp to outlive its ExecState along with any
active scope.

  • kjs/ExecState.cpp: (KJS::ExecState::ExecState):
  • kjs/function.cpp: (KJS::FunctionImp::~FunctionImp): (KJS::ActivationImp::ActivationImp):
  • kjs/function.h: (KJS::ActivationImp::ActivationImpPrivate::ActivationImpPrivate):

Also made HashTable a little more crash-happy in debug builds, so
problems like this will show up earlier:


  • wtf/HashTable.h: (WTF::HashTable::~HashTable):

LayoutTests:

Reviewed by Maciej Stachowiak.


Layout test for ​http://bugs.webkit.org/show_bug.cgi?id=15785
REGRESSION(r27344): Crash on load at finance.yahoo.com

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