DynamicHashTest.cpp revision f7834221ac5342a3446b9b299398ea3ff7976946 
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
11namespace {
12
13struct Entry {
14    int key;
15    double value;
16
17    static const int& GetKey(const Entry& entry) { return entry.key; }
18    static uint32_t Hash(const int& key) { return key; }
19};
20
21
22class Hash : public SkTDynamicHash<Entry, int> {
23public:
24    Hash() : INHERITED() {}
25
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:
31    typedef SkTDynamicHash<Entry, int> INHERITED;
32};
33
34}  // namespace
35
36#define ASSERT(x) REPORTER_ASSERT(reporter, x)
37
38DEF_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
66DEF_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
78DEF_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) != NULL);
104    ASSERT(hash.find(1)->value == 2.0);
105    ASSERT(hash.find(5) != NULL);
106    ASSERT(hash.find(5)->value == 3.0);
107
108    // These aren't in the hash.
109    ASSERT(hash.find(2) == NULL);
110    ASSERT(hash.find(9) == NULL);
111}
112
113DEF_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) == NULL);
127    ASSERT(hash.find(5) != NULL);
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) != NULL);
134    ASSERT(hash.find(9)->value == 4.0);
135    ASSERT(hash.find(5) != NULL);
136    ASSERT(hash.find(5)->value == 3.0);
137}
138
139template<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) != NULL);
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) != NULL);
181        ++count;
182    }
183    ASSERT(2 == count);
184    ASSERT(keys[0] != keys[1]);
185}
186
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
218    ASSERT(hash.find(1) != NULL);
219    ASSERT(hash.find(2) != NULL);
220}
221
222DEF_TEST(DynamicHash_reset, reporter) {
223    TestResetOrRewind(reporter, true);
224}
225
226DEF_TEST(DynamicHash_rewind, reporter) {
227    TestResetOrRewind(reporter, false);
228}
229