Fix Deque.swap for deques with inline capacity

Source/wtf/DequeTest.cpp

 /*
  * Copyright (C) 2011 Apple 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:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 23 matching lines @@
 
 namespace {
 
 TEST(DequeTest, Basic)
 {
     Deque<int> intDeque;
     EXPECT_TRUE(intDeque.isEmpty());
     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)
             --it;
 
         EXPECT_EQ(i, *it);
 
         if (increment)
             ++it;
     }
     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)
             --it;
 
         EXPECT_EQ(i, *it);
 
         if (increment)
             ++it;
     }
     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);
     intDeque.append(13);
 
     checkNumberSequence(intDeque, 10, 13, true);
     checkNumberSequence(intDeque, 13, 10, false);
     checkNumberSequenceReverse(intDeque, 13, 10, true);
     checkNumberSequenceReverse(intDeque, 10, 13, false);
 
@@ skipping 13 matching lines @@
     checkNumberSequenceReverse(intDeque, 199, 11, true);
     checkNumberSequenceReverse(intDeque, 11, 199, false);
 
     for (int i = 0; i < 180; ++i)
         EXPECT_EQ(i + 11, intDeque.takeFirst());
     checkNumberSequence(intDeque, 191, 199, true);
     checkNumberSequence(intDeque, 199, 191, false);
     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);
     checkNumberSequence(intDeque2, 199, 191, false);
     checkNumberSequenceReverse(intDeque2, 199, 191, true);
     checkNumberSequenceReverse(intDeque2, 191, 199, false);
 
     intDeque.swap(intDeque2);
 
     checkNumberSequence(intDeque, 191, 199, true);
     checkNumberSequence(intDeque, 199, 191, false);
     checkNumberSequenceReverse(intDeque, 199, 191, true);
     checkNumberSequenceReverse(intDeque, 191, 199, false);
 
     intDeque.swap(intDeque2);
 
     checkNumberSequence(intDeque2, 191, 199, true);
     checkNumberSequence(intDeque2, 199, 191, false);
     checkNumberSequenceReverse(intDeque2, 199, 191, true);
     checkNumberSequenceReverse(intDeque2, 191, 199, false);
 }
 
+TEST(DequeTest, Reverse)
+{
+    reverseTest<0>();
+    reverseTest<2>();
+}
+
 class DestructCounter {
 public:
     explicit DestructCounter(int i, int* destructNumber)
         : m_i(i)
         , m_destructNumber(destructNumber)
     { }
 
     ~DestructCounter() { ++(*m_destructNumber); }
     int get() const { return m_i; }
 
 private:
     int m_i;
     int* m_destructNumber;
 };
 
-typedef WTF::Deque<OwnPtr<DestructCounter> > OwnPtrDeque;
-
-TEST(DequeTest, OwnPtr)
+template<typename OwnPtrDeque>
+void ownPtrTest()
 {
     int destructNumber = 0;
     OwnPtrDeque deque;
     deque.append(adoptPtr(new DestructCounter(0, &destructNumber)));
     deque.append(adoptPtr(new DestructCounter(1, &destructNumber)));
     EXPECT_EQ(2u, deque.size());
 
     OwnPtr<DestructCounter>& counter0 = deque.first();
     EXPECT_EQ(0, counter0->get());
     int counter1 = deque.last()->get();
     EXPECT_EQ(1, counter1);
     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()));
         index++;
     }
     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()));
         index++;
         ++it;
     }
     EXPECT_EQ(0, destructNumber);
 
     EXPECT_EQ(0, deque.first()->get());
     deque.removeFirst();
@@ skipping 22 matching lines @@
     OwnPtrDeque copyDeque;
     deque.swap(copyDeque);
     EXPECT_EQ(0, destructNumber);
     EXPECT_EQ(count, copyDeque.size());
     EXPECT_EQ(0u, deque.size());
 
     copyDeque.clear();
     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 {
 public:
     WrappedInt(int i = 0)
         : m_originalThisPtr(this)
         , m_i(i)
     {
         constructedWrappedInts.add(this);
     }
@@ skipping 18 matching lines @@
         constructedWrappedInts.remove(this);
     }
 
     int get() const { return m_i; }
 
 private:
     void* m_originalThisPtr;
     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());
     dequeA.swap(dequeB);
 
     ASSERT_EQ(1u, dequeA.size());
     EXPECT_EQ(2, dequeA.first().get());
     ASSERT_EQ(1u, dequeB.size());
     EXPECT_EQ(1, dequeB.first().get());
 
@@ skipping 19 matching lines @@
     dequeA.swap(dequeB);
 
     ASSERT_EQ(1u, dequeA.size());
     EXPECT_EQ(1, dequeA.first().get());
     ASSERT_EQ(3u, dequeB.size());
     EXPECT_EQ(2, dequeB.first().get());
 
     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;
+
+// Filter a few numbers out to improve the running speed of the tests. The
+// test has nested loops, and removing even numbers from 4 and up from the
+// loops makes it run 10 times faster.
+bool interestingNumber(int i)
+{
+    return i < 4 || (i & 1);
+}
+
+template<size_t inlineCapacity>
+void testDestructorAndConstructorCallsWhenSwappingWithInlineCapacity()
+{
+    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);
+
+    // Add various numbers of elements to deques, then remove various numbers
+    // of elements from the head. This creates in-use ranges in the backing
+    // that sometimes wrap around the end of the buffer, testing various ways
+    // in which the in-use ranges of the inline buffers can overlap when we
+    // call swap().
+    for (unsigned i = 0; i < 12; i++) {
+        if (!interestingNumber(i))
+            continue;
+        for (unsigned j = i; j < 12; j++) {
+            if (!interestingNumber(j))
+                continue;
+            deque.clear();
+            deque2.clear();
+            EXPECT_EQ(0u, LivenessCounter::s_live);
+            for (unsigned k = 0; k < j; k++)
+                deque.append(&counter);
+            EXPECT_EQ(j, LivenessCounter::s_live);
+            EXPECT_EQ(j, deque.size());
+            for (unsigned k = 0; k < i; k++)
+                deque.removeFirst();
+
+            EXPECT_EQ(j - i, LivenessCounter::s_live);
+            EXPECT_EQ(j - i, deque.size());
+            deque.swap(deque2);
+            EXPECT_EQ(j - i, LivenessCounter::s_live);
+            EXPECT_EQ(0u, deque.size());
+            EXPECT_EQ(j - i, deque2.size());
+            deque.swap(deque2);
+            EXPECT_EQ(j - i, LivenessCounter::s_live);
+
+            deque2.append(&counter);
+            deque2.append(&counter);
+            deque2.append(&counter);
+
+            for (unsigned k = 0; k < 12; k++) {
+                EXPECT_EQ(3 + j - i, LivenessCounter::s_live);
+                EXPECT_EQ(j - i, deque.size());
+                EXPECT_EQ(3u, deque2.size());
+                deque.swap(deque2);
+                EXPECT_EQ(3 + j - i, LivenessCounter::s_live);
+                EXPECT_EQ(j - i, deque2.size());
+                EXPECT_EQ(3u, deque.size());
+                deque.swap(deque2);
+                EXPECT_EQ(3 + j - i, LivenessCounter::s_live);
+                EXPECT_EQ(j - i, deque.size());
+                EXPECT_EQ(3u, deque2.size());
+
+                deque2.removeFirst();
+                deque2.append(&counter);
+            }
+        }
+    }
+
+}
+
+TEST(DequeTest, SwapWithConstructorsAndDestructors)
+{
+    testDestructorAndConstructorCallsWhenSwappingWithInlineCapacity<0>();
+    testDestructorAndConstructorCallsWhenSwappingWithInlineCapacity<4>();
+    testDestructorAndConstructorCallsWhenSwappingWithInlineCapacity<9>();
+}
+
+template<size_t inlineCapacity>
+void testValuesMovedAndSwappedWithInlineCapacity()
+{
+    Deque<unsigned, inlineCapacity> deque;
+    Deque<unsigned, inlineCapacity> deque2;
+
+    // Add various numbers of elements to deques, then remove various numbers
+    // of elements from the head. This creates in-use ranges in the backing
+    // that sometimes wrap around the end of the buffer, testing various ways
+    // in which the in-use ranges of the inline buffers can overlap when we
+    // call swap().
+    for (unsigned pad = 0; pad < 12; pad++) {
+        if (!interestingNumber(pad))
+            continue;
+        for (unsigned pad2 = 0; pad2 < 12; pad2++) {
+            if (!interestingNumber(pad2))
+                continue;
+            for (unsigned size = 0; size < 12; size++) {
+                if (!interestingNumber(size))
+                    continue;
+                for (unsigned size2 = 0; size2 < 12; size2++) {
+                    if (!interestingNumber(size2))
+                        continue;
+                    deque.clear();
+                    deque2.clear();
+                    for (unsigned i = 0; i < pad; i++)
+                        deque.append(103);
+                    for (unsigned i = 0; i < pad2; i++)
+                        deque2.append(888);
+                    for (unsigned i = 0; i < size; i++)
+                        deque.append(i);
+                    for (unsigned i = 0; i < size2; i++)
+                        deque2.append(i + 42);
+                    for (unsigned i = 0; i < pad; i++)
+                        EXPECT_EQ(103u, deque.takeFirst());
+                    for (unsigned i = 0; i < pad2; i++)
+                        EXPECT_EQ(888u, deque2.takeFirst());
+                    EXPECT_EQ(size, deque.size());
+                    EXPECT_EQ(size2, deque2.size());
+                    deque.swap(deque2);
+                    for (unsigned i = 0; i < size; i++)
+                        EXPECT_EQ(i, deque2.takeFirst());
+                    for (unsigned i = 0; i < size2; i++)
+                        EXPECT_EQ(i + 42, deque.takeFirst());
+                }
+            }
+        }
+    }
+}
+
+TEST(DequeTest, ValuesMovedAndSwappedWithInlineCapacity)
+{
+    testValuesMovedAndSwappedWithInlineCapacity<0>();
+    testValuesMovedAndSwappedWithInlineCapacity<4>();
+    testValuesMovedAndSwappedWithInlineCapacity<9>();
+}
+
 } // namespace