| /* |
| * 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<ListElement>& 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<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); |
| |
| 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<ListElement>::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<ListElement> 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 tail. |
| 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 |
| REPORTER_ASSERT(reporter, !list1.isEmpty()); |
| |
| 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<int>(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) |