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
12namespace {
13
14struct Entry {
15    int key;
16    double value;
17};
18
19const int& GetKey(const Entry& entry) { return entry.key; }
20uint32_t GetHash(const int& key) { return key; }
21bool AreEqual(const Entry& entry, const int& key) { return entry.key == key; }
22
23class Hash : public SkTDynamicHash<Entry, int, GetKey, GetHash, AreEqual> {
24public:
25    Hash() : INHERITED() {}
26    Hash(int capacity) : INHERITED(capacity) {}
27
28    // Promote protected methods to public for this test.
29    int capacity() const { return this->INHERITED::capacity(); }
30    int countCollisions(const int& key) const { return this->INHERITED::countCollisions(key); }
31
32private:
33    typedef SkTDynamicHash<Entry, int, GetKey, GetHash, AreEqual> INHERITED;
34};
35
36}  // namespace
37
38#define ASSERT(x) REPORTER_ASSERT(reporter, x)
39
40static 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
68static 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
80static 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
116static 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
143DEF_TEST(DynamicHash, reporter) {
144    test_growth(reporter);
145    test_add(reporter);
146    test_lookup(reporter);
147    test_remove(reporter);
148}
149