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 "include/core/SkTypes.h" 9 #include "src/core/SkTDynamicHash.h" 10 #include "tests/Test.h" 11 12 #include <cstring> 13 14 namespace { 15 16 struct Entry { 17 int key; 18 double value; 19 GetKey__anon7878c6ca0111::Entry20 static const int& GetKey(const Entry& entry) { return entry.key; } Hash__anon7878c6ca0111::Entry21 static uint32_t Hash(const int& key) { return key; } 22 }; 23 24 25 class Hash : public SkTDynamicHash<Entry, int> { 26 public: Hash()27 Hash() : INHERITED() {} 28 29 // Promote protected methods to public for this test. capacity() const30 int capacity() const { return this->INHERITED::capacity(); } countCollisions(const int & key) const31 int countCollisions(const int& key) const { return this->INHERITED::countCollisions(key); } 32 33 private: 34 typedef SkTDynamicHash<Entry, int> INHERITED; 35 }; 36 37 } // namespace 38 39 #define ASSERT(x) REPORTER_ASSERT(reporter, x) 40 DEF_TEST(DynamicHash_growth,reporter)41 DEF_TEST(DynamicHash_growth, reporter) { 42 Entry a = { 1, 2.0 }; 43 Entry b = { 2, 3.0 }; 44 Entry c = { 3, 4.0 }; 45 Entry d = { 4, 5.0 }; 46 Entry e = { 5, 6.0 }; 47 48 Hash hash; 49 ASSERT(hash.capacity() == 0); 50 51 hash.add(&a); 52 ASSERT(hash.capacity() == 4); 53 54 hash.add(&b); 55 ASSERT(hash.capacity() == 4); 56 57 hash.add(&c); 58 ASSERT(hash.capacity() == 4); 59 60 hash.add(&d); 61 ASSERT(hash.capacity() == 8); 62 63 hash.add(&e); 64 ASSERT(hash.capacity() == 8); 65 66 ASSERT(hash.count() == 5); 67 } 68 DEF_TEST(DynamicHash_growth_bounded,reporter)69 DEF_TEST(DynamicHash_growth_bounded, reporter) { 70 Entry a = { 1, 2.0 }; 71 Entry b = { 2, 3.0 }; 72 Entry c = { 3, 4.0 }; 73 Entry d = { 4, 5.0 }; 74 Entry e = { 5, 6.0 }; 75 76 Hash hash; 77 ASSERT(hash.capacity() == 0); 78 79 hash.add(&a); 80 ASSERT(hash.capacity() == 4); 81 82 hash.remove(a.key); 83 hash.add(&b); 84 ASSERT(hash.capacity() == 4); 85 86 hash.remove(b.key); 87 hash.add(&c); 88 ASSERT(hash.capacity() == 4); 89 90 hash.remove(c.key); 91 hash.add(&d); 92 ASSERT(hash.capacity() == 4); 93 94 hash.remove(d.key); 95 hash.add(&e); 96 ASSERT(hash.capacity() == 4); 97 98 ASSERT(hash.count() == 1); 99 } 100 DEF_TEST(DynamicHash_add,reporter)101 DEF_TEST(DynamicHash_add, reporter) { 102 Hash hash; 103 Entry a = { 1, 2.0 }; 104 Entry b = { 2, 3.0 }; 105 106 ASSERT(hash.count() == 0); 107 hash.add(&a); 108 ASSERT(hash.count() == 1); 109 hash.add(&b); 110 ASSERT(hash.count() == 2); 111 } 112 DEF_TEST(DynamicHash_lookup,reporter)113 DEF_TEST(DynamicHash_lookup, reporter) { 114 Hash hash; 115 116 // These collide. 117 Entry a = { 1, 2.0 }; 118 Entry b = { 5, 3.0 }; 119 120 // Before we insert anything, nothing can collide. 121 ASSERT(hash.countCollisions(1) == 0); 122 ASSERT(hash.countCollisions(5) == 0); 123 ASSERT(hash.countCollisions(9) == 0); 124 125 // First is easy. 126 hash.add(&a); 127 ASSERT(hash.countCollisions(1) == 0); 128 ASSERT(hash.countCollisions(5) == 1); 129 ASSERT(hash.countCollisions(9) == 1); 130 131 // Second is one step away. 132 hash.add(&b); 133 ASSERT(hash.countCollisions(1) == 0); 134 ASSERT(hash.countCollisions(5) == 1); 135 ASSERT(hash.countCollisions(9) == 2); 136 137 // We can find our data right? 138 ASSERT(hash.find(1) != nullptr); 139 ASSERT(hash.find(1)->value == 2.0); 140 ASSERT(hash.find(5) != nullptr); 141 ASSERT(hash.find(5)->value == 3.0); 142 143 // These aren't in the hash. 144 ASSERT(hash.find(2) == nullptr); 145 ASSERT(hash.find(9) == nullptr); 146 } 147 DEF_TEST(DynamicHash_remove,reporter)148 DEF_TEST(DynamicHash_remove, reporter) { 149 Hash hash; 150 151 // These collide. 152 Entry a = { 1, 2.0 }; 153 Entry b = { 5, 3.0 }; 154 Entry c = { 9, 4.0 }; 155 156 hash.add(&a); 157 hash.add(&b); 158 hash.remove(1); 159 // a should be marked deleted, and b should still be findable. 160 161 ASSERT(hash.find(1) == nullptr); 162 ASSERT(hash.find(5) != nullptr); 163 ASSERT(hash.find(5)->value == 3.0); 164 165 // This will go in the same slot as 'a' did before. 166 ASSERT(hash.countCollisions(9) == 0); 167 hash.add(&c); 168 ASSERT(hash.find(9) != nullptr); 169 ASSERT(hash.find(9)->value == 4.0); 170 ASSERT(hash.find(5) != nullptr); 171 ASSERT(hash.find(5)->value == 3.0); 172 } 173 TestIter(skiatest::Reporter * reporter)174 template<typename T> static void TestIter(skiatest::Reporter* reporter) { 175 Hash hash; 176 177 int count = 0; 178 // this should fall out of loop immediately 179 for (T iter(&hash); !iter.done(); ++iter) { 180 ++count; 181 } 182 ASSERT(0 == count); 183 184 // These collide. 185 Entry a = { 1, 2.0 }; 186 Entry b = { 5, 3.0 }; 187 Entry c = { 9, 4.0 }; 188 189 hash.add(&a); 190 hash.add(&b); 191 hash.add(&c); 192 193 // should see all 3 unique keys when iterating over hash 194 count = 0; 195 int keys[3] = {0, 0, 0}; 196 for (T iter(&hash); !iter.done(); ++iter) { 197 int key = (*iter).key; 198 keys[count] = key; 199 ASSERT(hash.find(key) != nullptr); 200 ++count; 201 } 202 ASSERT(3 == count); 203 ASSERT(keys[0] != keys[1]); 204 ASSERT(keys[0] != keys[2]); 205 ASSERT(keys[1] != keys[2]); 206 207 // should see 2 unique keys when iterating over hash that aren't 1 208 hash.remove(1); 209 count = 0; 210 memset(keys, 0, sizeof(keys)); 211 for (T iter(&hash); !iter.done(); ++iter) { 212 int key = (*iter).key; 213 keys[count] = key; 214 ASSERT(key != 1); 215 ASSERT(hash.find(key) != nullptr); 216 ++count; 217 } 218 ASSERT(2 == count); 219 ASSERT(keys[0] != keys[1]); 220 } 221 DEF_TEST(DynamicHash_iterator,reporter)222 DEF_TEST(DynamicHash_iterator, reporter) { 223 TestIter<Hash::Iter>(reporter); 224 TestIter<Hash::ConstIter>(reporter); 225 } 226 TestResetOrRewind(skiatest::Reporter * reporter,bool testReset)227 static void TestResetOrRewind(skiatest::Reporter* reporter, bool testReset) { 228 Hash hash; 229 Entry a = { 1, 2.0 }; 230 Entry b = { 2, 3.0 }; 231 232 ASSERT(hash.capacity() == 0); 233 hash.add(&a); 234 hash.add(&b); 235 ASSERT(hash.count() == 2); 236 ASSERT(hash.capacity() == 4); 237 238 if (testReset) { 239 hash.reset(); 240 ASSERT(hash.capacity() == 0); 241 } else { 242 hash.rewind(); 243 ASSERT(hash.capacity() == 4); 244 } 245 ASSERT(hash.count() == 0); 246 247 // make sure things still work 248 hash.add(&a); 249 hash.add(&b); 250 ASSERT(hash.count() == 2); 251 ASSERT(hash.capacity() == 4); 252 253 ASSERT(hash.find(1) != nullptr); 254 ASSERT(hash.find(2) != nullptr); 255 } 256 DEF_TEST(DynamicHash_reset,reporter)257 DEF_TEST(DynamicHash_reset, reporter) { 258 TestResetOrRewind(reporter, true); 259 } 260 DEF_TEST(DynamicHash_rewind,reporter)261 DEF_TEST(DynamicHash_rewind, reporter) { 262 TestResetOrRewind(reporter, false); 263 } 264