Add SkSTDArray.

include/core/SkTDArray.h

Index: include/core/SkTDArray.h
diff --git a/include/core/SkTDArray.h b/include/core/SkTDArray.h
index 31a11c7f3ea0c9a23e8d4f45f97a8a597873eee9..f62c3de62ff25f68041c889d37d2d7812e2fc647 100644
--- a/include/core/SkTDArray.h
+++ b/include/core/SkTDArray.h
@@ -11,43 +11,43 @@
 #define SkTDArray_DEFINED
 
 #include "SkTypes.h"
+#include "SkTemplates.h"
 
 template <typename T> class SkTDArray {
 public:
     SkTDArray() {
-        fReserve = fCount = 0;
-        fArray = NULL;
+        this->init(NULL, 0, NULL, 0);
     }
-    SkTDArray(const T src[], int count) {
-        SkASSERT(src || count == 0);
-
-        fReserve = fCount = 0;
-        fArray = NULL;
-        if (count) {
-            fArray = (T*)sk_malloc_throw(count * sizeof(T));
-            memcpy(fArray, src, sizeof(T) * count);
-            fReserve = fCount = count;
-        }
+    SkTDArray(const T src[], size_t count) {
+        this->init(src, count, NULL, 0);
     }
-    SkTDArray(const SkTDArray<T>& src) {
-        fReserve = fCount = 0;
-        fArray = NULL;
-        SkTDArray<T> tmp(src.fArray, src.fCount);
-        this->swap(tmp);
+    SkTDArray(const SkTDArray<T>& that) {
+        this->init(that.fArray, that.fCount, NULL, 0);
     }
+
     ~SkTDArray() {
-        sk_free(fArray);
+        if (fArray != fPreAllocMemArray) {
+            sk_free(fArray);
+        }
     }
 
-    SkTDArray<T>& operator=(const SkTDArray<T>& src) {
-        if (this != &src) {
-            if (src.fCount > fReserve) {
-                SkTDArray<T> tmp(src.fArray, src.fCount);
-                this->swap(tmp);
+    SkTDArray<T>& operator=(const SkTDArray<T>& that) {
+        if (this != &that) {
+            if (that.fCount > fReserve) {
+                T* oldArray = fArray;
+
+                T* newArray = (T*)sk_malloc_throw(that.fCount * sizeof(T));
+                memcpy(newArray, that.fArray, sizeof(T) * that.fCount);
+                SkTSwap(newArray, fArray);
+                fReserve = that.fCount;
+
+                if (oldArray != fPreAllocMemArray) {
+                    sk_free(oldArray);
+                }
             } else {
-                memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
-                fCount = src.fCount;
+                memcpy(fArray, that.fArray, sizeof(T) * that.fCount);
             }
+            fCount = that.fCount;
         }
         return *this;
     }
@@ -67,13 +67,18 @@ public:
         SkTSwap(fCount, other.fCount);
     }
 
-    /** Return a ptr to the array of data, to be freed with sk_free. This also
-        resets the SkTDArray to be empty.
+    /** Returns a pointer to the array of data, to be freed with sk_free.
+     *  This also resets the SkTDArray to be empty.
+     *  Note that the value returned may differ from begin().
      */
     T* detach() {
         T* array = fArray;
-        fArray = NULL;
-        fReserve = fCount = 0;
+        if (fArray == fPreAllocMemArray && fCount > 0) {
+            array = (T*)sk_malloc_throw(fCount * sizeof(T));
+            memcpy(array, fPreAllocMemArray, fCount * sizeof(T));
+        }
+        // The following line will not throw because the second parameter is 0.
+        this->init(NULL, 0, fPreAllocMemArray, fPreAllocMemArraySize);
         return array;
     }
 
@@ -102,11 +107,11 @@ public:
     const T*  end() const { return fArray ? fArray + fCount : NULL; }
 
     T&  operator[](int index) {
-        SkASSERT(index < fCount);
+        SkASSERT((size_t)index < fCount);
         return fArray[index];
     }
     const T&  operator[](int index) const {
-        SkASSERT(index < fCount);
+        SkASSERT((size_t)index < fCount);
         return fArray[index];
     }
 
@@ -118,12 +123,10 @@ public:
     }
 
     void reset() {
-        if (fArray) {
-            sk_free(fArray);
-            fArray = NULL;
-            fReserve = fCount = 0;
-        } else {
-            SkASSERT(fReserve == 0 && fCount == 0);
+        T* oldArray = fArray;
+        this->init(NULL, 0, fPreAllocMemArray, fPreAllocMemArraySize);
+        if (oldArray != fPreAllocMemArray) {
+            sk_free(oldArray);
         }
     }
 
@@ -140,20 +143,21 @@ public:
      */
     void setCount(int count) {
         SkASSERT(count >= 0);
-        if (count > fReserve) {
-            this->resizeStorageToAtLeast(count);
+        if ((size_t)count > fReserve) {
+            this->growReserveTo(count);
         }
         fCount = count;
     }
 
     void setReserve(int reserve) {
-        if (reserve > fReserve) {
-            this->resizeStorageToAtLeast(reserve);
+        if ((size_t)reserve > fReserve) {
+            SkASSERT((size_t)reserve > fCount);
+            this->growReserveTo(reserve);
         }
     }
 
     T* prepend() {
-        this->adjustCount(1);
+        this->growBy(1);
         memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
         return fArray;
     }
@@ -167,7 +171,7 @@ public:
             SkASSERT(src == NULL || fArray == NULL ||
                     src + count <= fArray || fArray + oldCount <= src);
 
-            this->adjustCount(count);
+            this->growBy(count);
             if (src) {
                 memcpy(fArray + oldCount, src, sizeof(T) * count);
             }
@@ -186,9 +190,9 @@ public:
     }
     T* insert(int index, int count, const T* src = NULL) {
         SkASSERT(count);
-        SkASSERT(index <= fCount);
+        SkASSERT((size_t)index <= fCount);
         size_t oldCount = fCount;
-        this->adjustCount(count);
+        this->growBy(count);
         T* dst = fArray + index;
         memmove(dst + count, dst, sizeof(T) * (oldCount - index));
         if (src) {
@@ -198,13 +202,13 @@ public:
     }
 
     void remove(int index, int count = 1) {
-        SkASSERT(index + count <= fCount);
+        SkASSERT((size_t)(index + count) <= fCount);
         fCount = fCount - count;
         memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
     }
 
     void removeShuffle(int index) {
-        SkASSERT(index < fCount);
+        SkASSERT((size_t)index < fCount);
         int newCount = fCount - 1;
         fCount = newCount;
         if (index != newCount) {
@@ -250,7 +254,7 @@ public:
     int copyRange(T* dst, int index, int max) const {
         SkASSERT(max >= 0);
         SkASSERT(!max || dst);
-        if (index >= fCount) {
+        if ((size_t)index >= fCount) {
             return 0;
         }
         int count = SkMin32(max, fCount - index);
@@ -321,44 +325,146 @@ public:
 
 #ifdef SK_DEBUG
     void validate() const {
-        SkASSERT((fReserve == 0 && fArray == NULL) ||
-                 (fReserve > 0 && fArray != NULL));
+        SkASSERT((fArray == NULL && fReserve == 0) ||
+                 (fArray == fPreAllocMemArray && fReserve == fPreAllocMemArraySize) ||
+                 (fArray != NULL && fArray != fPreAllocMemArray && fReserve > 0));
         SkASSERT(fCount <= fReserve);
+        SkASSERT(fReserve <= fPreAllocMemArraySize || fArray != fPreAllocMemArray);
     }
 #endif
 
-    void shrinkToFit() {
-        fReserve = fCount;
-        fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
+protected:
+    template <int N> SkTDArray(SkAlignedSTStorage<N, T>* storage) {
+        this->init(NULL, 0, (T*)storage->get(), N);
+    }
+    template <int N> SkTDArray(const T src[], size_t count, SkAlignedSTStorage<N, T>* storage) {
+        this->init(src, count, (T*)storage->get(), N);
+    }
+    template <int N> SkTDArray(const SkTDArray<T>& that, SkAlignedSTStorage<N, T>* storage) {
+        this->init(that.fArray, that.fCount, (T*)storage->get(), N);
+    }
+
+    void init(const T* src, size_t count, T* preAllocStorage, size_t preAllocCount) {
+        SkASSERT(src || count == 0);
+
+        fArray = preAllocStorage;
+        fPreAllocMemArray = preAllocStorage;
+        fReserve = preAllocCount;
+        fCount = count;
+        fPreAllocMemArraySize = preAllocCount;
+
+        // The following is almost equivalent to calling this->append(count, src).
+        // This creates a tight fit instead of allocating extra room.
+        if (count) {
+            if (NULL == fArray || count > fReserve) {
+                fArray = (T*)sk_malloc_throw(count * sizeof(T));
+                fReserve = count;
+            }
+            memcpy(fArray, src, sizeof(T) * count);
+            fCount = count;
+        }
     }
 
 private:
-    T*      fArray;
-    int     fReserve;
-    int     fCount;
+    /** The underlying storage.
+     *  If fArray == NULL; fReserve == 0, fCount == 0.
+     *  If fArray == fPreAllocMemArray; fReserve = fPreAllocMemArraySize.
+     *  Otherwise fArray points to sk_malloc memory.
+     */
+    T* fArray;
+
+    /** Fixed-size storage which may be used as underlying storage.
+     *  Once out of init, this value is constant.
+     *  If fPreAllocMemArray == NULL; fPreAllocMemArraySize == 0.
+     *  If fPreAllocMemArray == fArray; fReserve = fPreAllocMemArraySize.
+     */
+    T* fPreAllocMemArray;
+
+    /** The current total size of the underlying storage in elements.
+     *  If fReserve == 0; fArray == NULL, fCount == 0.
+     *  If fReserve > 0; fArray != NULL.
+     *  If fReserve > fPreAllocMemArraySize; fArray != fPreAllocMemArray.
+     *  fReserve >= fCount.
+     */
+    size_t fReserve;

[reed1, 2015/04/22 23:02:12]

Why change fReserve and fCount from int to size_t? Clearly in some places we had
to add casts. Can these stay ints?

+
+    /** The current logical number of elements.
+     *  fCount <= fReserve.
+     *  Note that 'If fCount == 0; fArray == NULL' is not maintained.
+     */
+    size_t fCount;
+
+    /** The total size of the fixed size storage in elements.
+     *  Once out of init, this value is constant.
+     *  If fPreAllocMemArraySize == 0; fPreAllocMemArray == NULL.
+     */
+    size_t fPreAllocMemArraySize;
 
     /**
      *  Adjusts the number of elements in the array.
-     *  This is the same as calling setCount(count() + delta).
+     *  This is the same as calling setCount(count() + extra).
      */
-    void adjustCount(int delta) {
-        this->setCount(fCount + delta);
+    void growBy(size_t extra) {
+        SkASSERT(extra);
+
+        size_t newCount = fCount + extra;
+        if (newCount > fReserve) {
+            size_t size = newCount + 4;
+            size += size >> 2;
+
+            growReserveTo(size);
+        }
+        fCount = newCount;
     }
 
     /**
-     *  Increase the storage allocation such that it can hold (fCount + extra)
-     *  elements.
+     *  Increase the storage allocation such that it can hold size) elements.
      *  It never shrinks the allocation, and it may increase the allocation by
      *  more than is strictly required, based on a private growth heuristic.
      *
-     *  note: does NOT modify fCount
+     *  Note: does NOT modify fCount.
      */
-    void resizeStorageToAtLeast(int count) {
-        SkASSERT(count > fReserve);
-        fReserve = count + 4;
-        fReserve += fReserve / 4;
-        fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
+    void growReserveTo(size_t size) {
+        SkASSERT(size > fReserve);
+
+        if (fArray == fPreAllocMemArray) {
+            fArray = (T*)sk_malloc_throw(size * sizeof(T));
+            memcpy(fArray, fPreAllocMemArray, fCount * sizeof(T));
+        } else {
+            fArray = (T*)sk_realloc_throw(fArray, size * sizeof(T));
+        }
+        fReserve = size;
+    }
+};
+
+
+/**
+ * Subclass of SkTDArray that contains a preallocated memory block for the array.
+ * @param N the number of T elements to store in the preallocated memory block.
+ */
+template <size_t N, typename T>
+class SkSTDArray : public SkTDArray<T> {
+private:
+    typedef SkTDArray<T> INHERITED;
+
+public:
+    SkSTDArray() : INHERITED(&fStorage) { }
+    SkSTDArray(const T* src, int count) : INHERITED(src, count, &fStorage) { }
+    SkSTDArray(const SkSTDArray& that) : INHERITED(that, &fStorage) { }
+
+    explicit SkSTDArray(const INHERITED& that) : INHERITED(that, &fStorage) { }
+
+    SkSTDArray& operator= (const SkSTDArray& that) {
+        return *this = *(const INHERITED*)&that;
     }
+
+    SkSTDArray& operator= (const INHERITED& that) {
+        INHERITED::operator=(that);
+        return *this;
+    }
+
+private:
+    SkAlignedSTStorage<N, T> fStorage;
 };
 
 #endif