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
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_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
97static 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
122template <typename T, bool MEM_MOVE>
123void test_copy_ctor(skiatest::Reporter* reporter, SkTArray<T, MEM_MOVE>&& array) {
124    SkASSERT(array.empty());
125    for (int i = 0; i < 5; ++i) {
126        array.emplace_back(new SkRefCnt);
127        REPORTER_ASSERT(reporter, array.back()->unique());
128    }
129
130    {
131        SkTArray<T, MEM_MOVE> copy(array);
132        for (const auto& ref : array)
133            REPORTER_ASSERT(reporter, !ref->unique());
134        for (const auto& ref : copy)
135            REPORTER_ASSERT(reporter, !ref->unique());
136    }
137
138    for (const auto& ref : array)
139        REPORTER_ASSERT(reporter, ref->unique());
140}
141
142static void test_move(skiatest::Reporter* reporter) {
143#define TEST_MOVE do {                                 \
144    SRC_T src;                                         \
145    src.emplace_back(sk_make_sp<SkRefCnt>());          \
146    {                                                  \
147        /* copy ctor */                                \
148        DST_T copy(src);                               \
149        REPORTER_ASSERT(reporter, !copy[0]->unique()); \
150    }                                                  \
151    {                                                  \
152        /* move ctor */                                \
153        DST_T move(std::move(src));                    \
154        REPORTER_ASSERT(reporter, move[0]->unique());  \
155    }                                                  \
156    REPORTER_ASSERT(reporter, src.empty());            \
157    src.emplace_back(sk_make_sp<SkRefCnt>());          \
158    {                                                  \
159        /* copy assignment */                          \
160        DST_T copy;                                    \
161        copy = src;                                    \
162        REPORTER_ASSERT(reporter, !copy[0]->unique()); \
163    }                                                  \
164    {                                                  \
165        /* move assignment */                          \
166        DST_T move;                                    \
167        move = std::move(src);                         \
168        REPORTER_ASSERT(reporter, move[0]->unique());  \
169    }                                                  \
170    REPORTER_ASSERT(reporter, src.empty());            \
171} while (false)
172
173    {
174        using SRC_T = SkTArray<sk_sp<SkRefCnt>, false>;
175        using DST_T = SkTArray<sk_sp<SkRefCnt>, false>;
176        TEST_MOVE;
177    }
178
179    {
180        using SRC_T = SkTArray<sk_sp<SkRefCnt>, true>;
181        using DST_T = SkTArray<sk_sp<SkRefCnt>, true>;
182        TEST_MOVE;
183    }
184
185    {
186        using SRC_T = SkSTArray<1, sk_sp<SkRefCnt>, false>;
187        using DST_T = SkSTArray<1, sk_sp<SkRefCnt>, false>;
188        TEST_MOVE;
189    }
190
191    {
192        using SRC_T = SkSTArray<1, sk_sp<SkRefCnt>, true>;
193        using DST_T = SkSTArray<1, sk_sp<SkRefCnt>, true>;
194        TEST_MOVE;
195    }
196
197    {
198        using SRC_T = SkTArray<sk_sp<SkRefCnt>, false>;
199        using DST_T = SkSTArray<1, sk_sp<SkRefCnt>, false>;
200        TEST_MOVE;
201    }
202
203    {
204        using SRC_T = SkTArray<sk_sp<SkRefCnt>, true>;
205        using DST_T = SkSTArray<1, sk_sp<SkRefCnt>, true>;
206        TEST_MOVE;
207    }
208
209    {
210        using SRC_T = SkSTArray<1, sk_sp<SkRefCnt>, false>;
211        using DST_T = SkTArray<sk_sp<SkRefCnt>, false>;
212        TEST_MOVE;
213    }
214
215    {
216        using SRC_T = SkSTArray<1, sk_sp<SkRefCnt>, true>;
217        using DST_T = SkTArray<sk_sp<SkRefCnt>, true>;
218        TEST_MOVE;
219    }
220#undef TEST_MOVE
221}
222
223template <typename T, bool MEM_MOVE> int SkTArray<T, MEM_MOVE>::allocCntForTest() const {
224    return fAllocCount;
225}
226
227void test_unnecessary_alloc(skiatest::Reporter* reporter) {
228    {
229        SkTArray<int> a;
230        REPORTER_ASSERT(reporter, a.allocCntForTest() == 0);
231    }
232    {
233        SkSTArray<10, int> a;
234        REPORTER_ASSERT(reporter, a.allocCntForTest() == 10);
235    }
236    {
237        SkTArray<int> a(1);
238        REPORTER_ASSERT(reporter, a.allocCntForTest() >= 1);
239    }
240    {
241        SkTArray<int> a, b;
242        b = a;
243        REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
244    }
245    {
246        SkSTArray<10, int> a;
247        SkTArray<int> b;
248        b = a;
249        REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
250    }
251    {
252        SkTArray<int> a;
253        SkTArray<int> b(a);
254        REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
255    }
256    {
257        SkSTArray<10, int> a;
258        SkTArray<int> b(a);
259        REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
260    }
261    {
262        SkTArray<int> a;
263        SkTArray<int> b(std::move(a));
264        REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
265    }
266    {
267        SkSTArray<10, int> a;
268        SkTArray<int> b(std::move(a));
269        REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
270    }
271    {
272        SkTArray<int> a;
273        SkTArray<int> b;
274        b = std::move(a);
275        REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
276    }
277    {
278        SkSTArray<10, int> a;
279        SkTArray<int> b;
280        b = std::move(a);
281        REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
282    }
283}
284
285static void test_self_assignment(skiatest::Reporter* reporter) {
286    SkTArray<int> a;
287    a.push_back(1);
288    REPORTER_ASSERT(reporter, !a.empty());
289    REPORTER_ASSERT(reporter, a.count() == 1);
290    REPORTER_ASSERT(reporter, a[0] == 1);
291
292    a = a;
293    REPORTER_ASSERT(reporter, !a.empty());
294    REPORTER_ASSERT(reporter, a.count() == 1);
295    REPORTER_ASSERT(reporter, a[0] == 1);
296}
297
298template <typename Array> static void test_array_reserve(skiatest::Reporter* reporter,
299                                                         Array* array, int reserveCount) {
300    SkRandom random;
301    REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
302    array->push_back();
303    REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
304    array->pop_back();
305    REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
306    while (array->count() < reserveCount) {
307        // Two steps forward, one step back
308        if (random.nextULessThan(3) < 2) {
309            array->push_back();
310        } else if (array->count() > 0) {
311            array->pop_back();
312        }
313        REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
314    }
315}
316
317template<typename Array> static void test_reserve(skiatest::Reporter* reporter) {
318    // Test that our allocated space stays >= to the reserve count until the array is filled to
319    // the reserve count
320    for (int reserveCount : {1, 2, 10, 100}) {
321        // Test setting reserve in constructor.
322        Array array1(reserveCount);
323        test_array_reserve(reporter, &array1, reserveCount);
324
325        // Test setting reserve after constructor.
326        Array array2;
327        array2.reserve(reserveCount);
328        test_array_reserve(reporter, &array2, reserveCount);
329
330        // Test increasing reserve after constructor.
331        Array array3(reserveCount/2);
332        array3.reserve(reserveCount);
333        test_array_reserve(reporter, &array3, reserveCount);
334
335        // Test setting reserve on non-empty array.
336        Array array4;
337        array4.push_back_n(reserveCount);
338        array4.reserve(reserveCount);
339        array4.pop_back_n(reserveCount);
340        test_array_reserve(reporter, &array4, 2 * reserveCount);
341    }
342}
343
344DEF_TEST(TArray, reporter) {
345    TestTSet_basic<true>(reporter);
346    TestTSet_basic<false>(reporter);
347    test_swap(reporter);
348
349    test_copy_ctor(reporter, SkTArray<sk_sp<SkRefCnt>, false>());
350    test_copy_ctor(reporter, SkTArray<sk_sp<SkRefCnt>,  true>());
351    test_copy_ctor(reporter, SkSTArray< 1, sk_sp<SkRefCnt>, false>());
352    test_copy_ctor(reporter, SkSTArray< 1, sk_sp<SkRefCnt>,  true>());
353    test_copy_ctor(reporter, SkSTArray<10, sk_sp<SkRefCnt>, false>());
354    test_copy_ctor(reporter, SkSTArray<10, sk_sp<SkRefCnt>,  true>());
355
356    test_move(reporter);
357
358    test_unnecessary_alloc(reporter);
359
360    test_self_assignment(reporter);
361
362    test_reserve<SkTArray<int>>(reporter);
363    test_reserve<SkSTArray<1, int>>(reporter);
364    test_reserve<SkSTArray<2, int>>(reporter);
365    test_reserve<SkSTArray<16, int>>(reporter);
366}
367