DynamicHashTest.cpp revision c9ab2b7dd8411f8a78654b237c69a5886567dfec 
1#include "Test.h"
2#include "SkTDynamicHash.h"
3
4namespace {
5
6struct Entry {
7    int key;
8    double value;
9};
10const int& GetKey(const Entry& entry) { return entry.key; }
11uint32_t GetHash(const int& key) { return key; }
12bool AreEqual(const Entry& entry, const int& key) { return entry.key == key; }
13
14
15class Hash : public SkTDynamicHash<Entry, int, GetKey, GetHash, AreEqual> {
16public:
17    Hash() : INHERITED() {}
18    Hash(int capacity) : INHERITED(capacity) {}
19
20    // Promote protected methods to public for this test.
21    int capacity() const { return this->INHERITED::capacity(); }
22    int countCollisions(const int& key) const { return this->INHERITED::countCollisions(key); }
23
24private:
25    typedef SkTDynamicHash<Entry, int, GetKey, GetHash, AreEqual> INHERITED;
26};
27
28}  // namespace
29
30#define ASSERT(x) REPORTER_ASSERT(reporter, x)
31
32static void test_growth(skiatest::Reporter* reporter) {
33    Entry a = { 1, 2.0 };
34    Entry b = { 2, 3.0 };
35    Entry c = { 3, 4.0 };
36    Entry d = { 4, 5.0 };
37    Entry e = { 5, 6.0 };
38
39    Hash hash(4);
40    ASSERT(hash.capacity() == 4);
41
42    hash.add(&a);
43    ASSERT(hash.capacity() == 4);
44
45    hash.add(&b);
46    ASSERT(hash.capacity() == 4);
47
48    hash.add(&c);
49    ASSERT(hash.capacity() == 4);
50
51    hash.add(&d);
52    ASSERT(hash.capacity() == 8);
53
54    hash.add(&e);
55    ASSERT(hash.capacity() == 8);
56
57    ASSERT(hash.count() == 5);
58}
59
60static void test_add(skiatest::Reporter* reporter) {
61    Hash hash;
62    Entry a = { 1, 2.0 };
63    Entry b = { 2, 3.0 };
64
65    ASSERT(hash.count() == 0);
66    hash.add(&a);
67    ASSERT(hash.count() == 1);
68    hash.add(&b);
69    ASSERT(hash.count() == 2);
70}
71
72static void test_lookup(skiatest::Reporter* reporter) {
73    Hash hash(4);
74    ASSERT(hash.capacity() == 4);
75
76    // These collide.
77    Entry a = { 1, 2.0 };
78    Entry b = { 5, 3.0 };
79
80    // Before we insert anything, nothing can collide.
81    ASSERT(hash.countCollisions(1) == 0);
82    ASSERT(hash.countCollisions(5) == 0);
83    ASSERT(hash.countCollisions(9) == 0);
84
85    // First is easy.
86    hash.add(&a);
87    ASSERT(hash.countCollisions(1) == 0);
88    ASSERT(hash.countCollisions(5) == 1);
89    ASSERT(hash.countCollisions(9) == 1);
90
91    // Second is one step away.
92    hash.add(&b);
93    ASSERT(hash.countCollisions(1) == 0);
94    ASSERT(hash.countCollisions(5) == 1);
95    ASSERT(hash.countCollisions(9) == 2);
96
97    // We can find our data right?
98    ASSERT(hash.find(1) != NULL);
99    ASSERT(hash.find(1)->value == 2.0);
100    ASSERT(hash.find(5) != NULL);
101    ASSERT(hash.find(5)->value == 3.0);
102
103    // These aren't in the hash.
104    ASSERT(hash.find(2) == NULL);
105    ASSERT(hash.find(9) == NULL);
106}
107
108static void test_remove(skiatest::Reporter* reporter) {
109    Hash hash(4);
110    ASSERT(hash.capacity() == 4);
111
112    // These collide.
113    Entry a = { 1, 2.0 };
114    Entry b = { 5, 3.0 };
115    Entry c = { 9, 4.0 };
116
117    hash.add(&a);
118    hash.add(&b);
119    hash.remove(1);
120    // a should be marked deleted, and b should still be findable.
121
122    ASSERT(hash.find(1) == NULL);
123    ASSERT(hash.find(5) != NULL);
124    ASSERT(hash.find(5)->value == 3.0);
125
126    // This will go in the same slot as 'a' did before.
127    ASSERT(hash.countCollisions(9) == 0);
128    hash.add(&c);
129    ASSERT(hash.find(9) != NULL);
130    ASSERT(hash.find(9)->value == 4.0);
131    ASSERT(hash.find(5) != NULL);
132    ASSERT(hash.find(5)->value == 3.0);
133}
134
135static void test_dynamic_hash(skiatest::Reporter* reporter) {
136    test_growth(reporter);
137    test_add(reporter);
138    test_lookup(reporter);
139    test_remove(reporter);
140}
141
142#include "TestClassDef.h"
143DEFINE_TESTCLASS("DynamicHash", DynamicHashTestClass, test_dynamic_hash);
144