Make block size a template parameter of SkTLList

tests/LListTest.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkRandom.h"
 #include "SkTInternalLList.h"
 #include "SkTLList.h"
@@ skipping 23 matching lines @@
 #ifdef SK_DEBUG
     list.validate();
     REPORTER_ASSERT(reporter, numElements == list.countEntries());
     REPORTER_ASSERT(reporter, in0 == list.isInList(&elements[0]));
     REPORTER_ASSERT(reporter, in1 == list.isInList(&elements[1]));
     REPORTER_ASSERT(reporter, in2 == list.isInList(&elements[2]));
     REPORTER_ASSERT(reporter, in3 == list.isInList(&elements[3]));
 #endif
 }
 
-static void TestTInternalLList(skiatest::Reporter* reporter) {
+static void test_tinternallist(skiatest::Reporter* reporter) {
     SkTInternalLList<ListElement> list;
     ListElement elements[4] = {
         ListElement(0),
         ListElement(1),
         ListElement(2),
         ListElement(3),
     };
 
     // list should be empty to start with
     check_list(list, reporter, true, 0, false, false, false, false, elements);
@@ skipping 52 matching lines @@
 
     list.addBefore(&elements[2], &elements[3]);
     check_list(list, reporter, false, 4, true, true, true, true, elements);
 
     cur = iter.init(list, Iter::kHead_IterStart);
     for (int i = 0; cur; ++i, cur = iter.next()) {
         REPORTER_ASSERT(reporter, cur->fID == i);
     }
 }
 
-static void TestTLList(skiatest::Reporter* reporter) {
-    typedef SkTLList<ListElement> ElList;
-    typedef ElList::Iter Iter;
+template <unsigned int N> static void test_tllist(skiatest::Reporter* reporter) {
+    typedef SkTLList<ListElement, N> ElList;
+    typedef typename ElList::Iter Iter;
     SkRandom random;
 
-    for (int i = 1; i <= 16; i *= 2) {
+    ElList list1;
+    ElList list2;
+    Iter iter1;
+    Iter iter2;
+    Iter iter3;
+    Iter iter4;
 
-        ElList list1(i);
-        ElList list2(i);
-        Iter iter1;
-        Iter iter2;
-        Iter iter3;
-        Iter iter4;
+    REPORTER_ASSERT(reporter, list1.isEmpty());
+    REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kHead_IterStart));
+    REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kTail_IterStart));
+    // Try popping an empty list
+    list1.popHead();
+    list1.popTail();
+    REPORTER_ASSERT(reporter, list1.isEmpty());
+    REPORTER_ASSERT(reporter, list1 == list2);
 
-        REPORTER_ASSERT(reporter, list1.isEmpty());
-        REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kHead_IterStart));
-        REPORTER_ASSERT(reporter, nullptr == iter1.init(list1, Iter::kTail_IterStart));
-        // Try popping an empty list
-        list1.popHead();
-        list1.popTail();
-        REPORTER_ASSERT(reporter, list1.isEmpty());
-        REPORTER_ASSERT(reporter, list1 == list2);
+    // Create two identical lists, one by appending to head and the other to the tail.
+    list1.addToHead(ListElement(1));
+    list2.addToTail(ListElement(1));
+    iter1.init(list1, Iter::kHead_IterStart);
+    iter2.init(list1, Iter::kTail_IterStart);
+    REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID);
+    iter3.init(list2, Iter::kHead_IterStart);
+    iter4.init(list2, Iter::kTail_IterStart);
+    REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
+    REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
+    REPORTER_ASSERT(reporter, list1 == list2);
 
-        // Create two identical lists, one by appending to head and the other to the tail.
-        list1.addToHead(ListElement(1));
-        list2.addToTail(ListElement(1));
-        iter1.init(list1, Iter::kHead_IterStart);
-        iter2.init(list1, Iter::kTail_IterStart);
-        REPORTER_ASSERT(reporter, iter1.get()->fID == iter2.get()->fID);
-        iter3.init(list2, Iter::kHead_IterStart);
-        iter4.init(list2, Iter::kTail_IterStart);
-        REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
-        REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
-        REPORTER_ASSERT(reporter, list1 == list2);
+    list2.reset();
 
-        list2.reset();
+    // use both before/after in-place construction on an empty list
+    list2.addBefore(list2.headIter(), 1);
+    REPORTER_ASSERT(reporter, list2 == list1);
+    list2.reset();
 
-        // use both before/after in-place construction on an empty list
-        list2.addBefore(list2.headIter(), 1);
-        REPORTER_ASSERT(reporter, list2 == list1);
-        list2.reset();
+    list2.addAfter(list2.tailIter(), 1);
+    REPORTER_ASSERT(reporter, list2 == list1);
 
-        list2.addAfter(list2.tailIter(), 1);
-        REPORTER_ASSERT(reporter, list2 == list1);
+    // add an element to the second list, check that iters are still valid
+    iter3.init(list2, Iter::kHead_IterStart);
+    iter4.init(list2, Iter::kTail_IterStart);
+    list2.addToHead(ListElement(2));
 
-        // add an element to the second list, check that iters are still valid
-        iter3.init(list2, Iter::kHead_IterStart);
-        iter4.init(list2, Iter::kTail_IterStart);
-        list2.addToHead(ListElement(2));
+    REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
+    REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
+    REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()->fID);
+    REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()->fID);
+    REPORTER_ASSERT(reporter, list1 != list2);
+    list1.addToHead(ListElement(2));
+    REPORTER_ASSERT(reporter, list1 == list2);
+    REPORTER_ASSERT(reporter, !list1.isEmpty());
 
-        REPORTER_ASSERT(reporter, iter3.get()->fID == iter1.get()->fID);
-        REPORTER_ASSERT(reporter, iter4.get()->fID == iter1.get()->fID);
-        REPORTER_ASSERT(reporter, 1 == Iter(list2, Iter::kTail_IterStart).get()->fID);
-        REPORTER_ASSERT(reporter, 2 == Iter(list2, Iter::kHead_IterStart).get()->fID);
-        REPORTER_ASSERT(reporter, list1 != list2);
-        list1.addToHead(ListElement(2));
-        REPORTER_ASSERT(reporter, list1 == list2);
-        REPORTER_ASSERT(reporter, !list1.isEmpty());
+    list1.reset();
+    list2.reset();
+    REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty());
 
-        list1.reset();
-        list2.reset();
-        REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty());
+    // randomly perform insertions and deletions on a list and perform tests
+    int count = 0;
+    for (int j = 0; j < 100; ++j) {
+        if (list1.isEmpty() || random.nextBiasedBool(3  * SK_Scalar1 / 4)) {
+            int id = j;
+            // Choose one of three ways to insert a new element: at the head, at the tail,
+            // before a random element, after a random element
+            int numValidMethods = 0 == count ? 2 : 4;
+            int insertionMethod = random.nextULessThan(numValidMethods);
+            switch (insertionMethod) {
+                case 0:
+                    list1.addToHead(ListElement(id));
+                    break;
+                case 1:
+                    list1.addToTail(ListElement(id));
+                    break;
+                case 2: // fallthru to share code that picks random element.
+                case 3: {
+                    int n = random.nextULessThan(list1.count());
+                    Iter iter = list1.headIter();
+                    // remember the elements before/after the insertion point.
+                    while (n--) {
+                        iter.next();
+                    }
+                    Iter prev(iter);
+                    Iter next(iter);
+                    next.next();
+                    prev.prev();
 
-        // randomly perform insertions and deletions on a list and perform tests
-        int count = 0;
-        for (int j = 0; j < 100; ++j) {
-            if (list1.isEmpty() || random.nextBiasedBool(3  * SK_Scalar1 / 4)) {
-                int id = j;
-                // Choose one of three ways to insert a new element: at the head, at the tail,
-                // before a random element, after a random element
-                int numValidMethods = 0 == count ? 2 : 4;
-                int insertionMethod = random.nextULessThan(numValidMethods);
-                switch (insertionMethod) {
-                    case 0:
-                        list1.addToHead(ListElement(id));
-                        break;
-                    case 1:
-                        list1.addToTail(ListElement(id));
-                        break;
-                    case 2: // fallthru to share code that picks random element.
-                    case 3: {
-                        int n = random.nextULessThan(list1.count());
-                        Iter iter = list1.headIter();
-                        // remember the elements before/after the insertion point.
-                        while (n--) {
-                            iter.next();
+                    SkASSERT(iter.get());
+                    // insert either before or after the iterator, then check that the
+                    // surrounding sequence is correct.
+                    if (2 == insertionMethod) {
+                        list1.addBefore(iter, id);
+                        Iter newItem(iter);
+                        newItem.prev();
+                        REPORTER_ASSERT(reporter, newItem.get()->fID == id);
+
+                        if (next.get()) {
+                            REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID);
                         }
-                        Iter prev(iter);
-                        Iter next(iter);
-                        next.next();
-                        prev.prev();
+                        if (prev.get()) {
+                            REPORTER_ASSERT(reporter, prev.next()->fID == id);
+                        }
+                    } else {
+                        list1.addAfter(iter, id);
+                        Iter newItem(iter);
+                        newItem.next();
+                        REPORTER_ASSERT(reporter, newItem.get()->fID == id);
 
-                        SkASSERT(iter.get());
-                        // insert either before or after the iterator, then check that the
-                        // surrounding sequence is correct.
-                        if (2 == insertionMethod) {
-                            list1.addBefore(iter, id);
-                            Iter newItem(iter);
-                            newItem.prev();
-                            REPORTER_ASSERT(reporter, newItem.get()->fID == id);
-
-                            if (next.get()) {
-                                REPORTER_ASSERT(reporter, next.prev()->fID == iter.get()->fID);
-                            }
-                            if (prev.get()) {
-                                REPORTER_ASSERT(reporter, prev.next()->fID == id);
-                            }
-                        } else {
-                            list1.addAfter(iter, id);
-                            Iter newItem(iter);
-                            newItem.next();
-                            REPORTER_ASSERT(reporter, newItem.get()->fID == id);
-
-                            if (next.get()) {
-                                REPORTER_ASSERT(reporter, next.prev()->fID == id);
-                            }
-                            if (prev.get()) {
-                                REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID);
-                            }
+                        if (next.get()) {
+                            REPORTER_ASSERT(reporter, next.prev()->fID == id);
+                        }
+                        if (prev.get()) {
+                            REPORTER_ASSERT(reporter, prev.next()->fID == iter.get()->fID);
                         }
                     }
                 }
-                ++count;
+            }
+            ++count;
+        } else {
+            // walk to a random place either forward or backwards and remove.
+            int n = random.nextULessThan(list1.count());
+            typename Iter::IterStart start;
+            ListElement* (Iter::*incrFunc)();
+
+            if (random.nextBool()) {
+                start = Iter::kHead_IterStart;
+                incrFunc = &Iter::next;
             } else {
-                // walk to a random place either forward or backwards and remove.
-                int n = random.nextULessThan(list1.count());
-                Iter::IterStart start;
-                ListElement* (Iter::*incrFunc)();
+                start = Iter::kTail_IterStart;
+                incrFunc = &Iter::prev;
+            }
 
-                if (random.nextBool()) {
-                    start = Iter::kHead_IterStart;
-                    incrFunc = &Iter::next;
-                } else {
-                    start = Iter::kTail_IterStart;
-                    incrFunc = &Iter::prev;
-                }
+            // find the element
+            Iter iter(list1, start);
+            while (n--) {
+                REPORTER_ASSERT(reporter, iter.get());
+                (iter.*incrFunc)();
+            }
+            REPORTER_ASSERT(reporter, iter.get());
 
-                // find the element
-                Iter iter(list1, start);
-                while (n--) {
-                    REPORTER_ASSERT(reporter, iter.get());
-                    (iter.*incrFunc)();
-                }
-                REPORTER_ASSERT(reporter, iter.get());
+            // remember the prev and next elements from the element to be removed
+            Iter prev = iter;
+            Iter next = iter;
+            prev.prev();
+            next.next();
+            list1.remove(iter.get());
 
-                // remember the prev and next elements from the element to be removed
-                Iter prev = iter;
-                Iter next = iter;
-                prev.prev();
-                next.next();
-                list1.remove(iter.get());
-
-                // make sure the remembered next/prev iters still work
-                Iter pn = prev; pn.next();
-                Iter np = next; np.prev();
-                // pn should match next unless the target node was the head, in which case prev
-                // walked off the list.
-                REPORTER_ASSERT(reporter, pn.get() == next.get() || nullptr == prev.get());
-                // Similarly, np should match prev unless next originally walked off the tail.
-                REPORTER_ASSERT(reporter, np.get() == prev.get() || nullptr == next.get());
-                --count;
-            }
-            REPORTER_ASSERT(reporter, count == list1.count());
+            // make sure the remembered next/prev iters still work
+            Iter pn = prev; pn.next();
+            Iter np = next; np.prev();
+            // pn should match next unless the target node was the head, in which case prev
+            // walked off the list.
+            REPORTER_ASSERT(reporter, pn.get() == next.get() || nullptr == prev.get());
+            // Similarly, np should match prev unless next originally walked off the tail.
+            REPORTER_ASSERT(reporter, np.get() == prev.get() || nullptr == next.get());
+            --count;
         }
-        list1.reset();
+        REPORTER_ASSERT(reporter, count == list1.count());
     }
 }
 
 DEF_TEST(LList, reporter) {
-    TestTInternalLList(reporter);
-    TestTLList(reporter);
+    test_tinternallist(reporter);
+    test_tllist<1>(reporter);
+    test_tllist<3>(reporter);
+    test_tllist<8>(reporter);
+    test_tllist<10>(reporter);
+    test_tllist<16>(reporter);
 }