Speed up GrResourceCache add and lookup by using TDynamicHash

src/gpu/GrTMultiset.h

Index: src/gpu/GrTMultiset.h
diff --git a/src/gpu/GrTMultiset.h b/src/gpu/GrTMultiset.h
new file mode 100644
index 0000000000000000000000000000000000000000..d6f184bcad12595fffed7d8c2d8c09e5fc11e04c
--- /dev/null
+++ b/src/gpu/GrTMultiset.h
@@ -0,0 +1,117 @@
+
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef GrTMultiset_DEFINED
+#define GrTMultiset_DEFINED
+
+#include "GrTypes.h"
+#include "SkTDynamicHash.h"
+
+/** A set that contains pointers to instances of T. Instances can be looked up with key Key.
+ * Multiple (possibly same) values can have the same key.
+ */
+template <typename T,
+          typename Key,
+          const Key& (GetKey)(const T&),
+          uint32_t (Hash)(const Key&),
+          bool (Equal)(const T&, const Key&)>
+class GrTMultiset {

[mtklein, 2014/01/17 15:08:43]

I think I'd prefer it if this were SkTMultiMap, in src/core.  I don't mind
following up to do that rename if it's a pain.

[Kimmo Kinnunen, 2014/01/17 17:14:45]

Done.

+    struct ValueList {
+        ValueList(T* value)
+            : fValue(value),
+              fNext(NULL) {

[mtklein, 2014/01/17 15:08:43]

We generally put the ',' in front of fNext here.

In this case, I'd even just write

explicit ValueList(T* value) : fValue(value), fNext(NULL) {}

Please do add explicit.

[Kimmo Kinnunen, 2014/01/17 17:14:45]

Done.

+        }
+
+        static const Key& ListGetKey(const ValueList& e) { return GetKey(*e.fValue); }
+        static uint32_t ListHash(const Key& key) { return Hash(key); }
+        static bool ListEqual(const ValueList& a, const Key& b) {
+            return Equal(*a.fValue, b);
+        }
+        T* fValue;
+        ValueList* fNext;
+    };
+public:
+    GrTMultiset()
+        : fCount(0) {
+    }
+
+    ~GrTMultiset() {
+        SkASSERT(fCount == 0);
+        SkASSERT(fHash.count() == 0);
+    }
+
+    void insert(const Key& key, T* value) {
+        ValueList* list = fHash.find(key);
+        if (NULL != list) {
+            ValueList* newEntry = SkNEW_ARGS(ValueList, (list->fValue));
+            newEntry->fNext = list->fNext;

[mtklein, 2014/01/17 15:08:43]

Can you just add a small comment here that we always insert at position 2 in the
list?  (Have I read this correctly?)

[Kimmo Kinnunen, 2014/01/17 17:14:45]

Correct. Done.

+            list->fNext = newEntry;
+            list->fValue = value;
+        } else {
+            fHash.add(SkNEW_ARGS(ValueList, (value)));
+        }
+
+        ++fCount;
+    }
+
+    void remove(const Key& key, T* value) {

[mtklein, 2014/01/17 15:08:43]

Curious, can we write this as const T* value?  We're only using it to establish
the identity of the removed T*, right?

[Kimmo Kinnunen, 2014/01/17 17:14:45]

Done.

+        ValueList* list = fHash.find(key);

[mtklein, 2014/01/17 15:08:43]

NULL check list?  If it's safe how it's used, SkASSERT(list != NULL), otherwise
I guess just return?

[Kimmo Kinnunen, 2014/01/17 17:14:45]

Done, added an assert.

+        ValueList* prev = NULL;
+        while (list->fValue != value) {
+            prev = list;
+            list = list->fNext;
+        }
+
+        if (NULL != list->fNext) {
+            ValueList* next = list->fNext;
+            list->fValue = next->fValue;
+            list->fNext = next->fNext;
+            delete next;

[mtklein, 2014/01/17 15:08:43]

Please use SkDELETE for all these.  (There's no difference as far as I know, but
it's nice to balance SkNEW and SkDELETE.)

[Kimmo Kinnunen, 2014/01/17 17:14:45]

Done.

+        } else if (NULL != prev) {
+            prev->fNext = NULL;
+            delete list;
+        } else {
+            fHash.remove(key);
+            delete list;
+        }
+
+        --fCount;
+    }
+
+    T* find(const Key& key) const {
+        ValueList* list = fHash.find(key);
+        if (NULL != list) {
+            return list->fValue;
+        }
+        return NULL;
+    }
+
+    template<class FindPredicate>
+    T* find(const Key& key, const FindPredicate f) {
+        ValueList* list = fHash.find(key);
+        while (NULL != list) {
+            if (f(list->fValue)){
+                return list->fValue;
+            }
+            list = list->fNext;
+        }
+        return NULL;
+    }
+
+    int count() const { return fCount; }
+
+private:
+    SkTDynamicHash<ValueList,
+                   Key,
+                   ValueList::ListGetKey,
+                   ValueList::ListHash,
+                   ValueList::ListEqual> fHash;
+    int fCount;
+};
+
+#endif