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 "SkTDynamicHash.h"
+#include "SkRandom.h"
 
 namespace {
 
 struct Entry {
     int key;
     double value;
 };
 
 const int& GetKey(const Entry& entry) { return entry.key; }
 uint32_t GetHash(const int& key) { return key; }
@@ skipping 112 matching lines @@
 
     // 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_validate(skiatest::Reporter* reporter) {
+    // Test validate after construction for different initial capacitys.
+    {
+        Entry a = { 1, 2.0 };
+        Entry b = { 2, 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(1);
+            hash.validate();
+            ASSERT(hash.find(2) == &b);
+            hash.remove(2);
+            hash.validate();
+            hash.add(&a);
+            hash.validate();
+            ASSERT(hash.find(1) == &a);
+            hash.remove(1);
+            hash.remove(9);
+            hash.validate();
+        }
+    }
+
+    {
+        SkRandom rand;
+        Entry entries[3333];

[mtklein, 2013/12/03 19:02:02]

Can you just mark 3333 and 237 as arbitrary somehow?  They don't need fancy
names, as long as we know they don't really matter too much.

+        Hash hash;
+
+        for (size_t i = 0; i < SK_ARRAY_COUNT(entries); ++i) {
+            entries[i].key = rand.nextU();

[mtklein, 2013/12/03 19:02:02]

It's unlikely, but this could trigger a uniqueness assert.  Call find or use i
as the key?

+            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].key);
+            hash.validate();
+        }
+    }
+}
+
 static void test_dynamic_hash(skiatest::Reporter* reporter) {
     test_growth(reporter);
     test_add(reporter);
     test_lookup(reporter);
     test_remove(reporter);
+    test_validate(reporter);
 }
 
 #include "TestClassDef.h"
 DEFINE_TESTCLASS("DynamicHash", DynamicHashTestClass, test_dynamic_hash);