epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2011 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 | */ |
tfarina@chromium.org | e4fafb1 | 2013-12-12 21:11:12 +0000 | [diff] [blame] | 7 | |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 8 | #include "SkDeque.h" |
tfarina@chromium.org | 8f6884a | 2014-01-24 20:56:26 +0000 | [diff] [blame] | 9 | #include "Test.h" |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 10 | |
| 11 | static void assert_count(skiatest::Reporter* reporter, const SkDeque& deq, int count) { |
| 12 | if (0 == count) { |
| 13 | REPORTER_ASSERT(reporter, deq.empty()); |
| 14 | REPORTER_ASSERT(reporter, 0 == deq.count()); |
| 15 | REPORTER_ASSERT(reporter, sizeof(int) == deq.elemSize()); |
| 16 | REPORTER_ASSERT(reporter, NULL == deq.front()); |
| 17 | REPORTER_ASSERT(reporter, NULL == deq.back()); |
| 18 | } else { |
| 19 | REPORTER_ASSERT(reporter, !deq.empty()); |
| 20 | REPORTER_ASSERT(reporter, count == deq.count()); |
| 21 | REPORTER_ASSERT(reporter, sizeof(int) == deq.elemSize()); |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 22 | REPORTER_ASSERT(reporter, deq.front()); |
| 23 | REPORTER_ASSERT(reporter, deq.back()); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 24 | if (1 == count) { |
| 25 | REPORTER_ASSERT(reporter, deq.back() == deq.front()); |
| 26 | } else { |
| 27 | REPORTER_ASSERT(reporter, deq.back() != deq.front()); |
| 28 | } |
| 29 | } |
| 30 | } |
| 31 | |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 32 | static void assert_iter(skiatest::Reporter* reporter, const SkDeque& deq, |
| 33 | int max, int min) { |
| 34 | // test forward iteration |
| 35 | SkDeque::Iter iter(deq, SkDeque::Iter::kFront_IterStart); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 36 | void* ptr; |
| 37 | |
| 38 | int value = max; |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 39 | while ((ptr = iter.next())) { |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 40 | REPORTER_ASSERT(reporter, value == *(int*)ptr); |
| 41 | value -= 1; |
| 42 | } |
| 43 | REPORTER_ASSERT(reporter, value+1 == min); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 44 | |
| 45 | // test reverse iteration |
| 46 | iter.reset(deq, SkDeque::Iter::kBack_IterStart); |
| 47 | |
| 48 | value = min; |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 49 | while ((ptr = iter.prev())) { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 50 | REPORTER_ASSERT(reporter, value == *(int*)ptr); |
| 51 | value += 1; |
| 52 | } |
| 53 | REPORTER_ASSERT(reporter, value-1 == max); |
| 54 | |
| 55 | // test mixed iteration |
| 56 | iter.reset(deq, SkDeque::Iter::kFront_IterStart); |
| 57 | |
| 58 | value = max; |
| 59 | // forward iteration half-way |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 60 | for (int i = 0; i < deq.count()/2 && (ptr = iter.next()); i++) { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 61 | REPORTER_ASSERT(reporter, value == *(int*)ptr); |
| 62 | value -= 1; |
| 63 | } |
| 64 | // then back down w/ reverse iteration |
bsalomon | 49f085d | 2014-09-05 13:34:00 -0700 | [diff] [blame] | 65 | while ((ptr = iter.prev())) { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 66 | REPORTER_ASSERT(reporter, value == *(int*)ptr); |
| 67 | value += 1; |
| 68 | } |
| 69 | REPORTER_ASSERT(reporter, value-1 == max); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 70 | } |
| 71 | |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 72 | // This helper is intended to only give the unit test access to SkDeque's |
| 73 | // private numBlocksAllocated method |
| 74 | class DequeUnitTestHelper { |
| 75 | public: |
| 76 | int fNumBlocksAllocated; |
| 77 | |
| 78 | DequeUnitTestHelper(const SkDeque& deq) { |
| 79 | fNumBlocksAllocated = deq.numBlocksAllocated(); |
| 80 | } |
| 81 | }; |
| 82 | |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 83 | static void assert_blocks(skiatest::Reporter* reporter, |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 84 | const SkDeque& deq, |
| 85 | int allocCount) { |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 86 | DequeUnitTestHelper helper(deq); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 87 | |
| 88 | if (0 == deq.count()) { |
| 89 | REPORTER_ASSERT(reporter, 1 == helper.fNumBlocksAllocated); |
| 90 | } else { |
| 91 | int expected = (deq.count() + allocCount - 1) / allocCount; |
| 92 | // A block isn't freed in the deque when it first becomes empty so |
| 93 | // sometimes an extra block lingers around |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 94 | REPORTER_ASSERT(reporter, |
| 95 | expected == helper.fNumBlocksAllocated || |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 96 | expected+1 == helper.fNumBlocksAllocated); |
| 97 | } |
| 98 | } |
| 99 | |
robertphillips@google.com | 2e41bec | 2012-07-16 17:19:21 +0000 | [diff] [blame] | 100 | static void TestSub(skiatest::Reporter* reporter, int allocCount) { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 101 | SkDeque deq(sizeof(int), allocCount); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 102 | int i; |
| 103 | |
reed@google.com | f9e7132 | 2011-02-22 19:56:18 +0000 | [diff] [blame] | 104 | // test pushing on the front |
| 105 | |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 106 | assert_count(reporter, deq, 0); |
| 107 | for (i = 1; i <= 10; i++) { |
| 108 | *(int*)deq.push_front() = i; |
| 109 | } |
| 110 | assert_count(reporter, deq, 10); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 111 | assert_iter(reporter, deq, 10, 1); |
| 112 | assert_blocks(reporter, deq, allocCount); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 113 | |
| 114 | for (i = 0; i < 5; i++) { |
| 115 | deq.pop_front(); |
| 116 | } |
| 117 | assert_count(reporter, deq, 5); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 118 | assert_iter(reporter, deq, 5, 1); |
| 119 | assert_blocks(reporter, deq, allocCount); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 120 | |
| 121 | for (i = 0; i < 5; i++) { |
| 122 | deq.pop_front(); |
| 123 | } |
| 124 | assert_count(reporter, deq, 0); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 125 | assert_blocks(reporter, deq, allocCount); |
reed@google.com | f9e7132 | 2011-02-22 19:56:18 +0000 | [diff] [blame] | 126 | |
| 127 | // now test pushing on the back |
| 128 | |
| 129 | for (i = 10; i >= 1; --i) { |
| 130 | *(int*)deq.push_back() = i; |
| 131 | } |
| 132 | assert_count(reporter, deq, 10); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 133 | assert_iter(reporter, deq, 10, 1); |
| 134 | assert_blocks(reporter, deq, allocCount); |
reed@google.com | f9e7132 | 2011-02-22 19:56:18 +0000 | [diff] [blame] | 135 | |
| 136 | for (i = 0; i < 5; i++) { |
| 137 | deq.pop_back(); |
| 138 | } |
| 139 | assert_count(reporter, deq, 5); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 140 | assert_iter(reporter, deq, 10, 6); |
| 141 | assert_blocks(reporter, deq, allocCount); |
reed@google.com | f9e7132 | 2011-02-22 19:56:18 +0000 | [diff] [blame] | 142 | |
| 143 | for (i = 0; i < 5; i++) { |
| 144 | deq.pop_back(); |
| 145 | } |
| 146 | assert_count(reporter, deq, 0); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 147 | assert_blocks(reporter, deq, allocCount); |
reed@google.com | f9e7132 | 2011-02-22 19:56:18 +0000 | [diff] [blame] | 148 | |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 149 | // now test pushing/popping on both ends |
reed@google.com | f9e7132 | 2011-02-22 19:56:18 +0000 | [diff] [blame] | 150 | |
| 151 | *(int*)deq.push_front() = 5; |
| 152 | *(int*)deq.push_back() = 4; |
| 153 | *(int*)deq.push_front() = 6; |
| 154 | *(int*)deq.push_back() = 3; |
| 155 | *(int*)deq.push_front() = 7; |
| 156 | *(int*)deq.push_back() = 2; |
| 157 | *(int*)deq.push_front() = 8; |
| 158 | *(int*)deq.push_back() = 1; |
| 159 | assert_count(reporter, deq, 8); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 160 | assert_iter(reporter, deq, 8, 1); |
| 161 | assert_blocks(reporter, deq, allocCount); |
reed@google.com | 4c09d5c | 2011-02-22 13:16:38 +0000 | [diff] [blame] | 162 | } |
| 163 | |
tfarina@chromium.org | e4fafb1 | 2013-12-12 21:11:12 +0000 | [diff] [blame] | 164 | DEF_TEST(Deque, reporter) { |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 165 | // test it once with the default allocation count |
robertphillips@google.com | 2e41bec | 2012-07-16 17:19:21 +0000 | [diff] [blame] | 166 | TestSub(reporter, 1); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 167 | // test it again with a generous allocation count |
robertphillips@google.com | 2e41bec | 2012-07-16 17:19:21 +0000 | [diff] [blame] | 168 | TestSub(reporter, 10); |
robertphillips@google.com | 0a78b0f | 2012-07-16 16:58:49 +0000 | [diff] [blame] | 169 | } |