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;

[Mikhail, 2014/04/03 07:56:44]

Why is LinkedHashSet needs to be declared here?

[Mads Ager (chromium), 2014/04/03 09:24:35]

For the friend declaration below?

[Erik Corry, 2014/04/10 10:47:37]

Yes.

     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 256 matching lines @@
         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&);
 
         void trace(typename Allocator::Visitor*);
 
 #ifdef ASSERT_ENABLED
         int64_t modifications() const { return m_modifications; }
         void registerModification() { m_modifications++; }
+        void checkModifications(int64_t mods) const { }

[Mikhail, 2014/04/03 07:56:44]

Looks like the changes in this file are unnecessary (traces of
https://codereview.chromium.org/219413002/ ?)

[Mads Ager (chromium), 2014/04/03 09:24:35]

mods -> modifications.

Also, you should probably move the ASSERT code here where asserts are enabled?
;-)

This is to be able to check from the LinkedHashSet iterator that no changes have
been made to the HashTable while we have a LinkedHashSet iterator, right?  

[Erik Corry, 2014/04/10 10:47:37]

No, rather the opposite, the checkModifications methods in the other review were
unnecessary traces of this one.  I now use this and need it.

[Erik Corry, 2014/04/10 10:47:37]

Nice catch!

 #else
         int64_t modifications() const { return 0; }
         void registerModification() { }
+        // 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); }
 #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 107 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