Speed up GrResourceCache add and lookup by using TDynamicHash

tests/DynamicHashTest.cpp

Index: tests/DynamicHashTest.cpp
diff --git a/tests/DynamicHashTest.cpp b/tests/DynamicHashTest.cpp
index f502dbae70287142449b8c1cd8ae5a438f6f354a..5621fa96b2c0770abcc6c840bb029e1b60cbbb22 100644
--- a/tests/DynamicHashTest.cpp
+++ b/tests/DynamicHashTest.cpp
@@ -6,6 +6,7 @@
  */
 
 #include "Test.h"
+#include "SkRandom.h"
 #include "SkTDynamicHash.h"
 
 namespace {
@@ -123,7 +124,7 @@ static void test_remove(skiatest::Reporter* reporter) {
 
     hash.add(&a);
     hash.add(&b);
-    hash.remove(1);
+    hash.remove(&a);
     // a should be marked deleted, and b should still be findable.
 
     ASSERT(hash.find(1) == NULL);
@@ -139,11 +140,100 @@ static void test_remove(skiatest::Reporter* reporter) {
     ASSERT(hash.find(5)->value == 3.0);
 }
 
+struct MatchInstance {
+    MatchInstance(Entry* toFind) : fToFind(toFind) { }
+    bool operator()(const Entry* v) const { return v == fToFind; }
+    Entry* fToFind;
+};
+
+static void test_multiple_same_keys(skiatest::Reporter* reporter) {
+    Hash hash(4);
+    ASSERT(hash.capacity() == 4);
+
+    Entry a = { 1, 2.0 };
+    Entry b = { 1, 3.0 };
+    Entry c = { 9, 4.0 };
+
+    hash.add(&a);
+    hash.add(&b);
+    hash.remove(&a);
+    // a should be marked deleted, and b should still be findable.
+
+    ASSERT(hash.find(1)->value == 3.0);
+
+    hash.add(&c);
+    ASSERT(hash.find(9) != NULL);
+    ASSERT(hash.find(9)->value == 4.0);
+    ASSERT(hash.find(1)->value == 3.0);
+
+    ASSERT(hash.find(1, MatchInstance(&a)) == NULL);
+    hash.add(&a);
+    ASSERT(hash.find(1, MatchInstance(&a))->value == 2.0);
+    ASSERT(hash.find(1, MatchInstance(&b))->value == 3.0);
+}
+
+static void test_validate(skiatest::Reporter* reporter) {
+    // Test validate after construction for different initial capacitys.
+    {
+        Entry a = { 1, 2.0 };
+        Entry b = { 1, 3.0 };
+        Entry c = { 9, 4.0 };
+
+        for (int i = 0; i < 77; ++i) {
+            Hash hash(i);
+            hash.validate();
+
+            hash.add(&a);
+            hash.validate();
+            hash.add(&b);
+            hash.validate();
+            hash.add(&c);
+            hash.validate();
+
+            ASSERT(hash.find(1) != NULL);
+            ASSERT(hash.find(9) != NULL);
+            hash.remove(&a);
+            hash.validate();
+            ASSERT(hash.find(1) == &b);
+            hash.remove(&b);
+            hash.validate();
+            hash.add(&a);
+            hash.validate();
+            ASSERT(hash.find(1) == &a);
+            hash.remove(&a);
+            hash.remove(&c);
+            hash.validate();
+        }
+    }
+
+    {
+        SkRandom rand;
+        Entry entries[3333];
+        Hash hash;
+
+        for (size_t i = 0; i < SK_ARRAY_COUNT(entries); ++i) {
+            entries[i].key = rand.nextU();
+            entries[i].value = rand.nextF();
+            hash.add(&entries[i]);
+        }
+
+        hash.validate();
+
+        for (size_t i = 0; i < SK_ARRAY_COUNT(entries); i += 237) {
+            ASSERT(hash.find(entries[i].key) != NULL);
+            hash.remove(&entries[i]);
+            hash.validate();
+        }
+    }
+}
+
 static void test_dynamic_hash(skiatest::Reporter* reporter) {
     test_growth(reporter);
     test_add(reporter);
     test_lookup(reporter);
     test_remove(reporter);
+    test_multiple_same_keys(reporter);
+    test_validate(reporter);
 }
 
 #include "TestClassDef.h"