Changeset 12162 in webkit


Ignore:
Timestamp:
Jan 17, 2006 8:33:55 PM (18 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
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r12161 r12162  
     12006-01-17  Darin Adler  <darin@apple.com>
     2
     3        Reviewed by Anders.
     4
     5        - http://bugzilla.opendarwin.org/show_bug.cgi?id=6611
     6          add assertions to check correct use of hash table iterators
     7
     8        * kxmlcore/HashTable.h:
     9        (KXMLCore::addIterator): Added. Helper function that adds an iterator to the list
     10        maintained by the specified hash table.
     11        (KXMLCore::removeIterator): Added. Helper function that removes an iterator from
     12        the list maintained by the hash table it's in.
     13        (KXMLCore::HashTableConstIterator::HashTableConstIterator): Added a HashTable
     14        parameter, ignored when not debugging. Call addIterator.
     15        (KXMLCore::HashTableConstIterator::~HashTableConstIterator):
     16        (KXMLCore::HashTableConstIterator::operator=): Call removeIterator.
     17        (KXMLCore::HashTableConstIterator::operator*): Call checkValidity.
     18        (KXMLCore::HashTableConstIterator::operator->): Ditto.
     19        (KXMLCore::HashTableConstIterator::operator++): Ditto.
     20        (KXMLCore::HashTableConstIterator::operator==): Ditto.
     21        (KXMLCore::HashTableConstIterator::operator!=): Ditto.
     22        (KXMLCore::HashTableConstIterator::checkValidity): Checks that the hash table
     23        pointer is not 0 and if there are two iterators that both point at the same table.
     24        (KXMLCore::HashTableIterator::HashTableIterator): Changed to use the const iterator
     25        as an implementation detail, to avoid having two separate iterator implementations.
     26        (KXMLCore::HashTableIterator::operator*): Ditto.
     27        (KXMLCore::HashTableIterator::operator->): Ditto.
     28        (KXMLCore::HashTableIterator::operator++): Ditto.
     29        (KXMLCore::HashTableIterator::operator==): Ditto.
     30        (KXMLCore::HashTableIterator::operator!=): Ditto.
     31        (KXMLCore::HashTable::HashTable): Initialize pointer to head of iterators list.
     32        (KXMLCore::HashTable::~HashTable): Added call to invalidateIterators.
     33        (KXMLCore::HashTable::makeIterator): Pass this pointer.
     34        (KXMLCore::HashTable::makeConstIterator): Ditto.
     35        (KXMLCore::HashTable::insert): Call invalidateIterators, since this is a public
     36        entry point that modifies the hash table.
     37        (KXMLCore::HashTable::remove): Ditto.
     38        (KXMLCore::HashTable::clear): Ditto.
     39        (KXMLCore::HashTable::swap): Ditto.
     40        (KXMLCore::HashTable::invalidateIterators): Added. Walks the iterators list and
     41        clears out the table, next, and previous pointers in all of them, and then clears
     42        the head so we have an empty list.
     43        (KXMLCore::addIterator): Added. Adds the iterator the the linked list in the
     44        passed-in table, and points the iterator at the table.
     45        (KXMLCore::removeIterator): Added. Removes the iterator from the linked list in
     46        the passed-in table.
     47
     48        * kxmlcore/HashTraits.h: A bit of tweaking and formatting.
     49
    1502006-01-17  Justin Garcia  <justin.garcia@apple.com>
    251

  • 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.