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