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 11 namespace { 12 13 struct 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 22 class Hash : public SkTDynamicHash<Entry, int> { 23 public: 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 30 private: 31 typedef SkTDynamicHash<Entry, int> INHERITED; 32 }; 33 34 } // namespace 35 36 #define ASSERT(x) REPORTER_ASSERT(reporter, x) 37 38 DEF_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 66 DEF_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 78 DEF_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) != nullptr); 104 ASSERT(hash.find(1)->value == 2.0); 105 ASSERT(hash.find(5) != nullptr); 106 ASSERT(hash.find(5)->value == 3.0); 107 108 // These aren't in the hash. 109 ASSERT(hash.find(2) == nullptr); 110 ASSERT(hash.find(9) == nullptr); 111 } 112 113 DEF_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) == nullptr); 127 ASSERT(hash.find(5) != nullptr); 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) != nullptr); 134 ASSERT(hash.find(9)->value == 4.0); 135 ASSERT(hash.find(5) != nullptr); 136 ASSERT(hash.find(5)->value == 3.0); 137 } 138 139 template<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) != nullptr); 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) != nullptr); 181 ++count; 182 } 183 ASSERT(2 == count); 184 ASSERT(keys[0] != keys[1]); 185 } 186 187 DEF_TEST(DynamicHash_iterator, reporter) { 188 TestIter<Hash::Iter>(reporter); 189 TestIter<Hash::ConstIter>(reporter); 190 } 191 192 static 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) != nullptr); 219 ASSERT(hash.find(2) != nullptr); 220 } 221 222 DEF_TEST(DynamicHash_reset, reporter) { 223 TestResetOrRewind(reporter, true); 224 } 225 226 DEF_TEST(DynamicHash_rewind, reporter) { 227 TestResetOrRewind(reporter, false); 228 } 229
