Make block size a template parameter of SkTLList
Review URL: https://codereview.chromium.org/1457123002
diff --git a/tests/LListTest.cpp b/tests/LListTest.cpp
index e0e55d0..70f320f 100644
--- a/tests/LListTest.cpp
+++ b/tests/LListTest.cpp
@@ -41,7 +41,7 @@
#endif
}
-static void TestTInternalLList(skiatest::Reporter* reporter) {
+static void test_tinternallist(skiatest::Reporter* reporter) {
SkTInternalLList<ListElement> list;
ListElement elements[4] = {
ListElement(0),
@@ -114,175 +114,175 @@
}
}
-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;
- } else {
- // walk to a random place either forward or backwards and remove.
- int n = random.nextULessThan(list1.count());
- Iter::IterStart start;
- ListElement* (Iter::*incrFunc)();
-
- 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());
-
- // 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());
+ ++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 {
+ 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());
+
+ // 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;
}
- 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);
}