Speed up GrResourceCache add and lookup by using TDynamicHash

tests/DynamicHashTest.cpp

 /*
  * Copyright 2013 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "Test.h"
+#include "SkRandom.h"
 #include "SkTDynamicHash.h"
 
 namespace {
 
 struct Entry {
     int key;
     double value;
 };
 
 const int& GetKey(const Entry& entry) { return entry.key; }
@@ skipping 97 matching lines @@
     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);
+    hash.remove(&a);
     // 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);
 }
 
+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"
 DEFINE_TESTCLASS("DynamicHash", DynamicHashTestClass, test_dynamic_hash);