revise SkTDynamicHash and add unit tests
BUG=
R=reed@google.com
Author: mtklein@google.com
Review URL: https://chromiumcodereview.appspot.com/22292004
git-svn-id: http://skia.googlecode.com/svn/trunk@10552 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/tests/DynamicHashTest.cpp b/tests/DynamicHashTest.cpp
new file mode 100644
index 0000000..e15aad5
--- /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);