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 "SkChecksum.h"
9 #include "SkRefCnt.h"
10 #include "SkString.h"
11 #include "SkTHash.h"
12 #include "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 for (int i = 0; i < N; i++) {
48 double* found = map.find(i);
49 REPORTER_ASSERT(r, found);
50 REPORTER_ASSERT(r, *found == i*2.0);
51 }
52 for (int i = N; i < 2*N; i++) {
53 REPORTER_ASSERT(r, !map.find(i));
54 }
55
56 REPORTER_ASSERT(r, map.count() == N);
57
58 for (int i = 0; i < N/2; i++) {
59 map.remove(i);
60 }
61 for (int i = 0; i < N; i++) {
62 double* found = map.find(i);
63 REPORTER_ASSERT(r, (found == nullptr) == (i < N/2));
64 }
65 REPORTER_ASSERT(r, map.count() == N/2);
66
67 map.reset();
68 REPORTER_ASSERT(r, map.count() == 0);
69
70 {
71 // Test that we don't leave dangling values in empty slots.
72 SkTHashMap<int, sk_sp<SkRefCnt>> refMap;
73 auto ref = sk_make_sp<SkRefCnt>();
74 REPORTER_ASSERT(r, ref->unique());
75
76 refMap.set(0, ref);
77 REPORTER_ASSERT(r, refMap.count() == 1);
78 REPORTER_ASSERT(r, !ref->unique());
79
80 refMap.remove(0);
81 REPORTER_ASSERT(r, refMap.count() == 0);
82 REPORTER_ASSERT(r, ref->unique());
83 }
84 }
85
DEF_TEST(HashSet,r)86 DEF_TEST(HashSet, r) {
87 SkTHashSet<SkString> set;
88
89 set.add(SkString("Hello"));
90 set.add(SkString("World"));
91
92 REPORTER_ASSERT(r, set.count() == 2);
93
94 REPORTER_ASSERT(r, set.contains(SkString("Hello")));
95 REPORTER_ASSERT(r, set.contains(SkString("World")));
96 REPORTER_ASSERT(r, !set.contains(SkString("Goodbye")));
97
98 REPORTER_ASSERT(r, set.find(SkString("Hello")));
99 REPORTER_ASSERT(r, *set.find(SkString("Hello")) == SkString("Hello"));
100
101 set.remove(SkString("Hello"));
102 REPORTER_ASSERT(r, !set.contains(SkString("Hello")));
103 REPORTER_ASSERT(r, set.count() == 1);
104
105 set.reset();
106 REPORTER_ASSERT(r, set.count() == 0);
107 }
108
109 namespace {
110
111 class CopyCounter {
112 public:
CopyCounter()113 CopyCounter() : fID(0), fCounter(nullptr) {}
114
CopyCounter(uint32_t id,uint32_t * counter)115 CopyCounter(uint32_t id, uint32_t* counter) : fID(id), fCounter(counter) {}
116
CopyCounter(const CopyCounter & other)117 CopyCounter(const CopyCounter& other)
118 : fID(other.fID)
119 , fCounter(other.fCounter) {
120 SkASSERT(fCounter);
121 *fCounter += 1;
122 }
123
operator =(const CopyCounter & other)124 void operator=(const CopyCounter& other) {
125 fID = other.fID;
126 fCounter = other.fCounter;
127 *fCounter += 1;
128 }
129
CopyCounter(CopyCounter && other)130 CopyCounter(CopyCounter&& other) { *this = std::move(other); }
operator =(CopyCounter && other)131 void operator=(CopyCounter&& other) {
132 fID = other.fID;
133 fCounter = other.fCounter;
134 }
135
136
operator ==(const CopyCounter & other) const137 bool operator==(const CopyCounter& other) const {
138 return fID == other.fID;
139 }
140
141 private:
142 uint32_t fID;
143 uint32_t* fCounter;
144 };
145
146 struct HashCopyCounter {
operator ()__anon970392c80311::HashCopyCounter147 uint32_t operator()(const CopyCounter&) const {
148 return 0; // let them collide, what do we care?
149 }
150 };
151
152 }
153
DEF_TEST(HashSetCopyCounter,r)154 DEF_TEST(HashSetCopyCounter, r) {
155 SkTHashSet<CopyCounter, HashCopyCounter> set;
156
157 uint32_t globalCounter = 0;
158 CopyCounter copyCounter1(1, &globalCounter);
159 CopyCounter copyCounter2(2, &globalCounter);
160 REPORTER_ASSERT(r, globalCounter == 0);
161
162 set.add(copyCounter1);
163 REPORTER_ASSERT(r, globalCounter == 1);
164 REPORTER_ASSERT(r, set.contains(copyCounter1));
165 REPORTER_ASSERT(r, globalCounter == 1);
166 set.add(copyCounter1);
167 // We allow copies for same-value adds for now.
168 REPORTER_ASSERT(r, globalCounter == 2);
169
170 set.add(copyCounter2);
171 REPORTER_ASSERT(r, globalCounter == 3);
172 REPORTER_ASSERT(r, set.contains(copyCounter1));
173 REPORTER_ASSERT(r, set.contains(copyCounter2));
174 REPORTER_ASSERT(r, globalCounter == 3);
175 set.add(copyCounter1);
176 set.add(copyCounter2);
177 // We allow copies for same-value adds for now.
178 REPORTER_ASSERT(r, globalCounter == 5);
179 }
180
181
DEF_TEST(HashFindOrNull,r)182 DEF_TEST(HashFindOrNull, r) {
183 struct Entry {
184 int key = 0;
185 int val = 0;
186 };
187
188 struct HashTraits {
189 static int GetKey(const Entry* e) { return e->key; }
190 static uint32_t Hash(int key) { return key; }
191 };
192
193 SkTHashTable<Entry*, int, HashTraits> table;
194
195 REPORTER_ASSERT(r, nullptr == table.findOrNull(7));
196
197 Entry seven = { 7, 24 };
198 table.set(&seven);
199
200 REPORTER_ASSERT(r, &seven == table.findOrNull(7));
201 }
202