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