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

Source/heap/Heap.h

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 19 matching lines @@
 
 #ifndef Heap_h
 #define Heap_h
 
 #include "heap/AddressSanitizer.h"
 #include "heap/HeapExport.h"
 #include "heap/ThreadState.h"
 #include "heap/Visitor.h"
 
 #include "wtf/Assertions.h"
+#include "wtf/LinkedHashSet.h"
 #include "wtf/OwnPtr.h"
 #include "wtf/PassRefPtr.h"
 
 #include <stdint.h>
 
 namespace WebCore {
 
 const size_t blinkPageSizeLog2 = 17;
 const size_t blinkPageSize = 1 << blinkPageSizeLog2;
 const size_t blinkPageOffsetMask = blinkPageSize - 1;
@@ skipping 1231 matching lines @@
     {
         return !visitor->isAlive(t);
     }
 
     template<typename T, typename U>
     static bool hasDeadMember(Visitor* visitor, const WTF::KeyValuePair<T, U>& t)
     {
         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);
     }
 
     template<typename T>
     struct ResultType {
         typedef T* Type;
     };
 
@@ skipping 47 matching lines @@
     typename KeyTraitsArg = HashTraits<KeyArg>,
     typename MappedTraitsArg = HashTraits<MappedArg> >
 class HeapHashMap : public HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, HeapAllocator> { };
 
 template<
     typename ValueArg,
     typename HashArg = typename DefaultHash<ValueArg>::Hash,
     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:
     HeapVector() { }
 
     explicit HeapVector(size_t size) : Vector<T, inlineCapacity, HeapAllocator>(size)
     {
     }
 
     HeapVector(size_t size, const T& val) : Vector<T, inlineCapacity, HeapAllocator>(size, val)
@@ skipping 14 matching lines @@
 
     template<typename U, size_t otherCapacity>
     void appendVector(const HeapVector<U, otherCapacity>& other)
     {
         const Vector<U, otherCapacity, HeapAllocator>& otherVector = other;
         Vector<T, inlineCapacity, HeapAllocator>::appendVector(otherVector);
     }
 };
 
 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;
 };
 
 template<typename T>
 struct ThreadingTrait<WeakMember<T> > {
     static const ThreadAffinity Affinity = ThreadingTrait<T>::Affinity;
 };
 
 template<typename Key, typename Value, typename T, typename U, typename V>
@@ skipping 68 matching lines @@
     static const GCInfo info;
 };
 
 template<typename T, typename U, typename V>
 const GCInfo GCInfoTrait<HashSet<T, U, V, HeapAllocator> >::info = {
     TraceTrait<HashSet<T, U, V, HeapAllocator> >::trace,
     0,
     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; }
     static const GCInfo info;
 };
 
 template<typename T>
 const GCInfo GCInfoTrait<Vector<T, 0, HeapAllocator> >::info = {
     TraceTrait<Vector<T, 0, HeapAllocator> >::trace,
     0,
@@ skipping 83 matching lines @@
 template<bool markWeakMembersStrongly, typename Key, typename Value, typename Traits>
 struct BaseVisitKeyValuePairTrait {
     static void mark(WebCore::Visitor* visitor, WTF::KeyValuePair<Key, Value>& self)
     {
         ASSERT(WTF::ShouldBeTraced<Traits>::value || (Traits::isWeak && markWeakMembersStrongly));
         CollectionBackingTraceTrait<WTF::ShouldBeTraced<typename Traits::KeyTraits>::value, Traits::KeyTraits::isWeak, markWeakMembersStrongly, Key, typename Traits::KeyTraits>::mark(visitor, self.key);
         CollectionBackingTraceTrait<WTF::ShouldBeTraced<typename Traits::ValueTraits>::value, Traits::ValueTraits::isWeak, markWeakMembersStrongly, Value, typename Traits::ValueTraits>::mark(visitor, self.value);
     }
 };
 
+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> {
     static void mark(Visitor*, const T&) { }
     static void mark(Visitor*, const void*) { }
 };
 
 // FTF - Things that don't need marking. They have weak pointers, but we are
 // not marking weak pointers in this object in this GC.
 template<typename T, typename U>
@@ skipping 30 matching lines @@
 // FTT (key value pair)
 template<typename Key, typename Value, typename Traits>
 struct CollectionBackingTraceTrait<false, true, true, WTF::KeyValuePair<Key, Value>, Traits> : public BaseVisitKeyValuePairTrait<true, Key, Value, Traits> {
 };
 
 // TXX (key value pair)
 template<bool isWeak, bool markWeakMembersStrongly, typename Key, typename Value, typename Traits>
 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> {
     static void mark(WebCore::Visitor* visitor, Member<T> self)
     {
         visitor->mark(self.get());
     }
 };
 
 // FTT (weak member)
@@ skipping 85 matching lines @@
     for (unsigned i = 0; i < length; i++) {
         if (!Table::isEmptyOrDeletedBucket(table[i]))
             table[i].~Value();
     }
 }
 
 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> > { };
 
 template<typename T>
 struct IfWeakMember;
 
 template<typename T>
 struct IfWeakMember {
     template<typename U>
     static bool isDead(Visitor*, const U&) { return false; }
 };
 
 template<typename T>
 struct IfWeakMember<WeakMember<T> > {
     static bool isDead(Visitor* visitor, const WeakMember<T>& t) { return !visitor->isAlive(t.get()); }
 };
 
 #if COMPILER(CLANG)
 // Clang does not export the symbols that we have explicitly asked it
 // to export. This forces it to export all the methods from ThreadHeap.
 template<> void ThreadHeap<FinalizedHeapObjectHeader>::addPageToHeap(const GCInfo*);
 template<> void ThreadHeap<HeapObjectHeader>::addPageToHeap(const GCInfo*);
 extern template class HEAP_EXPORT ThreadHeap<FinalizedHeapObjectHeader>;
 extern template class HEAP_EXPORT ThreadHeap<HeapObjectHeader>;
 #endif
 
 }
 
 #endif // Heap_h