Create HeapLinkedHashSet and LinkedHashSet, ordered heap-friendly hash sets.

Source/wtf/HashTable.h

 /*
  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2008 David Levin <levin@chromium.org>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
@@ skipping 43 matching lines @@
     };
 
 #endif
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     class HashTable;
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     class HashTableIterator;
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     class HashTableConstIterator;
+    template<typename Value, typename HashFunctions, typename HashTraits, typename Allocator>
+    class LinkedHashSet;
     template<bool x, typename T, typename U, typename V, typename W, typename X, typename Y, typename Z>
     struct WeakProcessingHashTableHelper;
 
     typedef enum { HashItemKnownGood } HashItemKnownGoodTag;
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     class HashTableConstIterator {
     private:
         typedef HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> HashTableType;
         typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator> iterator;
@@ skipping 23 matching lines @@
         }
 
         HashTableConstIterator(PointerType position, PointerType endPosition, const HashTableType* container, HashItemKnownGoodTag)
             : m_position(position)
             , m_endPosition(endPosition)
 #ifdef ASSERT_ENABLED
             , m_container(container)
             , m_containerModifications(container->modifications())
 #endif
         {
+            ASSERT(m_containerModifications == m_container->modifications());
         }
 
         void checkModifications() const
         {
             // HashTable and collections that build on it do not support
             // modifications while there is an iterator in use. The exception
             // is ListHashSet, which has its own iterators that tolerate
             // modification of the underlying set.
             ASSERT(m_containerModifications == m_container->modifications());
         }
@@ skipping 248 matching lines @@
 
         void remove(KeyPeekInType);
         void remove(iterator);
         void remove(const_iterator);
         void clear();
 
         static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
         static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
         static bool isEmptyOrDeletedBucket(const ValueType& value) { return HashTableHelper<ValueType, Extractor, KeyTraits>:: isEmptyOrDeletedBucket(value); }
 
-        ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorType>(key); }
-        template<typename HashTranslator, typename T> ValueType* lookup(const T&);
+        ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorType, KeyPeekInType>(key); }
+        template<typename HashTranslator, typename T> ValueType* lookup(T);
+        template<typename HashTranslator, typename T> const ValueType* lookup(T) const;
 
         void trace(typename Allocator::Visitor*);
 
 #ifdef ASSERT_ENABLED
         int64_t modifications() const { return m_modifications; }
         void registerModification() { m_modifications++; }
+        // HashTable and collections that build on it do not support
+        // modifications while there is an iterator in use. The exception is
+        // ListHashSet, which has its own iterators that tolerate modification
+        // of the underlying set.
+        void checkModifications(int64_t mods) const { ASSERT(mods == m_modifications); }
 #else
         int64_t modifications() const { return 0; }
         void registerModification() { }
+        void checkModifications(int64_t mods) const { }
 #endif
 
     private:
         static ValueType* allocateTable(unsigned size);
         static void deleteAllBucketsAndDeallocate(ValueType* table, unsigned size);
 
         typedef std::pair<ValueType*, bool> LookupType;
         typedef std::pair<LookupType, unsigned> FullLookupType;
 
         LookupType lookupForWriting(const Key& key) { return lookupForWriting<IdentityTranslatorType>(key); };
@@ skipping 33 matching lines @@
 #ifdef ASSERT_ENABLED
         unsigned m_modifications;
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
     public:
         mutable OwnPtr<Stats> m_stats;
 #endif
 
         template<bool x, typename T, typename U, typename V, typename W, typename X, typename Y, typename Z> friend struct WeakProcessingHashTableHelper;
+        template<typename T, typename U, typename V, typename W> friend class LinkedHashSet;
     };
 
     // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
     template<unsigned size> struct OneifyLowBits;
     template<>
     struct OneifyLowBits<0> {
         static const unsigned value = 0;
     };
     template<unsigned number>
     struct OneifyLowBits {
@@ skipping 48 matching lines @@
         key = ~key + (key >> 23);
         key ^= (key << 12);
         key ^= (key >> 7);
         key ^= (key << 2);
         key ^= (key >> 20);
         return key;
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T>
-    inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(const T& key)
+    inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key)
     {
-        ValueType* table = m_table;
+        return const_cast<Value*>(const_cast<const HashTable*>(this)->lookup<HashTranslator, T>(key));
+    }
+
+    template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
+    template<typename HashTranslator, typename T>
+    inline const Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key) const
+    {
+        const ValueType* table = m_table;
         if (!table)
             return 0;
 
         size_t k = 0;
         size_t sizeMask = m_tableSizeMask;
         unsigned h = HashTranslator::hash(key);
         size_t i = h & sizeMask;
 
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numAccesses);
         int probeCount = 0;
 #endif
 
 #if DUMP_HASHTABLE_STATS_PER_TABLE
         ++m_stats->numAccesses;
         int perTableProbeCount = 0;
 #endif
 
         while (1) {
-            ValueType* entry = table + i;
+            const 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))
@@ skipping 16 matching lines @@
                 k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T>
     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::LookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookupForWriting(const T& key)
     {
         ASSERT(m_table);
+        registerModification();
 
         size_t k = 0;
         ValueType* table = m_table;
         size_t sizeMask = m_tableSizeMask;
         unsigned h = HashTranslator::hash(key);
         size_t i = h & sizeMask;
 
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numAccesses);
         int probeCount = 0;
@@ skipping 42 matching lines @@
                 k = 1 | doubleHash(h);
             i = (i + k) & sizeMask;
         }
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T>
     inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::FullLookupType HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::fullLookupForWriting(const T& key)
     {
         ASSERT(m_table);
+        registerModification();
 
         size_t k = 0;
         ValueType* table = m_table;
         size_t sizeMask = m_tableSizeMask;
         unsigned h = HashTranslator::hash(key);
         size_t i = h & sizeMask;
 
 #if DUMP_HASHTABLE_STATS
         atomicIncrement(&HashTableStats::numAccesses);
         int probeCount = 0;
@@ skipping 66 matching lines @@
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::initializeBucket(ValueType& bucket)
     {
         HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T, typename Extra>
     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::add(const T& key, const Extra& extra)
     {
+        registerModification();
         if (!m_table)
             expand();
 
         ASSERT(m_table);
 
         size_t k = 0;
         ValueType* table = m_table;
         size_t sizeMask = m_tableSizeMask;
         unsigned h = HashTranslator::hash(key);
         size_t i = h & sizeMask;
@@ skipping 62 matching lines @@
         if (shouldExpand())
             entry = expand(entry);
 
         return AddResult(entry, true);
     }
 
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
     template<typename HashTranslator, typename T, typename Extra>
     typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::addPassingHashCode(const T& key, const Extra& extra)
     {
+        registerModification();
         if (!m_table)
             expand();
 
         FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key);
 
         ValueType* entry = lookupResult.first.first;
         bool found = lookupResult.first.second;
         unsigned h = lookupResult.second;
 
         if (found)
@@ skipping 422 matching lines @@
     inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
     {
         return a.m_impl != b.m_impl;
     }
 
 } // namespace WTF
 
 #include "wtf/HashIterators.h"
 
 #endif // WTF_HashTable_h