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

Source/wtf/ListHashSetTest.cpp

Index: Source/wtf/ListHashSetTest.cpp
diff --git a/Source/wtf/ListHashSetTest.cpp b/Source/wtf/ListHashSetTest.cpp
index f9e7644bd68511fae8df1c18c82803744cba96ad..315060a8bcbc5c72fa8781652d6929e262e98be3 100644
--- a/Source/wtf/ListHashSetTest.cpp
+++ b/Source/wtf/ListHashSetTest.cpp
@@ -25,6 +25,7 @@
 
 #include "config.h"
 
+#include "wtf/LinkedHashSet.h"
 #include "wtf/ListHashSet.h"
 #include "wtf/PassRefPtr.h"
 #include "wtf/RefCounted.h"
@@ -33,147 +34,211 @@
 
 namespace {
 
-TEST(WTF, ListHashSetRemoveFirst)
+template<typename Set>
+void removeFirstHelper()
 {
-    ListHashSet<int> list;
+    Set list;
+    list.add(-1);
+    list.add(0);
     list.add(1);
     list.add(2);
     list.add(3);
 
-    ASSERT_EQ(1, list.first());
+    EXPECT_EQ(-1, list.first());
+    EXPECT_EQ(3, list.last());
+
+    list.removeFirst();
+    EXPECT_EQ(0, list.first());
+
+    list.removeLast();
+    EXPECT_EQ(2, list.last());
 
     list.removeFirst();
-    ASSERT_EQ(2, list.first());
+    EXPECT_EQ(1, list.first());
 
     list.removeFirst();
-    ASSERT_EQ(3, list.first());
+    EXPECT_EQ(2, list.first());
 
     list.removeFirst();
-    ASSERT_TRUE(list.isEmpty());
+    EXPECT_TRUE(list.isEmpty());
 }
 
-TEST(WTF, ListHashSetAppendOrMoveToLastNewItems)
+TEST(WTF, ListHashSetRemoveFirst)
+{
+    removeFirstHelper<ListHashSet<int> >();
+}
+
+TEST(WTF, LinkedHashSetRemoveFirst)
+{
+    removeFirstHelper<LinkedHashSet<int> >();
+}
+
+template<typename Set>
+void appendOrMoveToLastNewItems()
 {
-    ListHashSet<int> list;
-    ListHashSet<int>::AddResult result = list.appendOrMoveToLast(1);
-    ASSERT_TRUE(result.isNewEntry);
+    Set list;
+    typename Set::AddResult result = list.appendOrMoveToLast(1);
+    EXPECT_TRUE(result.isNewEntry);
     result = list.add(2);
-    ASSERT_TRUE(result.isNewEntry);
+    EXPECT_TRUE(result.isNewEntry);
     result = list.appendOrMoveToLast(3);
-    ASSERT_TRUE(result.isNewEntry);
+    EXPECT_TRUE(result.isNewEntry);
 
-    ASSERT_EQ(list.size(), 3UL);
+    EXPECT_EQ(list.size(), 3UL);
 
     // The list should be in order 1, 2, 3.
-    ListHashSet<int>::iterator iterator = list.begin();
-    ASSERT_EQ(1, *iterator);
+    typename Set::iterator iterator = list.begin();
+    EXPECT_EQ(1, *iterator);
     ++iterator;
-    ASSERT_EQ(2, *iterator);
+    EXPECT_EQ(2, *iterator);
     ++iterator;
-    ASSERT_EQ(3, *iterator);
+    EXPECT_EQ(3, *iterator);
     ++iterator;
 }
 
-TEST(WTF, ListHashSetAppendOrMoveToLastWithDuplicates)
+TEST(WTF, ListHashSetAppendOrMoveToLastNewItems)
+{
+    appendOrMoveToLastNewItems<ListHashSet<int> >();
+}
+
+TEST(WTF, LinkedHashSetAppendOrMoveToLastNewItems)
+{
+    appendOrMoveToLastNewItems<LinkedHashSet<int> >();
+}
+
+template<typename Set>
+void appendOrMoveToLastWithDuplicates()
 {
-    ListHashSet<int> list;
+    Set list;
 
     // Add a single element twice.
-    ListHashSet<int>::AddResult result = list.add(1);
-    ASSERT_TRUE(result.isNewEntry);
+    typename Set::AddResult result = list.add(1);
+    EXPECT_TRUE(result.isNewEntry);
     result = list.appendOrMoveToLast(1);
-    ASSERT_FALSE(result.isNewEntry);
-    ASSERT_EQ(1UL, list.size());
+    EXPECT_FALSE(result.isNewEntry);
+    EXPECT_EQ(1UL, list.size());
 
     list.add(2);
     list.add(3);
-    ASSERT_EQ(3UL, list.size());
+    EXPECT_EQ(3UL, list.size());
 
     // Appending 2 move it to the end.
-    ASSERT_EQ(3, list.last());
+    EXPECT_EQ(3, list.last());
     result = list.appendOrMoveToLast(2);
-    ASSERT_FALSE(result.isNewEntry);
-    ASSERT_EQ(2, list.last());
+    EXPECT_FALSE(result.isNewEntry);
+    EXPECT_EQ(2, list.last());
 
     // Inverse the list by moving each element to end end.
     result = list.appendOrMoveToLast(3);
-    ASSERT_FALSE(result.isNewEntry);
+    EXPECT_FALSE(result.isNewEntry);
     result = list.appendOrMoveToLast(2);
-    ASSERT_FALSE(result.isNewEntry);
+    EXPECT_FALSE(result.isNewEntry);
     result = list.appendOrMoveToLast(1);
-    ASSERT_FALSE(result.isNewEntry);
-    ASSERT_EQ(3UL, list.size());
+    EXPECT_FALSE(result.isNewEntry);
+    EXPECT_EQ(3UL, list.size());
 
-    ListHashSet<int>::iterator iterator = list.begin();
-    ASSERT_EQ(3, *iterator);
+    typename Set::iterator iterator = list.begin();
+    EXPECT_EQ(3, *iterator);
     ++iterator;
-    ASSERT_EQ(2, *iterator);
+    EXPECT_EQ(2, *iterator);
     ++iterator;
-    ASSERT_EQ(1, *iterator);
+    EXPECT_EQ(1, *iterator);
     ++iterator;
 }
 
-TEST(WTF, ListHashSetPrependOrMoveToLastNewItems)
+TEST(WTF, ListHashSetAppendOrMoveToLastWithDuplicates)
+{
+    appendOrMoveToLastWithDuplicates<ListHashSet<int> >();
+}
+
+TEST(WTF, LinkedHashSetAppendOrMoveToLastWithDuplicates)
 {
-    ListHashSet<int> list;
-    ListHashSet<int>::AddResult result = list.prependOrMoveToFirst(1);
-    ASSERT_TRUE(result.isNewEntry);
+    appendOrMoveToLastWithDuplicates<LinkedHashSet<int> >();
+}
+
+template<typename Set>
+void prependOrMoveToFirstNewItems()
+{
+    Set list;
+    typename Set::AddResult result = list.prependOrMoveToFirst(1);
+    EXPECT_TRUE(result.isNewEntry);
     result = list.add(2);
-    ASSERT_TRUE(result.isNewEntry);
+    EXPECT_TRUE(result.isNewEntry);
     result = list.prependOrMoveToFirst(3);
-    ASSERT_TRUE(result.isNewEntry);
+    EXPECT_TRUE(result.isNewEntry);
 
-    ASSERT_EQ(list.size(), 3UL);
+    EXPECT_EQ(list.size(), 3UL);
 
     // The list should be in order 3, 1, 2.
-    ListHashSet<int>::iterator iterator = list.begin();
-    ASSERT_EQ(3, *iterator);
+    typename Set::iterator iterator = list.begin();
+    EXPECT_EQ(3, *iterator);
     ++iterator;
-    ASSERT_EQ(1, *iterator);
+    EXPECT_EQ(1, *iterator);
     ++iterator;
-    ASSERT_EQ(2, *iterator);
+    EXPECT_EQ(2, *iterator);
     ++iterator;
 }
 
-TEST(WTF, ListHashSetPrependOrMoveToLastWithDuplicates)
+TEST(WTF, ListHashSetPrependOrMoveToFirstNewItems)
+{
+    prependOrMoveToFirstNewItems<ListHashSet<int> >();
+}
+
+TEST(WTF, LinkedHashSetPrependOrMoveToFirstNewItems)
+{
+    prependOrMoveToFirstNewItems<LinkedHashSet<int> >();
+}
+
+template<typename Set>
+void prependOrMoveToLastWithDuplicates()
 {
-    ListHashSet<int> list;
+    Set list;
 
     // Add a single element twice.
-    ListHashSet<int>::AddResult result = list.add(1);
-    ASSERT_TRUE(result.isNewEntry);
+    typename Set::AddResult result = list.add(1);
+    EXPECT_TRUE(result.isNewEntry);
     result = list.prependOrMoveToFirst(1);
-    ASSERT_FALSE(result.isNewEntry);
-    ASSERT_EQ(1UL, list.size());
+    EXPECT_FALSE(result.isNewEntry);
+    EXPECT_EQ(1UL, list.size());
 
     list.add(2);
     list.add(3);
-    ASSERT_EQ(3UL, list.size());
+    EXPECT_EQ(3UL, list.size());
 
     // Prepending 2 move it to the beginning.
-    ASSERT_EQ(1, list.first());
+    EXPECT_EQ(1, list.first());
     result = list.prependOrMoveToFirst(2);
-    ASSERT_FALSE(result.isNewEntry);
-    ASSERT_EQ(2, list.first());
+    EXPECT_FALSE(result.isNewEntry);
+    EXPECT_EQ(2, list.first());
 
     // Inverse the list by moving each element to the first position.
     result = list.prependOrMoveToFirst(1);
-    ASSERT_FALSE(result.isNewEntry);
+    EXPECT_FALSE(result.isNewEntry);
     result = list.prependOrMoveToFirst(2);
-    ASSERT_FALSE(result.isNewEntry);
+    EXPECT_FALSE(result.isNewEntry);
     result = list.prependOrMoveToFirst(3);
-    ASSERT_FALSE(result.isNewEntry);
-    ASSERT_EQ(3UL, list.size());
+    EXPECT_FALSE(result.isNewEntry);
+    EXPECT_EQ(3UL, list.size());
 
-    ListHashSet<int>::iterator iterator = list.begin();
-    ASSERT_EQ(3, *iterator);
+    typename Set::iterator iterator = list.begin();
+    EXPECT_EQ(3, *iterator);
     ++iterator;
-    ASSERT_EQ(2, *iterator);
+    EXPECT_EQ(2, *iterator);
     ++iterator;
-    ASSERT_EQ(1, *iterator);
+    EXPECT_EQ(1, *iterator);
     ++iterator;
 }
 
+TEST(WTF, ListHashSetPrependOrMoveToLastWithDuplicates)
+{
+    prependOrMoveToLastWithDuplicates<ListHashSet<int> >();
+}
+
+TEST(WTF, LinkedHashSetPrependOrMoveToLastWithDuplicates)
+{
+    prependOrMoveToLastWithDuplicates<LinkedHashSet<int> >();
+}
+
 class DummyRefCounted: public WTF::RefCounted<DummyRefCounted> {
 public:
     DummyRefCounted(bool& isDeleted) : m_isDeleted(isDeleted) { m_isDeleted = false; }
@@ -192,30 +257,237 @@ private:
 
 int DummyRefCounted::m_refInvokesCount = 0;
 
-TEST(WTF, ListHashSetWithRefPtr)
+template<typename Set>
+void withRefPtr()
 {
     bool isDeleted;
+    DummyRefCounted::m_refInvokesCount = 0;
     RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted));
-    ASSERT_EQ(0, DummyRefCounted::m_refInvokesCount);
+    EXPECT_EQ(0, DummyRefCounted::m_refInvokesCount);
 
-    ListHashSet<RefPtr<DummyRefCounted> > list;
-    list.add(ptr);
+    Set set;
+    set.add(ptr);
     // Referenced only once (to store a copy in the container).
-    ASSERT_EQ(1, DummyRefCounted::m_refInvokesCount);
-    ASSERT_EQ(ptr, list.first());
+    EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
+    EXPECT_EQ(ptr, set.first());
+    EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
 
     DummyRefCounted* rawPtr = ptr.get();
 
-    ASSERT_TRUE(list.contains(ptr));
-    ASSERT_TRUE(list.contains(rawPtr));
+    EXPECT_TRUE(set.contains(ptr));
+    EXPECT_TRUE(set.contains(rawPtr));
+    EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
 
     ptr.clear();
-    ASSERT_FALSE(isDeleted);
+    EXPECT_FALSE(isDeleted);
+    EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
 
-    list.remove(rawPtr);
-    ASSERT_TRUE(isDeleted);
+    set.remove(rawPtr);
+    EXPECT_TRUE(isDeleted);
 
-    ASSERT_EQ(1, DummyRefCounted::m_refInvokesCount);
+    EXPECT_EQ(1, DummyRefCounted::m_refInvokesCount);
+}
+
+TEST(WTF, ListHashSetWithRefPtr)
+{
+    withRefPtr<ListHashSet<RefPtr<DummyRefCounted> > >();
+}
+
+TEST(WTF, LinkedHashSetWithRefPtr)
+{
+    withRefPtr<LinkedHashSet<RefPtr<DummyRefCounted> > >();
+}
+
+template<typename Set, typename SetRef, typename Iterator>
+void findHelper()
+{
+    Set set;
+    set.add(-1);
+    set.add(0);
+    set.add(1);
+    set.add(2);
+    set.add(3);
+
+    SetRef ref = set;
+    Iterator it = ref.find(2);
+    EXPECT_EQ(2, *it);
+    ++it;
+    EXPECT_EQ(3, *it);
+    --it;
+    --it;
+    EXPECT_EQ(1, *it);
+}
+
+TEST(WTF, ListHashSetFind)
+{
+    findHelper<ListHashSet<int>, const ListHashSet<int>&, ListHashSet<int>::const_iterator>();
+    findHelper<ListHashSet<int>, ListHashSet<int>&, ListHashSet<int>::iterator>();
+}
+
+TEST(WTF, LinkedHashSetFind)
+{
+    findHelper<LinkedHashSet<int>, const LinkedHashSet<int>&, LinkedHashSet<int>::const_iterator>();
+    findHelper<LinkedHashSet<int>, LinkedHashSet<int>&, LinkedHashSet<int>::iterator>();
+}
+
+template<typename Set>
+void insertBeforeHelper(bool canModifyWhileIterating)
+{
+    Set set;
+    set.add(-1);
+    set.add(0);
+    set.add(2);
+    set.add(3);
+
+    typename Set::iterator it = set.find(2);
+    EXPECT_EQ(2, *it);
+    set.insertBefore(it, 1);
+    if (!canModifyWhileIterating)
+        it = set.find(2);
+    ++it;
+    EXPECT_EQ(3, *it);
+    EXPECT_EQ(5u, set.size());
+    --it;
+    --it;
+    EXPECT_EQ(1, *it);
+    if (canModifyWhileIterating) {
+        set.remove(-1);
+        set.remove(0);
+        set.remove(2);
+        set.remove(3);
+        EXPECT_EQ(1u, set.size());
+        EXPECT_EQ(1, *it);
+        ++it;
+        EXPECT_EQ(it, set.end());
+        --it;
+        EXPECT_EQ(1, *it);
+        set.insertBefore(it, -1);
+        set.insertBefore(it, 0);
+        set.add(2);
+        set.add(3);
+    }
+    set.insertBefore(2, 42);
+    set.insertBefore(-1, 103);
+    EXPECT_EQ(103, set.first());
+    if (!canModifyWhileIterating)
+        it = set.find(1);
+    ++it;
+    EXPECT_EQ(42, *it);
+    EXPECT_EQ(7u, set.size());
+}
+
+TEST(WTF, ListHashSetInsertBefore)
+{
+    insertBeforeHelper<ListHashSet<int> >(true);
+}
+
+TEST(WTF, LinkedHashSetInsertBefore)
+{
+    insertBeforeHelper<LinkedHashSet<int> >(false);
+}
+
+template<typename Set>
+void addReturnIterator(bool canModifyWhileIterating)
+{
+    Set set;
+    set.add(-1);
+    set.add(0);
+    set.add(1);
+    set.add(2);
+
+    typename Set::iterator it = set.addReturnIterator(3);
+    EXPECT_EQ(3, *it);
+    --it;
+    EXPECT_EQ(2, *it);
+    EXPECT_EQ(5u, set.size());
+    --it;
+    EXPECT_EQ(1, *it);
+    --it;
+    EXPECT_EQ(0, *it);
+    it = set.addReturnIterator(4);
+    if (canModifyWhileIterating) {
+        set.remove(3);
+        set.remove(2);
+        set.remove(1);
+        set.remove(0);
+        set.remove(-1);
+        EXPECT_EQ(1u, set.size());
+    }
+    EXPECT_EQ(4, *it);
+    ++it;
+    EXPECT_EQ(it, set.end());
+    --it;
+    EXPECT_EQ(4, *it);
+    if (canModifyWhileIterating) {
+        set.insertBefore(it, -1);
+        set.insertBefore(it, 0);
+        set.insertBefore(it, 1);
+        set.insertBefore(it, 2);
+        set.insertBefore(it, 3);
+    }
+    EXPECT_EQ(6u, set.size());
+    it = set.addReturnIterator(5);
+    EXPECT_EQ(7u, set.size());
+    set.remove(it);
+    EXPECT_EQ(6u, set.size());
+    EXPECT_EQ(4, set.last());
+}
+
+TEST(WTF, ListHashSetAddReturnIterator)
+{
+    addReturnIterator<ListHashSet<int> >(true);
+}
+
+TEST(WTF, LinkedHashSetAddReturnIterator)
+{
+    addReturnIterator<LinkedHashSet<int> >(false);
+}
+
+template<typename Set>
+void excerciseValuePeekInType()
+{
+    Set set;
+    bool isDeleted = false;
+    bool isDeleted2 = false;
+
+    RefPtr<DummyRefCounted> ptr = adoptRef(new DummyRefCounted(isDeleted));
+    RefPtr<DummyRefCounted> ptr2 = adoptRef(new DummyRefCounted(isDeleted2));
+
+    typename Set::AddResult addResult = set.add(ptr);
+    EXPECT_TRUE(addResult.isNewEntry);
+    set.find(ptr);
+    const Set& constSet(set);
+    constSet.find(ptr);
+    EXPECT_TRUE(set.contains(ptr));
+    typename Set::iterator it = set.addReturnIterator(ptr);
+    set.appendOrMoveToLast(ptr);
+    set.prependOrMoveToFirst(ptr);
+    set.insertBefore(ptr, ptr);
+    set.insertBefore(it, ptr);
+    EXPECT_EQ(1u, set.size());
+    set.add(ptr2);
+    ptr2.clear();
+    set.remove(ptr);
+
+    EXPECT_FALSE(isDeleted);
+    ptr.clear();
+    EXPECT_TRUE(isDeleted);
+
+    EXPECT_FALSE(isDeleted2);
+    set.removeFirst();
+    EXPECT_TRUE(isDeleted2);
+
+    EXPECT_EQ(0u, set.size());
+}
+
+TEST(WTF, ListHashSetExcerciseValuePeekInType)
+{
+    excerciseValuePeekInType<ListHashSet<RefPtr<DummyRefCounted> > >();
+}
+
+TEST(WTF, LinkedHashSetExcerciseValuePeekInType)
+{
+    excerciseValuePeekInType<LinkedHashSet<RefPtr<DummyRefCounted> > >();
 }
 
 } // namespace