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 "include/core/SkRefCnt.h"
9 #include "include/private/SkTArray.h"
10 #include "include/utils/SkRandom.h"
11 #include "tests/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_construction(skiatest::Reporter * reporter)63 template <typename T> static void test_construction(skiatest::Reporter* reporter) {
64 // No arguments: Creates an empty array with no initial storage.
65 T arrayNoArgs;
66 REPORTER_ASSERT(reporter, arrayNoArgs.empty());
67
68 // Single integer: Creates an empty array that will preallocate space for reserveCount elements.
69 T arrayReserve(15);
70 REPORTER_ASSERT(reporter, arrayReserve.empty());
71 REPORTER_ASSERT(reporter, arrayReserve.capacity() == 15);
72
73 // Another array, const&: Copies one array to another.
74 T arrayInitial;
75 arrayInitial.push_back(1);
76 arrayInitial.push_back(2);
77 arrayInitial.push_back(3);
78
79 T arrayCopy(arrayInitial);
80 REPORTER_ASSERT(reporter, arrayInitial.size() == 3);
81 REPORTER_ASSERT(reporter, arrayInitial[0] == 1);
82 REPORTER_ASSERT(reporter, arrayInitial[1] == 2);
83 REPORTER_ASSERT(reporter, arrayInitial[2] == 3);
84 REPORTER_ASSERT(reporter, arrayCopy.size() == 3);
85 REPORTER_ASSERT(reporter, arrayCopy[0] == 1);
86 REPORTER_ASSERT(reporter, arrayCopy[1] == 2);
87 REPORTER_ASSERT(reporter, arrayCopy[2] == 3);
88
89 // Another array, &&: Moves one array to another.
90 T arrayMove(std::move(arrayInitial));
91 REPORTER_ASSERT(reporter, arrayInitial.empty()); // NOLINT(bugprone-use-after-move)
92 REPORTER_ASSERT(reporter, arrayMove.size() == 3);
93 REPORTER_ASSERT(reporter, arrayMove[0] == 1);
94 REPORTER_ASSERT(reporter, arrayMove[1] == 2);
95 REPORTER_ASSERT(reporter, arrayMove[2] == 3);
96
97 // Pointer and count: Copies contents of a standard C array.
98 typename T::value_type data[3] = { 7, 8, 9 };
99 T arrayPtrCount(data, 3);
100 REPORTER_ASSERT(reporter, arrayPtrCount.size() == 3);
101 REPORTER_ASSERT(reporter, arrayPtrCount[0] == 7);
102 REPORTER_ASSERT(reporter, arrayPtrCount[1] == 8);
103 REPORTER_ASSERT(reporter, arrayPtrCount[2] == 9);
104
105 // Initializer list.
106 T arrayInitializer{8, 6, 7, 5, 3, 0, 9};
107 REPORTER_ASSERT(reporter, arrayInitializer.size() == 7);
108 REPORTER_ASSERT(reporter, arrayInitializer[0] == 8);
109 REPORTER_ASSERT(reporter, arrayInitializer[1] == 6);
110 REPORTER_ASSERT(reporter, arrayInitializer[2] == 7);
111 REPORTER_ASSERT(reporter, arrayInitializer[3] == 5);
112 REPORTER_ASSERT(reporter, arrayInitializer[4] == 3);
113 REPORTER_ASSERT(reporter, arrayInitializer[5] == 0);
114 REPORTER_ASSERT(reporter, arrayInitializer[6] == 9);
115 }
116
117 template <typename T, typename U>
test_skstarray_compatibility(skiatest::Reporter * reporter)118 static void test_skstarray_compatibility(skiatest::Reporter* reporter) {
119 // We expect SkTArrays of the same type to be copyable and movable, even when:
120 // - one side is an SkTArray, and the other side is an SkSTArray
121 // - both sides are SkSTArray, but each side has a different internal capacity
122 T tArray;
123 tArray.push_back(1);
124 tArray.push_back(2);
125 tArray.push_back(3);
126 T tArray2 = tArray;
127
128 // Copy construction from other-type array.
129 U arrayCopy(tArray);
130 REPORTER_ASSERT(reporter, tArray.size() == 3);
131 REPORTER_ASSERT(reporter, tArray[0] == 1);
132 REPORTER_ASSERT(reporter, tArray[1] == 2);
133 REPORTER_ASSERT(reporter, tArray[2] == 3);
134 REPORTER_ASSERT(reporter, arrayCopy.size() == 3);
135 REPORTER_ASSERT(reporter, arrayCopy[0] == 1);
136 REPORTER_ASSERT(reporter, arrayCopy[1] == 2);
137 REPORTER_ASSERT(reporter, arrayCopy[2] == 3);
138
139 // Assignment from other-type array.
140 U arrayAssignment;
141 arrayAssignment = tArray;
142 REPORTER_ASSERT(reporter, tArray.size() == 3);
143 REPORTER_ASSERT(reporter, tArray[0] == 1);
144 REPORTER_ASSERT(reporter, tArray[1] == 2);
145 REPORTER_ASSERT(reporter, tArray[2] == 3);
146 REPORTER_ASSERT(reporter, arrayAssignment.size() == 3);
147 REPORTER_ASSERT(reporter, arrayAssignment[0] == 1);
148 REPORTER_ASSERT(reporter, arrayAssignment[1] == 2);
149 REPORTER_ASSERT(reporter, arrayAssignment[2] == 3);
150
151 // Move construction from other-type array.
152 U arrayMove(std::move(tArray));
153 REPORTER_ASSERT(reporter, tArray.empty()); // NOLINT(bugprone-use-after-move)
154 REPORTER_ASSERT(reporter, arrayMove.size() == 3);
155 REPORTER_ASSERT(reporter, arrayMove[0] == 1);
156 REPORTER_ASSERT(reporter, arrayMove[1] == 2);
157 REPORTER_ASSERT(reporter, arrayMove[2] == 3);
158
159 // Move assignment from other-type array.
160 U arrayMoveAssign;
161 arrayMoveAssign = std::move(tArray2);
162 REPORTER_ASSERT(reporter, tArray2.empty()); // NOLINT(bugprone-use-after-move)
163 REPORTER_ASSERT(reporter, arrayMoveAssign.size() == 3);
164 REPORTER_ASSERT(reporter, arrayMoveAssign[0] == 1);
165 REPORTER_ASSERT(reporter, arrayMoveAssign[1] == 2);
166 REPORTER_ASSERT(reporter, arrayMoveAssign[2] == 3);
167 }
168
test_swap(skiatest::Reporter * reporter,SkTArray<T> * (& arrays)[4],int (& sizes)[7])169 template <typename T> static void test_swap(skiatest::Reporter* reporter,
170 SkTArray<T>* (&arrays)[4],
171 int (&sizes)[7])
172 {
173 for (auto a : arrays) {
174 for (auto b : arrays) {
175 if (a == b) {
176 continue;
177 }
178
179 for (auto sizeA : sizes) {
180 for (auto sizeB : sizes) {
181 a->reset();
182 b->reset();
183
184 int curr = 0;
185 for (int i = 0; i < sizeA; i++) { a->push_back(curr++); }
186 for (int i = 0; i < sizeB; i++) { b->push_back(curr++); }
187
188 a->swap(*b);
189 REPORTER_ASSERT(reporter, b->count() == sizeA);
190 REPORTER_ASSERT(reporter, a->count() == sizeB);
191
192 curr = 0;
193 for (auto&& x : *b) { REPORTER_ASSERT(reporter, x == curr++); }
194 for (auto&& x : *a) { REPORTER_ASSERT(reporter, x == curr++); }
195
196 a->swap(*a);
197 curr = sizeA;
198 for (auto&& x : *a) { REPORTER_ASSERT(reporter, x == curr++); }
199 }}
200 }}
201 }
202
test_swap(skiatest::Reporter * reporter)203 static void test_swap(skiatest::Reporter* reporter) {
204 int sizes[] = {0, 1, 5, 10, 15, 20, 25};
205
206 SkTArray<int> arr;
207 SkSTArray< 5, int> arr5;
208 SkSTArray<10, int> arr10;
209 SkSTArray<20, int> arr20;
210 SkTArray<int>* arrays[] = { &arr, &arr5, &arr10, &arr20 };
211 test_swap(reporter, arrays, sizes);
212
213 struct MoveOnlyInt {
214 MoveOnlyInt(int i) : fInt(i) {}
215 MoveOnlyInt(MoveOnlyInt&& that) : fInt(that.fInt) {}
216 bool operator==(int i) { return fInt == i; }
217 int fInt;
218 };
219
220 SkTArray<MoveOnlyInt> moi;
221 SkSTArray< 5, MoveOnlyInt> moi5;
222 SkSTArray<10, MoveOnlyInt> moi10;
223 SkSTArray<20, MoveOnlyInt> moi20;
224 SkTArray<MoveOnlyInt>* arraysMoi[] = { &moi, &moi5, &moi10, &moi20 };
225 test_swap(reporter, arraysMoi, sizes);
226 }
227
test_unnecessary_alloc(skiatest::Reporter * reporter)228 void test_unnecessary_alloc(skiatest::Reporter* reporter) {
229 {
230 SkTArray<int> a;
231 REPORTER_ASSERT(reporter, a.capacity() == 0);
232 }
233 {
234 SkSTArray<10, int> a;
235 REPORTER_ASSERT(reporter, a.capacity() == 10);
236 }
237 {
238 SkTArray<int> a(1);
239 REPORTER_ASSERT(reporter, a.capacity() >= 1);
240 }
241 {
242 SkTArray<int> a, b;
243 b = a;
244 REPORTER_ASSERT(reporter, b.capacity() == 0);
245 }
246 {
247 SkSTArray<10, int> a;
248 SkTArray<int> b;
249 b = a;
250 REPORTER_ASSERT(reporter, b.capacity() == 0);
251 }
252 {
253 SkTArray<int> a;
254 SkTArray<int> b(a); // NOLINT(performance-unnecessary-copy-initialization)
255 REPORTER_ASSERT(reporter, b.capacity() == 0);
256 }
257 {
258 SkSTArray<10, int> a;
259 SkTArray<int> b(a); // NOLINT(performance-unnecessary-copy-initialization)
260 REPORTER_ASSERT(reporter, b.capacity() == 0);
261 }
262 {
263 SkTArray<int> a;
264 SkTArray<int> b(std::move(a));
265 REPORTER_ASSERT(reporter, b.capacity() == 0);
266 }
267 {
268 SkSTArray<10, int> a;
269 SkTArray<int> b(std::move(a));
270 REPORTER_ASSERT(reporter, b.capacity() == 0);
271 }
272 {
273 SkTArray<int> a;
274 SkTArray<int> b;
275 b = std::move(a);
276 REPORTER_ASSERT(reporter, b.capacity() == 0);
277 }
278 {
279 SkSTArray<10, int> a;
280 SkTArray<int> b;
281 b = std::move(a);
282 REPORTER_ASSERT(reporter, b.capacity() == 0);
283 }
284 }
285
test_self_assignment(skiatest::Reporter * reporter)286 static void test_self_assignment(skiatest::Reporter* reporter) {
287 SkTArray<int> a;
288 a.push_back(1);
289 REPORTER_ASSERT(reporter, !a.empty());
290 REPORTER_ASSERT(reporter, a.count() == 1);
291 REPORTER_ASSERT(reporter, a[0] == 1);
292
293 a = static_cast<decltype(a)&>(a);
294 REPORTER_ASSERT(reporter, !a.empty());
295 REPORTER_ASSERT(reporter, a.count() == 1);
296 REPORTER_ASSERT(reporter, a[0] == 1);
297 }
298
test_array_reserve(skiatest::Reporter * reporter,Array * array,int reserveCount)299 template <typename Array> static void test_array_reserve(skiatest::Reporter* reporter,
300 Array* array, int reserveCount) {
301 SkRandom random;
302 REPORTER_ASSERT(reporter, array->capacity() >= reserveCount);
303 array->push_back();
304 REPORTER_ASSERT(reporter, array->capacity() >= reserveCount);
305 array->pop_back();
306 REPORTER_ASSERT(reporter, array->capacity() >= reserveCount);
307 while (array->count() < reserveCount) {
308 // Two steps forward, one step back
309 if (random.nextULessThan(3) < 2) {
310 array->push_back();
311 } else if (array->count() > 0) {
312 array->pop_back();
313 }
314 REPORTER_ASSERT(reporter, array->capacity() >= reserveCount);
315 }
316 }
317
test_reserve(skiatest::Reporter * reporter)318 template<typename Array> static void test_reserve(skiatest::Reporter* reporter) {
319 // Test that our allocated space stays >= to the reserve count until the array is filled to
320 // the reserve count
321 for (int reserveCount : {1, 2, 10, 100}) {
322 // Test setting reserve in constructor.
323 Array array1(reserveCount);
324 test_array_reserve(reporter, &array1, reserveCount);
325
326 // Test setting reserve after constructor.
327 Array array2;
328 array2.reserve_back(reserveCount);
329 test_array_reserve(reporter, &array2, reserveCount);
330
331 // Test increasing reserve after constructor.
332 Array array3(reserveCount/2);
333 array3.reserve_back(reserveCount);
334 test_array_reserve(reporter, &array3, reserveCount);
335
336 // Test setting reserve on non-empty array.
337 Array array4;
338 array4.push_back_n(reserveCount);
339 array4.reserve_back(reserveCount);
340 array4.pop_back_n(reserveCount);
341 test_array_reserve(reporter, &array4, 2 * reserveCount);
342 }
343 }
344
DEF_TEST(TArray,reporter)345 DEF_TEST(TArray, reporter) {
346 TestTSet_basic<true>(reporter);
347 TestTSet_basic<false>(reporter);
348 test_swap(reporter);
349
350 test_unnecessary_alloc(reporter);
351
352 test_self_assignment(reporter);
353
354 test_reserve<SkTArray<int>>(reporter);
355 test_reserve<SkSTArray<1, int>>(reporter);
356 test_reserve<SkSTArray<2, int>>(reporter);
357 test_reserve<SkSTArray<16, int>>(reporter);
358
359 test_construction<SkTArray<int>>(reporter);
360 test_construction<SkTArray<double>>(reporter);
361 test_construction<SkSTArray<1, int>>(reporter);
362 test_construction<SkSTArray<5, char>>(reporter);
363 test_construction<SkSTArray<10, float>>(reporter);
364
365 test_skstarray_compatibility<SkSTArray<1, int>, SkTArray<int>>(reporter);
366 test_skstarray_compatibility<SkSTArray<5, char>, SkTArray<char>>(reporter);
367 test_skstarray_compatibility<SkSTArray<10, float>, SkTArray<float>>(reporter);
368 test_skstarray_compatibility<SkTArray<int>, SkSTArray<1, int>>(reporter);
369 test_skstarray_compatibility<SkTArray<char>, SkSTArray<5, char>>(reporter);
370 test_skstarray_compatibility<SkTArray<float>, SkSTArray<10, float>>(reporter);
371 test_skstarray_compatibility<SkSTArray<10, uint8_t>, SkSTArray<1, uint8_t>>(reporter);
372 test_skstarray_compatibility<SkSTArray<1, long>, SkSTArray<10, long>>(reporter);
373 test_skstarray_compatibility<SkSTArray<3, double>, SkSTArray<4, double>>(reporter);
374 test_skstarray_compatibility<SkSTArray<2, short>, SkSTArray<1, short>>(reporter);
375 }
376