Changeset 27176 in webkit


Ignore:
Timestamp:
Oct 28, 2007, 1:17:39 AM (17 years ago)
Author:
mjs
Message:

Reviewed by Oliver.


  • numerous HashTable performance improvements


This does not quite add up to a measurable win on SunSpider, but it allows a
follow-on > 3% improvement and probably helps WebCore too.


I made the following improvements, among others:


  • Made HashFunctions note whether it is ok to compare a real value with the equal() function to the empty or deleted value, and used this to optimize the comparisons done in hash lookup.


  • Specialized lookup so it doesn't have to do so many extra branches and build so many extra std::pairs for cases that don't need them. There are now four versions, one for read-only access, two for writing, and one folded directly into add() (these all were improvments).


  • Made HashMap::get() use lookup() directly instead of find() to avoid having to build iterators.


  • Made a special constructor for iterators that knows it points to a valid filled cell and so skips updating itself.
  • Reordered memory accesses in the various lookup functions for better codegetion


  • Made simple translators avoid passing a hash code around


  • Other minor tweaks


  • wtf/HashTable.h: (WTF::): (WTF::HashTableConstIterator::HashTableConstIterator): (WTF::HashTableIterator::HashTableIterator): (WTF::IdentityHashTranslator::translate): (WTF::HashTable::end): (WTF::HashTable::lookup): (WTF::HashTable::lookupForWriting): (WTF::HashTable::makeKnownGoodIterator): (WTF::HashTable::makeKnownGoodConstIterator): (WTF::::lookup): (WTF::::lookupForWriting): (WTF::::fullLookupForWriting): (WTF::::add): (WTF::::addPassingHashCode): (WTF::::reinsert): (WTF::::find): (WTF::::contains):
  • kjs/identifier.cpp: (WTF::):
  • wtf/HashFunctions.h: (WTF::):
  • wtf/HashMap.h: (WTF::): (WTF::::get):
  • wtf/HashSet.h: (WTF::): (WTF::::add):
  • wtf/ListHashSet.h: (WTF::ListHashSetTranslator::translate):
Location:
trunk/JavaScriptCore
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r27164 r27176  
     12007-10-27  Maciej Stachowiak  <mjs@apple.com>
     2
     3        Reviewed by Oliver.
     4       
     5        - numerous HashTable performance improvements
     6       
     7        This does not quite add up to a measurable win on SunSpider, but it allows a
     8        follow-on > 3% improvement and probably helps WebCore too.
     9       
     10        I made the following improvements, among others:
     11       
     12        - Made HashFunctions note whether it is ok to compare a real value with the equal() function
     13        to the empty or deleted value, and used this to optimize the comparisons done in hash lookup.
     14       
     15        - Specialized lookup so it doesn't have to do so many extra branches and build so many extra
     16        std::pairs for cases that don't need them. There are now four versions, one for read-only access,
     17        two for writing, and one folded directly into add() (these all were improvments).
     18       
     19        - Made HashMap::get() use lookup() directly instead of find() to avoid having to build iterators.
     20       
     21        - Made a special constructor for iterators that knows it points to
     22        a valid filled cell and so skips updating itself.
     23
     24        - Reordered memory accesses in the various lookup functions for better codegetion
     25       
     26        - Made simple translators avoid passing a hash code around
     27       
     28        - Other minor tweaks
     29       
     30        * wtf/HashTable.h:
     31        (WTF::):
     32        (WTF::HashTableConstIterator::HashTableConstIterator):
     33        (WTF::HashTableIterator::HashTableIterator):
     34        (WTF::IdentityHashTranslator::translate):
     35        (WTF::HashTable::end):
     36        (WTF::HashTable::lookup):
     37        (WTF::HashTable::lookupForWriting):
     38        (WTF::HashTable::makeKnownGoodIterator):
     39        (WTF::HashTable::makeKnownGoodConstIterator):
     40        (WTF::::lookup):
     41        (WTF::::lookupForWriting):
     42        (WTF::::fullLookupForWriting):
     43        (WTF::::add):
     44        (WTF::::addPassingHashCode):
     45        (WTF::::reinsert):
     46        (WTF::::find):
     47        (WTF::::contains):
     48        * kjs/identifier.cpp:
     49        (WTF::):
     50        * wtf/HashFunctions.h:
     51        (WTF::):
     52        * wtf/HashMap.h:
     53        (WTF::):
     54        (WTF::::get):
     55        * wtf/HashSet.h:
     56        (WTF::):
     57        (WTF::::add):
     58        * wtf/ListHashSet.h:
     59        (WTF::ListHashSetTranslator::translate):
     60
    1612007-10-27  Darin Adler  <darin@apple.com>
    262

  • trunk/JavaScriptCore/kjs/identifier.cpp

    r27153 r27176  
    3939        static unsigned hash(const KJS::UString::Rep *key) { return key->hash(); }
    4040        static bool equal(const KJS::UString::Rep *a, const KJS::UString::Rep *b) { return KJS::Identifier::equal(a, b); }
     41        static const bool safeToCompareToEmptyOrDeleted = false;
    4142    };
    4243

  • trunk/JavaScriptCore/kjs/nodes.h

    r27134 r27176  
    12581258   
    12591259    // Properties that will go into the ActivationImp's local storage. (Used for initializing the ActivationImp.)
    1260      DeclarationStacks::VarStack m_varStack;
    1261      DeclarationStacks::FunctionStack m_functionStack;
    1262      Vector<Identifier> m_parameters;
     1260    DeclarationStacks::VarStack m_varStack;
     1261    DeclarationStacks::FunctionStack m_functionStack;
     1262    Vector<Identifier> m_parameters;
    12631263
    12641264    // Mapping from property name -> local storage index. (Used once to transform the AST, and subsequently for residual slow case lookups.)

  • trunk/JavaScriptCore/wtf/HashFunctions.h

    r26417 r27176  
    6666        static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
    6767        static bool equal(T a, T b) { return a == b; }
     68        static const bool safeToCompareToEmptyOrDeleted = true;
    6869    };
    6970
    … …  
    7172        static unsigned hash(T key) { return intHash(*reinterpret_cast<typename IntTypes<sizeof(T)>::UnsignedType*>(&key)); }
    7273        static bool equal(T a, T b) { return a == b; }
     74        static const bool safeToCompareToEmptyOrDeleted = true;
    7375    };
    7476
    … …  
    8890        }
    8991        static bool equal(T a, T b) { return a == b; }
     92        static const bool safeToCompareToEmptyOrDeleted = true;
    9093    };
    9194    template<typename P> struct PtrHash<RefPtr<P> > {
    9295        static unsigned hash(const RefPtr<P>& key) { return PtrHash<P*>::hash(key.get()); }
    9396        static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a == b; }
     97        static const bool safeToCompareToEmptyOrDeleted = true;
    9498    };
    9599

  • trunk/JavaScriptCore/wtf/HashMap.h

    r25365 r27176  
    130130        static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
    131131        static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
    132         static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)
     132        static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped)
    133133        {
    134134            Assigner<KeyTraits::needsRef, KeyType, KeyStorageType, KeyTraits>::assign(key, location.first);
    … …  
    151151        static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
    152152        static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
    153         static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)
     153        static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped)
    154154        {
    155155            if (location.first == KeyStorageTraits::deletedValue())
    … …  
    292292
    293293    template<typename T, typename U, typename V, typename W, typename MappedTraits>
    294     inline typename HashMap<T, U, V, W, MappedTraits>::MappedType
     294    typename HashMap<T, U, V, W, MappedTraits>::MappedType
    295295    HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const
    296296    {
    297         const_iterator it = find(key);
    298         if (it == end())
     297        if (m_impl.isEmpty())
    299298            return MappedTraits::emptyValue();
    300         return it->second;
     299        ValueStorageType* entry = const_cast<HashTableType&>(m_impl).lookup(*(const KeyStorageType*)&key);
     300        if (!entry)
     301            return MappedTraits::emptyValue();
     302        return ((ValueType *)entry)->second;
    301303    }
    302304

  • trunk/JavaScriptCore/wtf/HashSet.h

    r25365 r27176  
    112112        static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
    113113        static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
    114         static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
     114        static void translate(StorageType& location, const ValueType& key, const ValueType&)
    115115        {
    116116            Assigner<ValueTraits::needsRef, ValueType, StorageType, ValueTraits>::assign(key, location);
    … …  
    123123        static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
    124124        static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
    125         static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
     125        static void translate(StorageType& location, const ValueType& key, const ValueType&)
    126126        {
    127127            if (location == StorageTraits::deletedValue())
    … …  
    277277        const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;
    278278        typedef HashSetTranslatorAdapter<canReplaceDeletedValue, ValueType, StorageTraits, T, Translator> Adapter;
    279         return m_impl.template add<T, T, Adapter>(value, value);
     279        return m_impl.template addPassingHashCode<T, T, Adapter>(value, value);
    280280    }
    281281

  • trunk/JavaScriptCore/wtf/HashTable.h

    r27093 r27176  
    7878#endif
    7979
     80    typedef enum { HashItemKnownGood } HashItemKnownGoodTag;
     81
     82
    8083    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    8184    class HashTableConstIterator {
    … …  
    104107        }
    105108
     109        HashTableConstIterator(const HashTableType* table, PointerType position, PointerType endPosition, HashItemKnownGoodTag)
     110            : m_position(position), m_endPosition(endPosition)
     111        {
     112            addIterator(table, this);
     113        }
     114
    106115    public:
    107116        HashTableConstIterator()
    … …  
    211220
    212221        HashTableIterator(HashTableType* table, PointerType pos, PointerType end) : m_iterator(table, pos, end) { }
     222        HashTableIterator(HashTableType* table, PointerType pos, PointerType end, HashItemKnownGoodTag tag) : m_iterator(table, pos, end, tag) { }
    213223
    214224    public:
    … …  
    256266        static unsigned hash(const Key& key) { return HashFunctions::hash(key); }
    257267        static bool equal(const Key& a, const Key& b) { return HashFunctions::equal(a, b); }
    258         static void translate(Value& location, const Key&, const Value& value, unsigned) { location = value; }
     268        static void translate(Value& location, const Key&, const Value& value) { location = value; }
    259269    };
    260270
    … …  
    277287
    278288        iterator begin() { return makeIterator(m_table); }
    279         iterator end() { return makeIterator(m_table + m_tableSize); }
     289        iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
    280290        const_iterator begin() const { return makeConstIterator(m_table); }
    281         const_iterator end() const { return makeConstIterator(m_table + m_tableSize); }
     291        const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
    282292
    283293        int size() const { return m_keyCount; }
    … …  
    291301        // in the table.
    292302        template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> add(const T& key, const Extra&);
     303        template<typename T, typename Extra, typename HashTranslator> pair<iterator, bool> addPassingHashCode(const T& key, const Extra&);
    293304
    294305        iterator find(const KeyType& key) { return find<KeyType, IdentityTranslatorType>(key); }
    … …  
    308319        static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
    309320
     321        ValueType* lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key); }
     322
    310323    private:
    311324        static ValueType* allocateTable(int size);
    … …  
    315328        typedef pair<LookupType, unsigned> FullLookupType;
    316329
    317         LookupType lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key).first; }
    318         template<typename T, typename HashTranslator> FullLookupType lookup(const T&);
     330        template<typename T, typename HashTranslator> ValueType* lookup(const T&);
     331        LookupType lookupForWriting(const Key& key) { return lookupForWriting<Key, IdentityTranslatorType>(key); };
     332        template<typename T, typename HashTranslator> FullLookupType fullLookupForWriting(const T&);
     333        template<typename T, typename HashTranslator> LookupType lookupForWriting(const T&);
    319334
    320335        void remove(ValueType*);
    … …  
    337352        iterator makeIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize); }
    338353        const_iterator makeConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
     354        iterator makeKnownGoodIterator(ValueType* pos) { return iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
     355        const_iterator makeKnownGoodConstIterator(ValueType* pos) const { return const_iterator(this, pos, m_table + m_tableSize, HashItemKnownGood); }
    339356
    340357#if CHECK_HASHTABLE_CONSISTENCY
    … …  
    383400    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    384401    template<typename T, typename HashTranslator>
    385     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
     402    inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
    386403    {
    387404        ASSERT(m_table);
    388405
     406        int k = 0;
     407        int sizeMask = m_tableSizeMask;
     408        ValueType* table = m_table;
    389409        unsigned h = HashTranslator::hash(key);
    390         int sizeMask = m_tableSizeMask;
    391410        int i = h & sizeMask;
    392         int k = 0;
    393411
    394412#if DUMP_HASHTABLE_STATS
    … …  
    397415#endif
    398416
    399         ValueType* table = m_table;
    400         ValueType* deletedEntry = 0;
    401 
    402417        while (1) {
    403418            ValueType* entry = table + i;
    404 
    405             if (isEmptyBucket(*entry))
    406                 return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
    407            
    408             if (isDeletedBucket(*entry))
    409                 deletedEntry = entry;
    410             else if (HashTranslator::equal(Extractor::extract(*entry), key))
    411                 return makeLookupResult(entry, true, h);
    412 
     419               
     420            // we count on the compiler to optimize out this branch
     421            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
     422                if (HashTranslator::equal(Extractor::extract(*entry), key))
     423                    return entry;
     424               
     425                if (isEmptyBucket(*entry))
     426                    return 0;
     427            } else {
     428                if (isEmptyBucket(*entry))
     429                    return 0;
     430               
     431                if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
     432                    return entry;
     433            }
    413434#if DUMP_HASHTABLE_STATS
    414435            ++probeCount;
    … …  
    422443
    423444    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     445    template<typename T, typename HashTranslator>
     446    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key)
     447    {
     448        ASSERT(m_table);
     449
     450        int k = 0;
     451        ValueType* table = m_table;
     452        int sizeMask = m_tableSizeMask;
     453        unsigned h = HashTranslator::hash(key);
     454        int i = h & sizeMask;
     455
     456#if DUMP_HASHTABLE_STATS
     457        ++HashTableStats::numAccesses;
     458        int probeCount = 0;
     459#endif
     460
     461        ValueType* deletedEntry = 0;
     462
     463        while (1) {
     464            ValueType* entry = table + i;
     465           
     466            // we count on the compiler to optimize out this branch
     467            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
     468                if (isEmptyBucket(*entry))
     469                    return LookupType(deletedEntry ? deletedEntry : entry, false);
     470               
     471                if (HashTranslator::equal(Extractor::extract(*entry), key))
     472                    return LookupType(entry, true);
     473               
     474                if (isDeletedBucket(*entry))
     475                    deletedEntry = entry;
     476            } else {
     477                if (isEmptyBucket(*entry))
     478                    return LookupType(deletedEntry ? deletedEntry : entry, false);
     479           
     480                if (isDeletedBucket(*entry))
     481                    deletedEntry = entry;
     482                else if (HashTranslator::equal(Extractor::extract(*entry), key))
     483                    return LookupType(entry, true);
     484            }
     485#if DUMP_HASHTABLE_STATS
     486            ++probeCount;
     487            HashTableStats::recordCollisionAtCount(probeCount);
     488#endif
     489            if (k == 0)
     490                k = 1 | (h % sizeMask);
     491            i = (i + k) & sizeMask;
     492        }
     493    }
     494
     495    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     496    template<typename T, typename HashTranslator>
     497    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key)
     498    {
     499        ASSERT(m_table);
     500
     501        int k = 0;
     502        ValueType* table = m_table;
     503        int sizeMask = m_tableSizeMask;
     504        unsigned h = HashTranslator::hash(key);
     505        int i = h & sizeMask;
     506
     507#if DUMP_HASHTABLE_STATS
     508        ++HashTableStats::numAccesses;
     509        int probeCount = 0;
     510#endif
     511
     512        ValueType* deletedEntry = 0;
     513
     514        while (1) {
     515            ValueType* entry = table + i;
     516           
     517            // we count on the compiler to optimize out this branch
     518            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
     519                if (isEmptyBucket(*entry))
     520                    return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
     521               
     522                if (HashTranslator::equal(Extractor::extract(*entry), key))
     523                    return makeLookupResult(entry, true, h);
     524               
     525                if (isDeletedBucket(*entry))
     526                    deletedEntry = entry;
     527            } else {
     528                if (isEmptyBucket(*entry))
     529                    return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
     530           
     531                if (isDeletedBucket(*entry))
     532                    deletedEntry = entry;
     533                else if (HashTranslator::equal(Extractor::extract(*entry), key))
     534                    return makeLookupResult(entry, true, h);
     535            }
     536#if DUMP_HASHTABLE_STATS
     537            ++probeCount;
     538            HashTableStats::recordCollisionAtCount(probeCount);
     539#endif
     540            if (k == 0)
     541                k = 1 | (h % sizeMask);
     542            i = (i + k) & sizeMask;
     543        }
     544    }
     545
     546    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    424547    template<typename T, typename Extra, typename HashTranslator>
    425     inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(const T& key, const Extra &extra)
     548    inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::add(const T& key, const Extra& extra)
    426549    {
    427550        invalidateIterators();
    … …  
    432555        checkTableConsistency();
    433556
    434         FullLookupType lookupResult = lookup<T, HashTranslator>(key);
    435 
    436         ValueType *entry = lookupResult.first.first;
    437         bool found = lookupResult.first.second;
    438         unsigned h = lookupResult.second;
    439 
    440         if (found)
    441             return std::make_pair(makeIterator(entry), false);
    442 
    443         if (isDeletedBucket(*entry))
    444             --m_deletedCount;
    445 
    446         HashTranslator::translate(*entry, key, extra, h);
     557        ASSERT(m_table);
     558
     559        int k = 0;
     560        ValueType* table = m_table;
     561        int sizeMask = m_tableSizeMask;
     562        unsigned h = HashTranslator::hash(key);
     563        int i = h & sizeMask;
     564
     565#if DUMP_HASHTABLE_STATS
     566        ++HashTableStats::numAccesses;
     567        int probeCount = 0;
     568#endif
     569
     570        ValueType* deletedEntry = 0;
     571        ValueType* entry;
     572        while (1) {
     573            entry = table + i;
     574           
     575            // we count on the compiler to optimize out this branch
     576            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
     577                if (isEmptyBucket(*entry))
     578                    break;
     579               
     580                if (HashTranslator::equal(Extractor::extract(*entry), key))
     581                    return std::make_pair(makeKnownGoodIterator(entry), false);
     582               
     583                if (isDeletedBucket(*entry))
     584                    deletedEntry = entry;
     585            } else {
     586                if (isEmptyBucket(*entry))
     587                    break;
     588           
     589                if (isDeletedBucket(*entry))
     590                    deletedEntry = entry;
     591                else if (HashTranslator::equal(Extractor::extract(*entry), key))
     592                    return std::make_pair(makeKnownGoodIterator(entry), false);
     593            }
     594#if DUMP_HASHTABLE_STATS
     595            ++probeCount;
     596            HashTableStats::recordCollisionAtCount(probeCount);
     597#endif
     598            if (k == 0)
     599                k = 1 | (h % sizeMask);
     600            i = (i + k) & sizeMask;
     601        }
     602
     603        if (deletedEntry) {
     604            entry = deletedEntry;
     605            --m_deletedCount;
     606        }
     607
     608        HashTranslator::translate(*entry, key, extra);
     609
    447610        ++m_keyCount;
    448 
     611       
    449612        if (shouldExpand()) {
    450613            // FIXME: this makes an extra copy on expand. Probably not that bad since
    … …  
    455618            return std::make_pair(find(enteredKey), true);
    456619        }
    457 
     620       
    458621        checkTableConsistency();
    459 
    460         return std::make_pair(makeIterator(entry), true);
     622       
     623        return std::make_pair(makeKnownGoodIterator(entry), true);
     624    }
     625
     626    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     627    template<typename T, typename Extra, typename HashTranslator>
     628    inline pair<typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::addPassingHashCode(const T& key, const Extra& extra)
     629    {
     630        invalidateIterators();
     631
     632        if (!m_table)
     633            expand();
     634
     635        checkTableConsistency();
     636
     637        FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key);
     638
     639        ValueType *entry = lookupResult.first.first;
     640        bool found = lookupResult.first.second;
     641        unsigned h = lookupResult.second;
     642       
     643        if (found)
     644            return std::make_pair(makeKnownGoodIterator(entry), false);
     645       
     646        if (isDeletedBucket(*entry))
     647            --m_deletedCount;
     648       
     649        HashTranslator::translate(*entry, key, extra, h);
     650        ++m_keyCount;
     651        if (shouldExpand()) {
     652            // FIXME: this makes an extra copy on expand. Probably not that bad since
     653            // expand is rare, but would be better to have a version of expand that can
     654            // follow a pivot entry and return the new position
     655            KeyType enteredKey = Extractor::extract(*entry);
     656            expand();
     657            return std::make_pair(find(enteredKey), true);
     658        }
     659
     660        checkTableConsistency();
     661
     662        return std::make_pair(makeKnownGoodIterator(entry), true);
    461663    }
    462664
    … …  
    465667    {
    466668        ASSERT(m_table);
    467         ASSERT(!lookup(Extractor::extract(entry)).second);
    468         ASSERT(!isDeletedBucket(*(lookup(Extractor::extract(entry)).first)));
     669        ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
     670        ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
    469671#if DUMP_HASHTABLE_STATS
    470672        ++HashTableStats::numReinserts;
    471673#endif
    472674
    473         Mover<ValueType, Traits::needsDestruction>::move(entry, *(lookup(Extractor::extract(entry)).first));
     675        Mover<ValueType, Traits::needsDestruction>::move(entry, *(lookupForWriting(Extractor::extract(entry)).first));
    474676    }
    475677
    … …  
    481683            return end();
    482684
    483         LookupType result = lookup<T, HashTranslator>(key).first;
    484         if (!result.second)
     685        ValueType* entry = lookup<T, HashTranslator>(key);
     686        if (!entry)
    485687            return end();
    486         return makeIterator(result.first);
     688
     689        return makeKnownGoodIterator(entry);
    487690    }
    488691
    … …  
    494697            return end();
    495698
    496         LookupType result = const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key).first;
    497         if (!result.second)
     699        ValueType* entry = const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key);
     700        if (!entry)
    498701            return end();
    499         return makeConstIterator(result.first);
     702
     703        return makeKnownGoodConstIterator(entry);
    500704    }
    501705
    … …  
    507711            return false;
    508712
    509         return const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key).first.second;
     713        return const_cast<HashTable *>(this)->lookup<T, HashTranslator>(key);
    510714    }
    511715

  • trunk/JavaScriptCore/wtf/ListHashSet.h

    r21175 r27176  
    221221        static unsigned hash(Node* const& key) { return HashArg::hash(key->m_value); }
    222222        static bool equal(Node* const& a, Node* const& b) { return HashArg::equal(a->m_value, b->m_value); }
     223        static const bool safeToCompareToEmptyOrDeleted = false;
    223224    };
    224225
    … …  
    341342        static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
    342343        static bool equal(Node* const& a, const ValueType& b) { return HashFunctions::equal(a->m_value, b); }
    343         static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator, unsigned)
     344        static void translate(Node*& location, const ValueType& key, NodeAllocator* allocator)
    344345        {
    345346            location = new (allocator) Node(key);
Note: See TracChangeset for help on using the changeset viewer.