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

Source/platform/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 "platform/PlatformExport.h"
 #include "platform/heap/AddressSanitizer.h"
 #include "platform/heap/ThreadState.h"
 #include "platform/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 1244 matching lines @@
     }
 
     static void markNoTracing(Visitor* visitor, const void* t)
     {
         visitor->mark(t, reinterpret_cast<TraceCallback>(0));
     }
 
     template<typename T, typename Traits>
     static void trace(Visitor* visitor, T& t)
     {
-        CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, Traits::isWeak, false, T, Traits>::mark(visitor, t);
+        CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, Traits::isWeak, WeakPointersActWeak, T, Traits>::mark(visitor, t);
     }
 
     template<typename T>
     static bool hasDeadMember(Visitor*, const T&)
     {
         return false;
     }
 
     template<typename T>
     static bool hasDeadMember(Visitor* visitor, const Member<T>& t)
     {
         ASSERT(visitor->isAlive(t));
         return false;
     }
 
     template<typename T>
     static bool hasDeadMember(Visitor* visitor, const WeakMember<T>& t)
     {
         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 54 matching lines @@
     }
 
     template<typename U>
     void append(const U& other)
     {
         Deque<T, inlineCapacity, HeapAllocator>::append(other);
     }
 };
 
 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 76 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, // Needs finalization. The anchor needs to unlink itself from the chain.
+};
+
 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 68 matching lines @@
     static const GCInfo info;
 };
 
 template<typename Table>
 const GCInfo GCInfoTrait<HeapHashTableBacking<Table> >::info = {
     TraceTrait<HeapHashTableBacking<Table> >::trace,
     HeapHashTableBacking<Table>::finalize,
     Table::ValueTraits::needsDestruction,
 };
 
-template<bool markWeakMembersStrongly, typename T, typename Traits>
+template<typename T, typename Traits>
 struct BaseVisitVectorBackingTrait {
     static void mark(WebCore::Visitor* visitor, void* self)
     {
         // The allocator can oversize the allocation a little, according to
         // the allocation granularity. The extra size is included in the
         // payloadSize call below, since there is nowhere to store the
         // originally allocated memory. This assert ensures that visiting the
         // last bit of memory can't cause trouble.
         COMPILE_ASSERT(!WTF::ShouldBeTraced<Traits>::value || sizeof(T) > allocationGranularity || Traits::canInitializeWithMemset, HeapOverallocationCanCauseSpuriousVisits);
 
         T* array = reinterpret_cast<T*>(self);
         WebCore::FinalizedHeapObjectHeader* header = WebCore::FinalizedHeapObjectHeader::fromPayload(self);
         // Use the payload size as recorded by the heap to determine how many
         // elements to mark.
         size_t length = header->payloadSize() / sizeof(T);
         for (size_t i = 0; i < length; i++)
-            CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, Traits::isWeak, markWeakMembersStrongly, T, Traits>::mark(visitor, array[i]);
+            CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, Traits::isWeak, WeakPointersActStrong, T, Traits>::mark(visitor, array[i]);
     }
 };
 
-template<bool markWeakMembersStrongly, typename Table>
+template<ShouldWeakPointersBeMarkedStrongly strongify, typename Table>
 struct BaseVisitHashTableBackingTrait {
     typedef typename Table::ValueType Value;
     typedef typename Table::ValueTraits Traits;
     static void mark(WebCore::Visitor* visitor, void* self)
     {
         Value* array = reinterpret_cast<Value*>(self);
         WebCore::FinalizedHeapObjectHeader* header = WebCore::FinalizedHeapObjectHeader::fromPayload(self);
         size_t length = header->payloadSize() / sizeof(Value);
         for (size_t i = 0; i < length; i++) {
             if (!WTF::HashTableHelper<Value, typename Table::ExtractorType, typename Table::KeyTraitsType>::isEmptyOrDeletedBucket(array[i]))
-                CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, Traits::isWeak, markWeakMembersStrongly, Value, Traits>::mark(visitor, array[i]);
+                CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, Traits::isWeak, strongify, Value, Traits>::mark(visitor, array[i]);
         }
     }
 };
 
-template<bool markWeakMembersStrongly, typename Key, typename Value, typename Traits>
+template<ShouldWeakPointersBeMarkedStrongly strongify, 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);
+        ASSERT(WTF::ShouldBeTraced<Traits>::value || (Traits::isWeak && strongify == WeakPointersActStrong));
+        CollectionBackingTraceTrait<WTF::ShouldBeTraced<typename Traits::KeyTraits>::value, Traits::KeyTraits::isWeak, strongify, Key, typename Traits::KeyTraits>::mark(visitor, self.key);
+        CollectionBackingTraceTrait<WTF::ShouldBeTraced<typename Traits::ValueTraits>::value, Traits::ValueTraits::isWeak, strongify, Value, typename Traits::ValueTraits>::mark(visitor, self.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> {
+template<ShouldWeakPointersBeMarkedStrongly strongify, typename Value, typename Traits>
+struct BaseVisitLinkedNodeTrait {
+    static void mark(WebCore::Visitor* visitor, WTF::LinkedHashSetNode<Value>& self)
+    {
+        ASSERT(WTF::ShouldBeTraced<Traits>::value || (Traits::isWeak && strongify == WeakPointersActStrong));
+        CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, Traits::isWeak, strongify, Value, Traits>::mark(visitor, self.m_value);
+    }
+};
+
+// Catch-all for things that don't need marking and have no weak pointers. We
+// do nothing, even if WeakPointersActStrong.
+template<ShouldWeakPointersBeMarkedStrongly strongify, typename T, typename U>
+struct CollectionBackingTraceTrait<false, false, strongify, 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.
+// Catch-all for 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>
-struct CollectionBackingTraceTrait<false, true, false, T, U> {
+struct CollectionBackingTraceTrait<false, true, WeakPointersActWeak, T, U> {
     static void mark(Visitor*, const T&) { }
     static void mark(Visitor*, const void*) { }
 };
 
-// For each type that we understand we have the FTT case and the TXX case. The
-// FTT case is where we would not normally need to mark it, but it has weak
-// pointers, and we are marking them as strong. The TXX case is the regular
-// case for things that need marking.
+// For each type that we understand we have the strongified case and the
+// needsMarking case. The strongified case is where we would not normally need
+// to mark it, but it has weak pointers, and we are marking them as strong
+// because there is a live iterator that would be disturbed if the collection
+// were subject to weak processing right now. The needsMarking case is the
+// case for things that need marking, which may also be strongified (eg. for
+// a map pair that has a key that is weak and a value that needs marking).
 
-// FTT (vector)
-template<typename T, typename Traits>
-struct CollectionBackingTraceTrait<false, true, true, HeapVectorBacking<T, Traits>, void> : public BaseVisitVectorBackingTrait<true, T, Traits> {
+// The body is the same for most objects, but there are two template
+// specializations because there is no way to express needsMarking || (isWeak
+// && WeakPointersActStrong) in a single specialization.
+
+// Hash table that would not normally need marking, but strongified.
+template<typename Table>
+struct CollectionBackingTraceTrait<false, true, WeakPointersActStrong, HeapHashTableBacking<Table>, void> : public BaseVisitHashTableBackingTrait<WeakPointersActStrong, Table> {
 };
 
-// TXX (vector)
-template<bool isWeak, bool markWeakMembersStrongly, typename T, typename Traits>
-struct CollectionBackingTraceTrait<true, isWeak, markWeakMembersStrongly, HeapVectorBacking<T, Traits>, void> : public BaseVisitVectorBackingTrait<markWeakMembersStrongly, T, Traits> {
+// Hash table that needs marking, optionally also strongified.
+template<bool isWeak, ShouldWeakPointersBeMarkedStrongly strongify, typename Table>
+struct CollectionBackingTraceTrait<true, isWeak, strongify, HeapHashTableBacking<Table>, void> : public BaseVisitHashTableBackingTrait<strongify, Table> {
 };
 
-// FTT (hash table)
-template<typename Table>
-struct CollectionBackingTraceTrait<false, true, true, HeapHashTableBacking<Table>, void> : public BaseVisitHashTableBackingTrait<true, Table> {
+// Key-value pair that would not normally need marking, but strongified.
+template<typename Key, typename Value, typename Traits>
+struct CollectionBackingTraceTrait<false, true, WeakPointersActStrong, WTF::KeyValuePair<Key, Value>, Traits> : public BaseVisitKeyValuePairTrait<WeakPointersActStrong, Key, Value, Traits> {
 };
 
-// TXX (hash table)
-template<bool isWeak, bool markWeakMembersStrongly, typename Table>
-struct CollectionBackingTraceTrait<true, isWeak, markWeakMembersStrongly, HeapHashTableBacking<Table>, void> : public BaseVisitHashTableBackingTrait<markWeakMembersStrongly, Table> {
+// Key value pair that needs marking, optionally also strongified.
+template<bool isWeak, ShouldWeakPointersBeMarkedStrongly strongify, typename Key, typename Value, typename Traits>
+struct CollectionBackingTraceTrait<true, isWeak, strongify, WTF::KeyValuePair<Key, Value>, Traits> : public BaseVisitKeyValuePairTrait<strongify, Key, Value, Traits> {
 };
 
-// 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> {
+// List hash set node that would not normally need marking, but strongified.
+template<typename Value, typename Traits>
+struct CollectionBackingTraceTrait<false, true, WeakPointersActStrong, WTF::LinkedHashSetNode<Value>, Traits> : public BaseVisitLinkedNodeTrait<WeakPointersActStrong, 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> {
+// List hash set node that needs marking, optionally also strongified.
+template<bool isWeak, ShouldWeakPointersBeMarkedStrongly strongify, typename Value, typename Traits>
+struct CollectionBackingTraceTrait<true, isWeak, strongify, WTF::LinkedHashSetNode<Value>, Traits> : public BaseVisitLinkedNodeTrait<strongify, Value, Traits> {
 };
 
-// TFX (member)
-template<bool markWeakMembersStrongly, typename T, typename Traits>
-struct CollectionBackingTraceTrait<true, false, markWeakMembersStrongly, Member<T>, Traits> {
+// Vector backing that needs marking. We don't support weak members in vectors,
+// so we don't need a strongified variant here.
+template<bool isWeak, ShouldWeakPointersBeMarkedStrongly strongify, typename T, typename Traits>
+struct CollectionBackingTraceTrait<true, isWeak, strongify, HeapVectorBacking<T, Traits>, void> : public BaseVisitVectorBackingTrait<T, Traits> {
+};
+
+// Member always needs marking, never weak.
+template<ShouldWeakPointersBeMarkedStrongly strongify, typename T, typename Traits>
+struct CollectionBackingTraceTrait<true, false, strongify, Member<T>, Traits> {
     static void mark(WebCore::Visitor* visitor, Member<T> self)
     {
         visitor->mark(self.get());
     }
 };
 
-// FTT (weak member)
+// Weak member never has needsMarking, always weak, strongified case.
 template<typename T, typename Traits>
-struct CollectionBackingTraceTrait<false, true, true, WeakMember<T>, Traits> {
+struct CollectionBackingTraceTrait<false, true, WeakPointersActStrong, WeakMember<T>, Traits> {
     static void mark(WebCore::Visitor* visitor, WeakMember<T> self)
     {
         // This can mark weak members as if they were strong. The reason we
         // need this is that we don't do weak processing unless we reach the
         // backing only through the hash table. Reaching it in any other way
         // makes it impossible to update the size and deleted slot count of the
         // table, and exposes us to weak processing during iteration issues.
         visitor->mark(self.get());
     }
 };
 
 // Catch-all for things that have a way to trace. For things that contain weak
 // pointers they will generally be visited weakly even if
-// markWeakMembersStrongly is true. This is what you want.
-template<bool isWeak, bool markWeakMembersStrongly, typename T, typename Traits>
-struct CollectionBackingTraceTrait<true, isWeak, markWeakMembersStrongly, T, Traits> {
+// WeakPointersActStrong. This is a deliberate choice: We currently don't
+// strongify weak members that are embedded in larger structures, they are just
+// zeroed during weak processing without the whole structure being
+// removed from the collection.
+template<bool isWeak, ShouldWeakPointersBeMarkedStrongly strongify, typename T, typename Traits>
+struct CollectionBackingTraceTrait<true, isWeak, strongify, T, Traits> {
     static void mark(WebCore::Visitor* visitor, T& t)
     {
         TraceTrait<T>::trace(visitor, &t);
     }
 };
 
 template<typename T, typename Traits>
 struct TraceTrait<HeapVectorBacking<T, Traits> > {
     typedef HeapVectorBacking<T, Traits> Backing;
     static void trace(WebCore::Visitor* visitor, void* self)
     {
         COMPILE_ASSERT(!Traits::isWeak, WeDontSupportWeaknessInHeapVectorsOrDeques);
         if (WTF::ShouldBeTraced<Traits>::value)
-            CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, false, false, HeapVectorBacking<T, Traits>, void>::mark(visitor, self);
+            CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, false, WeakPointersActWeak, HeapVectorBacking<T, Traits>, void>::mark(visitor, self);
     }
     static void mark(Visitor* visitor, const Backing* backing)
     {
         visitor->mark(backing, &trace);
     }
     static void checkGCInfo(Visitor* visitor, const Backing* backing)
     {
 #ifndef NDEBUG
         visitor->checkGCInfo(const_cast<Backing*>(backing), GCInfoTrait<Backing>::get());
 #endif
     }
 };
 
 // The trace trait for the heap hashtable backing is used when we find a
 // direct pointer to the backing from the conservative stack scanner. This
 // normally indicates that there is an ongoing iteration over the table, and so
 // we disable weak processing of table entries. When the backing is found
 // through the owning hash table we mark differently, in order to do weak
 // processing.
 template<typename Table>
 struct TraceTrait<HeapHashTableBacking<Table> > {
     typedef HeapHashTableBacking<Table> Backing;
     typedef typename Table::ValueTraits Traits;
     static void trace(WebCore::Visitor* visitor, void* self)
     {
         if (WTF::ShouldBeTraced<Traits>::value || Traits::isWeak)
-            CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, Traits::isWeak, true, Backing, void>::mark(visitor, self);
+            CollectionBackingTraceTrait<WTF::ShouldBeTraced<Traits>::value, Traits::isWeak, WeakPointersActStrong, Backing, void>::mark(visitor, self);
     }
     static void mark(Visitor* visitor, const Backing* backing)
     {
         if (WTF::ShouldBeTraced<Traits>::value || Traits::isWeak)
             visitor->mark(backing, &trace);
         else
             visitor->mark(backing, 0);
     }
     static void checkGCInfo(Visitor* visitor, const Backing* backing)
     {
@@ skipping 16 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, size_t inlineCapacity>
 struct GCInfoTrait<HeapDeque<T, inlineCapacity> > : public GCInfoTrait<Deque<T, inlineCapacity, HeapAllocator> > { };
 
 template<typename T>
 struct IfWeakMember;
 
 template<typename T>
 struct IfWeakMember {
@@ skipping 11 matching lines @@
 // 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 PLATFORM_EXPORT ThreadHeap<FinalizedHeapObjectHeader>;
 extern template class PLATFORM_EXPORT ThreadHeap<HeapObjectHeader>;
 #endif
 
 }
 
 #endif // Heap_h