From f045d600fc5c17f8a3537401baf45043e7617368 Mon Sep 17 00:00:00 2001 From: bsalomon Date: Wed, 18 Nov 2015 19:01:12 -0800 Subject: Make block size a template parameter of SkTLList Review URL: https://codereview.chromium.org/1457123002 --- tests/LListTest.cpp | 314 ++++++++++++++++++++++++++-------------------------- 1 file changed, 157 insertions(+), 157 deletions(-) (limited to 'tests') diff --git a/tests/LListTest.cpp b/tests/LListTest.cpp index e0e55d0419..70f320f977 100644 --- a/tests/LListTest.cpp +++ b/tests/LListTest.cpp @@ -41,7 +41,7 @@ static void check_list(const SkTInternalLList& list, #endif } -static void TestTInternalLList(skiatest::Reporter* reporter) { +static void test_tinternallist(skiatest::Reporter* reporter) { SkTInternalLList list; ListElement elements[4] = { ListElement(0), @@ -114,175 +114,175 @@ static void TestTInternalLList(skiatest::Reporter* reporter) { } } -static void TestTLList(skiatest::Reporter* reporter) { - typedef SkTLList ElList; - typedef ElList::Iter Iter; +template static void test_tllist(skiatest::Reporter* reporter) { + typedef SkTLList ElList; + typedef typename ElList::Iter Iter; SkRandom random; - for (int i = 1; i <= 16; i *= 2) { - - 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); - - // 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(); - - // 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); - - // 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()); - - 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(); + ElList list1; + ElList list2; + 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); + + // 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(); + + // 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); + + // 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()); + + 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(); + + 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); } - Iter prev(iter); - Iter next(iter); - next.next(); - prev.prev(); - - 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); - } + } 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); } } } - ++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)(); - - if (random.nextBool()) { - start = Iter::kHead_IterStart; - incrFunc = &Iter::next; - } else { - start = Iter::kTail_IterStart; - incrFunc = &Iter::prev; - } + start = Iter::kTail_IterStart; + incrFunc = &Iter::prev; + } - // find the element - Iter iter(list1, start); - while (n--) { - REPORTER_ASSERT(reporter, iter.get()); - (iter.*incrFunc)(); - } + // find the element + Iter iter(list1, start); + while (n--) { 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; + (iter.*incrFunc)(); } - REPORTER_ASSERT(reporter, count == list1.count()); + 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); } -- cgit v1.2.3