WTF

HashTable.h

00001 // -*- mode: c++; c-basic-offset: 4 -*-
00002 /*
00003  * This file is part of the KDE libraries
00004  * Copyright (C) 2005, 2006 Apple Computer, Inc.
00005  *
00006  * This library is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU Library General Public
00008  * License as published by the Free Software Foundation; either
00009  * version 2 of the License, or (at your option) any later version.
00010  *
00011  * This library is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * Library General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU Library General Public License
00017  * along with this library; see the file COPYING.LIB.  If not, write to
00018  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00019  * Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 #ifndef WTF_HashTable_h
00024 #define WTF_HashTable_h
00025 
00026 #include "FastMalloc.h"
00027 #include "HashTraits.h"
00028 #include <assert.h>
00029 
00030 namespace WTF {
00031 
00032 #define DUMP_HASHTABLE_STATS 0
00033 #define CHECK_HASHTABLE_CONSISTENCY 0
00034 
00035 // The Apple tree triggers this based on debug or not
00036 // We can't do this, since it would make the two builds BIC!
00037 #define CHECK_HASHTABLE_ITERATORS 0
00038 
00039 #if DUMP_HASHTABLE_STATS
00040 
00041     struct HashTableStats {
00042         ~HashTableStats();
00043         static int numAccesses;
00044         static int numCollisions;
00045         static int collisionGraph[4096];
00046         static int maxCollisions;
00047         static int numRehashes;
00048         static int numRemoves;
00049         static int numReinserts;
00050         static void recordCollisionAtCount(int count);
00051     };
00052 
00053 #endif
00054 
00055     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00056     class HashTable;
00057     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00058     class HashTableIterator;
00059     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00060     class HashTableConstIterator;
00061 
00062 #if CHECK_HASHTABLE_ITERATORS
00063     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00064     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
00065         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
00066 
00067     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00068     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*);
00069 #else
00070     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00071     inline void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*,
00072         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
00073 
00074     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00075     inline void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>*) { }
00076 #endif
00077 
00078     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00079     class HashTableConstIterator {
00080     private:
00081         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
00082         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
00083         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
00084         typedef Value ValueType;
00085         typedef const ValueType& ReferenceType;
00086         typedef const ValueType* PointerType;
00087 
00088         friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
00089         friend class HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
00090 
00091         void skipEmptyBuckets()
00092         {
00093             while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position))
00094                 ++m_position;
00095         }
00096 
00097         HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition)
00098             : m_position(position), m_endPosition(endPosition)
00099         {
00100             addIterator(table, this);
00101             skipEmptyBuckets();
00102         }
00103 
00104     public:
00105         HashTableConstIterator()
00106         {
00107             addIterator(0, this);
00108         }
00109 
00110         // default copy, assignment and destructor are OK if CHECK_HASHTABLE_ITERATORS is 0
00111 
00112 #if CHECK_HASHTABLE_ITERATORS
00113         ~HashTableConstIterator()
00114         {
00115             removeIterator(this);
00116         }
00117 
00118         HashTableConstIterator(const const_iterator& other)
00119             : m_position(other.m_position), m_endPosition(other.m_endPosition)
00120         {
00121             addIterator(other.m_table, this);
00122         }
00123 
00124         const_iterator& operator=(const const_iterator& other)
00125         {
00126             m_position = other.m_position;
00127             m_endPosition = other.m_endPosition;
00128 
00129             removeIterator(this);
00130             addIterator(other.m_table, this);
00131 
00132             return *this;
00133         }
00134 #endif
00135 
00136         PointerType get() const
00137         {
00138             checkValidity();
00139             return m_position;
00140         }
00141         ReferenceType operator*() const { return *get(); }
00142         PointerType operator->() const { return get(); }
00143 
00144         const_iterator& operator++()
00145         {
00146             checkValidity();
00147             assert(m_position != m_endPosition);
00148             ++m_position;
00149             skipEmptyBuckets();
00150             return *this;
00151         }
00152 
00153         // postfix ++ intentionally omitted
00154 
00155         // Comparison.
00156         bool operator==(const const_iterator& other) const
00157         {
00158             checkValidity(other);
00159             return m_position == other.m_position;
00160         }
00161         bool operator!=(const const_iterator& other) const
00162         {
00163             checkValidity(other);
00164             return m_position != other.m_position;
00165         }
00166 
00167     private:
00168         void checkValidity() const
00169         {
00170 #if CHECK_HASHTABLE_ITERATORS
00171             assert(m_table);
00172 #endif
00173         }
00174 
00175 
00176 #if CHECK_HASHTABLE_ITERATORS
00177         void checkValidity(const const_iterator& other) const
00178         {
00179             assert(m_table);
00180             assert(other.m_table);
00181             assert(m_table == other.m_table);
00182         }
00183 #else
00184         void checkValidity(const const_iterator&) const { }
00185 #endif
00186 
00187         PointerType m_position;
00188         PointerType m_endPosition;
00189 
00190 #if CHECK_HASHTABLE_ITERATORS
00191     public:
00192         mutable const HashTableType* m_table;
00193         mutable const_iterator* m_next;
00194         mutable const_iterator* m_previous;
00195 #endif
00196     };
00197 
00198     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00199     class HashTableIterator {
00200     private:
00201         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
00202         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
00203         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
00204         typedef Value ValueType;
00205         typedef ValueType& ReferenceType;
00206         typedef ValueType* PointerType;
00207 
00208         friend class HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>;
00209 
00210         HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { }
00211 
00212     public:
00213         HashTableIterator() { }
00214 
00215         // default copy, assignment and destructor are OK
00216 
00217         PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
00218         ReferenceType operator*() const { return *get(); }
00219         PointerType operator->() const { return get(); }
00220 
00221         iterator& operator++() { ++m_iterator; return *this; }
00222 
00223         // postfix ++ intentionally omitted
00224 
00225         // Comparison.
00226         bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
00227         bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
00228 
00229         operator const_iterator() const { return m_iterator; }
00230 
00231     private:
00232         const_iterator m_iterator;
00233     };
00234 
00235     using std::swap;
00236 
00237 #if !COMPILER(MSVC) && !COMPILER(CWP)
00238     // Visual C++ has a swap for pairs defined.
00239 
00240     // swap pairs by component, in case of pair members that specialize swap
00241     template<typename T, typename U> inline void swap(pair<T, U>& a, pair<T, U>& b)
00242     {
00243         swap(a.first, b.first);
00244         swap(a.second, b.second);
00245     }
00246 #endif
00247 
00248     template<typename T, bool useSwap> struct Mover;
00249     template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { swap(from, to); } };
00250     template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } };
00251 
00252     template<typename Key, typename Value, typename HashFunctions> class IdentityHashTranslator {
00253     public:
00254         static unsigned hash(const Key& key) { return HashFunctions::hash(key); }
00255         static bool equal(const Key& a, const Key& b) { return HashFunctions::equal(a, b); }
00256         static void translate(Value& location, const Key&, const Value& value, unsigned) { location = value; }
00257     };
00258 
00259     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00260     class HashTable {
00261     public:
00262         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
00263         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
00264         typedef Traits ValueTraits;
00265         typedef Key KeyType;
00266         typedef Value ValueType;
00267         typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType;
00268 
00269         HashTable();
00270         ~HashTable() { invalidateIterators(); deallocateTable(m_table, m_tableSize); }
00271 
00272         HashTable(const HashTable&);
00273         void swap(HashTable&);
00274         HashTable& operator=(const HashTable&);
00275 
00276         iterator begin() { return makeIterator(m_table); }
00277         iterator end() { return makeIterator(m_table + m_tableSize); }
00278         const_iterator begin() const { return makeConstIterator(m_table); }
00279         const_iterator end() const { return makeConstIterator(m_table + m_tableSize); }
00280 
00281         int size() const { return m_keyCount; }
00282         int capacity() const { return m_tableSize; }
00283         bool isEmpty() const { return !m_keyCount; }
00284 
00285         pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }
00286 
00287         // A special version of add() that finds the object by hashing and comparing
00288         // with some other type, to avoid the cost of type conversion if the object is already
00289         // in the table.
00290         template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&);
00291 
00292         iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); }
00293         const_iterator find(const KeyType& key) const { return find<KeyType, IdentityTranslatorType>(key); }
00294         bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); }
00295 
00296         template <typename T, typename HashTranslator> iterator find(const T&);
00297         template <typename T, typename HashTranslator> const_iterator find(const T&) const;
00298         template <typename T, typename HashTranslator> bool contains(const T&) const;
00299 
00300         void remove(const KeyType&);
00301         void remove(iterator);
00302         void clear();
00303 
00304         static bool isEmptyBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::emptyValue(); }
00305         static bool isDeletedBucket(const ValueType& value) { return Extractor::extract(value) == KeyTraits::deletedValue(); }
00306         static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
00307 
00308     private:
00309         static ValueType* allocateTable(int size);
00310         static void deallocateTable(ValueType* table, int size);
00311 
00312         typedef pair<ValueType*, bool> LookupType;
00313         typedef pair<LookupType, unsigned> FullLookupType;
00314 
00315         LookupType lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key).first; }
00316         template<typename T, typename HashTranslator> FullLookupType lookup(const T&);
00317 
00318         void remove(ValueType*);
00319 
00320         bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
00321         bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
00322         bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; }
00323         void expand();
00324         void shrink() { rehash(m_tableSize / 2); }
00325 
00326         void rehash(int newTableSize);
00327         void reinsert(ValueType&);
00328 
00329         static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }
00330         static void deleteBucket(ValueType& bucket) { assignDeleted<ValueType, Traits>(bucket); }
00331 
00332         FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
00333             { return FullLookupType(LookupType(position, found), hash); }
00334 
00335         iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
00336         const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
00337 
00338 #if CHECK_HASHTABLE_CONSISTENCY
00339         void checkTableConsistency() const;
00340         void checkTableConsistencyExceptSize() const;
00341 #else
00342         static void checkTableConsistency() { }
00343         static void checkTableConsistencyExceptSize() { }
00344 #endif
00345 
00346 #if CHECK_HASHTABLE_ITERATORS
00347         void invalidateIterators();
00348 #else
00349         static void invalidateIterators() { }
00350 #endif
00351 
00352         static const int m_minTableSize = 64;
00353         static const int m_maxLoad = 2;
00354         static const int m_minLoad = 6;
00355 
00356         ValueType* m_table;
00357         int m_tableSize;
00358         int m_tableSizeMask;
00359         int m_keyCount;
00360         int m_deletedCount;
00361 
00362 #if CHECK_HASHTABLE_ITERATORS
00363     public:
00364         mutable const_iterator* m_iterators;
00365 #endif
00366     };
00367 
00368     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00369     inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
00370         : m_table(0)
00371         , m_tableSize(0)
00372         , m_tableSizeMask(0)
00373         , m_keyCount(0)
00374         , m_deletedCount(0)
00375 #if CHECK_HASHTABLE_ITERATORS
00376         , m_iterators(0)
00377 #endif
00378     {
00379     }
00380 
00381     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00382     template<typename T, typename HashTranslator>
00383     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
00384     {
00385         assert(m_table);
00386 
00387         unsigned h = HashTranslator::hash(key);
00388         int sizeMask = m_tableSizeMask;
00389         int i = h & sizeMask;
00390         int k = 0;
00391 
00392 #if DUMP_HASHTABLE_STATS
00393         ++HashTableStats::numAccesses;
00394         int probeCount = 0;
00395 #endif
00396 
00397         ValueType *table = m_table;
00398         ValueType *entry;
00399         ValueType *deletedEntry = 0;
00400         while (!isEmptyBucket(*(entry = table + i))) {
00401             if (isDeletedBucket(*entry))
00402                 deletedEntry = entry;
00403             else if (HashTranslator::equal(Extractor::extract(*entry), key))
00404                 return makeLookupResult(entry, true, h);
00405 #if DUMP_HASHTABLE_STATS
00406             ++probeCount;
00407             HashTableStats::recordCollisionAtCount(probeCount);
00408 #endif
00409             if (k == 0)
00410                 k = 1 | (h % sizeMask);
00411             i = (i + k) & sizeMask;
00412         }
00413 
00414         return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
00415     }
00416 
00417 
00418     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00419     template<typename T, typename Extra, typename HashTranslator>
00420     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)
00421     {
00422         invalidateIterators();
00423 
00424         if (!m_table)
00425             expand();
00426 
00427         checkTableConsistency();
00428 
00429         FullLookupType lookupResult = lookup<T, HashTranslator>(key);
00430 
00431         ValueType *entry = lookupResult.first.first;
00432     
00433     // M.O: this code gets mis(?)-compiled by my gcc 4.2.1-ish install
00434     // with pure -O2. The next line is a dirty hack around it.
00435     // Not sure whether it's an aliasing problem in code or a gcc bug
00436     ValueType** volatile hack = &entry; (void)hack;
00437         bool found = lookupResult.first.second;
00438         unsigned h = lookupResult.second;
00439 
00440         if (found)
00441             return std::make_pair(makeIterator(entry), false);
00442 
00443         if (isDeletedBucket(*entry))
00444             --m_deletedCount;
00445 
00446         HashTranslator::translate(*entry, key, extra, h);
00447         ++m_keyCount;
00448 
00449         if (shouldExpand()) {
00450             // FIXME: this makes an extra copy on expand. Probably not that bad since
00451             // expand is rare, but would be better to have a version of expand that can
00452             // follow a pivot entry and return the new position
00453             KeyType enteredKey = Extractor::extract(*entry);
00454             expand();
00455             return std::make_pair(find(enteredKey), true);
00456         }
00457 
00458         checkTableConsistency();
00459 
00460         return std::make_pair(makeIterator(entry), true);
00461     }
00462 
00463     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00464     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)
00465     {
00466         assert(m_table);
00467         assert(!lookup(Extractor::extract(entry)).second);
00468         assert(!isDeletedBucket(*(lookup(Extractor::extract(entry)).first)));
00469 #if DUMP_HASHTABLE_STATS
00470         ++HashTableStats::numReinserts;
00471 #endif
00472 
00473         Mover<ValueType, Traits::needsDestruction>::move(entry, *(lookup(Extractor::extract(entry)).first));
00474     }
00475 
00476     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00477     template <typename T, typename HashTranslator> 
00478     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key)
00479     {
00480         if (!m_table)
00481             return end();
00482 
00483         LookupType result = lookup<T, HashTranslator>(key).first;
00484         if (!result.second)
00485             return end();
00486         return makeIterator(result.first);
00487     }
00488 
00489     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00490     template <typename T, typename HashTranslator> 
00491     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key) const
00492     {
00493         if (!m_table)
00494             return end();
00495 
00496         LookupType result = const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key).first;
00497         if (!result.second)
00498             return end();
00499         return makeConstIterator(result.first);
00500     }
00501 
00502     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00503     template <typename T, typename HashTranslator> 
00504     bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const T& key) const
00505     {
00506         if (!m_table)
00507             return false;
00508 
00509         return const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key).first.second;
00510     }
00511 
00512     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00513     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
00514     {
00515         invalidateIterators();
00516         checkTableConsistency();
00517 
00518 #if DUMP_HASHTABLE_STATS
00519         ++HashTableStats::numRemoves;
00520 #endif
00521 
00522         deleteBucket(*pos);
00523         ++m_deletedCount;
00524         --m_keyCount;
00525 
00526         if (shouldShrink())
00527             shrink();
00528 
00529         checkTableConsistency();
00530     }
00531 
00532     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00533     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
00534     {
00535         if (it == end())
00536             return;
00537 
00538         remove(const_cast<ValueType*>(it.m_iterator.m_position));
00539     }
00540 
00541     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00542     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
00543     {
00544         remove(find(key));
00545     }
00546 
00547     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00548     Value *HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
00549     {
00550         // would use a template member function with explicit specializations here, but
00551         // gcc doesn't appear to support that
00552         if (Traits::emptyValueIsZero)
00553             return static_cast<ValueType *>(fastCalloc(size, sizeof(ValueType)));
00554         ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
00555         for (int i = 0; i < size; i++)
00556             initializeBucket(result[i]);
00557         return result;
00558     }
00559 
00560     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00561     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
00562     {
00563         if (Traits::needsDestruction)
00564             for (int i = 0; i < size; ++i)
00565                 table[i].~ValueType();
00566         fastFree(table);
00567     }
00568 
00569     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00570     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
00571     {
00572         int newSize;
00573         if (m_tableSize == 0)
00574             newSize = m_minTableSize;
00575         else if (mustRehashInPlace())
00576             newSize = m_tableSize;
00577         else
00578             newSize = m_tableSize * 2;
00579 
00580         rehash(newSize);
00581     }
00582 
00583     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00584     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize)
00585     {
00586         checkTableConsistencyExceptSize();
00587 
00588         int oldTableSize = m_tableSize;
00589         ValueType *oldTable = m_table;
00590 
00591 #if DUMP_HASHTABLE_STATS
00592         if (oldTableSize != 0)
00593             ++HashTableStats::numRehashes;
00594 #endif
00595 
00596         m_tableSize = newTableSize;
00597         m_tableSizeMask = newTableSize - 1;
00598         m_table = allocateTable(newTableSize);
00599 
00600         for (int i = 0; i != oldTableSize; ++i)
00601             if (!isEmptyOrDeletedBucket(oldTable[i]))
00602                 reinsert(oldTable[i]);
00603 
00604         m_deletedCount = 0;
00605 
00606         deallocateTable(oldTable, oldTableSize);
00607 
00608         checkTableConsistency();
00609     }
00610 
00611     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00612     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
00613     {
00614         invalidateIterators();
00615         deallocateTable(m_table, m_tableSize);
00616         m_table = 0;
00617         m_tableSize = 0;
00618         m_tableSizeMask = 0;
00619         m_keyCount = 0;
00620     }
00621 
00622     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00623     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
00624         : m_table(0)
00625         , m_tableSize(0)
00626         , m_tableSizeMask(0)
00627         , m_keyCount(0)
00628         , m_deletedCount(0)
00629 #if CHECK_HASHTABLE_ITERATORS
00630         , m_iterators(0)
00631 #endif
00632     {
00633         // Copy the hash table the dumb way, by adding each element to the new table.
00634         // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
00635         const_iterator end = other.end();
00636         for (const_iterator it = other.begin(); it != end; ++it)
00637             add(*it);
00638     }
00639 
00640     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00641     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
00642     {
00643         invalidateIterators();
00644         other.invalidateIterators();
00645 
00646         ValueType *tmp_table = m_table;
00647         m_table = other.m_table;
00648         other.m_table = tmp_table;
00649 
00650         int tmp_tableSize = m_tableSize;
00651         m_tableSize = other.m_tableSize;
00652         other.m_tableSize = tmp_tableSize;
00653 
00654         int tmp_tableSizeMask = m_tableSizeMask;
00655         m_tableSizeMask = other.m_tableSizeMask;
00656         other.m_tableSizeMask = tmp_tableSizeMask;
00657 
00658         int tmp_keyCount = m_keyCount;
00659         m_keyCount = other.m_keyCount;
00660         other.m_keyCount = tmp_keyCount;
00661 
00662         int tmp_deletedCount = m_deletedCount;
00663         m_deletedCount = other.m_deletedCount;
00664         other.m_deletedCount = tmp_deletedCount;
00665     }
00666 
00667     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00668     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)
00669     {
00670         HashTable tmp(other);
00671         swap(tmp);
00672         return *this;
00673     }
00674 
00675 #if CHECK_HASHTABLE_CONSISTENCY
00676 
00677     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00678     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
00679     {
00680         checkTableConsistencyExceptSize();
00681         assert(!shouldExpand());
00682         assert(!shouldShrink());
00683     }
00684 
00685     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00686     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
00687     {
00688         if (!m_table)
00689             return;
00690 
00691         int count = 0;
00692         int deletedCount = 0;
00693         for (int j = 0; j < m_tableSize; ++j) {
00694             ValueType *entry = m_table + j;
00695             if (isEmptyBucket(*entry))
00696                 continue;
00697 
00698             if (isDeletedBucket(*entry)) {
00699                 ++deletedCount;
00700                 continue;
00701             }
00702 
00703             const_iterator it = find(Extractor::extract(*entry));
00704             assert(entry == it.m_position);
00705             ++count;
00706         }
00707 
00708         assert(count == m_keyCount);
00709         assert(deletedCount == m_deletedCount);
00710         assert(m_tableSize >= m_minTableSize);
00711         assert(m_tableSizeMask);
00712         assert(m_tableSize == m_tableSizeMask + 1);
00713     }
00714 
00715 #endif // CHECK_HASHTABLE_CONSISTENCY
00716 
00717 #if CHECK_HASHTABLE_ITERATORS
00718 
00719     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00720     void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::invalidateIterators()
00721     {
00722         const_iterator* next;
00723         for (const_iterator* p = m_iterators; p; p = next) {
00724             next = p->m_next;
00725             p->m_table = 0;
00726             p->m_next = 0;
00727             p->m_previous = 0;
00728         }
00729         m_iterators = 0;
00730     }
00731 
00732     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00733     void addIterator(const HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* table,
00734         HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
00735     {
00736         it->m_table = table;
00737         it->m_previous = 0;
00738 
00739         // Insert iterator at head of doubly-linked list of iterators.
00740         if (!table) {
00741             it->m_next = 0;
00742         } else {
00743             assert(table->m_iterators != it);
00744             it->m_next = table->m_iterators;
00745             table->m_iterators = it;
00746             if (it->m_next) {
00747                 assert(!it->m_next->m_previous);
00748                 it->m_next->m_previous = it;
00749             }
00750         }
00751     }
00752 
00753     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
00754     void removeIterator(HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>* it)
00755     {
00756         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> HashTableType;
00757         typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
00758 
00759         // Delete iterator from doubly-linked list of iterators.
00760         if (!it->m_table) {
00761             assert(!it->m_next);
00762             assert(!it->m_previous);
00763         } else {
00764             if (it->m_next) {
00765                 assert(it->m_next->m_previous == it);
00766                 it->m_next->m_previous = it->m_previous;
00767             }
00768             if (it->m_previous) {
00769                 assert(it->m_table->m_iterators != it);
00770                 assert(it->m_previous->m_next == it);
00771                 it->m_previous->m_next = it->m_next;
00772             } else {
00773                 assert(it->m_table->m_iterators == it);
00774                 it->m_table->m_iterators = it->m_next;
00775             }
00776         }
00777 
00778         it->m_table = 0;
00779         it->m_next = 0;
00780         it->m_previous = 0;
00781     }
00782 
00783 #endif // CHECK_HASHTABLE_ITERATORS
00784 
00785     // iterator adapters
00786 
00787     template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
00788         HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
00789 
00790         const ValueType* get() const { return (const ValueType*)m_impl.get(); }
00791         const ValueType& operator*() const { return *get(); }
00792         const ValueType* operator->() const { return get(); }
00793 
00794         HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
00795         // postfix ++ intentionally omitted
00796 
00797         typename HashTableType::const_iterator m_impl;
00798     };
00799 
00800     template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
00801         HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
00802 
00803         ValueType* get() const { return (ValueType*)m_impl.get(); }
00804         ValueType& operator*() const { return *get(); }
00805         ValueType* operator->() const { return get(); }
00806 
00807         HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
00808         // postfix ++ intentionally omitted
00809 
00810         operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
00811             typename HashTableType::const_iterator i = m_impl;
00812             return i;
00813         }
00814 
00815         typename HashTableType::iterator m_impl;
00816     };
00817 
00818     template<typename T, typename U>
00819     inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
00820     {
00821         return a.m_impl == b.m_impl;
00822     }
00823 
00824     template<typename T, typename U>
00825     inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
00826     {
00827         return a.m_impl != b.m_impl;
00828     }
00829 
00830     template<typename T, typename U>
00831     inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
00832     {
00833         return a.m_impl == b.m_impl;
00834     }
00835 
00836     template<typename T, typename U>
00837     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
00838     {
00839         return a.m_impl != b.m_impl;
00840     }
00841 
00842     // reference count manager
00843     
00844     template<typename ValueTraits, typename ValueStorageTraits> struct NeedsRef {
00845         static const bool value = ValueTraits::needsRef && !ValueStorageTraits::needsRef;
00846     };
00847     template<typename FirstTraits, typename SecondTraits, typename ValueStorageTraits>
00848     struct NeedsRef<PairBaseHashTraits<FirstTraits, SecondTraits>, ValueStorageTraits> {
00849         typedef typename ValueStorageTraits::FirstTraits FirstStorageTraits;
00850         typedef typename ValueStorageTraits::SecondTraits SecondStorageTraits;
00851         static const bool firstNeedsRef = NeedsRef<FirstTraits, FirstStorageTraits>::value;
00852         static const bool secondNeedsRef = NeedsRef<SecondTraits, SecondStorageTraits>::value;
00853         static const bool value = firstNeedsRef || secondNeedsRef;
00854     };
00855 
00856     template<bool needsRef, typename ValueTraits, typename ValueStorageTraits> struct RefCounterBase;
00857 
00858     template<typename ValueTraits, typename ValueStorageTraits>
00859     struct RefCounterBase<false, ValueTraits, ValueStorageTraits> {
00860         typedef typename ValueStorageTraits::TraitType ValueStorageType;
00861         static void ref(const ValueStorageType&) { }
00862         static void deref(const ValueStorageType&) { }
00863     };
00864 
00865     template<typename ValueTraits, typename ValueStorageTraits>
00866     struct RefCounterBase<true, ValueTraits, ValueStorageTraits> {
00867         typedef typename ValueStorageTraits::TraitType ValueStorageType;
00868         static void ref(const ValueStorageType& v) { ValueTraits::ref(v); }
00869         static void deref(const ValueStorageType& v) { ValueTraits::deref(v); }
00870     };
00871 
00872     template<typename ValueTraits, typename ValueStorageTraits> struct RefCounter {
00873         typedef typename ValueTraits::TraitType ValueType;
00874         typedef typename ValueStorageTraits::TraitType ValueStorageType;
00875         static const bool needsRef = NeedsRef<ValueTraits, ValueStorageTraits>::value;
00876         typedef RefCounterBase<needsRef, ValueTraits, ValueStorageTraits> Base;
00877         static void ref(const ValueStorageType& v) { Base::ref(v); }
00878         static void deref(const ValueStorageType& v) { Base::deref(v); }
00879     };
00880 
00881     template<typename FirstTraits, typename SecondTraits, typename ValueStorageTraits>
00882     struct RefCounter<PairBaseHashTraits<FirstTraits, SecondTraits>, ValueStorageTraits> {
00883         typedef typename FirstTraits::TraitType FirstType;
00884         typedef typename SecondTraits::TraitType SecondType;
00885         typedef typename ValueStorageTraits::FirstTraits FirstStorageTraits;
00886         typedef typename ValueStorageTraits::SecondTraits SecondStorageTraits;
00887         typedef typename ValueStorageTraits::TraitType ValueStorageType;
00888         static const bool firstNeedsRef = NeedsRef<FirstTraits, FirstStorageTraits>::value;
00889         static const bool secondNeedsRef = NeedsRef<SecondTraits, SecondStorageTraits>::value;
00890         typedef RefCounterBase<firstNeedsRef, FirstTraits, FirstStorageTraits> FirstBase;
00891         typedef RefCounterBase<secondNeedsRef, SecondTraits, SecondStorageTraits> SecondBase;
00892         static void ref(const ValueStorageType& v) {
00893             FirstBase::ref(v.first);
00894             SecondBase::ref(v.second);
00895         }
00896         static void deref(const ValueStorageType& v) {
00897             FirstBase::deref(v.first);
00898             SecondBase::deref(v.second);
00899         }
00900     };
00901 
00902     template<bool needsRef, typename HashTableType, typename ValueTraits> struct HashTableRefCounterBase;
00903 
00904     template<typename HashTableType, typename ValueTraits>
00905     struct HashTableRefCounterBase<false, HashTableType, ValueTraits>
00906     {
00907         static void refAll(HashTableType&) { }
00908         static void derefAll(HashTableType&) { }
00909     };
00910 
00911     template<typename HashTableType, typename ValueTraits>
00912     struct HashTableRefCounterBase<true, HashTableType, ValueTraits>
00913     {
00914         typedef typename HashTableType::iterator iterator;
00915         typedef RefCounter<ValueTraits, typename HashTableType::ValueTraits> ValueRefCounter;
00916         static void refAll(HashTableType&);
00917         static void derefAll(HashTableType&);
00918     };
00919 
00920     template<typename HashTableType, typename ValueTraits>
00921     void HashTableRefCounterBase<true, HashTableType, ValueTraits>::refAll(HashTableType& table)
00922     {
00923         iterator end = table.end();
00924         for (iterator it = table.begin(); it != end; ++it)
00925             ValueRefCounter::ref(*it);
00926     }
00927 
00928     template<typename HashTableType, typename ValueTraits>
00929     void HashTableRefCounterBase<true, HashTableType, ValueTraits>::derefAll(HashTableType& table)
00930     {
00931         iterator end = table.end();
00932         for (iterator it = table.begin(); it != end; ++it)
00933             ValueRefCounter::deref(*it);
00934     }
00935 
00936     template<typename HashTableType, typename ValueTraits> struct HashTableRefCounter {
00937         static const bool needsRef = NeedsRef<ValueTraits, typename HashTableType::ValueTraits>::value;
00938         typedef HashTableRefCounterBase<needsRef, HashTableType, ValueTraits> Base;
00939         static void refAll(HashTableType& table) { Base::refAll(table); }
00940         static void derefAll(HashTableType& table) { Base::derefAll(table); }
00941     };
00942 
00943     // helper template for HashMap and HashSet.
00944     template<bool needsRef, typename FromType, typename ToType, typename FromTraits> struct Assigner;
00945     
00946     template<typename FromType, typename ToType, typename FromTraits> struct Assigner<false, FromType, ToType, FromTraits> {
00947         typedef union { 
00948             FromType m_from; 
00949             ToType m_to; 
00950         } UnionType;
00951 
00952         static void assign(const FromType& from, ToType& to) { reinterpret_cast<UnionType*>(&to)->m_from = from; }
00953     };
00954     
00955     template<typename FromType, typename ToType, typename FromTraits> struct Assigner<true, FromType, ToType, FromTraits> {
00956         static void assign(const FromType& from, ToType& to) 
00957         { 
00958             ToType oldTo = to; 
00959             memcpy(&to, &from, sizeof(FromType)); 
00960             FromTraits::ref(to);
00961             FromTraits::deref(oldTo);
00962         }
00963     };
00964     
00965     template<typename FromType, typename FromTraits> struct Assigner<false, FromType, FromType, FromTraits> {
00966         static void assign(const FromType& from, FromType& to) { to = from; }
00967     };    
00968     
00969     template<typename FromType, typename FromTraits> struct Assigner<true, FromType, FromType, FromTraits> {
00970         static void assign(const FromType& from, FromType& to) { to = from; }
00971     };    
00972 
00973 } // namespace WTF
00974 
00975 #endif // WTF_HashTable_h
WTF

HashTable.h

WTF

kdelibs
