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