blob: 289b332c023a900ead2b41e4e5bd41421cff8434 [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"
tfarina@chromium.org8f6884a2014-01-24 20:56:26 +00009#include "Test.h"
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000010
11namespace {
12
13struct Entry {
14 int key;
mtklein@google.com0d9f5f72013-08-05 23:08:19 +000015 double value;
commit-bot@chromium.org55bd9402014-04-02 19:17:00 +000016
17 static const int& GetKey(const Entry& entry) { return entry.key; }
18 static uint32_t Hash(const int& key) { return key; }
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000019};
commit-bot@chromium.orgddf94cf2013-10-12 17:25:17 +000020
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000021
commit-bot@chromium.org55bd9402014-04-02 19:17:00 +000022class Hash : public SkTDynamicHash<Entry, int> {
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000023public:
24 Hash() : INHERITED() {}
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000025
26 // Promote protected methods to public for this test.
27 int capacity() const { return this->INHERITED::capacity(); }
28 int countCollisions(const int& key) const { return this->INHERITED::countCollisions(key); }
29
30private:
commit-bot@chromium.org55bd9402014-04-02 19:17:00 +000031 typedef SkTDynamicHash<Entry, int> INHERITED;
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000032};
33
34} // namespace
35
36#define ASSERT(x) REPORTER_ASSERT(reporter, x)
37
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +000038DEF_TEST(DynamicHash_growth, reporter) {
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000039 Entry a = { 1, 2.0 };
40 Entry b = { 2, 3.0 };
41 Entry c = { 3, 4.0 };
42 Entry d = { 4, 5.0 };
43 Entry e = { 5, 6.0 };
44
commit-bot@chromium.org7a4b9fa2014-01-13 18:28:14 +000045 Hash hash;
46 ASSERT(hash.capacity() == 0);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000047
48 hash.add(&a);
mtklein@google.comc9ab2b72013-08-12 14:51:25 +000049 ASSERT(hash.capacity() == 4);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000050
51 hash.add(&b);
52 ASSERT(hash.capacity() == 4);
53
54 hash.add(&c);
mtklein@google.comc9ab2b72013-08-12 14:51:25 +000055 ASSERT(hash.capacity() == 4);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000056
57 hash.add(&d);
58 ASSERT(hash.capacity() == 8);
59
60 hash.add(&e);
mtklein@google.comc9ab2b72013-08-12 14:51:25 +000061 ASSERT(hash.capacity() == 8);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000062
63 ASSERT(hash.count() == 5);
64}
65
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +000066DEF_TEST(DynamicHash_add, reporter) {
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000067 Hash hash;
68 Entry a = { 1, 2.0 };
69 Entry b = { 2, 3.0 };
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000070
71 ASSERT(hash.count() == 0);
72 hash.add(&a);
73 ASSERT(hash.count() == 1);
74 hash.add(&b);
75 ASSERT(hash.count() == 2);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000076}
77
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +000078DEF_TEST(DynamicHash_lookup, reporter) {
commit-bot@chromium.org7a4b9fa2014-01-13 18:28:14 +000079 Hash hash;
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +000080
81 // These collide.
82 Entry a = { 1, 2.0 };
83 Entry b = { 5, 3.0 };
84
85 // Before we insert anything, nothing can collide.
86 ASSERT(hash.countCollisions(1) == 0);
87 ASSERT(hash.countCollisions(5) == 0);
88 ASSERT(hash.countCollisions(9) == 0);
89
90 // First is easy.
91 hash.add(&a);
92 ASSERT(hash.countCollisions(1) == 0);
93 ASSERT(hash.countCollisions(5) == 1);
94 ASSERT(hash.countCollisions(9) == 1);
95
96 // Second is one step away.
97 hash.add(&b);
98 ASSERT(hash.countCollisions(1) == 0);
99 ASSERT(hash.countCollisions(5) == 1);
100 ASSERT(hash.countCollisions(9) == 2);
101
102 // We can find our data right?
halcanary96fcdcc2015-08-27 07:41:13 -0700103 ASSERT(hash.find(1) != nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000104 ASSERT(hash.find(1)->value == 2.0);
halcanary96fcdcc2015-08-27 07:41:13 -0700105 ASSERT(hash.find(5) != nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000106 ASSERT(hash.find(5)->value == 3.0);
107
108 // These aren't in the hash.
halcanary96fcdcc2015-08-27 07:41:13 -0700109 ASSERT(hash.find(2) == nullptr);
110 ASSERT(hash.find(9) == nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000111}
112
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000113DEF_TEST(DynamicHash_remove, 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 Entry c = { 9, 4.0 };
120
121 hash.add(&a);
122 hash.add(&b);
123 hash.remove(1);
124 // a should be marked deleted, and b should still be findable.
125
halcanary96fcdcc2015-08-27 07:41:13 -0700126 ASSERT(hash.find(1) == nullptr);
127 ASSERT(hash.find(5) != nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000128 ASSERT(hash.find(5)->value == 3.0);
129
130 // This will go in the same slot as 'a' did before.
131 ASSERT(hash.countCollisions(9) == 0);
132 hash.add(&c);
halcanary96fcdcc2015-08-27 07:41:13 -0700133 ASSERT(hash.find(9) != nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000134 ASSERT(hash.find(9)->value == 4.0);
halcanary96fcdcc2015-08-27 07:41:13 -0700135 ASSERT(hash.find(5) != nullptr);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000136 ASSERT(hash.find(5)->value == 3.0);
137}
138
robertphillips3d533ac2014-07-20 09:40:00 -0700139template<typename T> static void TestIter(skiatest::Reporter* reporter) {
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000140 Hash hash;
141
142 int count = 0;
143 // this should fall out of loop immediately
robertphillips3d533ac2014-07-20 09:40:00 -0700144 for (T iter(&hash); !iter.done(); ++iter) {
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000145 ++count;
146 }
147 ASSERT(0 == count);
148
149 // These collide.
150 Entry a = { 1, 2.0 };
151 Entry b = { 5, 3.0 };
152 Entry c = { 9, 4.0 };
153
154 hash.add(&a);
155 hash.add(&b);
156 hash.add(&c);
157
158 // should see all 3 unique keys when iterating over hash
159 count = 0;
160 int keys[3] = {0, 0, 0};
robertphillips3d533ac2014-07-20 09:40:00 -0700161 for (T iter(&hash); !iter.done(); ++iter) {
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000162 int key = (*iter).key;
163 keys[count] = key;
halcanary96fcdcc2015-08-27 07:41:13 -0700164 ASSERT(hash.find(key) != nullptr);
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000165 ++count;
166 }
167 ASSERT(3 == count);
168 ASSERT(keys[0] != keys[1]);
169 ASSERT(keys[0] != keys[2]);
170 ASSERT(keys[1] != keys[2]);
171
172 // should see 2 unique keys when iterating over hash that aren't 1
173 hash.remove(1);
174 count = 0;
robertphillips3d533ac2014-07-20 09:40:00 -0700175 memset(keys, 0, sizeof(keys));
176 for (T iter(&hash); !iter.done(); ++iter) {
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000177 int key = (*iter).key;
178 keys[count] = key;
179 ASSERT(key != 1);
halcanary96fcdcc2015-08-27 07:41:13 -0700180 ASSERT(hash.find(key) != nullptr);
commit-bot@chromium.org1f6cf692014-03-05 01:00:50 +0000181 ++count;
182 }
183 ASSERT(2 == count);
184 ASSERT(keys[0] != keys[1]);
commit-bot@chromium.orgf916f9e2013-08-05 22:31:20 +0000185}
robertphillips3d533ac2014-07-20 09:40:00 -0700186
187DEF_TEST(DynamicHash_iterator, reporter) {
188 TestIter<Hash::Iter>(reporter);
189 TestIter<Hash::ConstIter>(reporter);
190}
191
192static void TestResetOrRewind(skiatest::Reporter* reporter, bool testReset) {
193 Hash hash;
194 Entry a = { 1, 2.0 };
195 Entry b = { 2, 3.0 };
196
197 ASSERT(hash.capacity() == 0);
198 hash.add(&a);
199 hash.add(&b);
200 ASSERT(hash.count() == 2);
201 ASSERT(hash.capacity() == 4);
202
203 if (testReset) {
204 hash.reset();
205 ASSERT(hash.capacity() == 0);
206 } else {
207 hash.rewind();
208 ASSERT(hash.capacity() == 4);
209 }
210 ASSERT(hash.count() == 0);
211
212 // make sure things still work
213 hash.add(&a);
214 hash.add(&b);
215 ASSERT(hash.count() == 2);
216 ASSERT(hash.capacity() == 4);
217
halcanary96fcdcc2015-08-27 07:41:13 -0700218 ASSERT(hash.find(1) != nullptr);
219 ASSERT(hash.find(2) != nullptr);
robertphillips3d533ac2014-07-20 09:40:00 -0700220}
221
222DEF_TEST(DynamicHash_reset, reporter) {
223 TestResetOrRewind(reporter, true);
224}
225
226DEF_TEST(DynamicHash_rewind, reporter) {
227 TestResetOrRewind(reporter, false);
228}