hashtable.h

linux下开源浏览器WebKit的源码,市面上的很多商用浏览器都是移植自WebKit

#else
        static void checkTableConsistencyExceptSize() { }
#endif

#if CHECK_HASHTABLE_ITERATORS
        void invalidateIterators();
#else
        static void invalidateIterators() { }
#endif

        static const int m_minTableSize = 64;
        static const int m_maxLoad = 2;
        static const int m_minLoad = 6;

        ValueType* m_table;
        int m_tableSize;
        int m_tableSizeMask;
        int m_keyCount;
        int m_deletedCount;

#if CHECK_HASHTABLE_ITERATORS
    public:
        // All access to m_iterators should be guarded with m_mutex.
        mutable const_iterator* m_iterators;
        mutable Mutex m_mutex;
#endif
    };

    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
        : m_table(0)
        , m_tableSize(0)
        , m_tableSizeMask(0)
        , m_keyCount(0)
        , m_deletedCount(0)
#if CHECK_HASHTABLE_ITERATORS
        , m_iterators(0)
#endif
    {
    }

    static inline unsigned doubleHash(unsigned key)
    {
        key = ~key + (key >> 23);
        key ^= (key << 12);
        key ^= (key >> 7);
        key ^= (key << 2);
        key ^= (key >> 20);
        return key;
    }

#if ASSERT_DISABLED

    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    template<typename T, typename HashTranslator>
    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T&)
    {
    }

#else

    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    template<typename T, typename HashTranslator>
    void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::checkKey(const T& key)
    {
        if (!HashFunctions::safeToCompareToEmptyOrDeleted)
            return;
        ASSERT(!HashTranslator::equal(KeyTraits::emptyValue(), key));
        ValueType deletedValue = Traits::emptyValue();
        deletedValue.~ValueType();
        Traits::constructDeletedValue(deletedValue);
        ASSERT(!HashTranslator::equal(Extractor::extract(deletedValue), key));
        new (&deletedValue) ValueType(Traits::emptyValue());
    }

#endif

    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    template<typename T, typename HashTranslator>
    inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
    {
        checkKey<T, HashTranslator>(key);

        int k = 0;
        int sizeMask = m_tableSizeMask;
        ValueType* table = m_table;
        unsigned h = HashTranslator::hash(key);
        int i = h & sizeMask;

        if (!table)
            return 0;

#if DUMP_HASHTABLE_STATS
        atomicIncrement(&HashTableStats::numAccesses);
        int probeCount = 0;
#endif

        while (1) {
            ValueType* entry = table + i;
                
            // we count on the compiler to optimize out this branch
            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
                if (HashTranslator::equal(Extractor::extract(*entry), key))
                    return entry;
                
                if (isEmptyBucket(*entry))
                    return 0;
            } else {
                if (isEmptyBucket(*entry))
                    return 0;
                
                if (!isDeletedBucket(*entry) && HashTranslator::equal(Extractor::extract(*entry), key))
                    return entry;
            }
#if DUMP_HASHTABLE_STATS
            ++probeCount;
            HashTableStats::recordCollisionAtCount(probeCount);
#endif
            if (k == 0)
                k = 1 | doubleHash(h);
            i = (i + k) & sizeMask;
        }
    }

    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    template<typename T, typename HashTranslator>
    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::lookupForWriting(const T& key)
    {
        ASSERT(m_table);
        checkKey<T, HashTranslator>(key);

        int k = 0;
        ValueType* table = m_table;
        int sizeMask = m_tableSizeMask;
        unsigned h = HashTranslator::hash(key);
        int i = h & sizeMask;

#if DUMP_HASHTABLE_STATS
        atomicIncrement(&HashTableStats::numAccesses);
        int probeCount = 0;
#endif

        ValueType* deletedEntry = 0;

        while (1) {
            ValueType* entry = table + i;
            
            // we count on the compiler to optimize out this branch
            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
                if (isEmptyBucket(*entry))
                    return LookupType(deletedEntry ? deletedEntry : entry, false);
                
                if (HashTranslator::equal(Extractor::extract(*entry), key))
                    return LookupType(entry, true);
                
                if (isDeletedBucket(*entry))
                    deletedEntry = entry;
            } else {
                if (isEmptyBucket(*entry))
                    return LookupType(deletedEntry ? deletedEntry : entry, false);
            
                if (isDeletedBucket(*entry))
                    deletedEntry = entry;
                else if (HashTranslator::equal(Extractor::extract(*entry), key))
                    return LookupType(entry, true);
            }
#if DUMP_HASHTABLE_STATS
            ++probeCount;
            HashTableStats::recordCollisionAtCount(probeCount);
#endif
            if (k == 0)
                k = 1 | doubleHash(h);
            i = (i + k) & sizeMask;
        }
    }

    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    template<typename T, typename HashTranslator>
    inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::fullLookupForWriting(const T& key)
    {
        ASSERT(m_table);
        checkKey<T, HashTranslator>(key);

        int k = 0;
        ValueType* table = m_table;
        int sizeMask = m_tableSizeMask;
        unsigned h = HashTranslator::hash(key);
        int i = h & sizeMask;

#if DUMP_HASHTABLE_STATS
        atomicIncrement(&HashTableStats::numAccesses);
        int probeCount = 0;
#endif

        ValueType* deletedEntry = 0;

        while (1) {
            ValueType* entry = table + i;
            
            // we count on the compiler to optimize out this branch
            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
                if (isEmptyBucket(*entry))
                    return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
                
                if (HashTranslator::equal(Extractor::extract(*entry), key))
                    return makeLookupResult(entry, true, h);
                
                if (isDeletedBucket(*entry))
                    deletedEntry = entry;
            } else {
                if (isEmptyBucket(*entry))
                    return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
            
                if (isDeletedBucket(*entry))
                    deletedEntry = entry;
                else if (HashTranslator::equal(Extractor::extract(*entry), key))
                    return makeLookupResult(entry, true, h);
            }
#if DUMP_HASHTABLE_STATS
            ++probeCount;
            HashTableStats::recordCollisionAtCount(probeCount);
#endif
            if (k == 0)
                k = 1 | doubleHash(h);
            i = (i + k) & sizeMask;
        }
    }

    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    template<typename T, typename Extra, typename HashTranslator>
    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)
    {
        checkKey<T, HashTranslator>(key);

        invalidateIterators();

        if (!m_table)
            expand();

        checkTableConsistency();

        ASSERT(m_table);

        int k = 0;
        ValueType* table = m_table;
        int sizeMask = m_tableSizeMask;
        unsigned h = HashTranslator::hash(key);
        int i = h & sizeMask;

#if DUMP_HASHTABLE_STATS
        atomicIncrement(&HashTableStats::numAccesses);
        int probeCount = 0;
#endif

        ValueType* deletedEntry = 0;
        ValueType* entry;
        while (1) {
            entry = table + i;
            
            // we count on the compiler to optimize out this branch
            if (HashFunctions::safeToCompareToEmptyOrDeleted) {
                if (isEmptyBucket(*entry))
                    break;
                
                if (HashTranslator::equal(Extractor::extract(*entry), key))
                    return std::make_pair(makeKnownGoodIterator(entry), false);
                
                if (isDeletedBucket(*entry))
                    deletedEntry = entry;
            } else {
                if (isEmptyBucket(*entry))
                    break;
            
                if (isDeletedBucket(*entry))
                    deletedEntry = entry;
                else if (HashTranslator::equal(Extractor::extract(*entry), key))
                    return std::make_pair(makeKnownGoodIterator(entry), false);
            }
#if DUMP_HASHTABLE_STATS
            ++probeCount;
            HashTableStats::recordCollisionAtCount(probeCount);
#endif
            if (k == 0)
                k = 1 | doubleHash(h);
            i = (i + k) & sizeMask;
        }

        if (deletedEntry) {
            initializeBucket(*deletedEntry);
            entry = deletedEntry;
            --m_deletedCount; 
        }

        HashTranslator::translate(*entry, key, extra);

        ++m_keyCount;
        
        if (shouldExpand()) {
            // FIXME: This makes an extra copy on expand. Probably not that bad since
            // expand is rare, but would be better to have a version of expand that can
            // follow a pivot entry and return the new position.
            KeyType enteredKey = Extractor::extract(*entry);
            expand();
            pair<iterator, bool> p = std::make_pair(find(enteredKey), true);
            ASSERT(p.first != end());
            return p;
        }
        
        checkTableConsistency();
        
        return std::make_pair(makeKnownGoodIterator(entry), true);
    }

    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    template<typename T, typename Extra, typename HashTranslator>
    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)
    {
        checkKey<T, HashTranslator>(key);

        invalidateIterators();

        if (!m_table)
            expand();

        checkTableConsistency();

        FullLookupType lookupResult = fullLookupForWriting<T, HashTranslator>(key);

        ValueType* entry = lookupResult.first.first;
        bool found = lookupResult.first.second;
        unsigned h = lookupResult.second;
        
        if (found)
            return std::make_pair(makeKnownGoodIterator(entry), false);
        
        if (isDeletedBucket(*entry)) {
            initializeBucket(*entry);
            --m_deletedCount;
        }
        
        HashTranslator::translate(*entry, key, extra, h);
        ++m_keyCount;
        if (shouldExpand()) {
            // FIXME: This makes an extra copy on expand. Probably not that bad since
            // expand is rare, but would be better to have a version of expand that can
            // follow a pivot entry and return the new position.
            KeyType enteredKey = Extractor::extract(*entry);
            expand();
            pair<iterator, bool> p = std::make_pair(find(enteredKey), true);
            ASSERT(p.first != end());
            return p;
        }

        checkTableConsistency();

        return std::make_pair(makeKnownGoodIterator(entry), true);
    }

    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)
    {
        ASSERT(m_table);
        ASSERT(!lookupForWriting(Extractor::extract(entry)).second);
        ASSERT(!isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first)));
#if DUMP_HASHTABLE_STATS
        atomicIncrement(&HashTableStats::numReinserts);
#endif

        Mover<ValueType, Traits::needsDestruction>::move(entry, *lookupForWriting(Extractor::extract(entry)).first);
    }

    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    template <typename T, typename HashTranslator> 
    typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const T& key)
    {
        if (!m_table)
            return end();

        ValueType* entry = lookup<T, HashTranslator>(key);
        if (!entry)
            return end();

        return makeKnownGoodIterator(entry);
    }

    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
    template <typename T, typename HashTranslator>