Refactor SkPtrSet

src/core/SkPtrRecorder.h

Index: src/core/SkPtrRecorder.h
diff --git a/src/core/SkPtrRecorder.h b/src/core/SkPtrRecorder.h
index 06e14ab6ec03de555e41a57274deec4424906afd..7759c530b2d201f7f23c0c08c08b58cfde8c5cf6 100644
--- a/src/core/SkPtrRecorder.h
+++ b/src/core/SkPtrRecorder.h
@@ -13,6 +13,7 @@
 #include "SkRefCnt.h"
 #include "SkFlattenable.h"
 #include "SkTDArray.h"
+#include "SkTSearch.h"
 
 /**
  *  Maintains a set of ptrs, assigning each a unique ID [1...N]. Duplicate ptrs
@@ -20,15 +21,30 @@
  *  and decPtr(). incPtr() is called each time a unique ptr is added ot the
  *  set. decPtr() is called on each ptr when the set is destroyed or reset.
  */
-class SkPtrSet : public SkRefCnt {
+template <typename T>
+class SkTPtrSet : public SkRefCnt {
 public:
-    SK_DECLARE_INST_COUNT(SkPtrSet)
+    SK_DECLARE_INST_COUNT(SkTPtrSet)
 
     /**
      *  Search for the specified ptr in the set. If it is found, return its
      *  32bit ID [1..N], or if not found, return 0. Always returns 0 for NULL.
      */
-    uint32_t find(void*) const;
+    uint32_t find(T* ptr) const {
+        if (NULL == ptr) {
+            return 0;
+        }
+
+        int count = fList.count();
+        Pair pair;
+        pair.fPtr = ptr;
+
+        int index = SkTSearch<Pair, SkTPtrSet<T>::Less>(fList.begin(), count, pair, sizeof(pair));
+        if (index < 0) {
+            return 0;
+        }
+        return fList[index].fIndex;
+    }
 
     /**
      *  Add the specified ptr to the set, returning a unique 32bit ID for it
@@ -36,7 +52,26 @@ public:
      *
      *  If the ptr is NULL, it is not added, and 0 is returned.
      */
-    uint32_t add(void*);
+    uint32_t add(T* ptr) {
+        if (NULL == ptr) {
+            return 0;
+        }
+
+        int count = fList.count();
+        Pair pair;
+        pair.fPtr = ptr;
+
+        int index = SkTSearch<Pair, SkTPtrSet<T>::Less>(fList.begin(), count, pair, sizeof(pair));
+        if (index < 0) {
+            index = ~index; // turn it back into an index for insertion
+            this->incPtr(ptr);
+            pair.fIndex = count + 1;
+            *fList.insert(index) = pair;
+            return count + 1;
+        } else {
+            return fList[index].fIndex;
+        }
+    }
 
     /**
      *  Return the number of (non-null) ptrs in the set.
@@ -50,22 +85,58 @@ public:
      *
      *  incPtr() and decPtr() are not called during this operation.
      */
-    void copyToArray(void* array[]) const;
+    void copyToArray(T* array[]) const {
+        int count = fList.count();
+        if (count > 0) {
+            SkASSERT(array);
+            const Pair* p = fList.begin();
+            // p->fIndex is base-1, so we need to subtract to find its slot
+            for (int i = 0; i < count; i++) {
+                int index = p[i].fIndex - 1;
+                SkASSERT((unsigned)index < (unsigned)count);
+                array[index] = p[i].fPtr;
+            }
+        }
+    }
 
     /**
      *  Call decPtr() on each ptr in the set, and the reset the size of the set
      *  to 0.
      */
-    void reset();
+    void reset() {
+        Iter iter(*this);
+        for (T* ptr = iter.next(); NULL != ptr; ptr = iter.next()) {
+            this->decPtr(ptr);
+        }
 
-protected:
-    virtual void incPtr(void*) {}
-    virtual void decPtr(void*) {}
+        fList.reset();
+    }
+
+    class Iter {
+    public:
+        Iter(const SkTPtrSet<T>& set)
+            : fSet(set)
+            , fIndex(0) {}
+
+        T* next() {
+            if (fIndex >= fSet.fList.count()) {
+                return NULL;
+            }
+            return fSet.fList[fIndex++].fPtr;
+        }
+
+    private:
+        const SkTPtrSet<T>& fSet;
+        int                 fIndex;
+    };
 
 private:
+    void incPtr(T*) {}
+    void decPtr(T*) {}
+
     struct Pair {
-        void*       fPtr;   // never NULL
-        uint32_t    fIndex; // 1...N
+        T*       fPtr;   // never NULL
+        uint32_t fIndex; // 1...N
     };
 
     // we store the ptrs in sorted-order (using Cmp) so that we can efficiently
@@ -74,48 +145,27 @@ private:
     // is not related to its "index".
     SkTDArray<Pair>  fList;
 
-    static bool Less(const Pair& a, const Pair& b);
+    static bool Less(const Pair& a, const Pair& b) {
+        return (char*)a.fPtr < (char*)b.fPtr;
+    }
 
     typedef SkRefCnt INHERITED;
 };
 
-/**
- *  Templated wrapper for SkPtrSet, just meant to automate typecasting
- *  parameters to and from void* (which the base class expects).
- */
-template <typename T> class SkTPtrSet : public SkPtrSet {
-public:
-    uint32_t find(T ptr) {
-        return this->INHERITED::find((void*)ptr);
-    }
-    uint32_t add(T ptr) {
-        return this->INHERITED::add((void*)ptr);
-    }
+template <>
+inline void SkTPtrSet<SkRefCnt>::incPtr(SkRefCnt* ptr) { ptr->ref(); }
 
-    void copyToArray(T* array) const {
-        this->INHERITED::copyToArray((void**)array);
-    }
-
-private:
-    typedef SkPtrSet INHERITED;
-};
+template <>
+inline void SkTPtrSet<SkRefCnt>::decPtr(SkRefCnt* ptr) { ptr->unref(); }
 
-/**
- *  Subclass of SkTPtrSet specialed to call ref() and unref() when the
- *  base class's incPtr() and decPtr() are called. This makes it a valid owner
- *  of each ptr, which is released when the set is reset or destroyed.
- */
-class SkRefCntSet : public SkTPtrSet<SkRefCnt*> {
+class SkRefCntSet : public SkTPtrSet<SkRefCnt> {
 public:
-    virtual ~SkRefCntSet();
-
-protected:
-    // overrides
-    virtual void incPtr(void*);
-    virtual void decPtr(void*);
+    virtual ~SkRefCntSet() {
+        this->reset();
+    }
 };
 
-class SkFactorySet : public SkTPtrSet<SkFlattenable::Factory> {};
+class SkFactorySet : public SkTPtrSet<SkFlattenable::FactoryRef> {};
 
 /**
  * Similar to SkFactorySet, but only allows Factorys that have registered names.