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