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