Fix Deque.swap for deques with inline capacity

Source/wtf/DequeTest.cpp

Index: Source/wtf/DequeTest.cpp
diff --git a/Source/wtf/DequeTest.cpp b/Source/wtf/DequeTest.cpp
index e343158dfc6fec0f7cd0f874f5011a5a6a50ebec..60b6f7dbf4fbb06d43d95b3eb349338fdf614503 100644
--- a/Source/wtf/DequeTest.cpp
+++ b/Source/wtf/DequeTest.cpp
@@ -41,9 +41,10 @@ TEST(DequeTest, Basic)
     EXPECT_EQ(0ul, intDeque.size());
 }
 
-void checkNumberSequence(Deque<int>& deque, int from, int to, bool increment)
+template<size_t inlineCapacity>
+void checkNumberSequence(Deque<int, inlineCapacity>& deque, int from, int to, bool increment)
 {
-    Deque<int>::iterator it = increment ? deque.begin() : deque.end();
+    typename Deque<int, inlineCapacity>::iterator it = increment ? deque.begin() : deque.end();
     int step = from < to ? 1 : -1;
     for (int i = from; i != to + step; i += step) {
         if (!increment)
@@ -57,9 +58,10 @@ void checkNumberSequence(Deque<int>& deque, int from, int to, bool increment)
     EXPECT_EQ(increment ? deque.end() : deque.begin(), it);
 }
 
-void checkNumberSequenceReverse(Deque<int>& deque, int from, int to, bool increment)
+template<size_t inlineCapacity>
+void checkNumberSequenceReverse(Deque<int, inlineCapacity>& deque, int from, int to, bool increment)
 {
-    Deque<int>::reverse_iterator it = increment ? deque.rbegin() : deque.rend();
+    typename Deque<int, inlineCapacity>::reverse_iterator it = increment ? deque.rbegin() : deque.rend();
     int step = from < to ? 1 : -1;
     for (int i = from; i != to + step; i += step) {
         if (!increment)
@@ -73,9 +75,10 @@ void checkNumberSequenceReverse(Deque<int>& deque, int from, int to, bool increm
     EXPECT_EQ(increment ? deque.rend() : deque.rbegin(), it);
 }
 
-TEST(DequeTest, Reverse)
+template<size_t inlineCapacity>
+void reverseTest()
 {
-    Deque<int> intDeque;
+    Deque<int, inlineCapacity> intDeque;
     intDeque.append(10);
     intDeque.append(11);
     intDeque.append(12);
@@ -109,7 +112,7 @@ TEST(DequeTest, Reverse)
     checkNumberSequenceReverse(intDeque, 199, 191, true);
     checkNumberSequenceReverse(intDeque, 191, 199, false);
 
-    Deque<int> intDeque2;
+    Deque<int, inlineCapacity> intDeque2;
     swap(intDeque, intDeque2);
 
     checkNumberSequence(intDeque2, 191, 199, true);
@@ -132,6 +135,12 @@ TEST(DequeTest, Reverse)
     checkNumberSequenceReverse(intDeque2, 191, 199, false);
 }
 
+TEST(DequeTest, Reverse)
+{
+    reverseTest<0>();
+    reverseTest<2>();
+}
+
 class DestructCounter {
 public:
     explicit DestructCounter(int i, int* destructNumber)
@@ -147,9 +156,8 @@ private:
     int* m_destructNumber;
 };
 
-typedef WTF::Deque<OwnPtr<DestructCounter> > OwnPtrDeque;
-
-TEST(DequeTest, OwnPtr)
+template<typename OwnPtrDeque>
+void ownPtrTest()
 {
     int destructNumber = 0;
     OwnPtrDeque deque;
@@ -164,7 +172,7 @@ TEST(DequeTest, OwnPtr)
     EXPECT_EQ(0, destructNumber);
 
     size_t index = 0;
-    for (OwnPtrDeque::iterator iter = deque.begin(); iter != deque.end(); ++iter) {
+    for (typename OwnPtrDeque::iterator iter = deque.begin(); iter != deque.end(); ++iter) {
         OwnPtr<DestructCounter>& refCounter = *iter;
         EXPECT_EQ(index, static_cast<size_t>(refCounter->get()));
         EXPECT_EQ(index, static_cast<size_t>((*refCounter).get()));
@@ -172,7 +180,7 @@ TEST(DequeTest, OwnPtr)
     }
     EXPECT_EQ(0, destructNumber);
 
-    OwnPtrDeque::iterator it = deque.begin();
+    typename OwnPtrDeque::iterator it = deque.begin();
     for (index = 0; index < deque.size(); ++index) {
         OwnPtr<DestructCounter>& refCounter = *it;
         EXPECT_EQ(index, static_cast<size_t>(refCounter->get()));
@@ -215,6 +223,13 @@ TEST(DequeTest, OwnPtr)
     EXPECT_EQ(count, static_cast<size_t>(destructNumber));
 }
 
+TEST(DequeTest, OwnPtr)
+{
+    ownPtrTest<WTF::Deque<OwnPtr<DestructCounter> > >();
+    ownPtrTest<WTF::Deque<OwnPtr<DestructCounter>, 2> >();
+}
+
+
 // WrappedInt class will fail if it was memmoved or memcpyed.
 static HashSet<void*> constructedWrappedInts;
 class WrappedInt {
@@ -253,11 +268,12 @@ private:
     int m_i;
 };
 
-TEST(DequeTest, SwapWithoutInlineCapacity)
+template<size_t inlineCapacity>
+void swapWithOrWithoutInlineCapacity()
 {
-    Deque<WrappedInt> dequeA;
+    Deque<WrappedInt, inlineCapacity> dequeA;
     dequeA.append(WrappedInt(1));
-    Deque<WrappedInt> dequeB;
+    Deque<WrappedInt, inlineCapacity> dequeB;
     dequeB.append(WrappedInt(2));
 
     ASSERT_EQ(dequeA.size(), dequeB.size());
@@ -297,4 +313,95 @@ TEST(DequeTest, SwapWithoutInlineCapacity)
     dequeB.swap(dequeA);
 }
 
+TEST(DequeTest, SwapWithOrWithoutInlineCapacity)
+{
+    swapWithOrWithoutInlineCapacity<0>();
+    swapWithOrWithoutInlineCapacity<2>();
+}
+
+class LivenessCounter {
+public:
+    void ref() { s_live++; }
+    void deref() { s_live--; }
+
+    static unsigned s_live;
+};
+
+unsigned LivenessCounter::s_live = 0;
+
+bool fairlyPrime(int i)
+{
+    return !(i % 2 || i % 3 || i % 5 || i % 7);
+}
+
+template<size_t inlineCapacity>
+void theBigSwapTest()
+{
+    LivenessCounter::s_live = 0;
+    LivenessCounter counter;
+    EXPECT_EQ(0u, LivenessCounter::s_live);
+
+    Deque<RefPtr<LivenessCounter>, inlineCapacity> deque;
+    Deque<RefPtr<LivenessCounter>, inlineCapacity> deque2;
+    deque.append(&counter);
+    deque2.append(&counter);
+    EXPECT_EQ(2u, LivenessCounter::s_live);
+
+    for (unsigned i = 0; i < 13; i++) {
+        if (!fairlyPrime(i))
+            continue;
+        for (unsigned j = i; j < 13; j++) {
+            if (!fairlyPrime(j))
+                continue;
+            deque.clear();
+            deque2.clear();
+            EXPECT_EQ(0u, LivenessCounter::s_live);
+            for (unsigned k = 0; k < i; k++)
+                deque.append(&counter);
+            EXPECT_EQ(i, LivenessCounter::s_live);
+            EXPECT_EQ(i, deque.size());
+            for (unsigned k = 0; k < j; k++)
+                deque.removeFirst();
+
+            EXPECT_EQ(i - j, LivenessCounter::s_live);

[Ken Russell (switch to Gerrit), 2014/07/16 07:38:42]

How does this work? It looks to me like in the nested loops above, j is greater
than or equal to i. Won't that cause removeFirst() to be called too many times?

[Erik Corry, 2014/07/17 12:40:04]

It doesn't work, but the fairlyPrime test that was supposed to make the test run
faster by skipping some boring cases accidentally disabled most of the test.
Ooops!

+            EXPECT_EQ(i - j, deque.size());
+            deque.swap(deque2);
+            EXPECT_EQ(i - j, LivenessCounter::s_live);
+            EXPECT_EQ(0u, deque.size());
+            EXPECT_EQ(i - j, deque2.size());
+            deque.swap(deque2);
+            EXPECT_EQ(i - j, LivenessCounter::s_live);
+
+            deque2.append(&counter);
+            deque2.append(&counter);
+            deque2.append(&counter);
+
+            for (unsigned k = 0; k < 13; k++) {
+                EXPECT_EQ(3 + i - j, LivenessCounter::s_live);
+                EXPECT_EQ(i - j, deque.size());
+                EXPECT_EQ(3u, deque2.size());
+                deque.swap(deque2);
+                EXPECT_EQ(3 + i - j, LivenessCounter::s_live);
+                EXPECT_EQ(i - j, deque2.size());
+                EXPECT_EQ(3u, deque.size());
+                deque.swap(deque2);
+                EXPECT_EQ(3 + i - j, LivenessCounter::s_live);
+                EXPECT_EQ(i - j, deque.size());
+                EXPECT_EQ(3u, deque2.size());
+
+                deque2.removeFirst();
+                deque2.append(&counter);
+            }
+        }
+    }
+
+}
+
+TEST(DequeTest, BigSwapTest)
+{
+    theBigSwapTest<0>();
+    theBigSwapTest<2>();
+    theBigSwapTest<10>();
+}
+
 } // namespace