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