xref: /third_party/skia/tests/TArrayTest.cpp (revision cb93a386) 
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
15template <bool MEM_MOVE>
16static 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
63template <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
117template <typename T, typename U>
118static 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
169template <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
203static 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
228void 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
286static 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
299template <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
318template<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
345DEF_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