1 /*
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
8 #include "SkTDynamicHash.h"
9 #include "Test.h"
10
11 namespace {
12
13 struct Entry {
14 int key;
15 double value;
16
GetKey__anon776810e40111::Entry17 static const int& GetKey(const Entry& entry) { return entry.key; }
Hash__anon776810e40111::Entry18 static uint32_t Hash(const int& key) { return key; }
19 };
20
21
22 class Hash : public SkTDynamicHash<Entry, int> {
23 public:
Hash()24 Hash() : INHERITED() {}
25
26 // Promote protected methods to public for this test.
capacity() const27 int capacity() const { return this->INHERITED::capacity(); }
countCollisions(const int & key) const28 int countCollisions(const int& key) const { return this->INHERITED::countCollisions(key); }
29
30 private:
31 typedef SkTDynamicHash<Entry, int> INHERITED;
32 };
33
34 } // namespace
35
36 #define ASSERT(x) REPORTER_ASSERT(reporter, x)
37
DEF_TEST(DynamicHash_growth,reporter)38 DEF_TEST(DynamicHash_growth, reporter) {
39 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
45 Hash hash;
46 ASSERT(hash.capacity() == 0);
47
48 hash.add(&a);
49 ASSERT(hash.capacity() == 4);
50
51 hash.add(&b);
52 ASSERT(hash.capacity() == 4);
53
54 hash.add(&c);
55 ASSERT(hash.capacity() == 4);
56
57 hash.add(&d);
58 ASSERT(hash.capacity() == 8);
59
60 hash.add(&e);
61 ASSERT(hash.capacity() == 8);
62
63 ASSERT(hash.count() == 5);
64 }
65
DEF_TEST(DynamicHash_add,reporter)66 DEF_TEST(DynamicHash_add, reporter) {
67 Hash hash;
68 Entry a = { 1, 2.0 };
69 Entry b = { 2, 3.0 };
70
71 ASSERT(hash.count() == 0);
72 hash.add(&a);
73 ASSERT(hash.count() == 1);
74 hash.add(&b);
75 ASSERT(hash.count() == 2);
76 }
77
DEF_TEST(DynamicHash_lookup,reporter)78 DEF_TEST(DynamicHash_lookup, reporter) {
79 Hash hash;
80
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?
103 ASSERT(hash.find(1) != nullptr);
104 ASSERT(hash.find(1)->value == 2.0);
105 ASSERT(hash.find(5) != nullptr);
106 ASSERT(hash.find(5)->value == 3.0);
107
108 // These aren't in the hash.
109 ASSERT(hash.find(2) == nullptr);
110 ASSERT(hash.find(9) == nullptr);
111 }
112
DEF_TEST(DynamicHash_remove,reporter)113 DEF_TEST(DynamicHash_remove, reporter) {
114 Hash hash;
115
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
126 ASSERT(hash.find(1) == nullptr);
127 ASSERT(hash.find(5) != nullptr);
128 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);
133 ASSERT(hash.find(9) != nullptr);
134 ASSERT(hash.find(9)->value == 4.0);
135 ASSERT(hash.find(5) != nullptr);
136 ASSERT(hash.find(5)->value == 3.0);
137 }
138
TestIter(skiatest::Reporter * reporter)139 template<typename T> static void TestIter(skiatest::Reporter* reporter) {
140 Hash hash;
141
142 int count = 0;
143 // this should fall out of loop immediately
144 for (T iter(&hash); !iter.done(); ++iter) {
145 ++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};
161 for (T iter(&hash); !iter.done(); ++iter) {
162 int key = (*iter).key;
163 keys[count] = key;
164 ASSERT(hash.find(key) != nullptr);
165 ++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;
175 memset(keys, 0, sizeof(keys));
176 for (T iter(&hash); !iter.done(); ++iter) {
177 int key = (*iter).key;
178 keys[count] = key;
179 ASSERT(key != 1);
180 ASSERT(hash.find(key) != nullptr);
181 ++count;
182 }
183 ASSERT(2 == count);
184 ASSERT(keys[0] != keys[1]);
185 }
186
DEF_TEST(DynamicHash_iterator,reporter)187 DEF_TEST(DynamicHash_iterator, reporter) {
188 TestIter<Hash::Iter>(reporter);
189 TestIter<Hash::ConstIter>(reporter);
190 }
191
TestResetOrRewind(skiatest::Reporter * reporter,bool testReset)192 static 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
218 ASSERT(hash.find(1) != nullptr);
219 ASSERT(hash.find(2) != nullptr);
220 }
221
DEF_TEST(DynamicHash_reset,reporter)222 DEF_TEST(DynamicHash_reset, reporter) {
223 TestResetOrRewind(reporter, true);
224 }
225
DEF_TEST(DynamicHash_rewind,reporter)226 DEF_TEST(DynamicHash_rewind, reporter) {
227 TestResetOrRewind(reporter, false);
228 }
229