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 
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_swap(skiatest::Reporter * reporter,SkTArray<T> * (& arrays)[4],int (& sizes)[7])63 template <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 
test_swap(skiatest::Reporter * reporter)97 static 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 
allocCntForTest() const122 template <typename T, bool MEM_MOVE> int SkTArray<T, MEM_MOVE>::allocCntForTest() const {
123     return fAllocCount;
124 }
125 
test_unnecessary_alloc(skiatest::Reporter * reporter)126 void test_unnecessary_alloc(skiatest::Reporter* reporter) {
127     {
128         SkTArray<int> a;
129         REPORTER_ASSERT(reporter, a.allocCntForTest() == 0);
130     }
131     {
132         SkSTArray<10, int> a;
133         REPORTER_ASSERT(reporter, a.allocCntForTest() == 10);
134     }
135     {
136         SkTArray<int> a(1);
137         REPORTER_ASSERT(reporter, a.allocCntForTest() >= 1);
138     }
139     {
140         SkTArray<int> a, b;
141         b = a;
142         REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
143     }
144     {
145         SkSTArray<10, int> a;
146         SkTArray<int> b;
147         b = a;
148         REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
149     }
150     {
151         SkTArray<int> a;
152         SkTArray<int> b(a);
153         REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
154     }
155     {
156         SkSTArray<10, int> a;
157         SkTArray<int> b(a);
158         REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
159     }
160     {
161         SkTArray<int> a;
162         SkTArray<int> b(std::move(a));
163         REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
164     }
165     {
166         SkSTArray<10, int> a;
167         SkTArray<int> b(std::move(a));
168         REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
169     }
170     {
171         SkTArray<int> a;
172         SkTArray<int> b;
173         b = std::move(a);
174         REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
175     }
176     {
177         SkSTArray<10, int> a;
178         SkTArray<int> b;
179         b = std::move(a);
180         REPORTER_ASSERT(reporter, b.allocCntForTest() == 0);
181     }
182 }
183 
test_self_assignment(skiatest::Reporter * reporter)184 static void test_self_assignment(skiatest::Reporter* reporter) {
185     SkTArray<int> a;
186     a.push_back(1);
187     REPORTER_ASSERT(reporter, !a.empty());
188     REPORTER_ASSERT(reporter, a.count() == 1);
189     REPORTER_ASSERT(reporter, a[0] == 1);
190 
191     a = static_cast<decltype(a)&>(a);
192     REPORTER_ASSERT(reporter, !a.empty());
193     REPORTER_ASSERT(reporter, a.count() == 1);
194     REPORTER_ASSERT(reporter, a[0] == 1);
195 }
196 
test_array_reserve(skiatest::Reporter * reporter,Array * array,int reserveCount)197 template <typename Array> static void test_array_reserve(skiatest::Reporter* reporter,
198                                                          Array* array, int reserveCount) {
199     SkRandom random;
200     REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
201     array->push_back();
202     REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
203     array->pop_back();
204     REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
205     while (array->count() < reserveCount) {
206         // Two steps forward, one step back
207         if (random.nextULessThan(3) < 2) {
208             array->push_back();
209         } else if (array->count() > 0) {
210             array->pop_back();
211         }
212         REPORTER_ASSERT(reporter, array->allocCntForTest() >= reserveCount);
213     }
214 }
215 
test_reserve(skiatest::Reporter * reporter)216 template<typename Array> static void test_reserve(skiatest::Reporter* reporter) {
217     // Test that our allocated space stays >= to the reserve count until the array is filled to
218     // the reserve count
219     for (int reserveCount : {1, 2, 10, 100}) {
220         // Test setting reserve in constructor.
221         Array array1(reserveCount);
222         test_array_reserve(reporter, &array1, reserveCount);
223 
224         // Test setting reserve after constructor.
225         Array array2;
226         array2.reserve(reserveCount);
227         test_array_reserve(reporter, &array2, reserveCount);
228 
229         // Test increasing reserve after constructor.
230         Array array3(reserveCount/2);
231         array3.reserve(reserveCount);
232         test_array_reserve(reporter, &array3, reserveCount);
233 
234         // Test setting reserve on non-empty array.
235         Array array4;
236         array4.push_back_n(reserveCount);
237         array4.reserve(reserveCount);
238         array4.pop_back_n(reserveCount);
239         test_array_reserve(reporter, &array4, 2 * reserveCount);
240     }
241 }
242 
DEF_TEST(TArray,reporter)243 DEF_TEST(TArray, reporter) {
244     TestTSet_basic<true>(reporter);
245     TestTSet_basic<false>(reporter);
246     test_swap(reporter);
247 
248     test_unnecessary_alloc(reporter);
249 
250     test_self_assignment(reporter);
251 
252     test_reserve<SkTArray<int>>(reporter);
253     test_reserve<SkSTArray<1, int>>(reporter);
254     test_reserve<SkSTArray<2, int>>(reporter);
255     test_reserve<SkSTArray<16, int>>(reporter);
256 }
257