Speed up GrResourceCache add and lookup by using TDynamicHash

include/core/SkTInternalLList.h

Index: include/core/SkTInternalLList.h
diff --git a/include/core/SkTInternalLList.h b/include/core/SkTInternalLList.h
index a6b6f153530796097c1f92a7294220f2209bd481..7a89dd63ce5d477b4329743f9a0d1257dfb5268e 100644
--- a/include/core/SkTInternalLList.h
+++ b/include/core/SkTInternalLList.h
@@ -29,16 +29,60 @@ template <typename T> class SkPtrWrapper {
  * placed in the private section of any class that will be stored in a double linked list.
  */
 #define SK_DECLARE_INTERNAL_LLIST_INTERFACE(ClassName)              \
-    friend class SkTInternalLList<ClassName>;                       \
+    friend class SkTInternalLListDefaultExtractor<ClassName>;       \

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

I'm somewhat worried about the general design of GrResourceCache if we're forced
to shove its elements into three separate intrusive linked lists.  That's hard
to think about.  I'm not outright opposed to these changes here, but it does
smell.  Any thoughts on how to not do this?

     /* back pointer to the owning list - for debugging */           \
     SkDEBUGCODE(SkPtrWrapper<SkTInternalLList<ClassName> > fList;)  \
     SkPtrWrapper<ClassName> fPrev;                                  \
-    SkPtrWrapper<ClassName> fNext
+    SkPtrWrapper<ClassName> fNext;
+
+/**
+ * This macro creates the members for storing the instance to a specific, named linked list. It
+ * should be placed in the public section of any class that will be stored in a double linked
+ * list. Classes that use this macro need to use corresponding _DATA macro below.
+ */
+#define SK_DECLARE_NAMED_INTERNAL_LLIST_INTERFACE(T, Name)         \
+    struct InternalLListExtractor##Name {                          \
+        typedef SkTInternalLList<T, InternalLListExtractor##Name > ListType; \
+        static SkPtrWrapper<T>& Prev(T* o) { return o->fPrev##Name; } \
+        static SkPtrWrapper<T>& Next(T* o) { return o->fNext##Name; } \
+        SkDEBUGCODE(static SkPtrWrapper<ListType>& List(T* o) { return o->fList##Name; }) \
+        SkDEBUGCODE(static const ListType* List(const T* o) { return o->fList##Name; }) \
+    };                                                             \
+    friend class InternalLListExtractor##Name;
+
+/**
+ * This macro creates the member variables for storing the instance to a specific, named linked
+ * list. It should be placed in the private section of the class.
+ */
+#define SK_DECLARE_NAMED_INTERNAL_LLIST_INTERFACE_DATA(T, Name)    \
+    SkPtrWrapper<T> fPrev##Name;                                   \
+    SkPtrWrapper<T> fNext##Name;                                   \
+    SkDEBUGCODE(SkPtrWrapper<InternalLListExtractor##Name::ListType> fList##Name;)
+
+/**
+ * This macro creates the member variable and short-cut typedefs for a specific, named linked list.
+ * This should be placed in the class declaration or code that creates the named linked list.
+ */
+#define SK_DECLARE_NAMED_INTERNAL_LLIST(T, Name, VarName)          \
+    typedef SkTInternalLList<T, T::InternalLListExtractor##Name> Name##InternalLListType; \
+    Name##InternalLListType VarName;
+
+template <class T, class E> class SkTInternalLList;
+
+template<typename T>
+struct SkTInternalLListDefaultExtractor {
+    typedef SkTInternalLList<T, SkTInternalLListDefaultExtractor<T> > ListType;
+    static SkPtrWrapper<T>& Prev(T* o) { return o->fPrev; }
+    static SkPtrWrapper<T>& Next(T* o) { return o->fNext; }
+    SkDEBUGCODE(static SkPtrWrapper<ListType>& List(T* o) { return o->fList; })
+    SkDEBUGCODE(static const ListType* List(const T* o) { return o->fList; })
+};
 
 /**
  * This class implements a templated internal doubly linked list data structure.
  */
-template <class T> class SkTInternalLList : public SkNoncopyable {
+template <class T, class E = SkTInternalLListDefaultExtractor<T> >
+class SkTInternalLList : public SkNoncopyable {
 public:
     SkTInternalLList()
         : fHead(NULL)
@@ -49,36 +93,36 @@ public:
         SkASSERT(NULL != fHead && NULL != fTail);
         SkASSERT(this->isInList(entry));
 
-        T* prev = entry->fPrev;
-        T* next = entry->fNext;
+        T* prev = E::Prev(entry);
+        T* next = E::Next(entry);
 
         if (NULL != prev) {
-            prev->fNext = next;
+            E::Next(prev) = next;
         } else {
             fHead = next;
         }
         if (NULL != next) {
-            next->fPrev = prev;
+            E::Prev(next) = prev;
         } else {
             fTail = prev;
         }
 
-        entry->fPrev = NULL;
-        entry->fNext = NULL;
+        E::Prev(entry) = NULL;
+        E::Next(entry) = NULL;
 
 #ifdef SK_DEBUG
-        entry->fList = NULL;
+        E::List(entry) = NULL;
 #endif
     }
 
     void addToHead(T* entry) {
-        SkASSERT(NULL == entry->fPrev && NULL == entry->fNext);
-        SkASSERT(NULL == entry->fList);
+        SkASSERT(NULL == E::Prev(entry) && NULL == E::Next(entry));
+        SkASSERT(NULL == E::List(entry));
 
-        entry->fPrev = NULL;
-        entry->fNext = fHead;
+        E::Prev(entry) = NULL;
+        E::Next(entry) = fHead;
         if (NULL != fHead) {
-            fHead->fPrev = entry;
+            E::Prev(fHead) = entry;
         }
         fHead = entry;
         if (NULL == fTail) {
@@ -86,18 +130,18 @@ public:
         }
 
 #ifdef SK_DEBUG
-        entry->fList = this;
+        E::List(entry) = this;
 #endif
     }
 
     void addToTail(T* entry) {
-        SkASSERT(NULL == entry->fPrev && NULL == entry->fNext);
-        SkASSERT(NULL == entry->fList);
+        SkASSERT(NULL == E::Prev(entry) && NULL == E::Next(entry));
+        SkASSERT(NULL == E::List(entry));
 
-        entry->fPrev = fTail;
-        entry->fNext = NULL;
+        E::Prev(entry) = fTail;
+        E::Next(entry) = NULL;
         if (NULL != fTail) {
-            fTail->fNext = entry;
+            E::Next(fTail) = entry;
         }
         fTail = entry;
         if (NULL == fHead) {
@@ -105,7 +149,7 @@ public:
         }
 
 #ifdef SK_DEBUG
-        entry->fList = this;
+        E::List(entry) = this;
 #endif
     }
 
@@ -123,18 +167,18 @@ public:
         }
 
         SkASSERT(this->isInList(existingEntry));
-        newEntry->fNext = existingEntry;
-        T* prev = existingEntry->fPrev;
-        existingEntry->fPrev = newEntry;
-        newEntry->fPrev = prev;
+        E::Next(newEntry) = existingEntry;
+        T* prev = E::Prev(existingEntry);
+        E::Prev(existingEntry) = newEntry;
+        E::Prev(newEntry) = prev;
         if (NULL == prev) {
             SkASSERT(fHead == existingEntry);
             fHead = newEntry;
         } else {
-            prev->fNext = newEntry;
+            E::Next(prev) = newEntry;
         }
 #ifdef SK_DEBUG
-        newEntry->fList = this;
+        E::List(newEntry) = this;
 #endif
     }
 
@@ -152,18 +196,18 @@ public:
         }
 
         SkASSERT(this->isInList(existingEntry));
-        newEntry->fPrev = existingEntry;
-        T* next = existingEntry->fNext;
-        existingEntry->fNext = newEntry;
-        newEntry->fNext = next;
+        E::Prev(newEntry) = existingEntry;
+        T* next = E::Next(existingEntry);
+        E::Next(existingEntry) = newEntry;
+        E::Next(newEntry) = next;
         if (NULL == next) {
             SkASSERT(fTail == existingEntry);
             fTail = newEntry;
         } else {
-            next->fPrev = newEntry;
+            E::Prev(next) = newEntry;
         }
 #ifdef SK_DEBUG
-        newEntry->fList = this;
+        E::List(newEntry) = this;
 #endif
     }
 
@@ -206,7 +250,7 @@ public:
                 return NULL;
             }
 
-            fCurr = fCurr->fNext;
+            fCurr = E::Next(fCurr);
             return fCurr;
         }
 
@@ -215,7 +259,7 @@ public:
                 return NULL;
             }
 
-            fCurr = fCurr->fPrev;
+            fCurr = E::Prev(fCurr);
             return fCurr;
         }
 
@@ -223,21 +267,32 @@ public:
         T* fCurr;
     };
 
+    template <typename PredicateFunctor>
+    T* find(const PredicateFunctor& f) {

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

I'm still skeptical of adding a method like this.  There's nothing here that the
caller can't do itself just as efficiently through the list's public API.  This
sort of filtered lookup is unique to GrResourceCache, so it really should stay
there as much as possible.

+        Iter iter;
+        for (T* item = iter.init(*this, Iter::kHead_IterStart); NULL != item; item = iter.next()) {
+            if (f(item)) {
+                return item;
+            }
+        }
+        return NULL;
+    }
+
 #ifdef SK_DEBUG
     void validate() const {
         SkASSERT(!fHead == !fTail);
         Iter iter;
-        for (T* item = iter.init(*this, Iter::kHead_IterStart); NULL != (item = iter.next()); ) {
+        for (T* item = iter.init(*this, Iter::kHead_IterStart); NULL != item;  item = iter.next()) {
             SkASSERT(this->isInList(item));
-            if (NULL == item->fPrev) {
+            if (NULL == E::Prev(item)) {
                 SkASSERT(fHead == item);
             } else {
-                SkASSERT(item->fPrev->fNext == item);
+                SkASSERT(E::Next(E::Prev(item)) == item);
             }
-            if (NULL == item->fNext) {
+            if (NULL == E::Next(item)) {
                 SkASSERT(fTail == item);
             } else {
-                SkASSERT(item->fNext->fPrev == item);
+                SkASSERT(E::Prev(E::Next(item)) == item);
             }
         }
     }
@@ -247,7 +302,7 @@ public:
      * list.
      */
     bool isInList(const T* entry) const {
-        return entry->fList == this;
+        return E::List(entry) == this;
     }
 
     /**
@@ -255,7 +310,7 @@ public:
      */
     int countEntries() const {
         int count = 0;
-        for (T* entry = fHead; NULL != entry; entry = entry->fNext) {
+        for (T* entry = fHead; NULL != entry; entry = E::Next(entry)) {
             ++count;
         }
         return count;