1 /*
2 * Copyright 2014 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 "SkRandom.h"
9 #include "SkRefCnt.h"
10 #include "SkTArray.h"
11 #include "Test.h"
12
13 // Tests the SkTArray<T> class template.
14
15 template <bool MEM_MOVE>
TestTSet_basic(skiatest::Reporter * reporter)16 static void TestTSet_basic(skiatest::Reporter* reporter) {
17 SkTArray<int, MEM_MOVE> a;
18
19 // Starts empty.
20 REPORTER_ASSERT(reporter, a.empty());
21 REPORTER_ASSERT(reporter, a.count() == 0);
22
23 // { }, add a default constructed element
24 a.push_back() = 0;
25 REPORTER_ASSERT(reporter, !a.empty());
26 REPORTER_ASSERT(reporter, a.count() == 1);
27
28 // { 0 }, removeShuffle the only element.
29 a.removeShuffle(0);
30 REPORTER_ASSERT(reporter, a.empty());
31 REPORTER_ASSERT(reporter, a.count() == 0);
32
33 // { }, add a default, add a 1, remove first
34 a.push_back() = 0;
35 REPORTER_ASSERT(reporter, a.push_back() = 1);
36 a.removeShuffle(0);
37 REPORTER_ASSERT(reporter, !a.empty());
38 REPORTER_ASSERT(reporter, a.count() == 1);
39 REPORTER_ASSERT(reporter, a[0] == 1);
40
41 // { 1 }, replace with new array
42 int b[5] = { 0, 1, 2, 3, 4 };
43 a.reset(b, SK_ARRAY_COUNT(b));
44 REPORTER_ASSERT(reporter, a.count() == SK_ARRAY_COUNT(b));
45 REPORTER_ASSERT(reporter, a[2] == 2);
46 REPORTER_ASSERT(reporter, a[4] == 4);
47
48 // { 0, 1, 2, 3, 4 }, removeShuffle the last
49 a.removeShuffle(4);
50 REPORTER_ASSERT(reporter, a.count() == SK_ARRAY_COUNT(b) - 1);
51 REPORTER_ASSERT(reporter, a[3] == 3);
52
53 // { 0, 1, 2, 3 }, remove a middle, note shuffle
54 a.removeShuffle(1);
55 REPORTER_ASSERT(reporter, a.count() == SK_ARRAY_COUNT(b) - 2);
56 REPORTER_ASSERT(reporter, a[0] == 0);
57 REPORTER_ASSERT(reporter, a[1] == 3);
58 REPORTER_ASSERT(reporter, a[2] == 2);
59
60 // {0, 3, 2 }
61 }
62
test_swap(skiatest::Reporter * reporter,SkTArray<T> * (& arrays)[4],int (& sizes)[7])63 template <typename T> static void test_swap(skiatest::Reporter* reporter,
64 SkTArray<T>* (&arrays)[4],
65 int (&sizes)[7])
66 {
67 for (auto a : arrays) {
68 for (auto b : arrays) {
69 if (a == b) {
70 continue;
71 }
72
73 for (auto sizeA : sizes) {
74 for (auto sizeB : sizes) {
75 a->reset();
76 b->reset();
77
78 int curr = 0;
79 for (int i = 0; i < sizeA; i++) { a->push_back(curr++); }
80 for (int i = 0; i < sizeB; i++) { b->push_back(curr++); }
81
82 a->swap(*b);
83 REPORTER_ASSERT(reporter, b->count() == sizeA);
84 REPORTER_ASSERT(reporter, a->count() == sizeB);
85
86 curr = 0;
87 for (auto&& x : *b) { REPORTER_ASSERT(reporter, x == curr++); }
88 for (auto&& x : *a) { REPORTER_ASSERT(reporter, x == curr++); }
89
90 a->swap(*a);
91 curr = sizeA;
92 for (auto&& x : *a) { REPORTER_ASSERT(reporter, x == curr++); }
93 }}
94 }}
95 }
96
test_swap(skiatest::Reporter * reporter)97 static void test_swap(skiatest::Reporter* reporter) {
98 int sizes[] = {0, 1, 5, 10, 15, 20, 25};
99
100 SkTArray<int> arr;
101 SkSTArray< 5, int> arr5;
102 SkSTArray<10, int> arr10;
103 SkSTArray<20, int> arr20;
104 SkTArray<int>* arrays[] = { &arr, &arr5, &arr10, &arr20 };
105 test_swap(reporter, arrays, sizes);
106
107 struct MoveOnlyInt {
108 MoveOnlyInt(int i) : fInt(i) {}
109 MoveOnlyInt(MoveOnlyInt&& that) : fInt(that.fInt) {}
110 bool operator==(int i) { return fInt == i; }
111 int fInt;
112 };
113
114 SkTArray<MoveOnlyInt> moi;
115 SkSTArray< 5, MoveOnlyInt> moi5;
116 SkSTArray<10, MoveOnlyInt> moi10;
117 SkSTArray<20, MoveOnlyInt> moi20;
118 SkTArray<MoveOnlyInt>* arraysMoi[] = { &moi, &moi5, &moi10, &moi20 };
119 test_swap(reporter, arraysMoi, sizes);
120 }
121
allocCntForTest() const122 template <typename T, bool MEM_MOVE> int SkTArray<T, MEM_MOVE>::allocCntForTest() const {
123 return fAllocCount;
124 }
125
test_unnecessary_alloc(skiatest::Reporter * reporter)126 void test_unnecessary_alloc(skiatest::Reporter* reporter) {
127 {
128 SkTArray<int> a;
129 REPORTER_ASSERT(reporter, a.allocCntForTest() == 0);
130 }
131 {
132 SkSTArray<10, int> a;
133 REPORTER_ASSERT(reporter, a.allocCntForTest() == 10);
134 }
135 {
136 SkTArray<int> a(1);
137 REPORTER_ASSERT(reporter, a.allocCntForTest() >= 1);
138 }
139 {
140 SkTArray<int> a, b;
141 b = a;
142 REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
143 }
144 {
145 SkSTArray<10, int> a;
146 SkTArray<int> b;
147 b = a;
148 REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
149 }
150 {
151 SkTArray<int> a;
152 SkTArray<int> b(a);
153 REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
154 }
155 {
156 SkSTArray<10, int> a;
157 SkTArray<int> b(a);
158 REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
159 }
160 {
161 SkTArray<int> a;
162 SkTArray<int> b(std::move(a));
163 REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
164 }
165 {
166 SkSTArray<10, int> a;
167 SkTArray<int> b(std::move(a));
168 REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
169 }
170 {
171 SkTArray<int> a;
172 SkTArray<int> b;
173 b = std::move(a);
174 REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
175 }
176 {
177 SkSTArray<10, int> a;
178 SkTArray<int> b;
179 b = std::move(a);
180 REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
181 }
182 }
183
test_self_assignment(skiatest::Reporter * reporter)184 static void test_self_assignment(skiatest::Reporter* reporter) {
185 SkTArray<int> a;
186 a.push_back(1);
187 REPORTER_ASSERT(reporter, !a.empty());
188 REPORTER_ASSERT(reporter, a.count() == 1);
189 REPORTER_ASSERT(reporter, a[0] == 1);
190
191 a = static_cast<decltype(a)&>(a);
192 REPORTER_ASSERT(reporter, !a.empty());
193 REPORTER_ASSERT(reporter, a.count() == 1);
194 REPORTER_ASSERT(reporter, a[0] == 1);
195 }
196
test_array_reserve(skiatest::Reporter * reporter,Array * array,int reserveCount)197 template <typename Array> static void test_array_reserve(skiatest::Reporter* reporter,
198 Array* array, int reserveCount) {
199 SkRandom random;
200 REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
201 array->push_back();
202 REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
203 array->pop_back();
204 REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
205 while (array->count() < reserveCount) {
206 // Two steps forward, one step back
207 if (random.nextULessThan(3) < 2) {
208 array->push_back();
209 } else if (array->count() > 0) {
210 array->pop_back();
211 }
212 REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
213 }
214 }
215
test_reserve(skiatest::Reporter * reporter)216 template<typename Array> static void test_reserve(skiatest::Reporter* reporter) {
217 // Test that our allocated space stays >= to the reserve count until the array is filled to
218 // the reserve count
219 for (int reserveCount : {1, 2, 10, 100}) {
220 // Test setting reserve in constructor.
221 Array array1(reserveCount);
222 test_array_reserve(reporter, &array1, reserveCount);
223
224 // Test setting reserve after constructor.
225 Array array2;
226 array2.reserve(reserveCount);
227 test_array_reserve(reporter, &array2, reserveCount);
228
229 // Test increasing reserve after constructor.
230 Array array3(reserveCount/2);
231 array3.reserve(reserveCount);
232 test_array_reserve(reporter, &array3, reserveCount);
233
234 // Test setting reserve on non-empty array.
235 Array array4;
236 array4.push_back_n(reserveCount);
237 array4.reserve(reserveCount);
238 array4.pop_back_n(reserveCount);
239 test_array_reserve(reporter, &array4, 2 * reserveCount);
240 }
241 }
242
DEF_TEST(TArray,reporter)243 DEF_TEST(TArray, reporter) {
244 TestTSet_basic<true>(reporter);
245 TestTSet_basic<false>(reporter);
246 test_swap(reporter);
247
248 test_unnecessary_alloc(reporter);
249
250 test_self_assignment(reporter);
251
252 test_reserve<SkTArray<int>>(reporter);
253 test_reserve<SkSTArray<1, int>>(reporter);
254 test_reserve<SkSTArray<2, int>>(reporter);
255 test_reserve<SkSTArray<16, int>>(reporter);
256 }
257