Changeset 12162 in webkit for trunk/JavaScriptCore/kxmlcore


Ignore:
Timestamp:
Jan 17, 2006, 8:33:55 PM (19 years ago)
Author:
darin
Message:

Reviewed by Anders.

  • kxmlcore/HashTable.h: (KXMLCore::addIterator): Added. Helper function that adds an iterator to the list maintained by the specified hash table. (KXMLCore::removeIterator): Added. Helper function that removes an iterator from the list maintained by the hash table it's in. (KXMLCore::HashTableConstIterator::HashTableConstIterator): Added a HashTable parameter, ignored when not debugging. Call addIterator. (KXMLCore::HashTableConstIterator::~HashTableConstIterator): (KXMLCore::HashTableConstIterator::operator=): Call removeIterator. (KXMLCore::HashTableConstIterator::operator*): Call checkValidity. (KXMLCore::HashTableConstIterator::operator->): Ditto. (KXMLCore::HashTableConstIterator::operator++): Ditto. (KXMLCore::HashTableConstIterator::operator==): Ditto. (KXMLCore::HashTableConstIterator::operator!=): Ditto. (KXMLCore::HashTableConstIterator::checkValidity): Checks that the hash table pointer is not 0 and if there are two iterators that both point at the same table. (KXMLCore::HashTableIterator::HashTableIterator): Changed to use the const iterator as an implementation detail, to avoid having two separate iterator implementations. (KXMLCore::HashTableIterator::operator*): Ditto. (KXMLCore::HashTableIterator::operator->): Ditto. (KXMLCore::HashTableIterator::operator++): Ditto. (KXMLCore::HashTableIterator::operator==): Ditto. (KXMLCore::HashTableIterator::operator!=): Ditto. (KXMLCore::HashTable::HashTable): Initialize pointer to head of iterators list. (KXMLCore::HashTable::~HashTable): Added call to invalidateIterators. (KXMLCore::HashTable::makeIterator): Pass this pointer. (KXMLCore::HashTable::makeConstIterator): Ditto. (KXMLCore::HashTable::insert): Call invalidateIterators, since this is a public entry point that modifies the hash table. (KXMLCore::HashTable::remove): Ditto. (KXMLCore::HashTable::clear): Ditto. (KXMLCore::HashTable::swap): Ditto. (KXMLCore::HashTable::invalidateIterators): Added. Walks the iterators list and clears out the table, next, and previous pointers in all of them, and then clears the head so we have an empty list. (KXMLCore::addIterator): Added. Adds the iterator the the linked list in the passed-in table, and points the iterator at the table. (KXMLCore::removeIterator): Added. Removes the iterator from the linked list in the passed-in table.
  • kxmlcore/HashTraits.h: A bit of tweaking and formatting.
Location:
trunk/JavaScriptCore/kxmlcore
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/kxmlcore/HashTable.h

    r12069 r12162  
    22/*
    33 * This file is part of the KDE libraries
    4  * Copyright (C) 2005 Apple Computer, Inc.
     4 * Copyright (C) 2005, 2006 Apple Computer, Inc.
    55 *
    66 * This library is free software; you can redistribute it and/or
    … …  
    2727#include "HashTraits.h"
    2828#include <assert.h>
    29 #include <utility>
    3029#include <algorithm>
    3130
    … …  
    3433#define DUMP_HASHTABLE_STATS 0
    3534#define CHECK_HASHTABLE_CONSISTENCY 0
    36    
     35
     36#if NDEBUG
     37#define CHECK_HASHTABLE_ITERATORS 0
     38#else
     39#define CHECK_HASHTABLE_ITERATORS 1
     40#endif
     41
    3742#if DUMP_HASHTABLE_STATS
    38    
     43
    3944    struct HashTableStats {
    40         ~HashTableStats(); 
     45        ~HashTableStats();
    4146        static int numAccesses;
    4247        static int numCollisions;
    … …  
    4853        static void recordCollisionAtCount(int count);
    4954    };
    50    
    51 #endif
    52    
    53 #if !CHECK_HASHTABLE_CONSISTENCY
    54 #define checkTableConsistency() ((void)0)
    55 #define checkTableConsistencyExceptSize() ((void)0)
    56 #endif
    57    
    58     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     55
     56#endif
     57
     58    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    5959    class HashTable;
    60    
    61     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
    62     class HashTableIterator {
    63     private:
    64         typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> HashTableType;
    65         typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> iterator;
    66         typedef Value ValueType;
    67         typedef ValueType& ReferenceType;
    68         typedef ValueType *PointerType;
    69        
    70         friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>;
    71        
    72         void skipEmptyBuckets()
    73         {
    74             while (m_position != m_endPosition && (HashTableType::isEmptyOrDeletedBucket(*m_position))) {
    75                 ++m_position;
    76             }
    77         }
    78        
    79         HashTableIterator(PointerType position, PointerType endPosition)
    80             : m_position(position), m_endPosition(endPosition)
    81         {
    82             skipEmptyBuckets();
    83         }
    84     public:
    85         HashTableIterator() {}
    86        
    87         // default copy, assignment and destructor are ok
    88        
    89         ReferenceType operator*() const { return *m_position; }
    90         PointerType operator->() const { return &(operator*()); }
    91        
    92         iterator& operator++()
    93         {
    94             ++m_position;
    95             skipEmptyBuckets();
    96             return *this;
    97         }
    98        
    99         // postfix ++ intentionally omitted
    100        
    101         // Comparison.
    102         bool operator==(const iterator& other) const
    103         {
    104             return m_position == other.m_position;
    105         }
    106        
    107         bool operator!=(const iterator& other) const
    108         {
    109             return m_position != other.m_position;
    110         }
    111        
    112     private:
    113         PointerType m_position;
    114         PointerType m_endPosition;
    115     };
    116 
    117     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     60    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     61    class HashTableIterator;
     62    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     63    class HashTableConstIterator;
     64
     65#if CHECK_HASHTABLE_ITERATORS
     66    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     67    void addIterator(const HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>*,
     68        HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>*);
     69
     70    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     71    void removeIterator(HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>*);
     72#else
     73    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     74    inline void addIterator(const HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>*,
     75        HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>*) { }
     76
     77    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     78    inline void removeIterator(HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>*) { }
     79#endif
     80
     81    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    11882    class HashTableConstIterator {
    11983    private:
    … …  
    12387        typedef Value ValueType;
    12488        typedef const ValueType& ReferenceType;
    125         typedef const ValueType *PointerType;
    126        
     89        typedef const ValueType* PointerType;
     90
    12791        friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>;
    128        
    129         HashTableConstIterator(PointerType position, PointerType endPosition)
    130             : m_position(position), m_endPosition(endPosition)
    131         {
     92        friend class HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>;
     93
     94        void skipEmptyBuckets()
     95        {
     96            while (m_position != m_endPosition && HashTableType::isEmptyOrDeletedBucket(*m_position))
     97                ++m_position;
     98        }
     99
     100        HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition)
     101            : m_position(position), m_endPosition(endPosition)
     102        {
     103            addIterator(table, this);
    132104            skipEmptyBuckets();
    133105        }
     106
    134107    public:
    135         HashTableConstIterator() {}
    136         HashTableConstIterator(const iterator &other)
    137             : m_position(other.m_position), m_endPosition(other.m_endPosition) { }
    138        
    139         // default copy, assignment and destructor are ok
    140        
    141         ReferenceType operator*() const { return *m_position; }
    142         PointerType operator->() const { return &(operator*()); }
    143        
    144         void skipEmptyBuckets()
    145         {
    146             while (m_position != m_endPosition && (HashTableType::isEmptyOrDeletedBucket(*m_position))) {
    147                 ++m_position;
    148             }
    149         }
    150        
     108        HashTableConstIterator()
     109        {
     110            addIterator(0, this);
     111        }
     112
     113        HashTableConstIterator(const iterator& other)
     114            : m_position(other.m_position), m_endPosition(other.m_endPosition)
     115        {
     116#if CHECK_HASHTABLE_ITERATORS
     117            addIterator(other.m_table, this);
     118#endif
     119        }
     120
     121        // default copy, assignment and destructor are OK if CHECK_HASHTABLE_ITERATORS is 0
     122
     123#if CHECK_HASHTABLE_ITERATORS
     124        ~HashTableConstIterator()
     125        {
     126            removeIterator(this);
     127        }
     128
     129        HashTableConstIterator(const const_iterator& other)
     130            : m_position(other.m_position), m_endPosition(other.m_endPosition)
     131        {
     132            addIterator(other.m_table, this);
     133        }
     134
     135        const_iterator& operator=(const const_iterator& other)
     136        {
     137            m_position = other.m_position;
     138            m_endPosition = other.m_endPosition;
     139
     140            removeIterator(this);
     141            addIterator(other.m_table, this);
     142        }
     143#endif
     144
     145        ReferenceType operator*() const
     146        {
     147            checkValidity();
     148            return *m_position;
     149        }
     150        PointerType operator->() const { return &**this; }
     151
    151152        const_iterator& operator++()
    152153        {
     154            checkValidity();
     155            assert(m_position != m_endPosition);
    153156            ++m_position;
    154157            skipEmptyBuckets();
    155158            return *this;
    156159        }
    157        
     160
    158161        // postfix ++ intentionally omitted
    159        
     162
    160163        // Comparison.
    161164        bool operator==(const const_iterator& other) const
    162         {
    163             return m_position == other.m_position;
    164         }
    165        
    166         bool operator!=(const const_iterator& other) const
    167         {
    168             return m_position != other.m_position;
    169         }
    170        
     165        {
     166            checkValidity(other);
     167            return m_position == other.m_position;
     168        }
     169        bool operator!=(const const_iterator& other) const
     170        {
     171            checkValidity(other);
     172            return m_position != other.m_position;
     173        }
     174
    171175    private:
     176        void checkValidity() const
     177        {
     178#if CHECK_HASHTABLE_ITERATORS
     179            assert(m_table);
     180#endif
     181        }
     182
     183        void checkValidity(const const_iterator& other) const
     184        {
     185#if CHECK_HASHTABLE_ITERATORS
     186            assert(m_table);
     187            assert(other.m_table);
     188            assert(m_table == other.m_table);
     189#endif
     190        }
     191
    172192        PointerType m_position;
    173193        PointerType m_endPosition;
     194
     195#if CHECK_HASHTABLE_ITERATORS
     196    public:
     197        mutable const HashTableType* m_table;
     198        mutable const_iterator* m_next;
     199        mutable const_iterator* m_previous;
     200#endif
    174201    };
    175    
     202
     203    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     204    class HashTableIterator {
     205    private:
     206        typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> HashTableType;
     207        typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> iterator;
     208        typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> const_iterator;
     209        typedef Value ValueType;
     210        typedef ValueType& ReferenceType;
     211        typedef ValueType* PointerType;
     212
     213        friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>;
     214
     215        HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { }
     216
     217    public:
     218        HashTableIterator() { }
     219
     220        // default copy, assignment and destructor are OK
     221
     222        ReferenceType operator*() const { return const_cast<ReferenceType>(*m_iterator); }
     223        PointerType operator->() const { return &**this; }
     224
     225        iterator& operator++() { ++m_iterator; return *this; }
     226
     227        // postfix ++ intentionally omitted
     228
     229        // Comparison.
     230        bool operator==(const iterator& other) const { return m_iterator == other.m_iterator; }
     231        bool operator!=(const iterator& other) const { return m_iterator != other.m_iterator; }
     232
     233    private:
     234        const_iterator m_iterator;
     235    };
     236
    176237    using std::swap;
    177238
    178 #ifndef WIN32
     239#if !WIN32
    179240    // Visual C++ has a swap for pairs defined.
     241
    180242    // swap pairs by component, in case of pair members that specialize swap
    181     template<typename T, typename U>
    182     inline void swap(pair<T, U>& a, pair<T, U>& b)
     243    template<typename T, typename U> inline void swap(pair<T, U>& a, pair<T, U>& b)
    183244    {
    184245        swap(a.first, b.first);
    … …  
    187248#endif
    188249
    189     template<typename T, bool useSwap>
    190     class Mover;
    191 
    192     template<typename T>
    193     struct Mover<T, true> {
    194         static void move(T& from, T& to)
    195         {
    196             swap(from, to);
    197         }
     250    template<typename T, bool useSwap> struct Mover;
     251    template<typename T> struct Mover<T, true> { static void move(T& from, T& to) { swap(from, to); } };
     252    template<typename T> struct Mover<T, false> { static void move(T& from, T& to) { to = from; } };
     253
     254    template<typename Key, typename Value, typename HashFunctions> class IdentityHashTranslator {
     255    public:
     256        static unsigned hash(const Key& key) { return HashFunctions::hash(key); }
     257        static bool equal(const Key& a, const Key& b) { return HashFunctions::equal(a, b); }
     258        static void translate(Value& location, const Key& key, const Value& value, unsigned) { location = value; }
    198259    };
    199260
    200     template<typename T>
    201     struct Mover<T, false> {
    202         static void move(T& from, T& to)
    203         {
    204             to = from;
    205         }
    206     };
    207 
    208     template<typename Key, typename Value, typename HashFunctions>
    209     class IdentityHashTranslator {
    210        
    211     public:
    212         static unsigned hash(const Key& key)
    213         {
    214             return HashFunctions::hash(key);
    215         }
    216 
    217         static bool equal(const Key& a, const Key& b)
    218         {
    219             return HashFunctions::equal(a, b);
    220         }
    221 
    222         static void translate(Value& location, const Key& key, const Value& value, unsigned)
    223         {
    224             location = value;
    225         }
    226     };
    227 
    228     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     261    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    229262    class HashTable {
    230263    public:
    … …  
    234267        typedef Value ValueType;
    235268        typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType;
    236        
    237         HashTable() : m_table(0), m_tableSize(0), m_tableSizeMask(0), m_keyCount(0), m_deletedCount(0) {}
    238         ~HashTable() { deallocateTable(m_table, m_tableSize); }
    239        
    240         HashTable(const HashTable& other);
    241         void swap(const HashTable& other);
    242         HashTable& operator=(const HashTable& other);
    243        
     269
     270        HashTable();
     271        ~HashTable() { invalidateIterators(); deallocateTable(m_table, m_tableSize); }
     272
     273        HashTable(const HashTable&);
     274        void swap(HashTable&);
     275        HashTable& operator=(const HashTable&);
     276
    244277        iterator begin() { return makeIterator(m_table); }
    245278        iterator end() { return makeIterator(m_table + m_tableSize); }
    246279        const_iterator begin() const { return makeConstIterator(m_table); }
    247280        const_iterator end() const { return makeConstIterator(m_table + m_tableSize); }
    248        
     281
    249282        int size() const { return m_keyCount; }
    250283        int capacity() const { return m_tableSize; }
    251        
     284
    252285        pair<iterator, bool> insert(const ValueType& value) { return insert<KeyType, ValueType, IdentityTranslatorType>(ExtractKey(value), value); }
    253        
    254         // a special version of insert() that finds the object by hashing and comparing
     286
     287        // A special version of insert() that finds the object by hashing and comparing
    255288        // with some other type, to avoid the cost of type conversion if the object is already
    256         // in the table
    257         template<typename T, typename Extra, typename HashTranslator>
    258         pair<iterator, bool> insert(const T& key, const Extra& extra);
    259        
    260         iterator find(const KeyType& key);
    261         const_iterator find(const KeyType& key) const;
    262         bool contains(const KeyType& key) const;
    263        
    264         void remove(const KeyType& key);
    265         void remove(iterator it);
     289        // in the table.
     290        template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> insert(const T& key, const Extra&);
     291
     292        iterator find(const KeyType&);
     293        const_iterator find(const KeyType&) const;
     294        bool contains(const KeyType&) const;
     295
     296        void remove(const KeyType&);
     297        void remove(iterator);
    266298        void clear();
    267        
     299
    268300        static bool isEmptyBucket(const ValueType& value) { return ExtractKey(value) == KeyTraits::emptyValue(); }
    269301        static bool isDeletedBucket(const ValueType& value) { return ExtractKey(value) == KeyTraits::deletedValue(); }
    270302        static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
    271        
     303
    272304    private:
    273         static ValueType *allocateTable(int size);
    274         static void deallocateTable(ValueType *table, int size);
    275 
    276         typedef pair<ValueType *, bool> LookupType;
     305        static ValueType* allocateTable(int size);
     306        static void deallocateTable(ValueType* table, int size);
     307
     308        typedef pair<ValueType*, bool> LookupType;
    277309        typedef pair<LookupType, unsigned> FullLookupType;
    278        
     310
    279311        LookupType lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key).first; }
    280         template<typename T, typename HashTranslator>
    281         FullLookupType lookup(const T&);
    282        
    283         void remove(ValueType *);
    284        
     312        template<typename T, typename HashTranslator> FullLookupType lookup(const T&);
     313
     314        void remove(ValueType*);
     315
    285316        bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
    286317        bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
    … …  
    288319        void expand();
    289320        void shrink() { rehash(m_tableSize / 2); }
    290        
     321
    291322        void rehash(int newTableSize);
    292323        void reinsert(ValueType&);
    293        
     324
    294325        static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }
    295326        static void deleteBucket(ValueType& bucket) { assignDeleted<ValueType, Traits>(bucket); }
    296        
    297         FullLookupType makeLookupResult(ValueType *position, bool found, unsigned hash)
    298         {
    299             return FullLookupType(LookupType(position, found), hash);
    300         }
    301        
    302         iterator makeIterator(ValueType *pos) { return iterator(pos, m_table + m_tableSize); }
    303         const_iterator makeConstIterator(ValueType *pos) const { return const_iterator(pos, m_table + m_tableSize); }
    304        
     327
     328        FullLookupType makeLookupResult(ValueType* position, bool found, unsigned hash)
     329            { return FullLookupType(LookupType(position, found), hash); }
     330
     331        iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
     332        const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
     333
    305334#if CHECK_HASHTABLE_CONSISTENCY
    306335        void checkTableConsistency() const;
    307336        void checkTableConsistencyExceptSize() const;
    308 #endif
    309        
     337#else
     338        static void checkTableConsistency() { }
     339        static void checkTableConsistencyExceptSize() { }
     340#endif
     341
     342#if CHECK_HASHTABLE_ITERATORS
     343        void invalidateIterators();
     344#else
     345        static void invalidateIterators() { }
     346#endif
     347
    310348        static const int m_minTableSize = 64;
    311349        static const int m_maxLoad = 2;
    312350        static const int m_minLoad = 6;
    313        
    314         ValueType *m_table;
     351
     352        ValueType* m_table;
    315353        int m_tableSize;
    316354        int m_tableSizeMask;
    317355        int m_keyCount;
    318356        int m_deletedCount;
     357
     358#if CHECK_HASHTABLE_ITERATORS
     359    public:
     360        mutable const_iterator* m_iterators;
     361#endif
    319362    };
    320    
    321     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     363
     364    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     365    inline HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::HashTable()
     366        : m_table(0)
     367        , m_tableSize(0)
     368        , m_tableSizeMask(0)
     369        , m_keyCount(0)
     370        , m_deletedCount(0)
     371#if CHECK_HASHTABLE_ITERATORS
     372        , m_iterators(0)
     373#endif
     374    {
     375    }
     376
     377    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    322378    template<typename T, typename HashTranslator>
    323379    inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
    324380    {
    325381        assert(m_table);
    326        
     382
    327383        unsigned h = HashTranslator::hash(key);
    328384        int sizeMask = m_tableSizeMask;
    329385        int i = h & sizeMask;
    330386        int k = 0;
    331        
     387
    332388#if DUMP_HASHTABLE_STATS
    333389        ++HashTableStats::numAccesses;
    334390        int probeCount = 0;
    335391#endif
    336        
     392
    337393        ValueType *table = m_table;
    338394        ValueType *entry;
    … …  
    351407            i = (i + k) & sizeMask;
    352408        }
    353        
     409
    354410        return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
    355411    }
    356    
    357    
    358     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
    359     template<typename T, typename Extra, typename HashTranslator> 
     412
     413
     414    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     415    template<typename T, typename Extra, typename HashTranslator>
    360416    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)
    361417    {
     418        invalidateIterators();
     419
    362420        if (!m_table)
    363421            expand();
    364        
     422
    365423        checkTableConsistency();
    366        
     424
    367425        FullLookupType lookupResult = lookup<T, HashTranslator>(key);
    368        
     426
    369427        ValueType *entry = lookupResult.first.first;
    370428        bool found = lookupResult.first.second;
    371429        unsigned h = lookupResult.second;
    372        
    373         if (found) {
     430
     431        if (found)
    374432            return std::make_pair(makeIterator(entry), false);
    375         }
    376        
     433
    377434        if (isDeletedBucket(*entry))
    378435            --m_deletedCount;
    379        
     436
    380437        HashTranslator::translate(*entry, key, extra, h);
    381438        ++m_keyCount;
    382        
     439
    383440        if (shouldExpand()) {
    384441            // FIXME: this makes an extra copy on expand. Probably not that bad since
    … …  
    389446            return std::make_pair(find(enteredKey), true);
    390447        }
    391        
     448
    392449        checkTableConsistency();
    393        
     450
    394451        return std::make_pair(makeIterator(entry), true);
    395452    }
    396    
    397     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     453
     454    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    398455    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)
    399456    {
    … …  
    404461        ++HashTableStats::numReinserts;
    405462#endif
    406        
     463
    407464        Mover<ValueType, Traits::needsDestruction>::move(entry, *(lookup(ExtractKey(entry)).first));
    408465    }
    409    
    410     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     466
     467    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    411468    inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::find(const Key& key)
    412469    {
    413470        if (!m_table)
    414471            return end();
    415        
     472
    416473        LookupType result = lookup(key);
    417474        if (!result.second)
    … …  
    419476        return makeIterator(result.first);
    420477    }
    421    
    422     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     478
     479    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    423480    inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::find(const Key& key) const
    424481    {
    425482        if (!m_table)
    426483            return end();
    427        
     484
    428485        LookupType result = const_cast<HashTable *>(this)->lookup(key);
    429486        if (!result.second)
    … …  
    431488        return makeConstIterator(result.first);
    432489    }
    433    
    434     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
    435     inline bool HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const 
     490
     491    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     492    inline bool HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const
    436493    {
    437494        if (!m_table)
    438495            return false;
    439        
     496
    440497        return const_cast<HashTable *>(this)->lookup(key).second;
    441498    }
    442    
    443     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
    444     inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::remove(ValueType *pos)
    445     {
     499
     500    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     501    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
     502    {
     503        invalidateIterators();
    446504        checkTableConsistency();
    447        
     505
    448506#if DUMP_HASHTABLE_STATS
    449507        ++HashTableStats::numRemoves;
    450508#endif
    451        
     509
    452510        deleteBucket(*pos);
    453511        ++m_deletedCount;
    454512        --m_keyCount;
    455        
     513
    456514        if (shouldShrink())
    457515            shrink();
    458        
     516
    459517        checkTableConsistency();
    460518    }
    461    
    462     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     519
     520    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    463521    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
    464     { 
     522    {
    465523        if (!m_table)
    466524            return;
    467        
    468         remove(find(key)); 
    469     }
    470    
    471     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     525
     526        remove(find(key));
     527    }
     528
     529    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    472530    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::remove(iterator it)
    473     { 
     531    {
    474532        if (it == end())
    475533            return;
    476        
    477         remove(it.m_position);
    478     }
    479    
    480    
    481     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     534
     535        remove(const_cast<ValueType*>(it.m_iterator.m_position));
     536    }
     537
     538
     539    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    482540    inline Value *HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
    483541    {
    … …  
    485543        // gcc doesn't appear to support that
    486544        if (Traits::emptyValueIsZero)
    487             return reinterpret_cast<ValueType *>(fastCalloc(size, sizeof(ValueType))); 
     545            return reinterpret_cast<ValueType *>(fastCalloc(size, sizeof(ValueType)));
    488546        else {
    489             ValueType *result = reinterpret_cast<ValueType *>(fastMalloc(size * sizeof(ValueType))); 
     547            ValueType *result = reinterpret_cast<ValueType *>(fastMalloc(size * sizeof(ValueType)));
    490548            for (int i = 0; i < size; i++) {
    491549                initializeBucket(result[i]);
    … …  
    495553    }
    496554
    497     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     555    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    498556    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
    499557    {
    … …  
    506564        fastFree(table);
    507565    }
    508    
    509     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     566
     567    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    510568    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::expand()
    511     { 
     569    {
    512570        int newSize;
    513571        if (m_tableSize == 0)
    … …  
    517575        else
    518576            newSize = m_tableSize * 2;
    519        
    520         rehash(newSize); 
    521     }
    522    
    523     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     577
     578        rehash(newSize);
     579    }
     580
     581    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    524582    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize)
    525583    {
    526584        checkTableConsistencyExceptSize();
    527        
     585
    528586        int oldTableSize = m_tableSize;
    529587        ValueType *oldTable = m_table;
    530        
     588
    531589#if DUMP_HASHTABLE_STATS
    532590        if (oldTableSize != 0)
    533591            ++HashTableStats::numRehashes;
    534592#endif
    535        
     593
    536594        m_tableSize = newTableSize;
    537595        m_tableSizeMask = newTableSize - 1;
    538596        m_table = allocateTable(newTableSize);
    539        
     597
    540598        for (int i = 0; i != oldTableSize; ++i) {
    541599            if (!isEmptyOrDeletedBucket(oldTable[i]))
    542600                reinsert(oldTable[i]);
    543601        }
    544        
     602
    545603        m_deletedCount = 0;
    546        
     604
    547605        deallocateTable(oldTable, oldTableSize);
    548        
     606
    549607        checkTableConsistency();
    550608    }
    551    
    552     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     609
     610    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    553611    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::clear()
    554612    {
     613        invalidateIterators();
    555614        deallocateTable(m_table, m_tableSize);
    556615        m_table = 0;
    … …  
    559618        m_keyCount = 0;
    560619    }
    561    
    562     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     620
     621    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    563622    HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::HashTable(const HashTable& other)
    564623        : m_table(0)
    … …  
    567626        , m_keyCount(0)
    568627        , m_deletedCount(0)
    569     {
    570         // doesn't matter if copying a hashtable is efficient so just
    571         // do it the dumb way, by copying each element.
     628#if CHECK_HASHTABLE_ITERATORS
     629        , m_iterators(0)
     630#endif
     631    {
     632        // Copy the hash table the dumb way, by inserting each element into the new table.
     633        // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
    572634        const_iterator end = other.end();
    573         for (const_iterator it = other.begin(); it != end; ++it) {
     635        for (const_iterator it = other.begin(); it != end; ++it)
    574636            insert(*it);
    575         }
    576     }
    577    
    578     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
    579     void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::swap(const HashTable& other)
    580     {
     637    }
     638
     639    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     640    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::swap(HashTable& other)
     641    {
     642        invalidateIterators();
     643        other.invalidateIterators();
     644
    581645        ValueType *tmp_table = m_table;
    582646        m_table = other.m_table;
    583647        other.m_table = tmp_table;
    584        
     648
    585649        int tmp_tableSize = m_tableSize;
    586650        m_tableSize = other.m_tableSize;
    587651        other.m_tableSize = tmp_tableSize;
    588        
     652
    589653        int tmp_tableSizeMask = m_tableSizeMask;
    590654        m_tableSizeMask = other.m_tableSizeMask;
    591655        other.m_tableSizeMask = tmp_tableSizeMask;
    592        
     656
    593657        int tmp_keyCount = m_keyCount;
    594658        m_keyCount = other.m_keyCount;
    595659        other.m_keyCount = tmp_keyCount;
    596        
     660
    597661        int tmp_deletedCount = m_deletedCount;
    598662        m_deletedCount = other.m_deletedCount;
    599663        other.m_deletedCount = tmp_deletedCount;
    600664    }
    601    
    602     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     665
     666    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    603667    HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)
    604668    {
    … …  
    607671        return *this;
    608672    }
    609    
     673
    610674#if CHECK_HASHTABLE_CONSISTENCY
    611    
    612     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     675
     676    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    613677    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
    614678    {
    … …  
    617681        assert(!shouldShrink());
    618682    }
    619    
    620     template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
     683
     684    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
    621685    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
    622686    {
    623687        if (!m_table)
    624688            return;
    625        
     689
    626690        int count = 0;
    627691        int deletedCount = 0;
    … …  
    630694            if (isEmptyBucket(*entry))
    631695                continue;
    632            
     696
    633697            if (isDeletedBucket(*entry)) {
    634698                ++deletedCount;
    635699                continue;
    636700            }
    637            
     701
    638702            const_iterator it = find(ExtractKey(*entry));
    639703            assert(entry == it.m_position);
    640704            ++count;
    641705        }
    642        
     706
    643707        assert(count == m_keyCount);
    644708        assert(deletedCount == m_deletedCount);
    … …  
    647711        assert(m_tableSize == m_tableSizeMask + 1);
    648712    }
    649    
     713
    650714#endif // CHECK_HASHTABLE_CONSISTENCY
    651    
     715
     716#if CHECK_HASHTABLE_ITERATORS
     717
     718    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     719    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::invalidateIterators()
     720    {
     721        const_iterator* next;
     722        for (const_iterator* p = m_iterators; p; p = next) {
     723            next = p->m_next;
     724            p->m_table = 0;
     725            p->m_next = 0;
     726            p->m_previous = 0;
     727        }
     728        m_iterators = 0;
     729    }
     730
     731    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     732    void addIterator(const HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>* table,
     733        HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>* it)
     734    {
     735        it->m_table = table;
     736        it->m_previous = 0;
     737
     738        // Insert iterator at head of doubly-linked list of iterators.
     739        if (!table) {
     740            it->m_next = 0;
     741        } else {
     742            assert(table->m_iterators != it);
     743            it->m_next = table->m_iterators;
     744            table->m_iterators = it;
     745            if (it->m_next) {
     746                assert(!it->m_next->m_previous);
     747                it->m_next->m_previous = it;
     748            }
     749        }
     750    }
     751
     752    template<typename Key, typename Value, const Key& ExtractKey(const Value&), typename HashFunctions, typename Traits, typename KeyTraits>
     753    void removeIterator(HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>* it)
     754    {
     755        typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> HashTableType;
     756        typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> const_iterator;
     757
     758        // Delete iterator from doubly-linked list of iterators.
     759        if (!it->m_table) {
     760            assert(!it->m_next);
     761            assert(!it->m_previous);
     762        } else {
     763            if (it->m_next) {
     764                assert(it->m_next->m_previous == it);
     765                it->m_next->m_previous = it->m_previous;
     766            }
     767            if (it->m_previous) {
     768                assert(it->m_table->m_iterators != it);
     769                assert(it->m_previous->m_next == it);
     770                it->m_previous->m_next = it->m_next;
     771            } else {
     772                assert(it->m_table->m_iterators == it);
     773                it->m_table->m_iterators = it->m_next;
     774            }
     775        }
     776
     777        it->m_table = 0;
     778        it->m_next = 0;
     779        it->m_previous = 0;
     780    }
     781
     782#endif // CHECK_HASHTABLE_ITERATORS
     783
    652784} // namespace KXMLCore
    653785

  • trunk/JavaScriptCore/kxmlcore/HashTraits.h

    r11962 r12162  
    22/*
    33 * This file is part of the KDE libraries
    4  * Copyright (C) 2005 Apple Computer, Inc.
     4 * Copyright (C) 2005, 2006 Apple Computer, Inc.
    55 *
    66 * This library is free software; you can redistribute it and/or
    … …  
    3030
    3131    using std::pair;
    32    
     32
    3333    template <typename T> struct IsInteger           { static const bool value = false; };
    3434    template <> struct IsInteger<bool>               { static const bool value = true; };
    … …  
    4444    template <> struct IsInteger<long long>          { static const bool value = true; };
    4545    template <> struct IsInteger<unsigned long long> { static const bool value = true; };
    46        
    47     template<typename T>
    48     struct GenericHashTraits {
     46
     47    template<typename T> struct GenericHashTraits {
    4948        typedef T TraitType;
    5049        static const bool emptyValueIsZero = IsInteger<T>::value;
    … …  
    5352    };
    5453
    55     template<typename T>
    56     struct HashTraits : GenericHashTraits<T> {
    57     };
     54    template<typename T> struct HashTraits : GenericHashTraits<T> { };
    5855
    59     // may not be appropriate for all uses since it would disallow 0 and -1 as keys
    60     template<>
    61     struct HashTraits<int> : GenericHashTraits<int> {
     56    // may not be appropriate for all uses since it disallows 0 and -1 as keys
     57    template<> struct HashTraits<int> : GenericHashTraits<int> {
    6258        static TraitType deletedValue() { return -1; }
    6359    };
    6460
    65     template<typename P>
    66     struct HashTraits<P *> : GenericHashTraits<P *> {
    67         typedef P *TraitType;
     61    template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
     62        typedef P* TraitType;
    6863        static const bool emptyValueIsZero = true;
    6964        static const bool needsDestruction = false;
    70         static TraitType emptyValue() { return reinterpret_cast<P *>(0); }
    71         static TraitType deletedValue() { return reinterpret_cast<P *>(-1); }
     65        static TraitType emptyValue() { return 0; }
     66        static TraitType deletedValue() { return reinterpret_cast<P*>(-1); }
    7267    };
    7368
    74     template<typename P>
    75     struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
     69    template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
    7670        static const bool emptyValueIsZero = true;
    7771    };
    7872
    79     template<typename T, typename Traits>
    80     class DeletedValueAssigner;
     73    template<typename T, typename Traits> class DeletedValueAssigner;
    8174
    82     template<typename T, typename Traits>
    83     inline void assignDeleted(T& location)
     75    template<typename T, typename Traits> inline void assignDeleted(T& location)
    8476    {
    8577        DeletedValueAssigner<T, Traits>::assignDeletedValue(location);
    … …  
    9688        static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
    9789        static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
    98        
    99         static TraitType emptyValue() 
     90
     91        static TraitType emptyValue()
    10092        {
    10193            return TraitType(FirstTraits::emptyValue(), SecondTraits::emptyValue());
    10294        }
    10395
    104         static TraitType deletedValue() 
     96        static TraitType deletedValue()
    10597        {
    10698            return TraitType(FirstTraits::deletedValue(), SecondTraits::emptyValue());
    … …  
    115107
    116108    template<typename First, typename Second>
    117     struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > {
    118     };
     109    struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
    119110
    120     template<typename T, typename Traits>
    121     struct DeletedValueAssigner
    122     {
    123         static void assignDeletedValue(T& location)
    124         {
    125             location = Traits::deletedValue();
    126         }
     111    template<typename T, typename Traits> struct DeletedValueAssigner {
     112        static void assignDeletedValue(T& location) { location = Traits::deletedValue(); }
    127113    };
    128114
    … …  
    130116    struct DeletedValueAssigner<pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>, PairHashTraits<FirstTraits, SecondTraits> >
    131117    {
    132         static void assignDeletedValue(pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>& location) 
    133         { 
     118        static void assignDeletedValue(pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>& location)
     119        {
    134120            PairHashTraits<FirstTraits, SecondTraits>::assignDeletedValue(location);
    135121        }
    … …  
    139125    struct DeletedValueAssigner<pair<First, Second>, HashTraits<pair<First, Second> > >
    140126    {
    141         static void assignDeletedValue(pair<First, Second>& location) 
    142         { 
     127        static void assignDeletedValue(pair<First, Second>& location)
     128        {
    143129            HashTraits<pair<First, Second> >::assignDeletedValue(location);
    144130        }
Note: See TracChangeset for help on using the changeset viewer.