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