Add SkSTDArray.

include/core/SkTDArray.h

 
 /*
  * Copyright 2006 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 SkTDArray_DEFINED
 #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);
+    SkTDArray(const T src[], size_t count) {
+        this->init(src, count, NULL, 0);
+    }
+    SkTDArray(const SkTDArray<T>& that) {
+        this->init(that.fArray, that.fCount, NULL, 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() {
+        if (fArray != fPreAllocMemArray) {
+            sk_free(fArray);
         }
     }
-    SkTDArray(const SkTDArray<T>& src) {
-        fReserve = fCount = 0;
-        fArray = NULL;
-        SkTDArray<T> tmp(src.fArray, src.fCount);
-        this->swap(tmp);
-    }
-    ~SkTDArray() {
-        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;
     }
 
     friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
         return  a.fCount == b.fCount &&
                 (a.fCount == 0 ||
                  !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
     }
     friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) {
         return !(a == b);
     }
 
     void swap(SkTDArray<T>& other) {

[bungeman-skia, 2015/04/22 22:20:29]

This swap is wrong for any STD versions, haven't thought about how to fix.

         SkTSwap(fArray, other.fArray);
         SkTSwap(fReserve, other.fReserve);
         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;
     }
 
     bool isEmpty() const { return fCount == 0; }
 
     /**
      *  Return the number of elements in the array
      */
     int count() const { return fCount; }
 
     /**
      *  Return the total number of elements allocated.
      *  reserved() - count() gives you the number of elements you can add
      *  without causing an allocation.
      */
     int reserved() const { return fReserve; }
 
     /**
      *  return the number of bytes in the array: count * sizeof(T)
      */
     size_t bytes() const { return fCount * sizeof(T); }
 
     T*  begin() { return fArray; }
     const T*  begin() const { return fArray; }
     T*  end() { return fArray ? fArray + fCount : NULL; }
     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];
     }
 
     T&  getAt(int index)  {
         return (*this)[index];
     }
     const T&  getAt(int index) const {
         return (*this)[index];
     }
 
     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);
         }
     }
 
     void rewind() {
         // same as setCount(0)
         fCount = 0;
     }
 
     /**
      *  Sets the number of elements in the array.
      *  If the array does not have space for count elements, it will increase
      *  the storage allocated to some amount greater than that required.
      *  It will never shrink the shrink the storage.
      */
     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;
     }
 
     T* append() {
         return this->append(1, NULL);
     }
     T* append(int count, const T* src = NULL) {
         int oldCount = fCount;
         if (count)  {
             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);
             }
         }
         return fArray + oldCount;
     }
 
     T* appendClear() {
         T* result = this->append();
         *result = 0;
         return result;
     }
 
     T* insert(int index) {
         return this->insert(index, 1, NULL);
     }
     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) {
             memcpy(dst, src, sizeof(T) * count);
         }
         return dst;
     }
 
     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) {
             memcpy(fArray + index, fArray + newCount, sizeof(T));
         }
     }
 
     int find(const T& elem) const {
         const T* iter = fArray;
         const T* stop = fArray + fCount;
@@ skipping 25 matching lines @@
         return (this->find(elem) >= 0);
     }
 
     /**
      * Copies up to max elements into dst. The number of items copied is
      * capped by count - index. The actual number copied is returned.
      */
     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);
         memcpy(dst, fArray + index, sizeof(T) * count);
         return count;
     }
 
     void copy(T* dst) const {
         this->copyRange(dst, 0, fCount);
     }
@@ skipping 50 matching lines @@
         T* stop = this->end();
         for (T* curr = this->begin(); curr < stop; curr++) {
             if (*curr) {
                 visitor(*curr);
             }
         }
     }
 
 #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