blob: 62c070aca1a4eaa079959015e0601eb75fc12968 [file] [log] [blame]
commit-bot@chromium.orgddf94cf2013-10-12 17:25:17 +00001/*
2 * Copyright 2013 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
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +00008#include "SkTDynamicHash.h"
Ben Wagnerd90cd3b2018-05-22 10:48:08 -04009#include "SkTypes.h"
tfarina@chromium.org8f6884a2014-01-24 20:56:26 +000010#include "Test.h"
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000011
Ben Wagnerd90cd3b2018-05-22 10:48:08 -040012#include <cstring>
13
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000014namespace {
15
16struct Entry {
17 int key;
mtklein@google.com0d9f5f72013-08-05 23:08:19 +000018 double value;
commit-bot@chromium.org55bd9402014-04-02 19:17:00 +000019
20 static const int& GetKey(const Entry& entry) { return entry.key; }
21 static uint32_t Hash(const int& key) { return key; }
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000022};
commit-bot@chromium.orgddf94cf2013-10-12 17:25:17 +000023
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000024
commit-bot@chromium.org55bd9402014-04-02 19:17:00 +000025class Hash : public SkTDynamicHash<Entry, int> {
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000026public:
27 Hash() : INHERITED() {}
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000028
29 // Promote protected methods to public for this test.
30 int capacity() const { return this->INHERITED::capacity(); }
31 int countCollisions(const int& key) const { return this->INHERITED::countCollisions(key); }
32
33private:
commit-bot@chromium.org55bd9402014-04-02 19:17:00 +000034 typedef SkTDynamicHash<Entry, int> INHERITED;
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000035};
36
37} // namespace
38
39#define ASSERT(x) REPORTER_ASSERT(reporter, x)
40
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +000041DEF_TEST(DynamicHash_growth, reporter) {
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000042 Entry a = { 1, 2.0 };
43 Entry b = { 2, 3.0 };
44 Entry c = { 3, 4.0 };
45 Entry d = { 4, 5.0 };
46 Entry e = { 5, 6.0 };
47
commit-bot@chromium.org7a4b9fa2014-01-13 18:28:14 +000048 Hash hash;
49 ASSERT(hash.capacity() == 0);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000050
51 hash.add(&a);
mtklein@google.comc9ab2b72013-08-12 14:51:25 +000052 ASSERT(hash.capacity() == 4);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000053
54 hash.add(&b);
55 ASSERT(hash.capacity() == 4);
56
57 hash.add(&c);
mtklein@google.comc9ab2b72013-08-12 14:51:25 +000058 ASSERT(hash.capacity() == 4);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000059
60 hash.add(&d);
61 ASSERT(hash.capacity() == 8);
62
63 hash.add(&e);
mtklein@google.comc9ab2b72013-08-12 14:51:25 +000064 ASSERT(hash.capacity() == 8);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000065
66 ASSERT(hash.count() == 5);
67}
68
Florin Malitac274f8f2018-04-18 16:57:32 -040069DEF_TEST(DynamicHash_growth_bounded, reporter) {
70 Entry a = { 1, 2.0 };
71 Entry b = { 2, 3.0 };
72 Entry c = { 3, 4.0 };
73 Entry d = { 4, 5.0 };
74 Entry e = { 5, 6.0 };
75
76 Hash hash;
77 ASSERT(hash.capacity() == 0);
78
79 hash.add(&a);
80 ASSERT(hash.capacity() == 4);
81
82 hash.remove(a.key);
83 hash.add(&b);
84 ASSERT(hash.capacity() == 4);
85
86 hash.remove(b.key);
87 hash.add(&c);
88 ASSERT(hash.capacity() == 4);
89
90 hash.remove(c.key);
91 hash.add(&d);
92 ASSERT(hash.capacity() == 4);
93
94 hash.remove(d.key);
95 hash.add(&e);
96 ASSERT(hash.capacity() == 4);
97
98 ASSERT(hash.count() == 1);
99}
100
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000101DEF_TEST(DynamicHash_add, reporter) {
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000102 Hash hash;
103 Entry a = { 1, 2.0 };
104 Entry b = { 2, 3.0 };
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000105
106 ASSERT(hash.count() == 0);
107 hash.add(&a);
108 ASSERT(hash.count() == 1);
109 hash.add(&b);
110 ASSERT(hash.count() == 2);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000111}
112
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000113DEF_TEST(DynamicHash_lookup, reporter) {
commit-bot@chromium.org7a4b9fa2014-01-13 18:28:14 +0000114 Hash hash;
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000115
116 // These collide.
117 Entry a = { 1, 2.0 };
118 Entry b = { 5, 3.0 };
119
120 // Before we insert anything, nothing can collide.
121 ASSERT(hash.countCollisions(1) == 0);
122 ASSERT(hash.countCollisions(5) == 0);
123 ASSERT(hash.countCollisions(9) == 0);
124
125 // First is easy.
126 hash.add(&a);
127 ASSERT(hash.countCollisions(1) == 0);
128 ASSERT(hash.countCollisions(5) == 1);
129 ASSERT(hash.countCollisions(9) == 1);
130
131 // Second is one step away.
132 hash.add(&b);
133 ASSERT(hash.countCollisions(1) == 0);
134 ASSERT(hash.countCollisions(5) == 1);
135 ASSERT(hash.countCollisions(9) == 2);
136
137 // We can find our data right?
halcanary96fcdcc2015-08-27 07:41:13 -0700138 ASSERT(hash.find(1) != nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000139 ASSERT(hash.find(1)->value == 2.0);
halcanary96fcdcc2015-08-27 07:41:13 -0700140 ASSERT(hash.find(5) != nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000141 ASSERT(hash.find(5)->value == 3.0);
142
143 // These aren't in the hash.
halcanary96fcdcc2015-08-27 07:41:13 -0700144 ASSERT(hash.find(2) == nullptr);
145 ASSERT(hash.find(9) == nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000146}
147
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000148DEF_TEST(DynamicHash_remove, reporter) {
commit-bot@chromium.org7a4b9fa2014-01-13 18:28:14 +0000149 Hash hash;
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000150
151 // These collide.
152 Entry a = { 1, 2.0 };
153 Entry b = { 5, 3.0 };
154 Entry c = { 9, 4.0 };
155
156 hash.add(&a);
157 hash.add(&b);
158 hash.remove(1);
159 // a should be marked deleted, and b should still be findable.
160
halcanary96fcdcc2015-08-27 07:41:13 -0700161 ASSERT(hash.find(1) == nullptr);
162 ASSERT(hash.find(5) != nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000163 ASSERT(hash.find(5)->value == 3.0);
164
165 // This will go in the same slot as 'a' did before.
166 ASSERT(hash.countCollisions(9) == 0);
167 hash.add(&c);
halcanary96fcdcc2015-08-27 07:41:13 -0700168 ASSERT(hash.find(9) != nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000169 ASSERT(hash.find(9)->value == 4.0);
halcanary96fcdcc2015-08-27 07:41:13 -0700170 ASSERT(hash.find(5) != nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000171 ASSERT(hash.find(5)->value == 3.0);
172}
173
robertphillips3d533ac2014-07-20 09:40:00 -0700174template<typename T> static void TestIter(skiatest::Reporter* reporter) {
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000175 Hash hash;
176
177 int count = 0;
178 // this should fall out of loop immediately
robertphillips3d533ac2014-07-20 09:40:00 -0700179 for (T iter(&hash); !iter.done(); ++iter) {
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000180 ++count;
181 }
182 ASSERT(0 == count);
183
184 // These collide.
185 Entry a = { 1, 2.0 };
186 Entry b = { 5, 3.0 };
187 Entry c = { 9, 4.0 };
188
189 hash.add(&a);
190 hash.add(&b);
191 hash.add(&c);
192
193 // should see all 3 unique keys when iterating over hash
194 count = 0;
195 int keys[3] = {0, 0, 0};
robertphillips3d533ac2014-07-20 09:40:00 -0700196 for (T iter(&hash); !iter.done(); ++iter) {
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000197 int key = (*iter).key;
198 keys[count] = key;
halcanary96fcdcc2015-08-27 07:41:13 -0700199 ASSERT(hash.find(key) != nullptr);
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000200 ++count;
201 }
202 ASSERT(3 == count);
203 ASSERT(keys[0] != keys[1]);
204 ASSERT(keys[0] != keys[2]);
205 ASSERT(keys[1] != keys[2]);
206
207 // should see 2 unique keys when iterating over hash that aren't 1
208 hash.remove(1);
209 count = 0;
robertphillips3d533ac2014-07-20 09:40:00 -0700210 memset(keys, 0, sizeof(keys));
211 for (T iter(&hash); !iter.done(); ++iter) {
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000212 int key = (*iter).key;
213 keys[count] = key;
214 ASSERT(key != 1);
halcanary96fcdcc2015-08-27 07:41:13 -0700215 ASSERT(hash.find(key) != nullptr);
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000216 ++count;
217 }
218 ASSERT(2 == count);
219 ASSERT(keys[0] != keys[1]);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000220}
robertphillips3d533ac2014-07-20 09:40:00 -0700221
222DEF_TEST(DynamicHash_iterator, reporter) {
223 TestIter<Hash::Iter>(reporter);
224 TestIter<Hash::ConstIter>(reporter);
225}
226
227static void TestResetOrRewind(skiatest::Reporter* reporter, bool testReset) {
228 Hash hash;
229 Entry a = { 1, 2.0 };
230 Entry b = { 2, 3.0 };
231
232 ASSERT(hash.capacity() == 0);
233 hash.add(&a);
234 hash.add(&b);
235 ASSERT(hash.count() == 2);
236 ASSERT(hash.capacity() == 4);
237
238 if (testReset) {
239 hash.reset();
240 ASSERT(hash.capacity() == 0);
241 } else {
242 hash.rewind();
243 ASSERT(hash.capacity() == 4);
244 }
245 ASSERT(hash.count() == 0);
246
247 // make sure things still work
248 hash.add(&a);
249 hash.add(&b);
250 ASSERT(hash.count() == 2);
251 ASSERT(hash.capacity() == 4);
252
halcanary96fcdcc2015-08-27 07:41:13 -0700253 ASSERT(hash.find(1) != nullptr);
254 ASSERT(hash.find(2) != nullptr);
robertphillips3d533ac2014-07-20 09:40:00 -0700255}
256
257DEF_TEST(DynamicHash_reset, reporter) {
258 TestResetOrRewind(reporter, true);
259}
260
261DEF_TEST(DynamicHash_rewind, reporter) {
262 TestResetOrRewind(reporter, false);
263}