bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2012 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 8 | #include "include/utils/SkRandom.h" |
Ben Wagner | 729a23f | 2019-05-17 16:29:34 -0400 | [diff] [blame] | 9 | #include "src/core/SkTInternalLList.h" |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 10 | #include "tests/Test.h" |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 11 | |
| 12 | class ListElement { |
| 13 | public: |
| 14 | ListElement(int id) : fID(id) { |
| 15 | } |
| 16 | bool operator== (const ListElement& other) { return fID == other.fID; } |
| 17 | |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 18 | int fID; |
| 19 | |
| 20 | private: |
mtklein | 2766c00 | 2015-06-26 11:45:03 -0700 | [diff] [blame] | 21 | |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 22 | SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement); |
| 23 | }; |
| 24 | |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 25 | static void check_list(const SkTInternalLList<ListElement>& list, |
| 26 | skiatest::Reporter* reporter, |
| 27 | bool empty, |
| 28 | int numElements, |
| 29 | bool in0, bool in1, bool in2, bool in3, |
| 30 | ListElement elements[4]) { |
| 31 | |
| 32 | REPORTER_ASSERT(reporter, empty == list.isEmpty()); |
commit-bot@chromium.org | 515dcd3 | 2013-08-28 14:17:03 +0000 | [diff] [blame] | 33 | #ifdef SK_DEBUG |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 34 | list.validate(); |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 35 | REPORTER_ASSERT(reporter, numElements == list.countEntries()); |
| 36 | REPORTER_ASSERT(reporter, in0 == list.isInList(&elements[0])); |
| 37 | REPORTER_ASSERT(reporter, in1 == list.isInList(&elements[1])); |
| 38 | REPORTER_ASSERT(reporter, in2 == list.isInList(&elements[2])); |
| 39 | REPORTER_ASSERT(reporter, in3 == list.isInList(&elements[3])); |
| 40 | #endif |
| 41 | } |
| 42 | |
Michael Ludwig | b23630c | 2021-08-10 12:27:25 -0400 | [diff] [blame] | 43 | DEF_TEST(InternalLList, reporter) { |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 44 | SkTInternalLList<ListElement> list; |
| 45 | ListElement elements[4] = { |
| 46 | ListElement(0), |
| 47 | ListElement(1), |
| 48 | ListElement(2), |
| 49 | ListElement(3), |
| 50 | }; |
| 51 | |
| 52 | // list should be empty to start with |
| 53 | check_list(list, reporter, true, 0, false, false, false, false, elements); |
| 54 | |
| 55 | list.addToHead(&elements[0]); |
| 56 | |
| 57 | check_list(list, reporter, false, 1, true, false, false, false, elements); |
| 58 | |
| 59 | list.addToHead(&elements[1]); |
| 60 | list.addToHead(&elements[2]); |
| 61 | list.addToHead(&elements[3]); |
| 62 | |
| 63 | check_list(list, reporter, false, 4, true, true, true, true, elements); |
| 64 | |
| 65 | // test out iterators |
| 66 | typedef SkTInternalLList<ListElement>::Iter Iter; |
| 67 | Iter iter; |
| 68 | |
| 69 | ListElement* cur = iter.init(list, Iter::kHead_IterStart); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 70 | for (int i = 0; cur; ++i, cur = iter.next()) { |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 71 | REPORTER_ASSERT(reporter, cur->fID == 3-i); |
| 72 | } |
| 73 | |
| 74 | cur = iter.init(list, Iter::kTail_IterStart); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 75 | for (int i = 0; cur; ++i, cur = iter.prev()) { |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 76 | REPORTER_ASSERT(reporter, cur->fID == i); |
| 77 | } |
| 78 | |
| 79 | // remove middle, frontmost then backmost |
| 80 | list.remove(&elements[1]); |
| 81 | list.remove(&elements[3]); |
| 82 | list.remove(&elements[0]); |
| 83 | |
| 84 | check_list(list, reporter, false, 1, false, false, true, false, elements); |
| 85 | |
| 86 | // remove last element |
| 87 | list.remove(&elements[2]); |
| 88 | |
| 89 | // list should be empty again |
| 90 | check_list(list, reporter, true, 0, false, false, false, false, elements); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 91 | |
| 92 | // test out methods that add to the middle of the list. |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 93 | list.addAfter(&elements[1], nullptr); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 94 | check_list(list, reporter, false, 1, false, true, false, false, elements); |
| 95 | |
| 96 | list.remove(&elements[1]); |
| 97 | |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 98 | list.addBefore(&elements[1], nullptr); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 99 | check_list(list, reporter, false, 1, false, true, false, false, elements); |
| 100 | |
| 101 | list.addBefore(&elements[0], &elements[1]); |
| 102 | check_list(list, reporter, false, 2, true, true, false, false, elements); |
| 103 | |
| 104 | list.addAfter(&elements[3], &elements[1]); |
| 105 | check_list(list, reporter, false, 3, true, true, false, true, elements); |
| 106 | |
| 107 | list.addBefore(&elements[2], &elements[3]); |
| 108 | check_list(list, reporter, false, 4, true, true, true, true, elements); |
| 109 | |
| 110 | cur = iter.init(list, Iter::kHead_IterStart); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 111 | for (int i = 0; cur; ++i, cur = iter.next()) { |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 112 | REPORTER_ASSERT(reporter, cur->fID == i); |
| 113 | } |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 114 | while (!list.isEmpty()) { |
| 115 | list.remove(list.tail()); |
| 116 | } |
| 117 | |
| 118 | // test concat. |
| 119 | SkTInternalLList<ListElement> listA, listB; |
| 120 | listA.concat(std::move(listB)); |
| 121 | check_list(listA, reporter, true, 0, false, false, false, false, elements); |
Mike Klein | 1688507 | 2018-12-11 09:54:31 -0500 | [diff] [blame] | 122 | // NOLINTNEXTLINE(bugprone-use-after-move) |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 123 | check_list(listB, reporter, true, 0, false, false, false, false, elements); |
| 124 | |
| 125 | listB.addToTail(&elements[0]); |
| 126 | listA.concat(std::move(listB)); |
| 127 | check_list(listA, reporter, false, 1, true, false, false, false, elements); |
Mike Klein | 1688507 | 2018-12-11 09:54:31 -0500 | [diff] [blame] | 128 | // NOLINTNEXTLINE(bugprone-use-after-move) |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 129 | check_list(listB, reporter, true, 0, false, false, false, false, elements); |
| 130 | |
| 131 | listB.addToTail(&elements[1]); |
| 132 | listA.concat(std::move(listB)); |
| 133 | check_list(listA, reporter, false, 2, true, true, false, false, elements); |
Mike Klein | 1688507 | 2018-12-11 09:54:31 -0500 | [diff] [blame] | 134 | // NOLINTNEXTLINE(bugprone-use-after-move) |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 135 | check_list(listB, reporter, true, 0, false, false, false, false, elements); |
| 136 | |
| 137 | listA.concat(std::move(listB)); |
| 138 | check_list(listA, reporter, false, 2, true, true, false, false, elements); |
Mike Klein | 1688507 | 2018-12-11 09:54:31 -0500 | [diff] [blame] | 139 | // NOLINTNEXTLINE(bugprone-use-after-move) |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 140 | check_list(listB, reporter, true, 0, false, false, false, false, elements); |
| 141 | |
| 142 | listB.addToTail(&elements[2]); |
| 143 | listB.addToTail(&elements[3]); |
| 144 | listA.concat(std::move(listB)); |
| 145 | check_list(listA, reporter, false, 4, true, true, true, true, elements); |
Mike Klein | 1688507 | 2018-12-11 09:54:31 -0500 | [diff] [blame] | 146 | // NOLINTNEXTLINE(bugprone-use-after-move) |
Chris Dalton | 832bd2b | 2017-06-21 12:33:39 -0700 | [diff] [blame] | 147 | check_list(listB, reporter, true, 0, false, false, false, false, elements); |
| 148 | |
| 149 | cur = iter.init(listA, Iter::kHead_IterStart); |
| 150 | for (int i = 0; cur; ++i, cur = iter.next()) { |
| 151 | REPORTER_ASSERT(reporter, cur->fID == i); |
| 152 | } |
bsalomon@google.com | bbe5290 | 2012-12-03 18:01:45 +0000 | [diff] [blame] | 153 | } |