blob: c93a8124a66258dcffd15d9dcb47d15d965184dc [file] [log] [blame]
epoger@google.comec3ed6a2011-07-28 14:26:00 +00001/*
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.orge4fafb12013-12-12 21:11:12 +00007
Mike Reed4d170012020-02-17 16:51:14 -05008#include "include/private/SkDeque.h"
Mike Kleinc0bd9f92019-04-23 12:05:21 -05009#include "tests/Test.h"
reed@google.com4c09d5c2011-02-22 13:16:38 +000010
11static 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());
halcanary96fcdcc2015-08-27 07:41:13 -070016 REPORTER_ASSERT(reporter, nullptr == deq.front());
17 REPORTER_ASSERT(reporter, nullptr == deq.back());
reed@google.com4c09d5c2011-02-22 13:16:38 +000018 } else {
19 REPORTER_ASSERT(reporter, !deq.empty());
20 REPORTER_ASSERT(reporter, count == deq.count());
21 REPORTER_ASSERT(reporter, sizeof(int) == deq.elemSize());
bsalomon49f085d2014-09-05 13:34:00 -070022 REPORTER_ASSERT(reporter, deq.front());
23 REPORTER_ASSERT(reporter, deq.back());
reed@google.com4c09d5c2011-02-22 13:16:38 +000024 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.com0a78b0f2012-07-16 16:58:49 +000032static 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.com4c09d5c2011-02-22 13:16:38 +000036 void* ptr;
37
38 int value = max;
bsalomon49f085d2014-09-05 13:34:00 -070039 while ((ptr = iter.next())) {
reed@google.com4c09d5c2011-02-22 13:16:38 +000040 REPORTER_ASSERT(reporter, value == *(int*)ptr);
41 value -= 1;
42 }
43 REPORTER_ASSERT(reporter, value+1 == min);
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +000044
45 // test reverse iteration
46 iter.reset(deq, SkDeque::Iter::kBack_IterStart);
47
48 value = min;
bsalomon49f085d2014-09-05 13:34:00 -070049 while ((ptr = iter.prev())) {
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +000050 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
bsalomon49f085d2014-09-05 13:34:00 -070060 for (int i = 0; i < deq.count()/2 && (ptr = iter.next()); i++) {
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +000061 REPORTER_ASSERT(reporter, value == *(int*)ptr);
62 value -= 1;
63 }
64 // then back down w/ reverse iteration
bsalomon49f085d2014-09-05 13:34:00 -070065 while ((ptr = iter.prev())) {
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +000066 REPORTER_ASSERT(reporter, value == *(int*)ptr);
67 value += 1;
68 }
69 REPORTER_ASSERT(reporter, value-1 == max);
reed@google.com4c09d5c2011-02-22 13:16:38 +000070}
71
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +000072// This helper is intended to only give the unit test access to SkDeque's
73// private numBlocksAllocated method
74class DequeUnitTestHelper {
75public:
76 int fNumBlocksAllocated;
77
78 DequeUnitTestHelper(const SkDeque& deq) {
79 fNumBlocksAllocated = deq.numBlocksAllocated();
80 }
81};
82
rmistry@google.comd6176b02012-08-23 18:14:13 +000083static void assert_blocks(skiatest::Reporter* reporter,
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +000084 const SkDeque& deq,
85 int allocCount) {
rmistry@google.comd6176b02012-08-23 18:14:13 +000086 DequeUnitTestHelper helper(deq);
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +000087
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.comd6176b02012-08-23 18:14:13 +000094 REPORTER_ASSERT(reporter,
95 expected == helper.fNumBlocksAllocated ||
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +000096 expected+1 == helper.fNumBlocksAllocated);
97 }
98}
99
robertphillips@google.com2e41bec2012-07-16 17:19:21 +0000100static void TestSub(skiatest::Reporter* reporter, int allocCount) {
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +0000101 SkDeque deq(sizeof(int), allocCount);
reed@google.com4c09d5c2011-02-22 13:16:38 +0000102 int i;
103
reed@google.comf9e71322011-02-22 19:56:18 +0000104 // test pushing on the front
105
reed@google.com4c09d5c2011-02-22 13:16:38 +0000106 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.com0a78b0f2012-07-16 16:58:49 +0000111 assert_iter(reporter, deq, 10, 1);
112 assert_blocks(reporter, deq, allocCount);
reed@google.com4c09d5c2011-02-22 13:16:38 +0000113
114 for (i = 0; i < 5; i++) {
115 deq.pop_front();
116 }
117 assert_count(reporter, deq, 5);
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +0000118 assert_iter(reporter, deq, 5, 1);
119 assert_blocks(reporter, deq, allocCount);
reed@google.com4c09d5c2011-02-22 13:16:38 +0000120
121 for (i = 0; i < 5; i++) {
122 deq.pop_front();
123 }
124 assert_count(reporter, deq, 0);
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +0000125 assert_blocks(reporter, deq, allocCount);
reed@google.comf9e71322011-02-22 19:56:18 +0000126
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.com0a78b0f2012-07-16 16:58:49 +0000133 assert_iter(reporter, deq, 10, 1);
134 assert_blocks(reporter, deq, allocCount);
reed@google.comf9e71322011-02-22 19:56:18 +0000135
136 for (i = 0; i < 5; i++) {
137 deq.pop_back();
138 }
139 assert_count(reporter, deq, 5);
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +0000140 assert_iter(reporter, deq, 10, 6);
141 assert_blocks(reporter, deq, allocCount);
reed@google.comf9e71322011-02-22 19:56:18 +0000142
143 for (i = 0; i < 5; i++) {
144 deq.pop_back();
145 }
146 assert_count(reporter, deq, 0);
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +0000147 assert_blocks(reporter, deq, allocCount);
reed@google.comf9e71322011-02-22 19:56:18 +0000148
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +0000149 // now test pushing/popping on both ends
reed@google.comf9e71322011-02-22 19:56:18 +0000150
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.com0a78b0f2012-07-16 16:58:49 +0000160 assert_iter(reporter, deq, 8, 1);
161 assert_blocks(reporter, deq, allocCount);
reed@google.com4c09d5c2011-02-22 13:16:38 +0000162}
163
tfarina@chromium.orge4fafb12013-12-12 21:11:12 +0000164DEF_TEST(Deque, reporter) {
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +0000165 // test it once with the default allocation count
robertphillips@google.com2e41bec2012-07-16 17:19:21 +0000166 TestSub(reporter, 1);
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +0000167 // test it again with a generous allocation count
robertphillips@google.com2e41bec2012-07-16 17:19:21 +0000168 TestSub(reporter, 10);
robertphillips@google.com0a78b0f2012-07-16 16:58:49 +0000169}