From d29902e0d7e0a5860b6e4b5d11f4730a0728dc17 Mon Sep 17 00:00:00 2001 From: "bsalomon@google.com" Date: Mon, 3 Dec 2012 15:54:12 +0000 Subject: Add SkTLList, linked list class implemented on top of the internal llist class. R=robertphillips@google.com Review URL: https://codereview.appspot.com/6869049 git-svn-id: http://skia.googlecode.com/svn/trunk@6644 2bbb7eff-a529-9590-31e7-b0007b416f81 --- tests/LListTest.cpp | 231 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 231 insertions(+) create mode 100644 tests/LListTest.cpp (limited to 'tests/LListTest.cpp') diff --git a/tests/LListTest.cpp b/tests/LListTest.cpp new file mode 100644 index 0000000000..9d48e28135 --- /dev/null +++ b/tests/LListTest.cpp @@ -0,0 +1,231 @@ +/* + * 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 "Test.h" +#include "SkRandom.h" +#include "SkTInternalLList.h" +#include "SkTLList.h" + +class ListElement { +public: + ListElement(int id) : fID(id) { + } + bool operator== (const ListElement& other) { return fID == other.fID; } + +#ifdef SK_ENABLE_INST_COUNT + // Make the instance count available publicly. + static int InstanceCount() { return GetInstanceCount(); } +#endif + + int fID; + +private: + SK_DECLARE_INST_COUNT_ROOT(ListElement); + SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement); +}; + +SK_DEFINE_INST_COUNT(ListElement); + +static void check_list(const SkTInternalLList& list, + skiatest::Reporter* reporter, + bool empty, + int numElements, + bool in0, bool in1, bool in2, bool in3, + ListElement elements[4]) { + + REPORTER_ASSERT(reporter, empty == list.isEmpty()); +#if SK_DEBUG + 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) { + SkTInternalLList 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); + + list.addToHead(&elements[0]); + + check_list(list, reporter, false, 1, true, false, false, false, elements); + + list.addToHead(&elements[1]); + list.addToHead(&elements[2]); + list.addToHead(&elements[3]); + + check_list(list, reporter, false, 4, true, true, true, true, elements); + + // test out iterators + typedef SkTInternalLList::Iter Iter; + Iter iter; + + ListElement* cur = iter.init(list, Iter::kHead_IterStart); + for (int i = 0; NULL != cur; ++i, cur = iter.next()) { + REPORTER_ASSERT(reporter, cur->fID == 3-i); + } + + cur = iter.init(list, Iter::kTail_IterStart); + for (int i = 0; NULL != cur; ++i, cur = iter.prev()) { + REPORTER_ASSERT(reporter, cur->fID == i); + } + + // remove middle, frontmost then backmost + list.remove(&elements[1]); + list.remove(&elements[3]); + list.remove(&elements[0]); + + check_list(list, reporter, false, 1, false, false, true, false, elements); + + // remove last element + list.remove(&elements[2]); + + // list should be empty again + check_list(list, reporter, true, 0, false, false, false, false, elements); +} + +static void TestTLList(skiatest::Reporter* reporter) { + typedef SkTLList ElList; + typedef 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; + +#ifdef SK_ENABLE_INST_COUNT + SkASSERT(0 == ListElement::InstanceCount()); +#endif + + REPORTER_ASSERT(reporter, list1.isEmpty()); + REPORTER_ASSERT(reporter, NULL == iter1.init(list1, Iter::kHead_IterStart)); + REPORTER_ASSERT(reporter, NULL == 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 head. + list1.addToHead(ListElement(1)); + list2.addToTail(ListElement(1)); +#ifdef SK_ENABLE_INST_COUNT + SkASSERT(2 == ListElement::InstanceCount()); +#endif + 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); + + // add an element to the second list, check that iters are still valid + list2.addToHead(ListElement(2)); +#ifdef SK_ENABLE_INST_COUNT + SkASSERT(3 == ListElement::InstanceCount()); +#endif + 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); +#ifdef SK_ENABLE_INST_COUNT + SkASSERT(4 == ListElement::InstanceCount()); +#endif + list1.reset(); + list2.reset(); +#ifdef SK_ENABLE_INST_COUNT + SkASSERT(0 == ListElement::InstanceCount()); +#endif + REPORTER_ASSERT(reporter, list1.isEmpty() && list2.isEmpty()); + + int count = 0; + for (int j = 0; j < 100; ++j) { + if (list1.isEmpty() || random.nextBiasedBool(3 * SK_Scalar1 / 4)) { + int id = static_cast(random.nextU()); + if (random.nextBool()) { + list1.addToHead(ListElement(id)); + } else { + list1.addToTail(ListElement(id)); + } + ++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, NULL != iter.get()); + (iter.*incrFunc)(); + } + REPORTER_ASSERT(reporter, NULL != 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() || NULL == prev.get()); + // Similarly, np should match prev unless next originally walked off the tail. + REPORTER_ASSERT(reporter, np.get() == prev.get() || NULL == next.get()); + --count; + } + REPORTER_ASSERT(reporter, count == list1.count()); +#ifdef SK_ENABLE_INST_COUNT + SkASSERT(count == ListElement::InstanceCount()); +#endif + } + list1.reset(); +#ifdef SK_ENABLE_INST_COUNT + SkASSERT(0 == ListElement::InstanceCount()); +#endif + } +} + +static void test_llists(skiatest::Reporter* reporter) { + TestTInternalLList(reporter); + TestTLList(reporter); +} + +#include "TestClassDef.h" +DEFINE_TESTCLASS("LList", TestLListClass, test_llists) -- cgit v1.2.3