Speed up GrResourceCache add and lookup by using TDynamicHash

tests/LListTest.cpp

 /*
  * Copyright 2012 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 "SkTInternalLList.h"
 #include "SkTLList.h"
 
 class ListElement {
 public:
     ListElement(int id) : fID(id) {
     }
     bool operator== (const ListElement& other) { return fID == other.fID; }
 
 #if SK_ENABLE_INST_COUNT
     // Make the instance count available publicly.
     static int InstanceCount() { return GetInstanceCount(); }
 #endif
 
     int fID;
 
+    SK_DECLARE_NAMED_INTERNAL_LLIST_INTERFACE(ListElement, NamedList);
 private:
     SK_DECLARE_INST_COUNT_ROOT(ListElement);
     SK_DECLARE_INTERNAL_LLIST_INTERFACE(ListElement);
+
+    SK_DECLARE_NAMED_INTERNAL_LLIST_INTERFACE_DATA(ListElement, NamedList);
 };
 
 SK_DEFINE_INST_COUNT(ListElement);
 
 static void check_list(const SkTInternalLList<ListElement>& list,
                        skiatest::Reporter* reporter,
                        bool empty,
                        int numElements,
                        bool in0, bool in1, bool in2, bool in3,
                        ListElement elements[4]) {
@@ skipping 75 matching lines @@
 
     list.addBefore(&elements[2], &elements[3]);
     check_list(list, reporter, false, 4, true, true, true, true, elements);
 
     cur = iter.init(list, Iter::kHead_IterStart);
     for (int i = 0; NULL != cur; ++i, cur = iter.next()) {
         REPORTER_ASSERT(reporter, cur->fID == i);
     }
 }
 
+static void TestNamedTInternalLList(skiatest::Reporter* reporter) {
+    SK_DECLARE_NAMED_INTERNAL_LLIST(ListElement, NamedList, list);
+    ListElement elements[4] = {
+        ListElement(0),
+        ListElement(1),
+        ListElement(2),
+        ListElement(3),
+    };
+    list.addToHead(&elements[0]);
+    list.addToHead(&elements[1]);
+    list.addToHead(&elements[2]);
+    list.addToHead(&elements[3]);
+
+
+    NamedListInternalLListType::Iter iter;
+    ListElement* e = iter.init(list, NamedListInternalLListType::Iter::kTail_IterStart);
+    REPORTER_ASSERT(reporter, e == &elements[0]);
+    REPORTER_ASSERT(reporter, iter.prev() == &elements[1]);
+    REPORTER_ASSERT(reporter, iter.prev() == &elements[2]);
+    REPORTER_ASSERT(reporter, iter.prev() == &elements[3]);
+    REPORTER_ASSERT(reporter, iter.prev() == NULL);
+}
+
+struct ElementFinder {
+    ElementFinder(int id)
+        : fID(id) {
+    }
+
+    bool operator()(const ListElement* element) const {
+        return element->fID == fID;
+    }
+
+    int fID;
+};
+
+
+static void TestTInternalLListFind(skiatest::Reporter* reporter) {
+    SK_DECLARE_NAMED_INTERNAL_LLIST(ListElement, NamedList, list);
+    ListElement elements[4] = {
+        ListElement(0),
+        ListElement(1),
+        ListElement(2),
+        ListElement(3),
+    };
+    list.addToHead(&elements[0]);
+    list.addToHead(&elements[1]);
+    list.addToHead(&elements[2]);
+    list.addToHead(&elements[3]);
+
+    for (size_t i = 0; i < SK_ARRAY_COUNT(elements); ++i) {
+        REPORTER_ASSERT(reporter, &elements[i] == list.find(ElementFinder(elements[i].fID)));
+    }
+}
+
 static void TestTLList(skiatest::Reporter* reporter) {
     typedef SkTLList<ListElement> ElList;
     typedef ElList::Iter Iter;
     SkRandom random;
 
     for (int i = 1; i <= 16; i *= 2) {
 
         ElList list1(i);
         ElList list2(i);
         Iter iter1;
@@ skipping 173 matching lines @@
         }
         list1.reset();
 #if SK_ENABLE_INST_COUNT
         SkASSERT(0 == ListElement::InstanceCount());
 #endif
     }
 }
 
 static void test_llists(skiatest::Reporter* reporter) {
     TestTInternalLList(reporter);
+    TestNamedTInternalLList(reporter);
+    TestTInternalLListFind(reporter);
     TestTLList(reporter);
+
 }
 
 #include "TestClassDef.h"
 DEFINE_TESTCLASS("LList", TestLListClass, test_llists)