Refactor SkPtrSet

src/core/SkPtrRecorder.h

 
 /*
  * Copyright 2008 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 
 #ifndef SkPtrSet_DEFINED
 #define SkPtrSet_DEFINED
 
 #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
  *  return the same ID (since its a set). Subclasses can override inPtr()
  *  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
      *  [1...N]. Duplicate ptrs will return the same ID.
      *
      *  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.
      */
     int count() const { return fList.count(); }
 
     /**
      *  Copy the ptrs in the set into the specified array (allocated by the
      *  caller). The ptrs are assgined to the array based on their corresponding
      *  ID. e.g. array[ptr.ID - 1] = ptr.
      *
      *  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
     // detect duplicates when add() is called. Hence we need to store the
     // ptr and its ID/fIndex explicitly, since the ptr's position in the array
     // 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 {
+template <>
+inline void SkTPtrSet<SkRefCnt>::incPtr(SkRefCnt* ptr) { ptr->ref(); }
+
+template <>
+inline void SkTPtrSet<SkRefCnt>::decPtr(SkRefCnt* ptr) { ptr->unref(); }
+
+class SkRefCntSet : public SkTPtrSet<SkRefCnt> {
 public:
-    uint32_t find(T ptr) {
-        return this->INHERITED::find((void*)ptr);
+    virtual ~SkRefCntSet() {
+        this->reset();
     }
-    uint32_t add(T ptr) {
-        return this->INHERITED::add((void*)ptr);
-    }
-
-    void copyToArray(T* array) const {
-        this->INHERITED::copyToArray((void**)array);
-    }
-
-private:
-    typedef SkPtrSet INHERITED;
 };
 
-/**
- *  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*> {
-public:
-    virtual ~SkRefCntSet();
-
-protected:
-    // overrides
-    virtual void incPtr(void*);
-    virtual void decPtr(void*);
-};
-
-class SkFactorySet : public SkTPtrSet<SkFlattenable::Factory> {};
+class SkFactorySet : public SkTPtrSet<SkFlattenable::FactoryRef> {};
 
 /**
  * Similar to SkFactorySet, but only allows Factorys that have registered names.
  * Also has a function to return the next added Factory's name.
  */
 class SkNamedFactorySet : public SkRefCnt {
 public:
     SK_DECLARE_INST_COUNT(SkNamedFactorySet)
 
     SkNamedFactorySet();
@@ skipping 13 matching lines @@
     const char* getNextAddedFactoryName();
 private:
     int                    fNextAddedFactory;
     SkFactorySet           fFactorySet;
     SkTDArray<const char*> fNames;
 
     typedef SkRefCnt INHERITED;
 };
 
 #endif