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
122 template <typename T, bool MEM_MOVE>
test_copy_ctor(skiatest::Reporter * reporter,SkTArray<T,MEM_MOVE> && array)123 void 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
test_move(skiatest::Reporter * reporter)142 static 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
allocCntForTest() const223 template <typename T, bool MEM_MOVE> int SkTArray<T, MEM_MOVE>::allocCntForTest() const {
224 return fAllocCount;
225 }
226
test_unnecessary_alloc(skiatest::Reporter * reporter)227 void 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
test_self_assignment(skiatest::Reporter * reporter)285 static 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
test_array_reserve(skiatest::Reporter * reporter,Array * array,int reserveCount)298 template <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
test_reserve(skiatest::Reporter * reporter)317 template<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
DEF_TEST(TArray,reporter)344 DEF_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