1 /*
2 * Copyright 2015 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/core/SkString.h"
10 #include "include/core/SkTypes.h"
11 #include "src/core/SkTHash.h"
12 #include "tests/Test.h"
13
14 #include <cstdint>
15 #include <initializer_list>
16 #include <string>
17 #include <string_view>
18 #include <utility>
19
20 using namespace skia_private;
21
22 // Tests use of const foreach(). map.count() is of course the better way to do this.
count(const THashMap<int,double> & map)23 static int count(const THashMap<int, double>& map) {
24 int n = 0;
25 map.foreach([&n](int, double) { n++; });
26 return n;
27 }
28
DEF_TEST(HashMap,r)29 DEF_TEST(HashMap, r) {
30 THashMap<int, double> map;
31
32 map.set(3, 4.0);
33 REPORTER_ASSERT(r, map.count() == 1);
34
35 REPORTER_ASSERT(r, map.approxBytesUsed() > 0);
36
37 double* found = map.find(3);
38 REPORTER_ASSERT(r, found);
39 REPORTER_ASSERT(r, *found == 4.0);
40
41 map.foreach([](int key, double* d){ *d = -key; });
42 REPORTER_ASSERT(r, count(map) == 1);
43
44 found = map.find(3);
45 REPORTER_ASSERT(r, found);
46 REPORTER_ASSERT(r, *found == -3.0);
47
48 REPORTER_ASSERT(r, !map.find(2));
49
50 const int N = 20;
51
52 for (int i = 0; i < N; i++) {
53 map.set(i, 2.0*i);
54 }
55
56 // Test walking the map with foreach(const K&, V)
57 map.foreach([&](const int& key, double value) {
58 REPORTER_ASSERT(r, key * 2 == value);
59 });
60
61 // Test walking the map with foreach(const K&, V*)
62 map.foreach([&](const int& key, double* value) {
63 REPORTER_ASSERT(r, key * 2 == *value);
64 });
65
66 // Test walking the map with foreach(const Pair&)
67 map.foreach([&](const THashMap<int, double>::Pair& pair) {
68 REPORTER_ASSERT(r, pair.first * 2 == pair.second);
69 });
70
71 // Test walking the map with iterators, using preincrement (++iter).
72 for (THashMap<int, double>::Iter iter = map.begin(); iter != map.end(); ++iter) {
73 REPORTER_ASSERT(r, iter->first * 2 == (*iter).second);
74 }
75
76 // Test walking the map with range-based for.
77 for (auto& entry : map) {
78 REPORTER_ASSERT(r, entry.first * 2 == entry.second);
79 }
80
81 // Ensure that iteration works equally well on a const map, using postincrement (iter++).
82 const auto& cmap = map;
83 for (THashMap<int, double>::Iter iter = cmap.begin(); iter != cmap.end(); iter++) {
84 REPORTER_ASSERT(r, iter->first * 2 == (*iter).second);
85 }
86
87 // Ensure that range-based for works equally well on a const map.
88 for (const auto& entry : cmap) {
89 REPORTER_ASSERT(r, entry.first * 2 == entry.second);
90 }
91
92 // Ensure that structured bindings work.
93 for (const auto& [number, timesTwo] : cmap) {
94 REPORTER_ASSERT(r, number * 2 == timesTwo);
95 }
96
97 THashMap<int, double> clone = map;
98
99 for (int i = 0; i < N; i++) {
100 found = map.find(i);
101 REPORTER_ASSERT(r, found);
102 REPORTER_ASSERT(r, *found == i*2.0);
103
104 found = clone.find(i);
105 REPORTER_ASSERT(r, found);
106 REPORTER_ASSERT(r, *found == i*2.0);
107 }
108 for (int i = N; i < 2*N; i++) {
109 REPORTER_ASSERT(r, !map.find(i));
110 REPORTER_ASSERT(r, !clone.find(i));
111 }
112
113 REPORTER_ASSERT(r, map.count() == N);
114 REPORTER_ASSERT(r, clone.count() == N);
115
116 for (int i = 0; i < N/2; i++) {
117 map.remove(i);
118 }
119 for (int i = 0; i < N; i++) {
120 found = map.find(i);
121 REPORTER_ASSERT(r, (found == nullptr) == (i < N/2));
122
123 found = clone.find(i);
124 REPORTER_ASSERT(r, *found == i*2.0);
125 }
126 REPORTER_ASSERT(r, map.count() == N/2);
127 REPORTER_ASSERT(r, clone.count() == N);
128
129 map.reset();
130 REPORTER_ASSERT(r, map.count() == 0);
131 REPORTER_ASSERT(r, clone.count() == N);
132
133 clone = map;
134 REPORTER_ASSERT(r, clone.count() == 0);
135
136 {
137 // Test that we don't leave dangling values in empty slots.
138 THashMap<int, sk_sp<SkRefCnt>> refMap;
139 auto ref = sk_make_sp<SkRefCnt>();
140 REPORTER_ASSERT(r, ref->unique());
141
142 refMap.set(0, ref);
143 REPORTER_ASSERT(r, refMap.count() == 1);
144 REPORTER_ASSERT(r, !ref->unique());
145
146 refMap.remove(0);
147 REPORTER_ASSERT(r, refMap.count() == 0);
148 REPORTER_ASSERT(r, ref->unique());
149 }
150 }
151
DEF_TEST(HashMapCtor,r)152 DEF_TEST(HashMapCtor, r) {
153 THashMap<int, std::string_view> map{{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}};
154 REPORTER_ASSERT(r, map.count() == 4);
155 REPORTER_ASSERT(r, map.approxBytesUsed() >= 4 * (sizeof(int) + sizeof(std::string_view)));
156
157 std::string_view* found = map.find(1);
158 REPORTER_ASSERT(r, found);
159 REPORTER_ASSERT(r, *found == "one");
160
161 found = map.find(2);
162 REPORTER_ASSERT(r, found);
163 REPORTER_ASSERT(r, *found == "two");
164
165 found = map.find(3);
166 REPORTER_ASSERT(r, found);
167 REPORTER_ASSERT(r, *found == "three");
168
169 found = map.find(4);
170 REPORTER_ASSERT(r, found);
171 REPORTER_ASSERT(r, *found == "four");
172
173 found = map.find(5);
174 REPORTER_ASSERT(r, !found);
175
176 found = map.find(6);
177 REPORTER_ASSERT(r, !found);
178 }
179
DEF_TEST(HashMapCtorOneElem,r)180 DEF_TEST(HashMapCtorOneElem, r) {
181 // Start out with a single element. The initializer list constructor sets the capacity
182 // conservatively. Searching for elements beyond the capacity should succeed.
183 THashMap<int, std::string_view> map{{1, "one"}};
184 REPORTER_ASSERT(r, map.count() == 1);
185 REPORTER_ASSERT(r, map.approxBytesUsed() >= (sizeof(int) + sizeof(std::string_view)));
186
187 std::string_view* found = map.find(1);
188 REPORTER_ASSERT(r, found);
189 REPORTER_ASSERT(r, *found == "one");
190
191 found = map.find(2);
192 REPORTER_ASSERT(r, !found);
193
194 // Grow the collection by one element. Searching for non-existing elements should still succeed.
195 map.set(2, "two");
196 found = map.find(2);
197 REPORTER_ASSERT(r, found);
198 REPORTER_ASSERT(r, *found == "two");
199
200 found = map.find(3);
201 REPORTER_ASSERT(r, !found);
202 }
203
DEF_TEST(HashSetCtor,r)204 DEF_TEST(HashSetCtor, r) {
205 THashSet<std::string_view> set{"one", "two", "three", "four"};
206 REPORTER_ASSERT(r, set.count() == 4);
207 REPORTER_ASSERT(r, set.approxBytesUsed() >= 4 * sizeof(std::string_view));
208
209 REPORTER_ASSERT(r, set.contains("one"));
210 REPORTER_ASSERT(r, set.contains("two"));
211 REPORTER_ASSERT(r, set.contains("three"));
212 REPORTER_ASSERT(r, set.contains("four"));
213 REPORTER_ASSERT(r, !set.contains("five"));
214 REPORTER_ASSERT(r, !set.contains("six"));
215 }
216
DEF_TEST(HashSetCtorOneElem,r)217 DEF_TEST(HashSetCtorOneElem, r) {
218 // Start out with a single element. The initializer list constructor sets the capacity
219 // conservatively. Searching for elements beyond the capacity should succeed.
220 THashSet<std::string_view> set{"one"};
221 REPORTER_ASSERT(r, set.count() == 1);
222 REPORTER_ASSERT(r, set.approxBytesUsed() >= sizeof(std::string_view));
223
224 REPORTER_ASSERT(r, set.contains("one"));
225 REPORTER_ASSERT(r, !set.contains("two"));
226
227 // Grow the collection by one element. Searching for non-existing elements should still succeed.
228 set.add("two");
229 REPORTER_ASSERT(r, set.contains("one"));
230 REPORTER_ASSERT(r, set.contains("two"));
231 REPORTER_ASSERT(r, !set.contains("three"));
232 }
233
234 template <typename T>
test_hash_set(skiatest::Reporter * r)235 static void test_hash_set(skiatest::Reporter* r) {
236 THashSet<T> set;
237
238 set.add(T("Hello"));
239 set.add(T("World"));
240 REPORTER_ASSERT(r, set.count() == 2);
241 REPORTER_ASSERT(r, set.contains(T("Hello")));
242 REPORTER_ASSERT(r, set.contains(T("World")));
243 REPORTER_ASSERT(r, !set.contains(T("Goodbye")));
244 REPORTER_ASSERT(r, set.find(T("Hello")));
245 REPORTER_ASSERT(r, *set.find(T("Hello")) == T("Hello"));
246
247 // Test walking the set with iterators, using preincrement (++iter).
248 for (typename THashSet<T>::Iter iter = set.begin(); iter != set.end(); ++iter) {
249 REPORTER_ASSERT(r, *iter == T("Hello") || *iter == T("World"));
250 }
251
252 // Test walking the set with iterators, using postincrement (iter++).
253 for (typename THashSet<T>::Iter iter = set.begin(); iter != set.end(); iter++) {
254 REPORTER_ASSERT(r, *iter == T("Hello") || *iter == T("World"));
255 }
256
257 // Test walking the set with range-based for.
258 for (auto& entry : set) {
259 REPORTER_ASSERT(r, entry == T("Hello") || entry == T("World"));
260 }
261
262 // Ensure that iteration works equally well on a const set.
263 const auto& cset = set;
264 for (typename THashSet<T>::Iter iter = cset.begin(); iter != cset.end(); iter++) {
265 REPORTER_ASSERT(r, *iter == T("Hello") || *iter == T("World"));
266 }
267
268 // Ensure that range-based for works equally well on a const set.
269 for (auto& entry : cset) {
270 REPORTER_ASSERT(r, entry == T("Hello") || entry == T("World"));
271 }
272
273 THashSet<T> clone = set;
274 REPORTER_ASSERT(r, clone.count() == 2);
275 REPORTER_ASSERT(r, clone.contains(T("Hello")));
276 REPORTER_ASSERT(r, clone.contains(T("World")));
277 REPORTER_ASSERT(r, !clone.contains(T("Goodbye")));
278 REPORTER_ASSERT(r, clone.find(T("Hello")));
279 REPORTER_ASSERT(r, *clone.find(T("Hello")) == T("Hello"));
280
281 set.remove(T("Hello"));
282 REPORTER_ASSERT(r, !set.contains(T("Hello")));
283 REPORTER_ASSERT(r, set.count() == 1);
284 REPORTER_ASSERT(r, clone.contains(T("Hello")));
285 REPORTER_ASSERT(r, clone.count() == 2);
286
287 set.reset();
288 REPORTER_ASSERT(r, set.count() == 0);
289
290 clone = set;
291 REPORTER_ASSERT(r, clone.count() == 0);
292 }
293
DEF_TEST(HashSetWithSkString,r)294 DEF_TEST(HashSetWithSkString, r) {
295 test_hash_set<SkString>(r);
296 }
297
DEF_TEST(HashSetWithStdString,r)298 DEF_TEST(HashSetWithStdString, r) {
299 test_hash_set<std::string>(r);
300 }
301
DEF_TEST(HashSetWithStdStringView,r)302 DEF_TEST(HashSetWithStdStringView, r) {
303 test_hash_set<std::string_view>(r);
304 }
305
306 namespace {
307
308 class CopyCounter {
309 public:
CopyCounter()310 CopyCounter() : fID(0), fCounter(nullptr) {}
311
CopyCounter(uint32_t id,uint32_t * counter)312 CopyCounter(uint32_t id, uint32_t* counter) : fID(id), fCounter(counter) {}
313
CopyCounter(const CopyCounter & other)314 CopyCounter(const CopyCounter& other)
315 : fID(other.fID)
316 , fCounter(other.fCounter) {
317 SkASSERT(fCounter);
318 *fCounter += 1;
319 }
320
operator =(const CopyCounter & other)321 void operator=(const CopyCounter& other) {
322 fID = other.fID;
323 fCounter = other.fCounter;
324 *fCounter += 1;
325 }
326
CopyCounter(CopyCounter && other)327 CopyCounter(CopyCounter&& other) { *this = std::move(other); }
operator =(CopyCounter && other)328 void operator=(CopyCounter&& other) {
329 fID = other.fID;
330 fCounter = other.fCounter;
331 }
332
333
operator ==(const CopyCounter & other) const334 bool operator==(const CopyCounter& other) const {
335 return fID == other.fID;
336 }
337
338 private:
339 uint32_t fID;
340 uint32_t* fCounter;
341 };
342
343 struct HashCopyCounter {
operator ()__anon4355cab50611::HashCopyCounter344 uint32_t operator()(const CopyCounter&) const {
345 return 0; // let them collide, what do we care?
346 }
347 };
348
349 } // namespace
350
DEF_TEST(HashSetCopyCounter,r)351 DEF_TEST(HashSetCopyCounter, r) {
352 THashSet<CopyCounter, HashCopyCounter> set;
353
354 uint32_t globalCounter = 0;
355 CopyCounter copyCounter1(1, &globalCounter);
356 CopyCounter copyCounter2(2, &globalCounter);
357 REPORTER_ASSERT(r, globalCounter == 0);
358
359 set.add(copyCounter1);
360 REPORTER_ASSERT(r, globalCounter == 1);
361 REPORTER_ASSERT(r, set.contains(copyCounter1));
362 REPORTER_ASSERT(r, globalCounter == 1);
363 set.add(copyCounter1);
364 // We allow copies for same-value adds for now.
365 REPORTER_ASSERT(r, globalCounter == 2);
366
367 set.add(copyCounter2);
368 REPORTER_ASSERT(r, globalCounter == 3);
369 REPORTER_ASSERT(r, set.contains(copyCounter1));
370 REPORTER_ASSERT(r, set.contains(copyCounter2));
371 REPORTER_ASSERT(r, globalCounter == 3);
372 set.add(copyCounter1);
373 set.add(copyCounter2);
374 // We allow copies for same-value adds for now.
375 REPORTER_ASSERT(r, globalCounter == 5);
376 }
377
DEF_TEST(HashFindOrNull,r)378 DEF_TEST(HashFindOrNull, r) {
379 struct Entry {
380 int key = 0;
381 int val = 0;
382 };
383
384 struct HashTraits {
385 static int GetKey(const Entry* e) { return e->key; }
386 static uint32_t Hash(int key) { return key; }
387 };
388
389 THashTable<Entry*, int, HashTraits> table;
390
391 REPORTER_ASSERT(r, nullptr == table.findOrNull(7));
392
393 Entry seven = { 7, 24 };
394 table.set(&seven);
395
396 REPORTER_ASSERT(r, &seven == table.findOrNull(7));
397 }
398
DEF_TEST(HashTableGrowsAndShrinks,r)399 DEF_TEST(HashTableGrowsAndShrinks, r) {
400 THashSet<int> s;
401 auto check_count_cap = [&](int count, int cap) {
402 REPORTER_ASSERT(r, s.count() == count,
403 "Expected: %d. Actual: %d.", count, s.count());
404
405 size_t expectedCapacityBytes = (sizeof(int) + sizeof(uint32_t)) * cap;
406 REPORTER_ASSERT(r, s.approxBytesUsed() == expectedCapacityBytes,
407 "Expected: %zu. Actual: %zu.", expectedCapacityBytes, s.approxBytesUsed());
408 };
409
410 // Add and remove some elements to test basic growth and shrink patterns.
411 check_count_cap(0, 0);
412 s.add(1); check_count_cap(1, 4);
413 s.add(2); check_count_cap(2, 4);
414 s.add(3); check_count_cap(3, 4);
415 s.add(4); check_count_cap(4, 8);
416
417 s.remove(4); check_count_cap(3, 8);
418 s.remove(3); check_count_cap(2, 4);
419 s.remove(2); check_count_cap(1, 4);
420 s.remove(1); check_count_cap(0, 4);
421
422 s.add(1); check_count_cap(1, 4);
423 s.add(2); check_count_cap(2, 4);
424 s.add(3); check_count_cap(3, 4);
425 s.add(4); check_count_cap(4, 8);
426
427 // Test that reserve() will preallocate space, rounded up to 2^n.
428 s.reserve(40); check_count_cap(4, 64);
429 s.reserve(48); check_count_cap(4, 64);
430 s.reserve(49); check_count_cap(4, 128);
431
432 // Test that reserve() will not shrink the capacity.
433 s.reserve(48); check_count_cap(4, 128);
434 s.reserve(12); check_count_cap(4, 128);
435 s.reserve(1); check_count_cap(4, 128);
436
437 // Test that adding elements will maintain the reserved capacity.
438 s.add(5); check_count_cap(5, 128);
439 s.add(6); check_count_cap(6, 128);
440 s.add(7); check_count_cap(7, 128);
441 s.add(8); check_count_cap(8, 128);
442
443 // Removing elements, on the other hand, _will_ allow the container to shrink.
444 s.remove(4); check_count_cap(7, 64);
445 s.remove(5); check_count_cap(6, 32);
446 s.remove(6); check_count_cap(5, 16);
447 s.remove(7); check_count_cap(4, 8);
448 s.remove(8); check_count_cap(3, 8);
449 s.add(4); check_count_cap(4, 8);
450
451 // Add and remove single elements repeatedly to test hysteresis
452 // avoids reallocating these small tables all the time.
453 for (int i = 0; i < 10; i++) {
454 s. add(5); check_count_cap(5,8);
455 s.remove(5); check_count_cap(4,8);
456 }
457
458 s.remove(4); check_count_cap(3,8);
459 for (int i = 0; i < 10; i++) {
460 s. add(4); check_count_cap(4,8);
461 s.remove(4); check_count_cap(3,8);
462 }
463
464 s.remove(3); check_count_cap(2,4);
465 for (int i = 0; i < 10; i++) {
466 s. add(4); check_count_cap(3,4);
467 s.remove(4); check_count_cap(2,4);
468 }
469
470 s.remove(2); check_count_cap(1,4);
471 for (int i = 0; i < 10; i++) {
472 s. add(2); check_count_cap(2,4);
473 s.remove(2); check_count_cap(1,4);
474 }
475 }
476
DEF_TEST(HashMapSwap,r)477 DEF_TEST(HashMapSwap, r) {
478 // Swap two maps.
479 THashMap<int, std::string_view> a{{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}};
480 THashMap<int, std::string_view> b{{1, "ichi"}, {2, "ni"}, {3, "san"}};
481
482 a.swap(b);
483 REPORTER_ASSERT(r, a.count() == 3);
484 REPORTER_ASSERT(r, a[1] == "ichi");
485 REPORTER_ASSERT(r, a[2] == "ni");
486 REPORTER_ASSERT(r, a[3] == "san");
487
488 REPORTER_ASSERT(r, b.count() == 4);
489 REPORTER_ASSERT(r, b[1] == "one");
490 REPORTER_ASSERT(r, b[2] == "two");
491 REPORTER_ASSERT(r, b[3] == "three");
492 REPORTER_ASSERT(r, b[4] == "four");
493
494 // Swap with an rvalue.
495 a.swap(THashMap<int, std::string_view>());
496 REPORTER_ASSERT(r, a.empty());
497 }
498
DEF_TEST(HashSetSwap,r)499 DEF_TEST(HashSetSwap, r) {
500 // Swap two maps.
501 THashSet<std::string_view> a{"one", "two", "three", "four"};
502 THashSet<std::string_view> b{"ichi", "ni", "san"};
503
504 a.swap(b);
505 REPORTER_ASSERT(r, a.count() == 3);
506 REPORTER_ASSERT(r, a.contains("ichi"));
507 REPORTER_ASSERT(r, a.contains("ni"));
508 REPORTER_ASSERT(r, a.contains("san"));
509
510 REPORTER_ASSERT(r, b.count() == 4);
511 REPORTER_ASSERT(r, b.contains("one"));
512 REPORTER_ASSERT(r, b.contains("two"));
513 REPORTER_ASSERT(r, b.contains("three"));
514 REPORTER_ASSERT(r, b.contains("four"));
515
516 // Swap with an rvalue.
517 a.swap(THashSet<std::string_view>());
518 REPORTER_ASSERT(r, a.empty());
519 }
520