Ignore:
Timestamp:
Dec 22, 2005, 5:52:43 PM (19 years ago)
Author:
mjs
Message:

JavaScriptCore:

Reviewed by Darin.

The changes for support are relatively simple, but I also made extensive changes to
avoid copying, so that there isn't refcount thrash when you put RefPtrs into a HashMap.

  • kxmlcore/HashTable.h: (KXMLCore::swap): specialize swap for pairs, to swap elements individually, so that excess copies can be avoided. (KXMLCore::Mover::move): Template function to either copy or swap, used when transferring elements from old table to new. (KXMLCore::IdentityHashTranslator::hash): The old "converting lookup" templates that took two or three function parameters now take a class parameter, this is the class used to do a normal lookup. (KXMLCore::IdentityHashTranslator::equal): Ditto. (KXMLCore::IdentityHashTranslator::translate): Ditto. Translate now takes a reference to write into instead of returning a value to avoid redundant copies. (KXMLCore::HashTable::~HashTable): Use deallocateTable instead of freeing directly. (KXMLCore::HashTable::insert): Based on HashTranslator now instead of separate functions. Added a FIXME about a remaining rare excess copy. (KXMLCore::HashTable::isEmptyBucket): Use KeyTraits directly instead of unwrapping the key from Traits, to avoid creating and destroying pair, which copies. (KXMLCore::HashTable::isDeletedBucket): ditto (KXMLCore::HashTable::lookup): Use HashTranslator now instead of separate functions. (KXMLCore::HashTable::initializeBucket): Renamed from emptyBucket. Use placement new to work right for non-POD types. (KXMLCore::HashTable::deleteBucket): Use assignDeleted to avoid excess copies. (KXMLCore::HashTable::reinsert): use Mover template to copy or swap as appropriate (KXMLCore::HashTable::allocateTable): Initialize every bucket if calloc won't do. (KXMLCore::HashTable::deallocateTable): Destruct every bucket if needed. (KXMLCore::HashTable::rehash): Avoid copy before reinserting, so that swap can do its magic. (KXMLCore::HashTable::clear): use deallocateTable instead of freeing directly. (KXMLCore::HashTable::HashTable): be more dumb when copying to ensure that non-POD types work right
  • kxmlcore/HashFunctions.h: (KXMLCore::PointerHash): Specialize PointerHash for RefPtr
  • kxmlcore/HashMap.h: (KXMLCore::extractFirst): Return a reference not a full object to avoid copies. (KXMLCore::HashMapTranslator::hash): Use a special translator for insertion to defer making the pair as long as possible, thus avoiding needless copies. (KXMLCore::HashMapTranslator::equal): ditto (KXMLCore::HashMapTranslator::translate): ditto (KXMLCore::::inlineAdd): Shared by set and add to insert using HashMapTranslator (KXMLCore::::set): Use inlineAdd (KXMLCore::::add): Use inlineAdd
  • kxmlcore/HashMapPtrSpec.h: (KXMLCore::): Pass KeyTraits along
  • kxmlcore/HashSet.h: (KXMLCore::identityExtract): Return a reference not a full object to avoid copies. (KXMLCore::HashSetTranslatorAdapter::hash): Redo adapter stuff to work with the new HashTranslator approach. (KXMLCore::HashSetTranslatorAdapter::equal): ditto (KXMLCore::HashSetTranslatorAdapter::translate): ditto (KXMLCore::::insert): ditto
  • kxmlcore/HashTraits.h: (KXMLCore::GenericHashTraits): This is intended be used as a base class for customized traits: sensible defaults. (KXMLCore::): Use it a bunch (KXMLCore::assignDeleted): template function to allow pairs to be assigned the deleted value w/o excess copies. (KXMLCore::PairHashTraits::emptyValue): Updated (KXMLCore::PairHashTraits::deletedValue): Updated (KXMLCore::PairHashTraits::assignDeletedValue): part of assignDeleted hack (KXMLCore::DeletedValueAssigner::assignDeletedValue): Use template magic to either use use deletedValue or assignDeletedValue for the cases where we care.
  • kxmlcore/RefPtr.h: (KXMLCore::RefPtr::swap): Added swap method. (KXMLCore::swap): Added swap free function.
  • kjs/identifier.cpp: (KJS::CStringTranslator::hash): Use new HashTranslator class approach to alternate type based insertion. (KJS::CStringTranslator::equal): ditto (KJS::CStringTranslator::translate): ditto (KJS::Identifier::add): ditto (KJS::UCharBufferTranslator::hash): ditto (KJS::UCharBufferTranslator::equal): ditto (KJS::UCharBufferTranslator::translate): ditto
  • irrelevant change:
  • kjs/array_object.cpp: (ArrayProtoFunc::callAsFunction): Removed a stray space.

WebCore:

Reviewed by Darin.

  • update for new HashTranslator stuff
  • khtml/xml/dom_atomicstring.cpp: (DOM::CStringTranslator::hash): (DOM::CStringTranslator::equal): (DOM::CStringTranslator::translate): (DOM::AtomicString::equal): (DOM::AtomicString::add): (DOM::QCharBufferTranslator::hash): (DOM::QCharBufferTranslator::equal): (DOM::QCharBufferTranslator::translate):
  • khtml/xml/dom_qname.cpp: (DOM::QNameComponentsTranslator::hash): (DOM::QNameComponentsTranslator::equal): (DOM::QNameComponentsTranslator::translate): (DOM::QualifiedName::QualifiedName):
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/kxmlcore/HashTable.h

    r10653 r11739  
    2525
    2626#include "FastMalloc.h"
     27#include "HashTraits.h"
    2728#include <utility>
     29#include <algorithm>
    2830
    2931namespace KXMLCore {
    … …  
    5355#endif
    5456   
    55     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
     57    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
    5658    class HashTable;
    5759   
    58     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
     60    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
    5961    class HashTableIterator {
    6062    private:
    61         typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits> HashTableType;
    62         typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
     63        typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> HashTableType;
     64        typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> iterator;
    6365        typedef Value ValueType;
    6466        typedef ValueType& ReferenceType;
    6567        typedef ValueType *PointerType;
    6668       
    67         friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits>;
     69        friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>;
    6870       
    6971        void skipEmptyBuckets()
    … …  
    112114    };
    113115
    114     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
     116    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
    115117    class HashTableConstIterator {
    116118    private:
    117         typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits> HashTableType;
    118         typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
    119         typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits> const_iterator;
     119        typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> HashTableType;
     120        typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> iterator;
     121        typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> const_iterator;
    120122        typedef Value ValueType;
    121123        typedef const ValueType& ReferenceType;
    122124        typedef const ValueType *PointerType;
    123125       
    124         friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits>;
     126        friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>;
    125127       
    126128        HashTableConstIterator(PointerType position, PointerType endPosition)
    … …  
    171173    };
    172174   
    173     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
     175    using std::swap;
     176
     177    // swap pairs by component, in case of pair members that specialize swap
     178    template<typename T, typename U>
     179    inline void swap(pair<T, U>& a, pair<T, U>& b)
     180    {
     181        swap(a.first, b.first);
     182        swap(a.second, b.second);
     183    }
     184
     185    template<typename T, bool useSwap>
     186    class Mover;
     187
     188    template<typename T>
     189    struct Mover<T, true> {
     190        static void move(T& from, T& to)
     191        {
     192            swap(from, to);
     193        }
     194    };
     195
     196    template<typename T>
     197    struct Mover<T, false> {
     198        static void move(T& from, T& to)
     199        {
     200            to = from;
     201        }
     202    };
     203
     204    template<typename Key, typename Value, typename HashFunctions>
     205    class IdentityHashTranslator {
     206       
     207    public:
     208        static unsigned hash(const Key& key)
     209        {
     210            return HashFunctions::hash(key);
     211        }
     212
     213        static bool equal(const Key& a, const Key& b)
     214        {
     215            return HashFunctions::equal(a, b);
     216        }
     217
     218        static void translate(Value& location, const Key& key, const Value& value, unsigned)
     219        {
     220            location = value;
     221        }
     222    };
     223
     224    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
    174225    class HashTable {
    175226    public:
    176         typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
    177         typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits> const_iterator;
     227        typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> iterator;
     228        typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> const_iterator;
    178229        typedef Key KeyType;
    179230        typedef Value ValueType;
     231        typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType;
    180232       
    181233        HashTable() : m_table(0), m_tableSize(0), m_tableSizeMask(0), m_keyCount(0), m_deletedCount(0) {}
    182         ~HashTable() { fastFree(m_table); }
     234        ~HashTable() { deallocateTable(m_table, m_tableSize); }
    183235       
    184236        HashTable(const HashTable& other);
    … …  
    194246        int capacity() const { return m_tableSize; }
    195247       
    196         std::pair<iterator, bool> insert(const ValueType& value) { return insert<KeyType, ValueType, hash, equal, identityConvert>(extractKey(value), value); }
     248        pair<iterator, bool> insert(const ValueType& value) { return insert<KeyType, ValueType, IdentityTranslatorType>(ExtractKey(value), value); }
    197249       
    198250        // a special version of insert() that finds the object by hashing and comparing
    199251        // with some other type, to avoid the cost of type conversion if the object is already
    200252        // in the table
    201         template<typename T, typename Extra, unsigned HashT(const T&), bool EqualT(const Key&, const T&), ValueType ConvertT(const T&, const Extra &, unsigned)>
    202         std::pair<iterator, bool> insert(const T& key, const Extra& extra);
     253        template<typename T, typename Extra, typename HashTranslator>
     254        pair<iterator, bool> insert(const T& key, const Extra& extra);
    203255       
    204256        iterator find(const KeyType& key);
    … …  
    210262        void clear();
    211263       
    212         static bool isEmptyBucket(const ValueType& value) { return extractKey(value) == extractKey(Traits::emptyValue()); }
    213         static bool isDeletedBucket(const ValueType& value) { return extractKey(value) == extractKey(Traits::deletedValue()); }
     264        static bool isEmptyBucket(const ValueType& value) { return ExtractKey(value) == KeyTraits::emptyValue(); }
     265        static bool isDeletedBucket(const ValueType& value) { return ExtractKey(value) == KeyTraits::deletedValue(); }
    214266        static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
    215267       
    216268    private:
    217         static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
    218         static bool equal(const KeyType& a, const KeyType& b) { return HashFunctions::equal(a, b); }                   
    219         // FIXME: assumes key == value; special lookup needs adjusting
    220         static ValueType identityConvert(const KeyType& key, const ValueType& value, unsigned) { return value; }
    221         static KeyType extractKey(const ValueType& value) { return ExtractKey(value); }
    222        
    223269        static ValueType *allocateTable(int size);
    224        
    225         typedef std::pair<ValueType *, bool> LookupType;
    226         typedef std::pair<LookupType, unsigned> FullLookupType;
    227        
    228         LookupType lookup(const Key& key) { return lookup<Key, hash, equal>(key).first; }
    229         template<typename T, unsigned HashT(const T&), bool EqualT(const Key&, const T&)>
     270        static void deallocateTable(ValueType *table, int size);
     271
     272        typedef pair<ValueType *, bool> LookupType;
     273        typedef pair<LookupType, unsigned> FullLookupType;
     274       
     275        LookupType lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key).first; }
     276        template<typename T, typename HashTranslator>
    230277        FullLookupType lookup(const T&);
    231278       
    … …  
    239286       
    240287        void rehash(int newTableSize);
    241         void reinsert(const ValueType&);
    242        
    243         static void clearBucket(ValueType& key) { key = Traits::emptyValue();}
    244         static void deleteBucket(ValueType& key) { key = Traits::deletedValue();}
     288        void reinsert(ValueType&);
     289       
     290        static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }
     291        static void deleteBucket(ValueType& bucket) { assignDeleted<ValueType, Traits>(bucket); }
    245292       
    246293        FullLookupType makeLookupResult(ValueType *position, bool found, unsigned hash)
    … …  
    268315    };
    269316   
    270     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    271     template<typename T, unsigned HashT(const T&), bool EqualT(const Key&, const T&)>
    272     inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::FullLookupType HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::lookup(const T& key)
     317    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     318    template<typename T, typename HashTranslator>
     319    inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
    273320    {
    274321        assert(m_table);
    275322       
    276         unsigned h = HashT(key);
     323        unsigned h = HashTranslator::hash(key);
    277324        int sizeMask = m_tableSizeMask;
    278325        int i = h & sizeMask;
    … …  
    290337            if (isDeletedBucket(*entry))
    291338                deletedEntry = entry;
    292             else if (EqualT(extractKey(*entry), key))
     339            else if (HashTranslator::equal(ExtractKey(*entry), key))
    293340                return makeLookupResult(entry, true, h);
    294341#if DUMP_HASHTABLE_STATS
    … …  
    305352   
    306353   
    307     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    308     template<typename T, typename Extra, unsigned HashT(const T&), bool EqualT(const Key&, const T&), Value ConvertT(const T&, const Extra &, unsigned)>
    309     inline std::pair<typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::iterator, bool> HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::insert(const T& key, const Extra &extra)
     354    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     355    template<typename T, typename Extra, typename HashTranslator>
     356    inline pair<typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::insert(const T& key, const Extra &extra)
    310357    {
    311358        if (!m_table)
    … …  
    314361        checkTableConsistency();
    315362       
    316         FullLookupType lookupResult = lookup<T, HashT, EqualT>(key);
     363        FullLookupType lookupResult = lookup<T, HashTranslator>(key);
    317364       
    318365        ValueType *entry = lookupResult.first.first;
    … …  
    327374            --m_deletedCount;
    328375       
    329         *entry = ConvertT(key, extra, h);
     376        HashTranslator::translate(*entry, key, extra, h);
    330377        ++m_keyCount;
    331378       
    332379        if (shouldExpand()) {
    333             KeyType enteredKey = extractKey(*entry);
     380            // FIXME: this makes an extra copy on expand. Probably not that bad since
     381            // expand is rare, but would be better to have a version of expand that can
     382            // follow a pivot entry and return the new position
     383            KeyType enteredKey = ExtractKey(*entry);
    334384            expand();
    335385            return std::make_pair(find(enteredKey), true);
    … …  
    341391    }
    342392   
    343     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    344     inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::reinsert(const ValueType& entry)
     393    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     394    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)
    345395    {
    346396        assert(m_table);
    347         assert(!lookup(extractKey(entry)).second);
    348         assert(!isDeletedBucket(*(lookup(extractKey(entry)).first)));
     397        assert(!lookup(ExtractKey(entry)).second);
     398        assert(!isDeletedBucket(*(lookup(ExtractKey(entry)).first)));
    349399#if DUMP_HASHTABLE_STATS
    350400        ++HashTableStats::numReinserts;
    351401#endif
    352402       
    353         *(lookup(extractKey(entry)).first) = entry;
    354     }
    355    
    356     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    357     inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::find(const Key& key)
     403        Mover<ValueType, Traits::needsDestruction>::move(entry, *(lookup(ExtractKey(entry)).first));
     404    }
     405   
     406    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     407    inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::find(const Key& key)
    358408    {
    359409        if (!m_table)
    … …  
    366416    }
    367417   
    368     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    369     inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::const_iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::find(const Key& key) const
     418    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     419    inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::find(const Key& key) const
    370420    {
    371421        if (!m_table)
    … …  
    378428    }
    379429   
    380     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    381     inline bool HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::contains(const KeyType& key) const
     430    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     431    inline bool HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const
    382432    {
    383433        if (!m_table)
    … …  
    387437    }
    388438   
    389     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    390     inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::remove(ValueType *pos)
     439    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     440    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::remove(ValueType *pos)
    391441    {
    392442        checkTableConsistency();
    … …  
    406456    }
    407457   
    408     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    409     inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::remove(const KeyType& key)
     458    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     459    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
    410460    {
    411461        if (!m_table)
    … …  
    415465    }
    416466   
    417     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    418     inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::remove(iterator it)
     467    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     468    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::remove(iterator it)
    419469    {
    420470        if (it == end())
    … …  
    425475   
    426476   
    427     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    428     inline Value *HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::allocateTable(int size)
     477    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     478    inline Value *HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
    429479    {
    430480        // would use a template member function with explicit specializations here, but
    … …  
    435485            ValueType *result = reinterpret_cast<ValueType *>(fastMalloc(size * sizeof(ValueType)));
    436486            for (int i = 0; i < size; i++) {
    437                 clearBucket(result[i]);
     487                initializeBucket(result[i]);
    438488            }
    439489            return result;
    440490        }
    441491    }
    442    
    443     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    444     inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::expand()
     492
     493    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     494    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
     495    {
     496        if (Traits::needsDestruction) {
     497            for (int i = 0; i < size; ++i) {
     498                (&table[i])->~ValueType();
     499            }
     500        }
     501
     502        fastFree(table);
     503    }
     504   
     505    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     506    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::expand()
    445507    {
    446508        int newSize;
    … …  
    455517    }
    456518   
    457     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    458     void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::rehash(int newTableSize)
     519    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     520    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize)
    459521    {
    460522        checkTableConsistencyExceptSize();
    … …  
    473535       
    474536        for (int i = 0; i != oldTableSize; ++i) {
    475             ValueType entry = oldTable[i];
    476             if (!isEmptyOrDeletedBucket(entry))
    477                 reinsert(entry);
     537            if (!isEmptyOrDeletedBucket(oldTable[i]))
     538                reinsert(oldTable[i]);
    478539        }
    479540       
    480541        m_deletedCount = 0;
    481542       
    482         fastFree(oldTable);
     543        deallocateTable(oldTable, oldTableSize);
    483544       
    484545        checkTableConsistency();
    485546    }
    486547   
    487     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    488     inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::clear()
    489     {
    490         fastFree(m_table);
     548    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     549    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::clear()
     550    {
     551        deallocateTable(m_table, m_tableSize);
    491552        m_table = 0;
    492553        m_tableSize = 0;
    … …  
    495556    }
    496557   
    497     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    498     HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::HashTable(const HashTable& other)
     558    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     559    HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
    499560        : m_table(0)
    500           , m_tableSize(other.m_tableSize)
    501           , m_tableSizeMask(other.m_tableSizeMask)
    502           , m_keyCount(other.m_keyCount)
    503           , m_deletedCount(other.m_deletedCount)
    504     {
    505         if (m_tableSize != 0) {
    506             m_table = fastMalloc(m_tableSize);
    507             memcpy(other.m_table, m_table, m_tableSize * sizeof(ValueType));
    508         }
    509     }
    510    
    511     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    512     void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::swap(const HashTable& other)
     561        , m_tableSize(0)
     562        , m_tableSizeMask(0)
     563        , m_keyCount(0)
     564        , m_deletedCount(0)
     565    {
     566        // doesn't matter if copying a hashtable is efficient so just
     567        // do it the dumb way, by copying each element.
     568        iterator end = other.end();
     569        for (iterator it = other.begin(); it != end; ++it) {
     570            insert(*it);
     571        }
     572    }
     573   
     574    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     575    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::swap(const HashTable& other)
    513576    {
    514577        ValueType *tmp_table = m_table;
    … …  
    533596    }
    534597   
    535     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    536     HashTable<Key, Value, ExtractKey, HashFunctions, Traits>& HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::operator=(const HashTable& other)
     598    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     599    HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)
    537600    {
    538601        HashTable tmp(other);
    … …  
    543606#if CHECK_HASHTABLE_CONSISTENCY
    544607   
    545     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    546     void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::checkTableConsistency() const
     608    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     609    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
    547610    {
    548611        checkTableConsistencyExceptSize();
    … …  
    551614    }
    552615   
    553     template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
    554     void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::checkTableConsistencyExceptSize() const
     616    template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     617    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
    555618    {
    556619        if (!m_table)
    … …  
    569632            }
    570633           
    571             const_iterator it = find(extractKey(*entry));
     634            const_iterator it = find(ExtractKey(*entry));
    572635            assert(entry == it.m_position);
    573636            ++count;
Note: See TracChangeset for help on using the changeset viewer.