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/private/SkChecksum.h"
11 #include "include/private/SkTHash.h"
12 #include "tests/Test.h"
13
14 #include <tuple>
15
16 // Tests use of const foreach(). map.count() is of course the better way to do this.
count(const SkTHashMap<int,double> & map)17 static int count(const SkTHashMap<int, double>& map) {
18 int n = 0;
19 map.foreach([&n](int, double) { n++; });
20 return n;
21 }
22
DEF_TEST(HashMap,r)23 DEF_TEST(HashMap, r) {
24 SkTHashMap<int, double> map;
25
26 map.set(3, 4.0);
27 REPORTER_ASSERT(r, map.count() == 1);
28
29 REPORTER_ASSERT(r, map.approxBytesUsed() > 0);
30
31 double* found = map.find(3);
32 REPORTER_ASSERT(r, found);
33 REPORTER_ASSERT(r, *found == 4.0);
34
35 map.foreach([](int key, double* d){ *d = -key; });
36 REPORTER_ASSERT(r, count(map) == 1);
37
38 found = map.find(3);
39 REPORTER_ASSERT(r, found);
40 REPORTER_ASSERT(r, *found == -3.0);
41
42 REPORTER_ASSERT(r, !map.find(2));
43
44 const int N = 20;
45
46 for (int i = 0; i < N; i++) {
47 map.set(i, 2.0*i);
48 }
49
50 // Test walking the map with iterators, using preincrement (++iter).
51 for (SkTHashMap<int, double>::Iter iter = map.begin(); iter != map.end(); ++iter) {
52 REPORTER_ASSERT(r, iter->first * 2 == (*iter).second);
53 }
54
55 // Test walking the map with range-based for.
56 for (auto& entry : map) {
57 REPORTER_ASSERT(r, entry.first * 2 == entry.second);
58 }
59
60 // Ensure that iteration works equally well on a const map, using postincrement (iter++).
61 const auto& cmap = map;
62 for (SkTHashMap<int, double>::Iter iter = cmap.begin(); iter != cmap.end(); iter++) {
63 REPORTER_ASSERT(r, iter->first * 2 == (*iter).second);
64 }
65
66 // Ensure that range-based for works equally well on a const map.
67 for (const auto& entry : cmap) {
68 REPORTER_ASSERT(r, entry.first * 2 == entry.second);
69 }
70
71 // Ensure that structured bindings work.
72 for (const auto& [number, timesTwo] : cmap) {
73 REPORTER_ASSERT(r, number * 2 == timesTwo);
74 }
75
76 SkTHashMap<int, double> clone = map;
77
78 for (int i = 0; i < N; i++) {
79 double* found = map.find(i);
80 REPORTER_ASSERT(r, found);
81 REPORTER_ASSERT(r, *found == i*2.0);
82
83 found = clone.find(i);
84 REPORTER_ASSERT(r, found);
85 REPORTER_ASSERT(r, *found == i*2.0);
86 }
87 for (int i = N; i < 2*N; i++) {
88 REPORTER_ASSERT(r, !map.find(i));
89 REPORTER_ASSERT(r, !clone.find(i));
90 }
91
92 REPORTER_ASSERT(r, map.count() == N);
93 REPORTER_ASSERT(r, clone.count() == N);
94
95 for (int i = 0; i < N/2; i++) {
96 map.remove(i);
97 }
98 for (int i = 0; i < N; i++) {
99 double* found = map.find(i);
100 REPORTER_ASSERT(r, (found == nullptr) == (i < N/2));
101
102 found = clone.find(i);
103 REPORTER_ASSERT(r, *found == i*2.0);
104 }
105 REPORTER_ASSERT(r, map.count() == N/2);
106 REPORTER_ASSERT(r, clone.count() == N);
107
108 map.reset();
109 REPORTER_ASSERT(r, map.count() == 0);
110 REPORTER_ASSERT(r, clone.count() == N);
111
112 clone = map;
113 REPORTER_ASSERT(r, clone.count() == 0);
114
115 {
116 // Test that we don't leave dangling values in empty slots.
117 SkTHashMap<int, sk_sp<SkRefCnt>> refMap;
118 auto ref = sk_make_sp<SkRefCnt>();
119 REPORTER_ASSERT(r, ref->unique());
120
121 refMap.set(0, ref);
122 REPORTER_ASSERT(r, refMap.count() == 1);
123 REPORTER_ASSERT(r, !ref->unique());
124
125 refMap.remove(0);
126 REPORTER_ASSERT(r, refMap.count() == 0);
127 REPORTER_ASSERT(r, ref->unique());
128 }
129 }
130
DEF_TEST(HashSet,r)131 DEF_TEST(HashSet, r) {
132 SkTHashSet<SkString> set;
133
134 set.add(SkString("Hello"));
135 set.add(SkString("World"));
136 REPORTER_ASSERT(r, set.count() == 2);
137 REPORTER_ASSERT(r, set.contains(SkString("Hello")));
138 REPORTER_ASSERT(r, set.contains(SkString("World")));
139 REPORTER_ASSERT(r, !set.contains(SkString("Goodbye")));
140 REPORTER_ASSERT(r, set.find(SkString("Hello")));
141 REPORTER_ASSERT(r, *set.find(SkString("Hello")) == SkString("Hello"));
142
143 // Test walking the set with iterators, using preincrement (++iter).
144 for (SkTHashSet<SkString>::Iter iter = set.begin(); iter != set.end(); ++iter) {
145 REPORTER_ASSERT(r, iter->equals("Hello") || (*iter).equals("World"));
146 }
147
148 // Test walking the set with iterators, using postincrement (iter++).
149 for (SkTHashSet<SkString>::Iter iter = set.begin(); iter != set.end(); iter++) {
150 REPORTER_ASSERT(r, iter->equals("Hello") || (*iter).equals("World"));
151 }
152
153 // Test walking the set with range-based for.
154 for (auto& entry : set) {
155 REPORTER_ASSERT(r, entry.equals("Hello") || entry.equals("World"));
156 }
157
158 // Ensure that iteration works equally well on a const set.
159 const auto& cset = set;
160 for (SkTHashSet<SkString>::Iter iter = cset.begin(); iter != cset.end(); iter++) {
161 REPORTER_ASSERT(r, iter->equals("Hello") || (*iter).equals("World"));
162 }
163
164 // Ensure that range-based for works equally well on a const set.
165 for (auto& entry : cset) {
166 REPORTER_ASSERT(r, entry.equals("Hello") || entry.equals("World"));
167 }
168
169 SkTHashSet<SkString> clone = set;
170 REPORTER_ASSERT(r, clone.count() == 2);
171 REPORTER_ASSERT(r, clone.contains(SkString("Hello")));
172 REPORTER_ASSERT(r, clone.contains(SkString("World")));
173 REPORTER_ASSERT(r, !clone.contains(SkString("Goodbye")));
174 REPORTER_ASSERT(r, clone.find(SkString("Hello")));
175 REPORTER_ASSERT(r, *clone.find(SkString("Hello")) == SkString("Hello"));
176
177 set.remove(SkString("Hello"));
178 REPORTER_ASSERT(r, !set.contains(SkString("Hello")));
179 REPORTER_ASSERT(r, set.count() == 1);
180 REPORTER_ASSERT(r, clone.contains(SkString("Hello")));
181 REPORTER_ASSERT(r, clone.count() == 2);
182
183 set.reset();
184 REPORTER_ASSERT(r, set.count() == 0);
185
186 clone = set;
187 REPORTER_ASSERT(r, clone.count() == 0);
188 }
189
190 namespace {
191
192 class CopyCounter {
193 public:
CopyCounter()194 CopyCounter() : fID(0), fCounter(nullptr) {}
195
CopyCounter(uint32_t id,uint32_t * counter)196 CopyCounter(uint32_t id, uint32_t* counter) : fID(id), fCounter(counter) {}
197
CopyCounter(const CopyCounter & other)198 CopyCounter(const CopyCounter& other)
199 : fID(other.fID)
200 , fCounter(other.fCounter) {
201 SkASSERT(fCounter);
202 *fCounter += 1;
203 }
204
operator =(const CopyCounter & other)205 void operator=(const CopyCounter& other) {
206 fID = other.fID;
207 fCounter = other.fCounter;
208 *fCounter += 1;
209 }
210
CopyCounter(CopyCounter && other)211 CopyCounter(CopyCounter&& other) { *this = std::move(other); }
operator =(CopyCounter && other)212 void operator=(CopyCounter&& other) {
213 fID = other.fID;
214 fCounter = other.fCounter;
215 }
216
217
operator ==(const CopyCounter & other) const218 bool operator==(const CopyCounter& other) const {
219 return fID == other.fID;
220 }
221
222 private:
223 uint32_t fID;
224 uint32_t* fCounter;
225 };
226
227 struct HashCopyCounter {
operator ()__anonbed1977f0311::HashCopyCounter228 uint32_t operator()(const CopyCounter&) const {
229 return 0; // let them collide, what do we care?
230 }
231 };
232
233 } // namespace
234
DEF_TEST(HashSetCopyCounter,r)235 DEF_TEST(HashSetCopyCounter, r) {
236 SkTHashSet<CopyCounter, HashCopyCounter> set;
237
238 uint32_t globalCounter = 0;
239 CopyCounter copyCounter1(1, &globalCounter);
240 CopyCounter copyCounter2(2, &globalCounter);
241 REPORTER_ASSERT(r, globalCounter == 0);
242
243 set.add(copyCounter1);
244 REPORTER_ASSERT(r, globalCounter == 1);
245 REPORTER_ASSERT(r, set.contains(copyCounter1));
246 REPORTER_ASSERT(r, globalCounter == 1);
247 set.add(copyCounter1);
248 // We allow copies for same-value adds for now.
249 REPORTER_ASSERT(r, globalCounter == 2);
250
251 set.add(copyCounter2);
252 REPORTER_ASSERT(r, globalCounter == 3);
253 REPORTER_ASSERT(r, set.contains(copyCounter1));
254 REPORTER_ASSERT(r, set.contains(copyCounter2));
255 REPORTER_ASSERT(r, globalCounter == 3);
256 set.add(copyCounter1);
257 set.add(copyCounter2);
258 // We allow copies for same-value adds for now.
259 REPORTER_ASSERT(r, globalCounter == 5);
260 }
261
262
DEF_TEST(HashFindOrNull,r)263 DEF_TEST(HashFindOrNull, r) {
264 struct Entry {
265 int key = 0;
266 int val = 0;
267 };
268
269 struct HashTraits {
270 static int GetKey(const Entry* e) { return e->key; }
271 static uint32_t Hash(int key) { return key; }
272 };
273
274 SkTHashTable<Entry*, int, HashTraits> table;
275
276 REPORTER_ASSERT(r, nullptr == table.findOrNull(7));
277
278 Entry seven = { 7, 24 };
279 table.set(&seven);
280
281 REPORTER_ASSERT(r, &seven == table.findOrNull(7));
282 }
283
DEF_TEST(HashTableGrowsAndShrinks,r)284 DEF_TEST(HashTableGrowsAndShrinks, r) {
285 SkTHashSet<int> s;
286 auto check_count_cap = [&](int count, int cap) {
287 REPORTER_ASSERT(r, s.count() == count);
288 REPORTER_ASSERT(r, s.approxBytesUsed() == (sizeof(int) + sizeof(uint32_t)) * cap);
289 };
290
291 // Add and remove some elements to test basic growth and shrink patterns.
292 check_count_cap(0,0);
293 s.add(1); check_count_cap(1,4);
294 s.add(2); check_count_cap(2,4);
295 s.add(3); check_count_cap(3,4);
296 s.add(4); check_count_cap(4,8);
297
298 s.remove(4); check_count_cap(3,8);
299 s.remove(3); check_count_cap(2,4);
300 s.remove(2); check_count_cap(1,4);
301 s.remove(1); check_count_cap(0,4);
302
303 s.add(1); check_count_cap(1,4);
304 s.add(2); check_count_cap(2,4);
305 s.add(3); check_count_cap(3,4);
306 s.add(4); check_count_cap(4,8);
307
308 // Add and remove single elements repeatedly to test hysteresis
309 // avoids reallocating these small tables all the time.
310 for (int i = 0; i < 10; i++) {
311 s. add(5); check_count_cap(5,8);
312 s.remove(5); check_count_cap(4,8);
313 }
314
315 s.remove(4); check_count_cap(3,8);
316 for (int i = 0; i < 10; i++) {
317 s. add(4); check_count_cap(4,8);
318 s.remove(4); check_count_cap(3,8);
319 }
320
321 s.remove(3); check_count_cap(2,4);
322 for (int i = 0; i < 10; i++) {
323 s. add(4); check_count_cap(3,4);
324 s.remove(4); check_count_cap(2,4);
325 }
326
327 s.remove(2); check_count_cap(1,4);
328 for (int i = 0; i < 10; i++) {
329 s. add(2); check_count_cap(2,4);
330 s.remove(2); check_count_cap(1,4);
331 }
332 }
333