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