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

Source/heap/Heap.h

Index: Source/heap/Heap.h
diff --git a/Source/heap/Heap.h b/Source/heap/Heap.h
index b00320f91886fceae29663f759a6f703ed4a3210..8726dc81e0e28a5b95e7558d857adc27bffc0f4e 100644
--- a/Source/heap/Heap.h
+++ b/Source/heap/Heap.h
@@ -37,6 +37,7 @@
 #include "heap/Visitor.h"
 
 #include "wtf/Assertions.h"
+#include "wtf/LinkedHashSet.h"
 #include "wtf/OwnPtr.h"
 #include "wtf/PassRefPtr.h"
 
@@ -1288,6 +1289,9 @@ public:
         return hasDeadMember(visitor, t.key) || hasDeadMember(visitor, t.value);
     }
 
+    template<typename T>
+    static bool hasDeadMember(Visitor*, const WTF::LinkedHashSetNode<T>&);
+
     static void registerWeakMembers(Visitor* visitor, const void* closure, const void* object, WeakPointerCallback callback)
     {
         visitor->registerWeakMembers(closure, object, callback);
@@ -1355,6 +1359,12 @@ template<
     typename TraitsArg = HashTraits<ValueArg> >
 class HeapHashSet : public HashSet<ValueArg, HashArg, TraitsArg, HeapAllocator> { };
 
+template<
+    typename ValueArg,
+    typename HashArg = typename DefaultHash<ValueArg>::Hash,
+    typename TraitsArg = HashTraits<ValueArg> >
+class HeapLinkedHashSet : public LinkedHashSet<ValueArg, HashArg, TraitsArg, HeapAllocator> { };
+
 template<typename T, size_t inlineCapacity = 0>
 class HeapVector : public Vector<T, inlineCapacity, HeapAllocator> {
 public:
@@ -1389,6 +1399,12 @@ public:
 };
 
 template<typename T>
+bool HeapAllocator::hasDeadMember(Visitor* visitor, const WTF::LinkedHashSetNode<T>& t)
+{
+    return hasDeadMember(visitor, t.m_value);
+}
+
+template<typename T>
 struct ThreadingTrait<Member<T> > {
     static const ThreadAffinity Affinity = ThreadingTrait<T>::Affinity;
 };
@@ -1477,6 +1493,19 @@ const GCInfo GCInfoTrait<HashSet<T, U, V, HeapAllocator> >::info = {
     false, // HashSet needs no finalizer.
 };
 
+template<typename T, typename U, typename V>
+struct GCInfoTrait<LinkedHashSet<T, U, V, HeapAllocator> > {
+    static const GCInfo* get() { return &info; }
+    static const GCInfo info;
+};  
+
+template<typename T, typename U, typename V>
+const GCInfo GCInfoTrait<LinkedHashSet<T, U, V, HeapAllocator> >::info = {
+    TraceTrait<LinkedHashSet<T, U, V, HeapAllocator> >::trace,
+    LinkedHashSet<T, U, V, HeapAllocator>::finalize,
+    true, // The anchor needs to unlink itself from the chain.

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

Maybe update the comment: Needs finalization: the anchor ...

Extra points for replacing the bool here with an enum value along the lines of
NeedsFinalization.

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

Done.

+};  
+
 template<typename T>
 struct GCInfoTrait<Vector<T, 0, HeapAllocator> > {
     static const GCInfo* get() { return &info; }
@@ -1580,6 +1609,15 @@ struct BaseVisitKeyValuePairTrait {
     }
 };
 
+template<bool markWeakMembersStrongly, typename Value, typename Traits>
+struct BaseVisitLinkedNodeTrait {
+    static void mark(WebCore::Visitor* visitor, WTF::LinkedHashSetNode<Value>& self)
+    {
+        ASSERT(WTF::ShouldBeTraced<Traits>::value || (Traits::isWeak && markWeakMembersStrongly));
+        CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, Traits::isWeak, markWeakMembersStrongly, Value, Traits>::mark(visitor, self.m_value);
+    }
+};
+
 // FFX - Things that don't need marking and have no weak pointers.
 template<bool markWeakMembersStrongly, typename T, typename U>
 struct CollectionBackingTraceTrait<false, false, markWeakMembersStrongly, T, U> {
@@ -1630,6 +1668,16 @@ template<bool isWeak, bool markWeakMembersStrongly, typename Key, typename Value
 struct CollectionBackingTraceTrait<true, isWeak, markWeakMembersStrongly, WTF::KeyValuePair<Key, Value>, Traits> : public BaseVisitKeyValuePairTrait<markWeakMembersStrongly, Key, Value, Traits> {
 };
 
+// FTT (list hash set node)

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

The bools here are still blowing my mind. Can you write out in the comment that
this is: needs tracing, is weak and mark weak members strongly?

I would still prefer to have the template parameters be named enum values in all
of these to make it easier to read. The FTT comment doesn't help me. I need to
chase around the source base to see what it means. The enum change doesn't have
to be for this change, but I think it would be good to do it.

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

I've changed the markWeakMembersStrongly to an enum.  The needsTracing and
isWeak arguments are closely linked to the IsWeak and NeedsTracing templates
from TypeTraits.h. They are bool there like all the other type traits, and it
wouldn't be in keeping with the style to have only these two templates define
their own macro. I've also clarified the comments, and moved vector to the end
since it's a special case.

+template<typename Value, typename Traits>
+struct CollectionBackingTraceTrait<false, true, true, WTF::LinkedHashSetNode<Value>, Traits> : public BaseVisitLinkedNodeTrait<true, Value, Traits> {
+};
+
+// TXX (list hash set node)
+template<bool isWeak, bool markWeakMembersStrongly, typename Value, typename Traits>
+struct CollectionBackingTraceTrait<true, isWeak, markWeakMembersStrongly, WTF::LinkedHashSetNode<Value>, Traits> : public BaseVisitLinkedNodeTrait<markWeakMembersStrongly, Value, Traits> {
+};
+
 // TFX (member)
 template<bool markWeakMembersStrongly, typename T, typename Traits>
 struct CollectionBackingTraceTrait<true, false, markWeakMembersStrongly, Member<T>, Traits> {
@@ -1735,6 +1783,8 @@ template<typename T, typename U, typename V, typename W, typename X>
 struct GCInfoTrait<HeapHashMap<T, U, V, W, X> > : public GCInfoTrait<HashMap<T, U, V, W, X, HeapAllocator> > { };
 template<typename T, typename U, typename V>
 struct GCInfoTrait<HeapHashSet<T, U, V> > : public GCInfoTrait<HashSet<T, U, V, HeapAllocator> > { };
+template<typename T, typename U, typename V>
+struct GCInfoTrait<HeapLinkedHashSet<T, U, V> > : public GCInfoTrait<LinkedHashSet<T, U, V, HeapAllocator> > { };
 template<typename T, size_t inlineCapacity>
 struct GCInfoTrait<HeapVector<T, inlineCapacity> > : public GCInfoTrait<Vector<T, inlineCapacity, HeapAllocator> > { };