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/private/base/SkTArray.h"
9 #include "src/base/SkRandom.h"
10 #include "tests/Test.h"
11
12 #include <array>
13 #include <cstdint>
14 #include <initializer_list>
15 #include <utility>
16
17 // This class is used to test SkTArray's behavior with classes containing a vtable.
18
19 namespace {
20
21 class TestClass {
22 public:
23 TestClass() = default;
24 TestClass(const TestClass&) = default;
25 TestClass& operator=(const TestClass&) = default;
TestClass(int v)26 TestClass(int v) : value(v) {}
~TestClass()27 virtual ~TestClass() {}
28
operator ==(const TestClass & c) const29 bool operator==(const TestClass& c) const { return value == c.value; }
30
31 int value = 0;
32 };
33
34 } // namespace
35
36 // Tests the SkTArray<T> class template.
37
38 template <typename T, bool MEM_MOVE>
TestTSet_basic(skiatest::Reporter * reporter)39 static void TestTSet_basic(skiatest::Reporter* reporter) {
40 SkTArray<T, MEM_MOVE> a;
41
42 // Starts empty.
43 REPORTER_ASSERT(reporter, a.empty());
44 REPORTER_ASSERT(reporter, a.size() == 0);
45
46 // { }, add a default constructed element
47 a.push_back() = T{0};
48 REPORTER_ASSERT(reporter, !a.empty());
49 REPORTER_ASSERT(reporter, a.size() == 1);
50
51 // { 0 }, removeShuffle the only element.
52 a.removeShuffle(0);
53 REPORTER_ASSERT(reporter, a.empty());
54 REPORTER_ASSERT(reporter, a.size() == 0);
55
56 // { }, add a default, add a 1, remove first
57 a.push_back() = T{0};
58 a.push_back() = T{1};
59 a.removeShuffle(0);
60 REPORTER_ASSERT(reporter, !a.empty());
61 REPORTER_ASSERT(reporter, a.size() == 1);
62 REPORTER_ASSERT(reporter, a[0] == T{1});
63
64 // { 1 }, replace with new array
65 T b[5] = {T{0}, T{1}, T{2}, T{3}, T{4}};
66 a.reset(b, std::size(b));
67 REPORTER_ASSERT(reporter, a.size() == std::size(b));
68 REPORTER_ASSERT(reporter, a[2] == T{2});
69 REPORTER_ASSERT(reporter, a[4] == T{4});
70
71 // { 0, 1, 2, 3, 4 }, removeShuffle the last
72 a.removeShuffle(4);
73 REPORTER_ASSERT(reporter, a.size() == std::size(b) - 1);
74 REPORTER_ASSERT(reporter, a[3] == T{3});
75
76 // { 0, 1, 2, 3 }, remove a middle, note shuffle
77 a.removeShuffle(1);
78 REPORTER_ASSERT(reporter, a.size() == std::size(b) - 2);
79 REPORTER_ASSERT(reporter, a[0] == T{0});
80 REPORTER_ASSERT(reporter, a[1] == T{3});
81 REPORTER_ASSERT(reporter, a[2] == T{2});
82
83 // { 0, 3, 2 }
84 }
85
test_construction(skiatest::Reporter * reporter)86 template <typename T> static void test_construction(skiatest::Reporter* reporter) {
87 using ValueType = typename T::value_type;
88
89 // No arguments: Creates an empty array with no initial storage.
90 T arrayNoArgs;
91 REPORTER_ASSERT(reporter, arrayNoArgs.empty());
92
93 // Single integer: Creates an empty array that will preallocate space for reserveCount elements.
94 T arrayReserve(15);
95 REPORTER_ASSERT(reporter, arrayReserve.empty());
96 // May get some extra elements for free because sk_allocate_* can round up.
97 REPORTER_ASSERT(reporter, arrayReserve.capacity() >= 15 && arrayReserve.capacity() < 50);
98
99 // Another array, const&: Copies one array to another.
100 T arrayInitial;
101 arrayInitial.push_back(ValueType{1});
102 arrayInitial.push_back(ValueType{2});
103 arrayInitial.push_back(ValueType{3});
104
105 T arrayCopy(arrayInitial);
106 REPORTER_ASSERT(reporter, arrayInitial.size() == 3);
107 REPORTER_ASSERT(reporter, arrayInitial[0] == ValueType{1});
108 REPORTER_ASSERT(reporter, arrayInitial[1] == ValueType{2});
109 REPORTER_ASSERT(reporter, arrayInitial[2] == ValueType{3});
110 REPORTER_ASSERT(reporter, arrayCopy.size() == 3);
111 REPORTER_ASSERT(reporter, arrayCopy[0] == ValueType{1});
112 REPORTER_ASSERT(reporter, arrayCopy[1] == ValueType{2});
113 REPORTER_ASSERT(reporter, arrayCopy[2] == ValueType{3});
114
115 // Another array, &&: Moves one array to another.
116 T arrayMove(std::move(arrayInitial));
117 REPORTER_ASSERT(reporter, arrayInitial.empty()); // NOLINT(bugprone-use-after-move)
118 REPORTER_ASSERT(reporter, arrayMove.size() == 3);
119 REPORTER_ASSERT(reporter, arrayMove[0] == ValueType{1});
120 REPORTER_ASSERT(reporter, arrayMove[1] == ValueType{2});
121 REPORTER_ASSERT(reporter, arrayMove[2] == ValueType{3});
122
123 // Pointer and count: Copies contents of a standard C array.
124 typename T::value_type data[3] = { 7, 8, 9 };
125 T arrayPtrCount(data, 3);
126 REPORTER_ASSERT(reporter, arrayPtrCount.size() == 3);
127 REPORTER_ASSERT(reporter, arrayPtrCount[0] == ValueType{7});
128 REPORTER_ASSERT(reporter, arrayPtrCount[1] == ValueType{8});
129 REPORTER_ASSERT(reporter, arrayPtrCount[2] == ValueType{9});
130
131 // Initializer list.
132 T arrayInitializer{8, 6, 7, 5, 3, 0, 9};
133 REPORTER_ASSERT(reporter, arrayInitializer.size() == 7);
134 REPORTER_ASSERT(reporter, arrayInitializer[0] == ValueType{8});
135 REPORTER_ASSERT(reporter, arrayInitializer[1] == ValueType{6});
136 REPORTER_ASSERT(reporter, arrayInitializer[2] == ValueType{7});
137 REPORTER_ASSERT(reporter, arrayInitializer[3] == ValueType{5});
138 REPORTER_ASSERT(reporter, arrayInitializer[4] == ValueType{3});
139 REPORTER_ASSERT(reporter, arrayInitializer[5] == ValueType{0});
140 REPORTER_ASSERT(reporter, arrayInitializer[6] == ValueType{9});
141 }
142
143 template <typename T, typename U>
test_skstarray_compatibility(skiatest::Reporter * reporter)144 static void test_skstarray_compatibility(skiatest::Reporter* reporter) {
145 // We expect SkTArrays of the same type to be copyable and movable, even when:
146 // - one side is an SkTArray, and the other side is an SkSTArray
147 // - both sides are SkSTArray, but each side has a different internal capacity
148 T tArray;
149 tArray.push_back(1);
150 tArray.push_back(2);
151 tArray.push_back(3);
152 T tArray2 = tArray;
153
154 // Copy construction from other-type array.
155 U arrayCopy(tArray);
156 REPORTER_ASSERT(reporter, tArray.size() == 3);
157 REPORTER_ASSERT(reporter, tArray[0] == 1);
158 REPORTER_ASSERT(reporter, tArray[1] == 2);
159 REPORTER_ASSERT(reporter, tArray[2] == 3);
160 REPORTER_ASSERT(reporter, arrayCopy.size() == 3);
161 REPORTER_ASSERT(reporter, arrayCopy[0] == 1);
162 REPORTER_ASSERT(reporter, arrayCopy[1] == 2);
163 REPORTER_ASSERT(reporter, arrayCopy[2] == 3);
164
165 // Assignment from other-type array.
166 U arrayAssignment;
167 arrayAssignment = tArray;
168 REPORTER_ASSERT(reporter, tArray.size() == 3);
169 REPORTER_ASSERT(reporter, tArray[0] == 1);
170 REPORTER_ASSERT(reporter, tArray[1] == 2);
171 REPORTER_ASSERT(reporter, tArray[2] == 3);
172 REPORTER_ASSERT(reporter, arrayAssignment.size() == 3);
173 REPORTER_ASSERT(reporter, arrayAssignment[0] == 1);
174 REPORTER_ASSERT(reporter, arrayAssignment[1] == 2);
175 REPORTER_ASSERT(reporter, arrayAssignment[2] == 3);
176
177 // Move construction from other-type array.
178 U arrayMove(std::move(tArray));
179 REPORTER_ASSERT(reporter, tArray.empty()); // NOLINT(bugprone-use-after-move)
180 REPORTER_ASSERT(reporter, arrayMove.size() == 3);
181 REPORTER_ASSERT(reporter, arrayMove[0] == 1);
182 REPORTER_ASSERT(reporter, arrayMove[1] == 2);
183 REPORTER_ASSERT(reporter, arrayMove[2] == 3);
184
185 // Move assignment from other-type array.
186 U arrayMoveAssign;
187 arrayMoveAssign = std::move(tArray2);
188 REPORTER_ASSERT(reporter, tArray2.empty()); // NOLINT(bugprone-use-after-move)
189 REPORTER_ASSERT(reporter, arrayMoveAssign.size() == 3);
190 REPORTER_ASSERT(reporter, arrayMoveAssign[0] == 1);
191 REPORTER_ASSERT(reporter, arrayMoveAssign[1] == 2);
192 REPORTER_ASSERT(reporter, arrayMoveAssign[2] == 3);
193 }
194
test_swap(skiatest::Reporter * reporter,SkTArray<T> * (& arrays)[4],int (& sizes)[7])195 template <typename T> static void test_swap(skiatest::Reporter* reporter,
196 SkTArray<T>* (&arrays)[4],
197 int (&sizes)[7])
198 {
199 for (auto a : arrays) {
200 for (auto b : arrays) {
201 if (a == b) {
202 continue;
203 }
204
205 for (auto sizeA : sizes) {
206 for (auto sizeB : sizes) {
207 a->clear();
208 b->clear();
209
210 int curr = 0;
211 for (int i = 0; i < sizeA; i++) { a->push_back(curr++); }
212 for (int i = 0; i < sizeB; i++) { b->push_back(curr++); }
213
214 a->swap(*b);
215 REPORTER_ASSERT(reporter, b->size() == sizeA);
216 REPORTER_ASSERT(reporter, a->size() == sizeB);
217
218 curr = 0;
219 for (auto&& x : *b) { REPORTER_ASSERT(reporter, x == curr++); }
220 for (auto&& x : *a) { REPORTER_ASSERT(reporter, x == curr++); }
221
222 a->swap(*a);
223 curr = sizeA;
224 for (auto&& x : *a) { REPORTER_ASSERT(reporter, x == curr++); }
225 }}
226 }}
227 }
228
test_swap(skiatest::Reporter * reporter)229 static void test_swap(skiatest::Reporter* reporter) {
230 int sizes[] = {0, 1, 5, 10, 15, 20, 25};
231
232 SkTArray<int> arr;
233 SkSTArray< 5, int> arr5;
234 SkSTArray<10, int> arr10;
235 SkSTArray<20, int> arr20;
236 SkTArray<int>* arrays[] = { &arr, &arr5, &arr10, &arr20 };
237 test_swap(reporter, arrays, sizes);
238
239 struct MoveOnlyInt {
240 MoveOnlyInt(int i) : fInt(i) {}
241 MoveOnlyInt(MoveOnlyInt&& that) : fInt(that.fInt) {}
242 bool operator==(int i) { return fInt == i; }
243 int fInt;
244 };
245
246 SkTArray<MoveOnlyInt> moi;
247 SkSTArray< 5, MoveOnlyInt> moi5;
248 SkSTArray<10, MoveOnlyInt> moi10;
249 SkSTArray<20, MoveOnlyInt> moi20;
250 SkTArray<MoveOnlyInt>* arraysMoi[] = { &moi, &moi5, &moi10, &moi20 };
251 test_swap(reporter, arraysMoi, sizes);
252 }
253
test_unnecessary_alloc(skiatest::Reporter * reporter)254 void test_unnecessary_alloc(skiatest::Reporter* reporter) {
255 {
256 SkTArray<int> a;
257 REPORTER_ASSERT(reporter, a.capacity() == 0);
258 }
259 {
260 SkSTArray<10, int> a;
261 REPORTER_ASSERT(reporter, a.capacity() == 10);
262 }
263 {
264 SkTArray<int> a(1);
265 REPORTER_ASSERT(reporter, a.capacity() >= 1);
266 }
267 {
268 SkTArray<int> a, b;
269 b = a;
270 REPORTER_ASSERT(reporter, b.capacity() == 0);
271 }
272 {
273 SkSTArray<10, int> a;
274 SkTArray<int> b;
275 b = a;
276 REPORTER_ASSERT(reporter, b.capacity() == 0);
277 }
278 {
279 SkTArray<int> a;
280 SkTArray<int> b(a); // NOLINT(performance-unnecessary-copy-initialization)
281 REPORTER_ASSERT(reporter, b.capacity() == 0);
282 }
283 {
284 SkSTArray<10, int> a;
285 SkTArray<int> b(a); // NOLINT(performance-unnecessary-copy-initialization)
286 REPORTER_ASSERT(reporter, b.capacity() == 0);
287 }
288 {
289 SkTArray<int> a;
290 SkTArray<int> b(std::move(a));
291 REPORTER_ASSERT(reporter, b.capacity() == 0);
292 }
293 {
294 SkSTArray<10, int> a;
295 SkTArray<int> b(std::move(a));
296 REPORTER_ASSERT(reporter, b.capacity() == 0);
297 }
298 {
299 SkTArray<int> a;
300 SkTArray<int> b;
301 b = std::move(a);
302 REPORTER_ASSERT(reporter, b.capacity() == 0);
303 }
304 {
305 SkSTArray<10, int> a;
306 SkTArray<int> b;
307 b = std::move(a);
308 REPORTER_ASSERT(reporter, b.capacity() == 0);
309 }
310 }
311
test_self_assignment(skiatest::Reporter * reporter)312 static void test_self_assignment(skiatest::Reporter* reporter) {
313 SkTArray<int> a;
314 a.push_back(1);
315 REPORTER_ASSERT(reporter, !a.empty());
316 REPORTER_ASSERT(reporter, a.size() == 1);
317 REPORTER_ASSERT(reporter, a[0] == 1);
318
319 a = static_cast<decltype(a)&>(a);
320 REPORTER_ASSERT(reporter, !a.empty());
321 REPORTER_ASSERT(reporter, a.size() == 1);
322 REPORTER_ASSERT(reporter, a[0] == 1);
323 }
324
test_array_reserve(skiatest::Reporter * reporter,Array * array,int reserveCount)325 template <typename Array> static void test_array_reserve(skiatest::Reporter* reporter,
326 Array* array, int reserveCount) {
327 SkRandom random;
328 REPORTER_ASSERT(reporter, array->capacity() >= reserveCount);
329 array->push_back();
330 REPORTER_ASSERT(reporter, array->capacity() >= reserveCount);
331 array->pop_back();
332 REPORTER_ASSERT(reporter, array->capacity() >= reserveCount);
333 while (array->size() < reserveCount) {
334 // Two steps forward, one step back
335 if (random.nextULessThan(3) < 2) {
336 array->push_back();
337 } else if (array->size() > 0) {
338 array->pop_back();
339 }
340 REPORTER_ASSERT(reporter, array->capacity() >= reserveCount);
341 }
342 }
343
test_reserve(skiatest::Reporter * reporter)344 template<typename Array> static void test_reserve(skiatest::Reporter* reporter) {
345 // Test that our allocated space stays >= to the reserve count until the array is filled to
346 // the reserve count
347 for (int reserveCount : {1, 2, 10, 100}) {
348 // Test setting reserve in constructor.
349 Array array1(reserveCount);
350 test_array_reserve(reporter, &array1, reserveCount);
351
352 // Test setting reserve after constructor.
353 Array array2;
354 array2.reserve_back(reserveCount);
355 test_array_reserve(reporter, &array2, reserveCount);
356
357 // Test increasing reserve after constructor.
358 Array array3(reserveCount/2);
359 array3.reserve_back(reserveCount);
360 test_array_reserve(reporter, &array3, reserveCount);
361
362 // Test setting reserve on non-empty array.
363 Array array4;
364 array4.push_back_n(reserveCount);
365 array4.reserve_back(reserveCount);
366 array4.pop_back_n(reserveCount);
367 test_array_reserve(reporter, &array4, 2 * reserveCount);
368 }
369 }
370
DEF_TEST(TArray,reporter)371 DEF_TEST(TArray, reporter) {
372 // ints are POD types and can work with either MEM_MOVE=true or false.
373 TestTSet_basic<int, true>(reporter);
374 TestTSet_basic<int, false>(reporter);
375
376 // TestClass has a vtable and can only work with MEM_MOVE=false.
377 TestTSet_basic<TestClass, false>(reporter);
378
379 test_swap(reporter);
380
381 test_unnecessary_alloc(reporter);
382
383 test_self_assignment(reporter);
384
385 test_reserve<SkTArray<int>>(reporter);
386 test_reserve<SkSTArray<1, int>>(reporter);
387 test_reserve<SkSTArray<2, int>>(reporter);
388 test_reserve<SkSTArray<16, int>>(reporter);
389
390 test_reserve<SkTArray<TestClass>>(reporter);
391 test_reserve<SkSTArray<1, TestClass>>(reporter);
392 test_reserve<SkSTArray<2, TestClass>>(reporter);
393 test_reserve<SkSTArray<16, TestClass>>(reporter);
394
395 test_construction<SkTArray<int>>(reporter);
396 test_construction<SkTArray<double>>(reporter);
397 test_construction<SkTArray<TestClass>>(reporter);
398 test_construction<SkSTArray<1, int>>(reporter);
399 test_construction<SkSTArray<5, char>>(reporter);
400 test_construction<SkSTArray<7, TestClass>>(reporter);
401 test_construction<SkSTArray<10, float>>(reporter);
402
403 test_skstarray_compatibility<SkSTArray<1, int>, SkTArray<int>>(reporter);
404 test_skstarray_compatibility<SkSTArray<5, char>, SkTArray<char>>(reporter);
405 test_skstarray_compatibility<SkSTArray<10, float>, SkTArray<float>>(reporter);
406 test_skstarray_compatibility<SkTArray<int>, SkSTArray<1, int>>(reporter);
407 test_skstarray_compatibility<SkTArray<char>, SkSTArray<5, char>>(reporter);
408 test_skstarray_compatibility<SkTArray<float>, SkSTArray<10, float>>(reporter);
409 test_skstarray_compatibility<SkSTArray<10, uint8_t>, SkSTArray<1, uint8_t>>(reporter);
410 test_skstarray_compatibility<SkSTArray<1, long>, SkSTArray<10, long>>(reporter);
411 test_skstarray_compatibility<SkSTArray<3, double>, SkSTArray<4, double>>(reporter);
412 test_skstarray_compatibility<SkSTArray<2, short>, SkSTArray<1, short>>(reporter);
413 }
414