revise SkTDynamicHash and add unit tests

tests/DynamicHashTest.cpp

Index: tests/DynamicHashTest.cpp
diff --git a/tests/DynamicHashTest.cpp b/tests/DynamicHashTest.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..e15aad584685d4619d261c84bf522d287b9aeb85
--- /dev/null
+++ b/tests/DynamicHashTest.cpp
@@ -0,0 +1,151 @@
+#include "Test.h"
+#include "SkTDynamicHash.h"
+
+namespace {
+
+struct Entry {
+    int key;
+    float value;
+
+    static const int& Key(const Entry& entry) { return entry.key; }
+    static uint32_t Hash(const int& key) { return key; }
+    static bool Equal(const Entry& entry, const int& key) { return entry.key == key; }
+};
+
+class Hash : public SkTDynamicHash<Entry, int, Entry::Key, Entry::Hash, Entry::Equal> {
+public:
+    Hash() : INHERITED() {}
+    Hash(int capacity) : INHERITED(capacity) {}
+
+    // Promote protected methods to public for this test.
+    int capacity() const { return this->INHERITED::capacity(); }
+    int countCollisions(const int& key) const { return this->INHERITED::countCollisions(key); }
+
+private:
+    typedef SkTDynamicHash<Entry, int, Entry::Key, Entry::Hash, Entry::Equal> INHERITED;
+};
+
+}  // namespace
+
+#define ASSERT(x) REPORTER_ASSERT(reporter, x)
+
+static void test_growth(skiatest::Reporter* reporter) {
+    Entry a = { 1, 2.0 };
+    Entry b = { 2, 3.0 };
+    Entry c = { 3, 4.0 };
+    Entry d = { 4, 5.0 };
+    Entry e = { 5, 6.0 };
+
+    Hash hash(0);
+    ASSERT(hash.capacity() == 1);
+
+    hash.add(&a);
+    ASSERT(hash.capacity() == 2);
+
+    hash.add(&b);
+    ASSERT(hash.capacity() == 4);
+
+    hash.add(&c);
+    ASSERT(hash.capacity() == 8);
+
+    hash.add(&d);
+    ASSERT(hash.capacity() == 8);
+
+    hash.add(&e);
+    ASSERT(hash.capacity() == 16);
+
+    ASSERT(hash.count() == 5);
+}
+
+static void test_add(skiatest::Reporter* reporter) {
+    Hash hash;
+    Entry a = { 1, 2.0 };
+    Entry b = { 2, 3.0 };
+    Entry c = { 1, 1.0 };
+
+    ASSERT(hash.count() == 0);
+    hash.add(&a);
+    ASSERT(hash.count() == 1);
+    hash.add(&b);
+    ASSERT(hash.count() == 2);
+    hash.add(&c);  // Overwrites a.
+    ASSERT(hash.count() == 2);
+
+    // Make sure the hash didn't modify the entries we inserted when overwriting.
+    ASSERT(a.value == 2.0);
+    ASSERT(b.value == 3.0);
+    ASSERT(c.value == 1.0);
+}
+
+static void test_lookup(skiatest::Reporter* reporter) {
+    Hash hash(4);
+    ASSERT(hash.capacity() == 4);
+
+    // These collide.
+    Entry a = { 1, 2.0 };
+    Entry b = { 5, 3.0 };
+
+    // Before we insert anything, nothing can collide.
+    ASSERT(hash.countCollisions(1) == 0);
+    ASSERT(hash.countCollisions(5) == 0);
+    ASSERT(hash.countCollisions(9) == 0);
+
+    // First is easy.
+    hash.add(&a);
+    ASSERT(hash.countCollisions(1) == 0);
+    ASSERT(hash.countCollisions(5) == 1);
+    ASSERT(hash.countCollisions(9) == 1);
+
+    // Second is one step away.
+    hash.add(&b);
+    ASSERT(hash.countCollisions(1) == 0);
+    ASSERT(hash.countCollisions(5) == 1);
+    ASSERT(hash.countCollisions(9) == 2);
+
+    // We can find our data right?
+    ASSERT(hash.find(1) != NULL);
+    ASSERT(hash.find(1)->value == 2.0);
+    ASSERT(hash.find(5) != NULL);
+    ASSERT(hash.find(5)->value == 3.0);
+
+    // These aren't in the hash.
+    ASSERT(hash.find(2) == NULL);
+    ASSERT(hash.find(9) == NULL);
+}
+
+static void test_remove(skiatest::Reporter* reporter) {
+    Hash hash(4);
+    ASSERT(hash.capacity() == 4);
+
+    // These collide.
+    Entry a = { 1, 2.0 };
+    Entry b = { 5, 3.0 };
+    Entry c = { 9, 4.0 };
+
+    hash.add(&a);
+    hash.add(&b);
+    hash.remove(1);
+    // a should be marked deleted, and b should still be findable.
+
+    ASSERT(hash.find(1) == NULL);
+    ASSERT(hash.find(5) != NULL);
+    ASSERT(hash.find(5)->value == 3.0);
+
+    // This will go in the same slot as 'a' did before.
+    ASSERT(hash.countCollisions(9) == 0);
+    hash.add(&c);
+    ASSERT(hash.find(9) != NULL);
+    ASSERT(hash.find(9)->value == 4.0);
+    ASSERT(hash.find(5) != NULL);
+    ASSERT(hash.find(5)->value == 3.0);
+}
+
+static void test_dynamic_hash(skiatest::Reporter* reporter) {
+    test_growth(reporter);
+    test_add(reporter);
+    test_lookup(reporter);
+    test_remove(reporter);
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("DynamicHash", DynamicHashTestClass, test_dynamic_hash);