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