Speed up GrResourceCache add and lookup by using TDynamicHash

include/core/SkTInternalLList.h

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef SkTInternalLList_DEFINED
 #define SkTInternalLList_DEFINED
 
@@ skipping 11 matching lines @@
   private:
       T* fPtr;
 };
 
 
 /**
  * This macro creates the member variables required by the SkTInternalLList class. It should be
  * 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)
         , fTail(NULL) {
     }
 
     void remove(T* entry) {
         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) {
             fTail = entry;
         }
 
 #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) {
             fHead = entry;
         }
 
 #ifdef SK_DEBUG
-        entry->fList = this;
+        E::List(entry) = this;
 #endif
     }
 
     /**
      * Inserts a new list entry before an existing list entry. The new entry must not already be
      * a member of this or any other list. If existingEntry is NULL then the new entry is added
      * at the tail.
      */
     void addBefore(T* newEntry, T* existingEntry) {
         SkASSERT(NULL != newEntry);
 
         if (NULL == existingEntry) {
             this->addToTail(newEntry);
             return;
         }
 
         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
     }
 
     /**
      * Inserts a new list entry after an existing list entry. The new entry must not already be
      * a member of this or any other list. If existingEntry is NULL then the new entry is added
      * at the head.
      */
     void addAfter(T* newEntry, T* existingEntry) {
         SkASSERT(NULL != newEntry);
 
         if (NULL == existingEntry) {
             this->addToHead(newEntry);
             return;
         }
 
         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
     }
 
     bool isEmpty() const {
         return NULL == fHead && NULL == fTail;
     }
 
     T* head() { return fHead; }
     T* tail() { return fTail; }
 
@@ skipping 22 matching lines @@
         T* get() { return fCurr; }
 
         /**
          * Return the next/previous element in the list or NULL if at the end.
          */
         T* next() {
             if (NULL == fCurr) {
                 return NULL;
             }
 
-            fCurr = fCurr->fNext;
+            fCurr = E::Next(fCurr);
             return fCurr;
         }
 
         T* prev() {
             if (NULL == fCurr) {
                 return NULL;
             }
 
-            fCurr = fCurr->fPrev;
+            fCurr = E::Prev(fCurr);
             return fCurr;
         }
 
     private:
         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);
             }
         }
     }
 
     /**
      * Debugging-only method that uses the list back pointer to check if 'entry' is indeed in 'this'
      * list.
      */
     bool isInList(const T* entry) const {
-        return entry->fList == this;
+        return E::List(entry) == this;
     }
 
     /**
      * Debugging-only method that laboriously counts the list entries.
      */
     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;
     }
 #endif // SK_DEBUG
 
 private:
     T* fHead;
     T* fTail;
 
     typedef SkNoncopyable INHERITED;
 };
 
 #endif