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