1/*
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
3 * Copyright (C) 2008 David Levin <levin@chromium.org>
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU * Library General Public License for more details.
12 *
13 * You should have received a copy of the GNU Library General Public License
14 * along with this library; see the file COPYING.LIB.  If not, write to
15 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
16 * Boston, MA 02110-1301, USA.
17 *
18 */
19
20#ifndef WTF_HashTable_h
21#define WTF_HashTable_h
22
23#include "wtf/Alignment.h"
24#include "wtf/Assertions.h"
25#include "wtf/DefaultAllocator.h"
26#include "wtf/HashTraits.h"
27#include "wtf/WTF.h"
28
29#define DUMP_HASHTABLE_STATS 0
30#define DUMP_HASHTABLE_STATS_PER_TABLE 0
31
32#if DUMP_HASHTABLE_STATS_PER_TABLE
33#include "wtf/DataLog.h"
34#endif
35
36#if DUMP_HASHTABLE_STATS
37#if DUMP_HASHTABLE_STATS_PER_TABLE
38#define UPDATE_PROBE_COUNTS()                            \
39    ++probeCount;                                        \
40    HashTableStats::recordCollisionAtCount(probeCount);  \
41    ++perTableProbeCount;                                \
42    m_stats->recordCollisionAtCount(perTableProbeCount)
43#define UPDATE_ACCESS_COUNTS()                           \
44    atomicIncrement(&HashTableStats::numAccesses);       \
45    int probeCount = 0;                                  \
46    ++m_stats->numAccesses;                              \
47    int perTableProbeCount = 0
48#else
49#define UPDATE_PROBE_COUNTS()                            \
50    ++probeCount;                                        \
51    HashTableStats::recordCollisionAtCount(probeCount)
52#define UPDATE_ACCESS_COUNTS()                           \
53    atomicIncrement(&HashTableStats::numAccesses);       \
54    int probeCount = 0
55#endif
56#else
57#if DUMP_HASHTABLE_STATS_PER_TABLE
58#define UPDATE_PROBE_COUNTS()                            \
59    ++perTableProbeCount;                                \
60    m_stats->recordCollisionAtCount(perTableProbeCount)
61#define UPDATE_ACCESS_COUNTS()                           \
62    ++m_stats->numAccesses;                              \
63    int perTableProbeCount = 0
64#else
65#define UPDATE_PROBE_COUNTS() do { } while (0)
66#define UPDATE_ACCESS_COUNTS() do { } while (0)
67#endif
68#endif
69
70namespace WTF {
71
72#if DUMP_HASHTABLE_STATS
73
74    struct HashTableStats {
75        // The following variables are all atomically incremented when modified.
76        static int numAccesses;
77        static int numRehashes;
78        static int numRemoves;
79        static int numReinserts;
80
81        // The following variables are only modified in the recordCollisionAtCount method within a mutex.
82        static int maxCollisions;
83        static int numCollisions;
84        static int collisionGraph[4096];
85
86        static void recordCollisionAtCount(int count);
87        static void dumpStats();
88    };
89
90#endif
91
92    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
93    class HashTable;
94    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
95    class HashTableIterator;
96    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
97    class HashTableConstIterator;
98    template<typename Value, typename HashFunctions, typename HashTraits, typename Allocator>
99    class LinkedHashSet;
100    template<WeakHandlingFlag x, typename T, typename U, typename V, typename W, typename X, typename Y, typename Z>
101    struct WeakProcessingHashTableHelper;
102
103    typedef enum { HashItemKnownGood } HashItemKnownGoodTag;
104
105    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
106    class HashTableConstIterator {
107    private:
108        typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> HashTableType;
109        typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
110        typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> const_iterator;
111        typedef Value ValueType;
112        typedef typename Traits::IteratorConstGetType GetType;
113        typedef const ValueType* PointerType;
114
115        friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
116        friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
117
118        void skipEmptyBuckets()
119        {
120            while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position))
121                ++m_position;
122        }
123
124        HashTableConstIterator(PointerType position, PointerType endPosition, const HashTableType* container)
125            : m_position(position)
126            , m_endPosition(endPosition)
127#ifdef ASSERT_ENABLED
128            , m_container(container)
129            , m_containerModifications(container->modifications())
130#endif
131        {
132            skipEmptyBuckets();
133        }
134
135        HashTableConstIterator(PointerType position, PointerType endPosition, const HashTableType* container, HashItemKnownGoodTag)
136            : m_position(position)
137            , m_endPosition(endPosition)
138#ifdef ASSERT_ENABLED
139            , m_container(container)
140            , m_containerModifications(container->modifications())
141#endif
142        {
143            ASSERT(m_containerModifications == m_container->modifications());
144        }
145
146        void checkModifications() const
147        {
148            // HashTable and collections that build on it do not support
149            // modifications while there is an iterator in use. The exception
150            // is ListHashSet, which has its own iterators that tolerate
151            // modification of the underlying set.
152            ASSERT(m_containerModifications == m_container->modifications());
153        }
154
155    public:
156        HashTableConstIterator()
157        {
158        }
159
160        GetType get() const
161        {
162            checkModifications();
163            return m_position;
164        }
165        typename Traits::IteratorConstReferenceType operator*() const { return Traits::getToReferenceConstConversion(get()); }
166        GetType operator->() const { return get(); }
167
168        const_iterator& operator++()
169        {
170            ASSERT(m_position != m_endPosition);
171            checkModifications();
172            ++m_position;
173            skipEmptyBuckets();
174            return *this;
175        }
176
177        // postfix ++ intentionally omitted
178
179        // Comparison.
180        bool operator==(const const_iterator& other) const
181        {
182            return m_position == other.m_position;
183        }
184        bool operator!=(const const_iterator& other) const
185        {
186            return m_position != other.m_position;
187        }
188        bool operator==(const iterator& other) const
189        {
190            return *this == static_cast<const_iterator>(other);
191        }
192        bool operator!=(const iterator& other) const
193        {
194            return *this != static_cast<const_iterator>(other);
195        }
196
197    private:
198        PointerType m_position;
199        PointerType m_endPosition;
200#ifdef ASSERT_ENABLED
201        const HashTableType* m_container;
202        int64_t m_containerModifications;
203#endif
204    };
205
206    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
207    class HashTableIterator {
208    private:
209        typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> HashTableType;
210        typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
211        typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> const_iterator;
212        typedef Value ValueType;
213        typedef typename Traits::IteratorGetType GetType;
214        typedef ValueType* PointerType;
215
216        friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>;
217
218        HashTableIterator(PointerType pos, PointerType end, const HashTableType* container) : m_iterator(pos, end, container) { }
219        HashTableIterator(PointerType pos, PointerType end, const HashTableType* container, HashItemKnownGoodTag tag) : m_iterator(pos, end, container, tag) { }
220
221    public:
222        HashTableIterator() { }
223
224        // default copy, assignment and destructor are OK
225
226        GetType get() const { return const_cast<GetType>(m_iterator.get()); }
227        typename Traits::IteratorReferenceType operator*() const { return Traits::getToReferenceConversion(get()); }
228        GetType operator->() const { return get(); }
229
230        iterator& operator++() { ++m_iterator; return *this; }
231
232        // postfix ++ intentionally omitted
233
234        // Comparison.
235        bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
236        bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
237        bool operator==(const const_iterator& other) const { return m_iterator == other; }
238        bool operator!=(const const_iterator& other) const { return m_iterator != other; }
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(KeyValuePair<T, U>& a, KeyValuePair<T, U>& b)
255    {
256        swap(a.key, b.key);
257        swap(a.value, b.value);
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 HashFunctions> class IdentityHashTranslator {
265    public:
266        template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
267        template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
268        template<typename T, typename U, typename V> static void translate(T& location, const U&, const V& value) { location = value; }
269    };
270
271    template<typename HashTableType, typename ValueType> struct HashTableAddResult {
272        HashTableAddResult(const HashTableType* container, ValueType* storedValue, bool isNewEntry)
273            : storedValue(storedValue)
274            , isNewEntry(isNewEntry)
275#if SECURITY_ASSERT_ENABLED
276            , m_container(container)
277            , m_containerModifications(container->modifications())
278#endif
279        {
280            ASSERT_UNUSED(container, container);
281        }
282
283        ~HashTableAddResult()
284        {
285            // If rehash happened before accessing storedValue, it's
286            // use-after-free. Any modification may cause a rehash, so we check
287            // for modifications here.
288            // Rehash after accessing storedValue is harmless but will assert if
289            // the AddResult destructor takes place after a modification. You
290            // may need to limit the scope of the AddResult.
291            ASSERT_WITH_SECURITY_IMPLICATION(m_containerModifications == m_container->modifications());
292        }
293
294        ValueType* storedValue;
295        bool isNewEntry;
296
297#if SECURITY_ASSERT_ENABLED
298    private:
299        const HashTableType* m_container;
300        const int64_t m_containerModifications;
301#endif
302    };
303
304    template<typename Value, typename Extractor, typename KeyTraits>
305    struct HashTableHelper {
306        static bool isEmptyBucket(const Value& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
307        static bool isDeletedBucket(const Value& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
308        static bool isEmptyOrDeletedBucket(const Value& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
309    };
310
311    template<typename HashTranslator, typename KeyTraits, bool safeToCompareToEmptyOrDeleted>
312    struct HashTableKeyChecker {
313        // There's no simple generic way to make this check if safeToCompareToEmptyOrDeleted is false,
314        // so the check always passes.
315        template <typename T>
316        static bool checkKey(const T&) { return true; }
317    };
318
319    template<typename HashTranslator, typename KeyTraits>
320    struct HashTableKeyChecker<HashTranslator, KeyTraits, true> {
321        template <typename T>
322        static bool checkKey(const T& key)
323        {
324            // FIXME : Check also equality to the deleted value.
325            return !HashTranslator::equal(KeyTraits::emptyValue(), key);
326        }
327    };
328
329    // Don't declare a destructor for HeapAllocated hash tables.
330    template<typename Derived, bool isGarbageCollected>
331    class HashTableDestructorBase;
332
333    template<typename Derived>
334    class HashTableDestructorBase<Derived, true> { };
335
336    template<typename Derived>
337    class HashTableDestructorBase<Derived, false> {
338    public:
339        ~HashTableDestructorBase() { static_cast<Derived*>(this)->finalize(); }
340    };
341
342    // Note: empty or deleted key values are not allowed, using them may lead to undefined behavior.
343    // For pointer keys this means that null pointers are not allowed unless you supply custom key traits.
344    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
345    class HashTable : public HashTableDestructorBase<HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>, Allocator::isGarbageCollected> {
346    public:
347        typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
348        typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> const_iterator;
349        typedef Traits ValueTraits;
350        typedef Key KeyType;
351        typedef typename KeyTraits::PeekInType KeyPeekInType;
352        typedef typename KeyTraits::PassInType KeyPassInType;
353        typedef Value ValueType;
354        typedef Extractor ExtractorType;
355        typedef KeyTraits KeyTraitsType;
356        typedef typename Traits::PassInType ValuePassInType;
357        typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType;
358        typedef HashTableAddResult<HashTable, ValueType> AddResult;
359
360#if DUMP_HASHTABLE_STATS_PER_TABLE
361        struct Stats {
362            Stats()
363                : numAccesses(0)
364                , numRehashes(0)
365                , numRemoves(0)
366                , numReinserts(0)
367                , maxCollisions(0)
368                , numCollisions(0)
369                , collisionGraph()
370            {
371            }
372
373            int numAccesses;
374            int numRehashes;
375            int numRemoves;
376            int numReinserts;
377
378            int maxCollisions;
379            int numCollisions;
380            int collisionGraph[4096];
381
382            void recordCollisionAtCount(int count)
383            {
384                if (count > maxCollisions)
385                    maxCollisions = count;
386                numCollisions++;
387                collisionGraph[count]++;
388            }
389
390            void dumpStats()
391            {
392                dataLogF("\nWTF::HashTable::Stats dump\n\n");
393                dataLogF("%d accesses\n", numAccesses);
394                dataLogF("%d total collisions, average %.2f probes per access\n", numCollisions, 1.0 * (numAccesses + numCollisions) / numAccesses);
395                dataLogF("longest collision chain: %d\n", maxCollisions);
396                for (int i = 1; i <= maxCollisions; i++) {
397                    dataLogF("  %d lookups with exactly %d collisions (%.2f%% , %.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses);
398                }
399                dataLogF("%d rehashes\n", numRehashes);
400                dataLogF("%d reinserts\n", numReinserts);
401            }
402        };
403#endif
404
405        HashTable();
406        void finalize()
407        {
408            ASSERT(!Allocator::isGarbageCollected);
409            if (LIKELY(!m_table))
410                return;
411            deleteAllBucketsAndDeallocate(m_table, m_tableSize);
412            m_table = 0;
413        }
414
415        HashTable(const HashTable&);
416        void swap(HashTable&);
417        HashTable& operator=(const HashTable&);
418
419        // When the hash table is empty, just return the same iterator for end as for begin.
420        // This is more efficient because we don't have to skip all the empty and deleted
421        // buckets, and iterating an empty table is a common case that's worth optimizing.
422        iterator begin() { return isEmpty() ? end() : makeIterator(m_table); }
423        iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
424        const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); }
425        const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
426
427        unsigned size() const { return m_keyCount; }
428        unsigned capacity() const { return m_tableSize; }
429        bool isEmpty() const { return !m_keyCount; }
430
431        AddResult add(ValuePassInType value)
432        {
433            return add<IdentityTranslatorType>(Extractor::extract(value), value);
434        }
435
436        // A special version of add() that finds the object by hashing and comparing
437        // with some other type, to avoid the cost of type conversion if the object is already
438        // in the table.
439        template<typename HashTranslator, typename T, typename Extra> AddResult add(const T& key, const Extra&);
440        template<typename HashTranslator, typename T, typename Extra> AddResult addPassingHashCode(const T& key, const Extra&);
441
442        iterator find(KeyPeekInType key) { return find<IdentityTranslatorType>(key); }
443        const_iterator find(KeyPeekInType key) const { return find<IdentityTranslatorType>(key); }
444        bool contains(KeyPeekInType key) const { return contains<IdentityTranslatorType>(key); }
445
446        template<typename HashTranslator, typename T> iterator find(const T&);
447        template<typename HashTranslator, typename T> const_iterator find(const T&) const;
448        template<typename HashTranslator, typename T> bool contains(const T&) const;
449
450        void remove(KeyPeekInType);
451        void remove(iterator);
452        void remove(const_iterator);
453        void clear();
454
455        static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
456        static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
457        static bool isEmptyOrDeletedBucket(const ValueType& value) { return HashTableHelper<ValueType, Extractor, KeyTraits>:: isEmptyOrDeletedBucket(value); }
458
459        ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorType, KeyPeekInType>(key); }
460        template<typename HashTranslator, typename T> ValueType* lookup(T);
461        template<typename HashTranslator, typename T> const ValueType* lookup(T) const;
462
463        void trace(typename Allocator::Visitor*);
464
465#ifdef ASSERT_ENABLED
466        int64_t modifications() const { return m_modifications; }
467        void registerModification() { m_modifications++; }
468        // HashTable and collections that build on it do not support
469        // modifications while there is an iterator in use. The exception is
470        // ListHashSet, which has its own iterators that tolerate modification
471        // of the underlying set.
472        void checkModifications(int64_t mods) const { ASSERT(mods == m_modifications); }
473#else
474        int64_t modifications() const { return 0; }
475        void registerModification() { }
476        void checkModifications(int64_t mods) const { }
477#endif
478
479    private:
480        static ValueType* allocateTable(unsigned size);
481        static void deleteAllBucketsAndDeallocate(ValueType* table, unsigned size);
482
483        typedef std::pair<ValueType*, bool> LookupType;
484        typedef std::pair<LookupType, unsigned> FullLookupType;
485
486        LookupType lookupForWriting(const Key& key) { return lookupForWriting<IdentityTranslatorType>(key); };
487        template<typename HashTranslator, typename T> FullLookupType fullLookupForWriting(const T&);
488        template<typename HashTranslator, typename T> LookupType lookupForWriting(const T&);
489
490        void remove(ValueType*);
491
492        bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
493        bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
494        bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > KeyTraits::minimumTableSize; }
495        ValueType* expand(ValueType* entry = 0);
496        void shrink() { rehash(m_tableSize / 2, 0); }
497
498        ValueType* rehash(unsigned newTableSize, ValueType* entry);
499        ValueType* reinsert(ValueType&);
500
501        static void initializeBucket(ValueType& bucket);
502        static void deleteBucket(ValueType& bucket) { bucket.~ValueType(); Traits::constructDeletedValue(bucket); }
503
504        FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
505            { return FullLookupType(LookupType(position, found), hash); }
506
507        iterator makeIterator(ValueType* pos) { return iterator(pos, m_table + m_tableSize, this); }
508        const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(pos, m_table + m_tableSize, this); }
509        iterator makeKnownGoodIterator(ValueType* pos) { return iterator(pos, m_table + m_tableSize, this, HashItemKnownGood); }
510        const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(pos, m_table + m_tableSize, this, HashItemKnownGood); }
511
512        static const unsigned m_maxLoad = 2;
513        static const unsigned m_minLoad = 6;
514
515        unsigned tableSizeMask() const
516        {
517            size_t mask = m_tableSize - 1;
518            ASSERT((mask & m_tableSize) == 0);
519            return mask;
520        }
521
522        ValueType* m_table;
523        unsigned m_tableSize;
524        unsigned m_keyCount;
525        unsigned m_deletedCount;
526#ifdef ASSERT_ENABLED
527        unsigned m_modifications;
528#endif
529
530#if DUMP_HASHTABLE_STATS_PER_TABLE
531    public:
532        mutable OwnPtr<Stats> m_stats;
533#endif
534
535        template<WeakHandlingFlag x, typename T, typename U, typename V, typename W, typename X, typename Y, typename Z> friend struct WeakProcessingHashTableHelper;
536        template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
537    };
538
539    // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
540    template<unsigned size> struct OneifyLowBits;
541    template<>
542    struct OneifyLowBits<0> {
543        static const unsigned value = 0;
544    };
545    template<unsigned number>
546    struct OneifyLowBits {
547        static const unsigned value = number | OneifyLowBits<(number >> 1)>::value;
548    };
549    // Compute the first power of two integer that is an upper bound of the parameter 'number'.
550    template<unsigned number>
551    struct UpperPowerOfTwoBound {
552        static const unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2;
553    };
554
555    // Because power of two numbers are the limit of maxLoad, their capacity is twice the
556    // UpperPowerOfTwoBound, or 4 times their values.
557    template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter;
558    template<unsigned size>
559    struct HashTableCapacityForSizeSplitter<size, true> {
560        static const unsigned value = size * 4;
561    };
562    template<unsigned size>
563    struct HashTableCapacityForSizeSplitter<size, false> {
564        static const unsigned value = UpperPowerOfTwoBound<size>::value;
565    };
566
567    // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter.
568    // This is done at compile time to initialize the HashTraits.
569    template<unsigned size>
570    struct HashTableCapacityForSize {
571        static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
572        COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
573        COMPILE_ASSERT(!static_cast<int>(value >> 31), HashTableNoCapacityOverflow);
574        COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
575    };
576
577    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
578    inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::HashTable()
579        : m_table(0)
580        , m_tableSize(0)
581        , m_keyCount(0)
582        , m_deletedCount(0)
583#ifdef ASSERT_ENABLED
584        , m_modifications(0)
585#endif
586#if DUMP_HASHTABLE_STATS_PER_TABLE
587        , m_stats(adoptPtr(new Stats))
588#endif
589    {
590    }
591
592    inline unsigned doubleHash(unsigned key)
593    {
594        key = ~key + (key >> 23);
595        key ^= (key << 12);
596        key ^= (key >> 7);
597        key ^= (key << 2);
598        key ^= (key >> 20);
599        return key;
600    }
601
602    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
603    template<typename HashTranslator, typename T>
604    inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key)
605    {
606        return const_cast<Value*>(const_cast<const HashTable*>(this)->lookup<HashTranslator, T>(key));
607    }
608
609    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
610    template<typename HashTranslator, typename T>
611    inline const Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key) const
612    {
613        ASSERT((HashTableKeyChecker<HashTranslator, KeyTraits, HashFunctions::safeToCompareToEmptyOrDeleted>::checkKey(key)));
614        const ValueType* table = m_table;
615        if (!table)
616            return 0;
617
618        size_t k = 0;
619        size_t sizeMask = tableSizeMask();
620        unsigned h = HashTranslator::hash(key);
621        size_t i = h & sizeMask;
622
623        UPDATE_ACCESS_COUNTS();
624
625        while (1) {
626            const ValueType* entry = table + i;
627
628            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
629                if (HashTranslator::equal(Extractor::extract(*entry), key))
630                    return entry;
631
632                if (isEmptyBucket(*entry))
633                    return 0;
634            } else {
635                if (isEmptyBucket(*entry))
636                    return 0;
637
638                if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
639                    return entry;
640            }
641            UPDATE_PROBE_COUNTS();
642            if (!k)
643                k = 1 | doubleHash(h);
644            i = (i + k) & sizeMask;
645        }
646    }
647
648    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
649    template<typename HashTranslator, typename T>
650    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookupForWriting(const T& key)
651    {
652        ASSERT(m_table);
653        registerModification();
654
655        ValueType* table = m_table;
656        size_t k = 0;
657        size_t sizeMask = tableSizeMask();
658        unsigned h = HashTranslator::hash(key);
659        size_t i = h & sizeMask;
660
661        UPDATE_ACCESS_COUNTS();
662
663        ValueType* deletedEntry = 0;
664
665        while (1) {
666            ValueType* entry = table + i;
667
668            if (isEmptyBucket(*entry))
669                return LookupType(deletedEntry ? deletedEntry : entry, false);
670
671            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
672                if (HashTranslator::equal(Extractor::extract(*entry), key))
673                    return LookupType(entry, true);
674
675                if (isDeletedBucket(*entry))
676                    deletedEntry = entry;
677            } else {
678                if (isDeletedBucket(*entry))
679                    deletedEntry = entry;
680                else if (HashTranslator::equal(Extractor::extract(*entry), key))
681                    return LookupType(entry, true);
682            }
683            UPDATE_PROBE_COUNTS();
684            if (!k)
685                k = 1 | doubleHash(h);
686            i = (i + k) & sizeMask;
687        }
688    }
689
690    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
691    template<typename HashTranslator, typename T>
692    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::fullLookupForWriting(const T& key)
693    {
694        ASSERT(m_table);
695        registerModification();
696
697        ValueType* table = m_table;
698        size_t k = 0;
699        size_t sizeMask = tableSizeMask();
700        unsigned h = HashTranslator::hash(key);
701        size_t i = h & sizeMask;
702
703        UPDATE_ACCESS_COUNTS();
704
705        ValueType* deletedEntry = 0;
706
707        while (1) {
708            ValueType* entry = table + i;
709
710            if (isEmptyBucket(*entry))
711                return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
712
713            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
714                if (HashTranslator::equal(Extractor::extract(*entry), key))
715                    return makeLookupResult(entry, true, h);
716
717                if (isDeletedBucket(*entry))
718                    deletedEntry = entry;
719            } else {
720                if (isDeletedBucket(*entry))
721                    deletedEntry = entry;
722                else if (HashTranslator::equal(Extractor::extract(*entry), key))
723                    return makeLookupResult(entry, true, h);
724            }
725            UPDATE_PROBE_COUNTS();
726            if (!k)
727                k = 1 | doubleHash(h);
728            i = (i + k) & sizeMask;
729        }
730    }
731
732    template<bool emptyValueIsZero> struct HashTableBucketInitializer;
733
734    template<> struct HashTableBucketInitializer<false> {
735        template<typename Traits, typename Value> static void initialize(Value& bucket)
736        {
737            new (NotNull, &bucket) Value(Traits::emptyValue());
738        }
739    };
740
741    template<> struct HashTableBucketInitializer<true> {
742        template<typename Traits, typename Value> static void initialize(Value& bucket)
743        {
744            // This initializes the bucket without copying the empty value.
745            // That makes it possible to use this with types that don't support copying.
746            // The memset to 0 looks like a slow operation but is optimized by the compilers.
747            memset(&bucket, 0, sizeof(bucket));
748        }
749    };
750
751    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
752    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::initializeBucket(ValueType& bucket)
753    {
754        HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket);
755    }
756
757    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
758    template<typename HashTranslator, typename T, typename Extra>
759    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::add(const T& key, const Extra& extra)
760    {
761        if (!m_table)
762            expand();
763
764        ASSERT(m_table);
765
766        ValueType* table = m_table;
767        size_t k = 0;
768        size_t sizeMask = tableSizeMask();
769        unsigned h = HashTranslator::hash(key);
770        size_t i = h & sizeMask;
771
772        UPDATE_ACCESS_COUNTS();
773
774        ValueType* deletedEntry = 0;
775        ValueType* entry;
776        while (1) {
777            entry = table + i;
778
779            if (isEmptyBucket(*entry))
780                break;
781
782            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
783                if (HashTranslator::equal(Extractor::extract(*entry), key))
784                    return AddResult(this, entry, false);
785
786                if (isDeletedBucket(*entry))
787                    deletedEntry = entry;
788            } else {
789                if (isDeletedBucket(*entry))
790                    deletedEntry = entry;
791                else if (HashTranslator::equal(Extractor::extract(*entry), key))
792                    return AddResult(this, entry, false);
793            }
794            UPDATE_PROBE_COUNTS();
795            if (!k)
796                k = 1 | doubleHash(h);
797            i = (i + k) & sizeMask;
798        }
799
800        registerModification();
801
802        if (deletedEntry) {
803            initializeBucket(*deletedEntry);
804            entry = deletedEntry;
805            --m_deletedCount;
806        }
807
808        HashTranslator::translate(*entry, key, extra);
809        ASSERT(!isEmptyOrDeletedBucket(*entry));
810
811        ++m_keyCount;
812
813        if (shouldExpand())
814            entry = expand(entry);
815
816        return AddResult(this, entry, true);
817    }
818
819    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
820    template<typename HashTranslator, typename T, typename Extra>
821    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::addPassingHashCode(const T& key, const Extra& extra)
822    {
823        if (!m_table)
824            expand();
825
826        FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key);
827
828        ValueType* entry = lookupResult.first.first;
829        bool found = lookupResult.first.second;
830        unsigned h = lookupResult.second;
831
832        if (found)
833            return AddResult(this, entry, false);
834
835        registerModification();
836
837        if (isDeletedBucket(*entry)) {
838            initializeBucket(*entry);
839            --m_deletedCount;
840        }
841
842        HashTranslator::translate(*entry, key, extra, h);
843        ASSERT(!isEmptyOrDeletedBucket(*entry));
844
845        ++m_keyCount;
846        if (shouldExpand())
847            entry = expand(entry);
848
849        return AddResult(this, entry, true);
850    }
851
852    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
853    Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::reinsert(ValueType& entry)
854    {
855        ASSERT(m_table);
856        registerModification();
857        ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
858        ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
859#if DUMP_HASHTABLE_STATS
860        atomicIncrement(&HashTableStats::numReinserts);
861#endif
862#if DUMP_HASHTABLE_STATS_PER_TABLE
863        ++m_stats->numReinserts;
864#endif
865        Value* newEntry = lookupForWriting(Extractor::extract(entry)).first;
866        Mover<ValueType, Traits::needsDestruction>::move(entry, *newEntry);
867
868        return newEntry;
869    }
870
871    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
872    template <typename HashTranslator, typename T>
873    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::find(const T& key)
874    {
875        ValueType* entry = lookup<HashTranslator>(key);
876        if (!entry)
877            return end();
878
879        return makeKnownGoodIterator(entry);
880    }
881
882    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
883    template <typename HashTranslator, typename T>
884    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::find(const T& key) const
885    {
886        ValueType* entry = const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
887        if (!entry)
888            return end();
889
890        return makeKnownGoodConstIterator(entry);
891    }
892
893    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
894    template <typename HashTranslator, typename T>
895    bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::contains(const T& key) const
896    {
897        return const_cast<HashTable*>(this)->lookup<HashTranslator>(key);
898    }
899
900    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
901    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(ValueType* pos)
902    {
903        registerModification();
904#if DUMP_HASHTABLE_STATS
905        atomicIncrement(&HashTableStats::numRemoves);
906#endif
907#if DUMP_HASHTABLE_STATS_PER_TABLE
908        ++m_stats->numRemoves;
909#endif
910
911        deleteBucket(*pos);
912        ++m_deletedCount;
913        --m_keyCount;
914
915        if (shouldShrink())
916            shrink();
917    }
918
919    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
920    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(iterator it)
921    {
922        if (it == end())
923            return;
924
925        remove(const_cast<ValueType*>(it.m_iterator.m_position));
926    }
927
928    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
929    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(const_iterator it)
930    {
931        if (it == end())
932            return;
933
934        remove(const_cast<ValueType*>(it.m_position));
935    }
936
937    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
938    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::remove(KeyPeekInType key)
939    {
940        remove(find(key));
941    }
942
943    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
944    Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::allocateTable(unsigned size)
945    {
946        typedef typename Allocator::template HashTableBackingHelper<HashTable>::Type HashTableBacking;
947
948        size_t allocSize = size * sizeof(ValueType);
949        ValueType* result;
950        COMPILE_ASSERT(!Traits::emptyValueIsZero || !IsPolymorphic<ValueType>::value, EmptyValueCannotBeZeroForThingsWithAVtable);
951        if (Traits::emptyValueIsZero) {
952            result = Allocator::template zeroedBackingMalloc<ValueType*, HashTableBacking>(allocSize);
953        } else {
954            result = Allocator::template backingMalloc<ValueType*, HashTableBacking>(allocSize);
955            for (unsigned i = 0; i < size; i++)
956                initializeBucket(result[i]);
957        }
958        return result;
959    }
960
961    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
962    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::deleteAllBucketsAndDeallocate(ValueType* table, unsigned size)
963    {
964        if (Traits::needsDestruction) {
965            for (unsigned i = 0; i < size; ++i) {
966                // This code is called when the hash table is cleared or
967                // resized. We have allocated a new backing store and we need
968                // to run the destructors on the old backing store, as it is
969                // being freed. If we are GCing we need to both call the
970                // destructor and mark the bucket as deleted, otherwise the
971                // destructor gets called again when the GC finds the backing
972                // store. With the default allocator it's enough to call the
973                // destructor, since we will free the memory explicitly and
974                // we won't see the memory with the bucket again.
975                if (!isEmptyOrDeletedBucket(table[i])) {
976                    if (Allocator::isGarbageCollected)
977                        deleteBucket(table[i]);
978                    else
979                        table[i].~ValueType();
980                }
981            }
982        }
983        Allocator::backingFree(table);
984    }
985
986    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
987    Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::expand(Value* entry)
988    {
989        unsigned newSize;
990        if (!m_tableSize) {
991            newSize = KeyTraits::minimumTableSize;
992        } else if (mustRehashInPlace()) {
993            newSize = m_tableSize;
994        } else {
995            newSize = m_tableSize * 2;
996            RELEASE_ASSERT(newSize > m_tableSize);
997        }
998
999        return rehash(newSize, entry);
1000    }
1001
1002    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1003    Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::rehash(unsigned newTableSize, Value* entry)
1004    {
1005        unsigned oldTableSize = m_tableSize;
1006        ValueType* oldTable = m_table;
1007
1008#if DUMP_HASHTABLE_STATS
1009        if (oldTableSize != 0)
1010            atomicIncrement(&HashTableStats::numRehashes);
1011#endif
1012
1013#if DUMP_HASHTABLE_STATS_PER_TABLE
1014        if (oldTableSize != 0)
1015            ++m_stats->numRehashes;
1016#endif
1017
1018        m_table = allocateTable(newTableSize);
1019        m_tableSize = newTableSize;
1020
1021        Value* newEntry = 0;
1022        for (unsigned i = 0; i != oldTableSize; ++i) {
1023            if (isEmptyOrDeletedBucket(oldTable[i])) {
1024                ASSERT(&oldTable[i] != entry);
1025                continue;
1026            }
1027
1028            Value* reinsertedEntry = reinsert(oldTable[i]);
1029            if (&oldTable[i] == entry) {
1030                ASSERT(!newEntry);
1031                newEntry = reinsertedEntry;
1032            }
1033        }
1034
1035        m_deletedCount = 0;
1036
1037        deleteAllBucketsAndDeallocate(oldTable, oldTableSize);
1038
1039        return newEntry;
1040    }
1041
1042    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1043    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::clear()
1044    {
1045        registerModification();
1046        if (!m_table)
1047            return;
1048
1049        deleteAllBucketsAndDeallocate(m_table, m_tableSize);
1050        m_table = 0;
1051        m_tableSize = 0;
1052        m_keyCount = 0;
1053    }
1054
1055    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1056    HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::HashTable(const HashTable& other)
1057        : m_table(0)
1058        , m_tableSize(0)
1059        , m_keyCount(0)
1060        , m_deletedCount(0)
1061#ifdef ASSERT_ENABLED
1062        , m_modifications(0)
1063#endif
1064#if DUMP_HASHTABLE_STATS_PER_TABLE
1065        , m_stats(adoptPtr(new Stats(*other.m_stats)))
1066#endif
1067    {
1068        // Copy the hash table the dumb way, by adding each element to the new table.
1069        // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
1070        const_iterator end = other.end();
1071        for (const_iterator it = other.begin(); it != end; ++it)
1072            add(*it);
1073    }
1074
1075    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1076    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::swap(HashTable& other)
1077    {
1078        std::swap(m_table, other.m_table);
1079        std::swap(m_tableSize, other.m_tableSize);
1080        std::swap(m_keyCount, other.m_keyCount);
1081        std::swap(m_deletedCount, other.m_deletedCount);
1082
1083#ifdef ASSERT_ENABLED
1084        std::swap(m_modifications, other.m_modifications);
1085#endif
1086
1087#if DUMP_HASHTABLE_STATS_PER_TABLE
1088        m_stats.swap(other.m_stats);
1089#endif
1090    }
1091
1092    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1093    HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::operator=(const HashTable& other)
1094    {
1095        HashTable tmp(other);
1096        swap(tmp);
1097        return *this;
1098    }
1099
1100    template<WeakHandlingFlag weakHandlingFlag, typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1101    struct WeakProcessingHashTableHelper;
1102
1103    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1104    struct WeakProcessingHashTableHelper<NoWeakHandlingInCollections, Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> {
1105        static void process(typename Allocator::Visitor* visitor, void* closure) { }
1106    };
1107
1108    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1109    struct WeakProcessingHashTableHelper<WeakHandlingInCollections, Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> {
1110        static void process(typename Allocator::Visitor* visitor, void* closure)
1111        {
1112            typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> HashTableType;
1113            HashTableType* table = reinterpret_cast<HashTableType*>(closure);
1114            if (table->m_table) {
1115                // This just marks it live and does not push anything onto the
1116                // marking stack.
1117                Allocator::markNoTracing(visitor, table->m_table);
1118                // Now perform weak processing (this is a no-op if the backing
1119                // was accessible through an iterator and was already marked
1120                // strongly).
1121                for (typename HashTableType::ValueType* element = table->m_table + table->m_tableSize - 1; element >= table->m_table; element--) {
1122                    if (!HashTableType::isEmptyOrDeletedBucket(*element)) {
1123                        if (Traits::shouldRemoveFromCollection(visitor, *element)) {
1124                            table->registerModification();
1125                            HashTableType::deleteBucket(*element); // Also calls the destructor.
1126                            table->m_deletedCount++;
1127                            table->m_keyCount--;
1128                            // We don't rehash the backing until the next add
1129                            // or delete, because that would cause allocation
1130                            // during GC.
1131                        }
1132                    }
1133                }
1134            }
1135        }
1136    };
1137
1138    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
1139    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::trace(typename Allocator::Visitor* visitor)
1140    {
1141        // If someone else already marked the backing and queued up the trace
1142        // and/or weak callback then we are done. This optimization does not
1143        // happen for ListHashSet since its iterator does not point at the
1144        // backing.
1145        if (!m_table || visitor->isAlive(m_table))
1146            return;
1147        // Normally, we mark the backing store without performing trace. This
1148        // means it is marked live, but the pointers inside it are not marked.
1149        // Instead we will mark the pointers below. However, for backing
1150        // stores that contain weak pointers the handling is rather different.
1151        // We don't mark the backing store here, so the marking GC will leave
1152        // the backing unmarked. If the backing is found in any other way than
1153        // through its HashTable (ie from an iterator) then the mark bit will
1154        // be set and the pointers will be marked strongly, avoiding problems
1155        // with iterating over things that disappear due to weak processing
1156        // while we are iterating over them. The weakProcessing callback will
1157        // mark the backing as a void pointer, and will perform weak processing
1158        // if needed.
1159        if (Traits::weakHandlingFlag == NoWeakHandlingInCollections)
1160            Allocator::markNoTracing(visitor, m_table);
1161        else
1162            Allocator::registerWeakMembers(visitor, this, m_table, WeakProcessingHashTableHelper<Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::process);
1163        if (ShouldBeTraced<Traits>::value) {
1164            for (ValueType* element = m_table + m_tableSize - 1; element >= m_table; element--) {
1165                if (!isEmptyOrDeletedBucket(*element))
1166                    Allocator::template trace<ValueType, Traits>(visitor, *element);
1167            }
1168        }
1169    }
1170
1171    // iterator adapters
1172
1173    template<typename HashTableType, typename Traits> struct HashTableConstIteratorAdapter {
1174        HashTableConstIteratorAdapter() {}
1175        HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
1176        typedef typename Traits::IteratorConstGetType GetType;
1177        typedef typename HashTableType::ValueTraits::IteratorConstGetType SourceGetType;
1178
1179        GetType get() const { return const_cast<GetType>(SourceGetType(m_impl.get())); }
1180        typename Traits::IteratorConstReferenceType operator*() const { return Traits::getToReferenceConstConversion(get()); }
1181        GetType operator->() const { return get(); }
1182
1183        HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
1184        // postfix ++ intentionally omitted
1185
1186        typename HashTableType::const_iterator m_impl;
1187    };
1188
1189    template<typename HashTableType, typename Traits> struct HashTableIteratorAdapter {
1190        typedef typename Traits::IteratorGetType GetType;
1191        typedef typename HashTableType::ValueTraits::IteratorGetType SourceGetType;
1192
1193        HashTableIteratorAdapter() {}
1194        HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
1195
1196        GetType get() const { return const_cast<GetType>(SourceGetType(m_impl.get())); }
1197        typename Traits::IteratorReferenceType operator*() const { return Traits::getToReferenceConversion(get()); }
1198        GetType operator->() const { return get(); }
1199
1200        HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
1201        // postfix ++ intentionally omitted
1202
1203        operator HashTableConstIteratorAdapter<HashTableType, Traits>()
1204        {
1205            typename HashTableType::const_iterator i = m_impl;
1206            return i;
1207        }
1208
1209        typename HashTableType::iterator m_impl;
1210    };
1211
1212    template<typename T, typename U>
1213    inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1214    {
1215        return a.m_impl == b.m_impl;
1216    }
1217
1218    template<typename T, typename U>
1219    inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1220    {
1221        return a.m_impl != b.m_impl;
1222    }
1223
1224    template<typename T, typename U>
1225    inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1226    {
1227        return a.m_impl == b.m_impl;
1228    }
1229
1230    template<typename T, typename U>
1231    inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1232    {
1233        return a.m_impl != b.m_impl;
1234    }
1235
1236    // All 4 combinations of ==, != and Const,non const.
1237    template<typename T, typename U>
1238    inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1239    {
1240        return a.m_impl == b.m_impl;
1241    }
1242
1243    template<typename T, typename U>
1244    inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
1245    {
1246        return a.m_impl != b.m_impl;
1247    }
1248
1249    template<typename T, typename U>
1250    inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1251    {
1252        return a.m_impl == b.m_impl;
1253    }
1254
1255    template<typename T, typename U>
1256    inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
1257    {
1258        return a.m_impl != b.m_impl;
1259    }
1260
1261    template<typename Collection1, typename Collection2>
1262    inline void removeAll(Collection1& collection, const Collection2& toBeRemoved)
1263    {
1264        if (collection.isEmpty() || toBeRemoved.isEmpty())
1265            return;
1266        typedef typename Collection2::const_iterator CollectionIterator;
1267        CollectionIterator end(toBeRemoved.end());
1268        for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it)
1269            collection.remove(*it);
1270    }
1271
1272} // namespace WTF
1273
1274#include "wtf/HashIterators.h"
1275
1276#endif // WTF_HashTable_h
1277