Add HeapHashCountedSet

Source/platform/heap/HeapTest.cpp

 /*
  * 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 1876 matching lines @@
 typedef std::pair<Member<IntWrapper>, WeakMember<IntWrapper> > PairStrongWeak;
 typedef std::pair<WeakMember<IntWrapper>, int> PairWeakUnwrapped;
 typedef std::pair<int, WeakMember<IntWrapper> > PairUnwrappedWeak;
 
 class Container : public GarbageCollected<Container> {
 public:
     static Container* create() { return new Container(); }
     HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > map;
     HeapHashSet<Member<IntWrapper> > set;
     HeapHashSet<Member<IntWrapper> > set2;
+    HeapHashCountedSet<Member<IntWrapper> > set3;
     HeapVector<Member<IntWrapper>, 2> vector;
     HeapVector<PairWrappedUnwrapped, 2> vectorWU;
     HeapVector<PairUnwrappedWrapped, 2> vectorUW;
     HeapDeque<Member<IntWrapper>, 0> deque;
     HeapDeque<PairWrappedUnwrapped, 0> dequeWU;
     HeapDeque<PairUnwrappedWrapped, 0> dequeUW;
     void trace(Visitor* visitor)
     {
         visitor->trace(map);
         visitor->trace(set);
         visitor->trace(set2);
+        visitor->trace(set3);
         visitor->trace(vector);
         visitor->trace(vectorWU);
         visitor->trace(vectorUW);
         visitor->trace(deque);
         visitor->trace(dequeWU);
         visitor->trace(dequeUW);
     }
 };
 
 struct ShouldBeTraced {
@@ skipping 197 matching lines @@
 TEST(HeapTest, HeapCollectionTypes)
 {
     HeapStats initialHeapSize;
     IntWrapper::s_destructorCalls = 0;
 
     typedef HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > MemberMember;
     typedef HeapHashMap<Member<IntWrapper>, int> MemberPrimitive;
     typedef HeapHashMap<int, Member<IntWrapper> > PrimitiveMember;
 
     typedef HeapHashSet<Member<IntWrapper> > MemberSet;
+    typedef HeapHashCountedSet<Member<IntWrapper> > MemberCountedSet;
 
     typedef HeapVector<Member<IntWrapper>, 2> MemberVector;
     typedef HeapDeque<Member<IntWrapper>, 0> MemberDeque;
 
     typedef HeapVector<PairWrappedUnwrapped, 2> VectorWU;
     typedef HeapVector<PairUnwrappedWrapped, 2> VectorUW;
     typedef HeapDeque<PairWrappedUnwrapped, 0> DequeWU;
     typedef HeapDeque<PairUnwrappedWrapped, 0> DequeUW;
 
     Persistent<MemberMember> memberMember = new MemberMember();
     Persistent<MemberMember> memberMember2 = new MemberMember();
     Persistent<MemberMember> memberMember3 = new MemberMember();
     Persistent<MemberPrimitive> memberPrimitive = new MemberPrimitive();
     Persistent<PrimitiveMember> primitiveMember = new PrimitiveMember();
     Persistent<MemberSet> set = new MemberSet();
     Persistent<MemberSet> set2 = new MemberSet();
+    Persistent<MemberCountedSet> set3 = new MemberCountedSet();
     Persistent<MemberVector> vector = new MemberVector();
     Persistent<MemberVector> vector2 = new MemberVector();
     Persistent<VectorWU> vectorWU = new VectorWU();
     Persistent<VectorWU> vectorWU2 = new VectorWU();
     Persistent<VectorUW> vectorUW = new VectorUW();
     Persistent<VectorUW> vectorUW2 = new VectorUW();
     Persistent<MemberDeque> deque = new MemberDeque();
     Persistent<MemberDeque> deque2 = new MemberDeque();
     Persistent<DequeWU> dequeWU = new DequeWU();
     Persistent<DequeWU> dequeWU2 = new DequeWU();
@@ skipping 40 matching lines @@
             primitiveMember->add(4, one);
             memberPrimitive->add(one, 2);
             memberPrimitive->add(two, 3);
             memberPrimitive->add(three, 4);
             memberPrimitive->add(four, 1);
             set2->add(one);
             set2->add(two);
             set2->add(three);
             set2->add(four);
             set->add(oneB);
+            set3->add(oneB);
+            set3->add(oneB);
             vector->append(oneB);
             deque->append(oneB);
             vector2->append(threeB);
             vector2->append(fourB);
             deque2->append(threeE);
             deque2->append(fourE);
             vectorWU->append(PairWrappedUnwrapped(&*oneC, 42));
             dequeWU->append(PairWrappedUnwrapped(&*oneE, 42));
             vectorWU2->append(PairWrappedUnwrapped(&*threeC, 43));
             vectorWU2->append(PairWrappedUnwrapped(&*fourC, 44));
@@ skipping 17 matching lines @@
             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
 
             EXPECT_TRUE(dequeContains(*deque, oneB));
 
             EXPECT_EQ(0u, memberMember->size());
             EXPECT_EQ(4u, memberMember2->size());
             EXPECT_EQ(4u, primitiveMember->size());
             EXPECT_EQ(4u, memberPrimitive->size());
             EXPECT_EQ(1u, set->size());
             EXPECT_EQ(4u, set2->size());
+            EXPECT_EQ(1u, set3->size());
             EXPECT_EQ(1u, vector->size());
             EXPECT_EQ(2u, vector2->size());
             EXPECT_EQ(1u, vectorWU->size());
             EXPECT_EQ(3u, vectorWU2->size());
             EXPECT_EQ(1u, vectorUW->size());
             EXPECT_EQ(3u, vectorUW2->size());
             EXPECT_EQ(1u, deque->size());
             EXPECT_EQ(2u, deque2->size());
             EXPECT_EQ(1u, dequeWU->size());
             EXPECT_EQ(3u, dequeWU2->size());
@@ skipping 32 matching lines @@
 
             // Swap set and set2 in a roundabout way.
             MemberSet& cset1 = container->set;
             MemberSet& cset2 = container->set2;
             set->swap(cset1);
             set2->swap(cset2);
             set->swap(cset2);
             cset1.swap(cset2);
             cset2.swap(set2);
 
+            MemberCountedSet& cCountedSet = container->set3;
+            set3->swap(cCountedSet);
+            EXPECT_EQ(0u, set3->size());
+            set3->swap(cCountedSet);
+
             // Triple swap.
             container->map.swap(memberMember2);
             MemberMember& containedMap = container->map;
             memberMember3->swap(containedMap);
             memberMember3->swap(memberMember);
 
             EXPECT_TRUE(memberMember->get(one) == two);
             EXPECT_TRUE(memberMember->get(two) == three);
             EXPECT_TRUE(memberMember->get(three) == four);
             EXPECT_TRUE(memberMember->get(four) == one);
             EXPECT_TRUE(primitiveMember->get(1) == two);
             EXPECT_TRUE(primitiveMember->get(2) == three);
             EXPECT_TRUE(primitiveMember->get(3) == four);
             EXPECT_TRUE(primitiveMember->get(4) == one);
             EXPECT_EQ(1, memberPrimitive->get(four));
             EXPECT_EQ(2, memberPrimitive->get(one));
             EXPECT_EQ(3, memberPrimitive->get(two));
             EXPECT_EQ(4, memberPrimitive->get(three));
             EXPECT_TRUE(set->contains(one));
             EXPECT_TRUE(set->contains(two));
             EXPECT_TRUE(set->contains(three));
             EXPECT_TRUE(set->contains(four));
             EXPECT_TRUE(set2->contains(oneB));
+            EXPECT_TRUE(set3->contains(oneB));
             EXPECT_TRUE(vector->contains(threeB));
             EXPECT_TRUE(vector->contains(fourB));
             EXPECT_TRUE(dequeContains(*deque, threeE));
             EXPECT_TRUE(dequeContains(*deque, fourE));
             EXPECT_TRUE(vector2->contains(oneB));
             EXPECT_FALSE(vector2->contains(threeB));
             EXPECT_TRUE(dequeContains(*deque2, oneB));
             EXPECT_FALSE(dequeContains(*deque2, threeE));
             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*threeC, 43)));
             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*fourC, 44)));
@@ skipping 18 matching lines @@
         }
 
         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 
         EXPECT_EQ(4u, memberMember->size());
         EXPECT_EQ(0u, memberMember2->size());
         EXPECT_EQ(4u, primitiveMember->size());
         EXPECT_EQ(4u, memberPrimitive->size());
         EXPECT_EQ(4u, set->size());
         EXPECT_EQ(1u, set2->size());
+        EXPECT_EQ(1u, set3->size());
         EXPECT_EQ(2u, vector->size());
         EXPECT_EQ(1u, vector2->size());
         EXPECT_EQ(3u, vectorUW->size());
         EXPECT_EQ(1u, vector2->size());
         EXPECT_EQ(2u, deque->size());
         EXPECT_EQ(1u, deque2->size());
         EXPECT_EQ(3u, dequeUW->size());
         EXPECT_EQ(1u, deque2->size());
 
         EXPECT_TRUE(memberMember->get(one) == two);
         EXPECT_TRUE(primitiveMember->get(1) == two);
         EXPECT_TRUE(primitiveMember->get(4) == one);
         EXPECT_EQ(2, memberPrimitive->get(one));
         EXPECT_EQ(3, memberPrimitive->get(two));
         EXPECT_TRUE(set->contains(one));
         EXPECT_TRUE(set->contains(two));
         EXPECT_FALSE(set->contains(oneB));
         EXPECT_TRUE(set2->contains(oneB));
+        EXPECT_TRUE(set3->contains(oneB));
+        EXPECT_EQ(2u, set3->find(oneB)->value);
         EXPECT_EQ(3, vector->at(0)->value());
         EXPECT_EQ(4, vector->at(1)->value());
         EXPECT_EQ(3, deque->begin()->get()->value());
     }
 
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 
     EXPECT_EQ(4u, memberMember->size());
     EXPECT_EQ(4u, primitiveMember->size());
@@ skipping 47 matching lines @@
     HeapStats initialHeapStats;
     clearOutOldGarbage(&initialHeapStats);
     IntWrapper::s_destructorCalls = 0;
 
     PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
 
     typedef HeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > WeakStrong;
     typedef HeapHashMap<Member<IntWrapper>, WeakMember<IntWrapper> > StrongWeak;
     typedef HeapHashMap<WeakMember<IntWrapper>, WeakMember<IntWrapper> > WeakWeak;
     typedef HeapHashSet<WeakMember<IntWrapper> > WeakSet;
+    typedef HeapHashCountedSet<WeakMember<IntWrapper> > WeakCountedSet;
 
     Persistent<WeakStrong> weakStrong = new WeakStrong();
     Persistent<StrongWeak> strongWeak = new StrongWeak();
     Persistent<WeakWeak> weakWeak = new WeakWeak();
     Persistent<WeakSet> weakSet = new WeakSet();
+    Persistent<WeakCountedSet> weakCountedSet = new WeakCountedSet();
 
     Persistent<IntWrapper> two = IntWrapper::create(2);
 
     keepNumbersAlive.append(IntWrapper::create(103));
     keepNumbersAlive.append(IntWrapper::create(10));
 
     {
         weakStrong->add(IntWrapper::create(1), two);
         strongWeak->add(two, IntWrapper::create(1));
         weakWeak->add(two, IntWrapper::create(42));
         weakWeak->add(IntWrapper::create(42), two);
         weakSet->add(IntWrapper::create(0));
         weakSet->add(two);
         weakSet->add(keepNumbersAlive[0]);
         weakSet->add(keepNumbersAlive[1]);
+        weakCountedSet->add(IntWrapper::create(0));
+        weakCountedSet->add(two);
+        weakCountedSet->add(two);
+        weakCountedSet->add(two);
+        weakCountedSet->add(keepNumbersAlive[0]);
+        weakCountedSet->add(keepNumbersAlive[1]);
         EXPECT_EQ(1u, weakStrong->size());
         EXPECT_EQ(1u, strongWeak->size());
         EXPECT_EQ(2u, weakWeak->size());
         EXPECT_EQ(4u, weakSet->size());
+        EXPECT_EQ(4u, weakCountedSet->size());
+        EXPECT_EQ(3u, weakCountedSet->find(two)->value);
+        weakCountedSet->remove(two);
+        EXPECT_EQ(2u, weakCountedSet->find(two)->value);
     }
 
     keepNumbersAlive[0] = nullptr;
 
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 
     EXPECT_EQ(0u, weakStrong->size());
     EXPECT_EQ(0u, strongWeak->size());
     EXPECT_EQ(0u, weakWeak->size());
     EXPECT_EQ(2u, weakSet->size());
+    EXPECT_EQ(2u, weakCountedSet->size());
 }
 
 template<typename Set>
 void linkedSetHelper(bool strong)
 {
     HeapStats initialHeapStats;
     clearOutOldGarbage(&initialHeapStats);
     IntWrapper::s_destructorCalls = 0;
 
     PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
@@ skipping 231 matching lines @@
 TEST(HeapTest, HeapMapDestructor)
 {
     heapMapDestructorHelper(true);
     heapMapDestructorHelper(false);
 }
 
 typedef HeapHashSet<PairWeakStrong> WeakStrongSet;
 typedef HeapHashSet<PairWeakUnwrapped> WeakUnwrappedSet;
 typedef HeapHashSet<PairStrongWeak> StrongWeakSet;
 typedef HeapHashSet<PairUnwrappedWeak> UnwrappedWeakSet;
+typedef HeapLinkedHashSet<PairWeakStrong> WeakStrongLinkedSet;
+typedef HeapLinkedHashSet<PairWeakUnwrapped> WeakUnwrappedLinkedSet;
+typedef HeapLinkedHashSet<PairStrongWeak> StrongWeakLinkedSet;
+typedef HeapLinkedHashSet<PairUnwrappedWeak> UnwrappedWeakLinkedSet;
+typedef HeapHashCountedSet<PairWeakStrong> WeakStrongCountedSet;
+typedef HeapHashCountedSet<PairWeakUnwrapped> WeakUnwrappedCountedSet;
+typedef HeapHashCountedSet<PairStrongWeak> StrongWeakCountedSet;
+typedef HeapHashCountedSet<PairUnwrappedWeak> UnwrappedWeakCountedSet;
 
+template<typename T>
+T& iteratorExtractor(WTF::KeyValuePair<T, unsigned>& pair)
+{
+    return pair.key;
+}
+
+template<typename T>
+T& iteratorExtractor(T& notAPair)
+{
+    return notAPair;
+}
+
+template<typename WSSet, typename SWSet, typename WUSet, typename UWSet>
 void checkPairSets(
-    Persistent<WeakStrongSet>& weakStrong,
-    Persistent<StrongWeakSet>& strongWeak,
-    Persistent<WeakUnwrappedSet>& weakUnwrapped,
-    Persistent<UnwrappedWeakSet>& unwrappedWeak,
+    Persistent<WSSet>& weakStrong,
+    Persistent<SWSet>& strongWeak,
+    Persistent<WUSet>& weakUnwrapped,
+    Persistent<UWSet>& unwrappedWeak,
     bool ones,
     Persistent<IntWrapper>& two)
 {
-    WeakStrongSet::iterator itWS = weakStrong->begin();
-    StrongWeakSet::iterator itSW = strongWeak->begin();
-    WeakUnwrappedSet::iterator itWU = weakUnwrapped->begin();
-    UnwrappedWeakSet::iterator itUW = unwrappedWeak->begin();
+    typename WSSet::iterator itWS = weakStrong->begin();
+    typename SWSet::iterator itSW = strongWeak->begin();
+    typename WUSet::iterator itWU = weakUnwrapped->begin();
+    typename UWSet::iterator itUW = unwrappedWeak->begin();
 
     EXPECT_EQ(2u, weakStrong->size());
     EXPECT_EQ(2u, strongWeak->size());
     EXPECT_EQ(2u, weakUnwrapped->size());
     EXPECT_EQ(2u, unwrappedWeak->size());
 
-    PairWeakStrong p = *itWS;
-    PairStrongWeak p2 = *itSW;
-    PairWeakUnwrapped p3 = *itWU;
-    PairUnwrappedWeak p4 = *itUW;
+    PairWeakStrong p = iteratorExtractor(*itWS);
+    PairStrongWeak p2 = iteratorExtractor(*itSW);
+    PairWeakUnwrapped p3 = iteratorExtractor(*itWU);
+    PairUnwrappedWeak p4 = iteratorExtractor(*itUW);
     if (p.first == two && p.second == two)
         ++itWS;
     if (p2.first == two && p2.second == two)
         ++itSW;
     if (p3.first == two && p3.second == 2)
         ++itWU;
     if (p4.first == 2 && p4.second == two)
         ++itUW;
-    p = *itWS;
-    p2 = *itSW;
-    p3 = *itWU;
-    p4 = *itUW;
+    p = iteratorExtractor(*itWS);
+    p2 = iteratorExtractor(*itSW);
+    p3 = iteratorExtractor(*itWU);
+    p4 = iteratorExtractor(*itUW);
     IntWrapper* nullWrapper = 0;
     if (ones) {
         EXPECT_EQ(p.first->value(), 1);
         EXPECT_EQ(p2.second->value(), 1);
         EXPECT_EQ(p3.first->value(), 1);
         EXPECT_EQ(p4.second->value(), 1);
     } else {
         EXPECT_EQ(p.first, nullWrapper);
         EXPECT_EQ(p2.second, nullWrapper);
         EXPECT_EQ(p3.first, nullWrapper);
         EXPECT_EQ(p4.second, nullWrapper);
     }
 
     EXPECT_EQ(p.second->value(), 2);
     EXPECT_EQ(p2.first->value(), 2);
     EXPECT_EQ(p3.second, 2);
     EXPECT_EQ(p4.first, 2);
 
     EXPECT_TRUE(weakStrong->contains(PairWeakStrong(&*two, &*two)));
     EXPECT_TRUE(strongWeak->contains(PairStrongWeak(&*two, &*two)));
     EXPECT_TRUE(weakUnwrapped->contains(PairWeakUnwrapped(&*two, 2)));
     EXPECT_TRUE(unwrappedWeak->contains(PairUnwrappedWeak(2, &*two)));
 }
 
-TEST(HeapTest, HeapWeakPairs)
+template<typename WSSet, typename SWSet, typename WUSet, typename UWSet>
+void heapWeakPairsHelper()
 {
     IntWrapper::s_destructorCalls = 0;
 
     PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
 
-    Persistent<WeakStrongSet> weakStrong = new WeakStrongSet();
-    Persistent<StrongWeakSet> strongWeak = new StrongWeakSet();
-    Persistent<WeakUnwrappedSet> weakUnwrapped = new WeakUnwrappedSet();
-    Persistent<UnwrappedWeakSet> unwrappedWeak = new UnwrappedWeakSet();
+    Persistent<WSSet> weakStrong = new WSSet();
+    Persistent<SWSet> strongWeak = new SWSet();
+    Persistent<WUSet> weakUnwrapped = new WUSet();
+    Persistent<UWSet> unwrappedWeak = new UWSet();
 
     Persistent<IntWrapper> two = IntWrapper::create(2);
 
     weakStrong->add(PairWeakStrong(IntWrapper::create(1), &*two));
     weakStrong->add(PairWeakStrong(&*two, &*two));
     strongWeak->add(PairStrongWeak(&*two, IntWrapper::create(1)));
     strongWeak->add(PairStrongWeak(&*two, &*two));
     weakUnwrapped->add(PairWeakUnwrapped(IntWrapper::create(1), 2));
     weakUnwrapped->add(PairWeakUnwrapped(&*two, 2));
     unwrappedWeak->add(PairUnwrappedWeak(2, IntWrapper::create(1)));
     unwrappedWeak->add(PairUnwrappedWeak(2, &*two));
 
     checkPairSets(weakStrong, strongWeak, weakUnwrapped, unwrappedWeak, true, two);
 
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
     checkPairSets(weakStrong, strongWeak, weakUnwrapped, unwrappedWeak, false, two);
 }
 
+TEST(HeapTest, HeapWeakPairs)
+{
+    heapWeakPairsHelper<WeakStrongSet, StrongWeakSet, WeakUnwrappedSet, UnwrappedWeakSet>();
+    heapWeakPairsHelper<WeakStrongCountedSet, StrongWeakCountedSet, WeakUnwrappedCountedSet, UnwrappedWeakCountedSet>();
+    heapWeakPairsHelper<WeakStrongLinkedSet, StrongWeakLinkedSet, WeakUnwrappedLinkedSet, UnwrappedWeakLinkedSet>();
+}
+
 TEST(HeapTest, HeapWeakCollectionTypes)
 {
     HeapStats initialHeapSize;
     IntWrapper::s_destructorCalls = 0;
 
     typedef HeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > WeakStrong;
     typedef HeapHashMap<Member<IntWrapper>, WeakMember<IntWrapper> > StrongWeak;
     typedef HeapHashMap<WeakMember<IntWrapper>, WeakMember<IntWrapper> > WeakWeak;
     typedef HeapHashSet<WeakMember<IntWrapper> > WeakSet;
 
@@ skipping 858 matching lines @@
     {
         Persistent<MixinB> b = obj;
         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
         EXPECT_EQ(0, IntWrapper::s_destructorCalls);
     }
     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
     EXPECT_EQ(3, IntWrapper::s_destructorCalls);
 }
 
 } // WebCore namespace