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 */
7
8 #include "SkDeque.h"
9 #include "Test.h"
10
assert_count(skiatest::Reporter * reporter,const SkDeque & deq,int count)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, nullptr == deq.front());
17 REPORTER_ASSERT(reporter, nullptr == 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());
22 REPORTER_ASSERT(reporter, deq.front());
23 REPORTER_ASSERT(reporter, deq.back());
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
assert_iter(skiatest::Reporter * reporter,const SkDeque & deq,int max,int min)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);
36 void* ptr;
37
38 int value = max;
39 while ((ptr = iter.next())) {
40 REPORTER_ASSERT(reporter, value == *(int*)ptr);
41 value -= 1;
42 }
43 REPORTER_ASSERT(reporter, value+1 == min);
44
45 // test reverse iteration
46 iter.reset(deq, SkDeque::Iter::kBack_IterStart);
47
48 value = min;
49 while ((ptr = iter.prev())) {
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
60 for (int i = 0; i < deq.count()/2 && (ptr = iter.next()); i++) {
61 REPORTER_ASSERT(reporter, value == *(int*)ptr);
62 value -= 1;
63 }
64 // then back down w/ reverse iteration
65 while ((ptr = iter.prev())) {
66 REPORTER_ASSERT(reporter, value == *(int*)ptr);
67 value += 1;
68 }
69 REPORTER_ASSERT(reporter, value-1 == max);
70 }
71
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
DequeUnitTestHelper(const SkDeque & deq)78 DequeUnitTestHelper(const SkDeque& deq) {
79 fNumBlocksAllocated = deq.numBlocksAllocated();
80 }
81 };
82
assert_blocks(skiatest::Reporter * reporter,const SkDeque & deq,int allocCount)83 static void assert_blocks(skiatest::Reporter* reporter,
84 const SkDeque& deq,
85 int allocCount) {
86 DequeUnitTestHelper helper(deq);
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
94 REPORTER_ASSERT(reporter,
95 expected == helper.fNumBlocksAllocated ||
96 expected+1 == helper.fNumBlocksAllocated);
97 }
98 }
99
TestSub(skiatest::Reporter * reporter,int allocCount)100 static void TestSub(skiatest::Reporter* reporter, int allocCount) {
101 SkDeque deq(sizeof(int), allocCount);
102 int i;
103
104 // test pushing on the front
105
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);
111 assert_iter(reporter, deq, 10, 1);
112 assert_blocks(reporter, deq, allocCount);
113
114 for (i = 0; i < 5; i++) {
115 deq.pop_front();
116 }
117 assert_count(reporter, deq, 5);
118 assert_iter(reporter, deq, 5, 1);
119 assert_blocks(reporter, deq, allocCount);
120
121 for (i = 0; i < 5; i++) {
122 deq.pop_front();
123 }
124 assert_count(reporter, deq, 0);
125 assert_blocks(reporter, deq, allocCount);
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);
133 assert_iter(reporter, deq, 10, 1);
134 assert_blocks(reporter, deq, allocCount);
135
136 for (i = 0; i < 5; i++) {
137 deq.pop_back();
138 }
139 assert_count(reporter, deq, 5);
140 assert_iter(reporter, deq, 10, 6);
141 assert_blocks(reporter, deq, allocCount);
142
143 for (i = 0; i < 5; i++) {
144 deq.pop_back();
145 }
146 assert_count(reporter, deq, 0);
147 assert_blocks(reporter, deq, allocCount);
148
149 // now test pushing/popping on both ends
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);
160 assert_iter(reporter, deq, 8, 1);
161 assert_blocks(reporter, deq, allocCount);
162 }
163
DEF_TEST(Deque,reporter)164 DEF_TEST(Deque, reporter) {
165 // test it once with the default allocation count
166 TestSub(reporter, 1);
167 // test it again with a generous allocation count
168 TestSub(reporter, 10);
169 }
170