michael@0: /*
michael@0:  * Copyright 2011 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #ifndef SkTArray_DEFINED
michael@0: #define SkTArray_DEFINED
michael@0: 
michael@0: #include <new>
michael@0: #include "SkTypes.h"
michael@0: #include "SkTemplates.h"
michael@0: 
michael@0: template <typename T, bool MEM_COPY = false> class SkTArray;
michael@0: 
michael@0: namespace SkTArrayExt {
michael@0: 
michael@0: template<typename T>
michael@0: inline void copy(SkTArray<T, true>* self, const T* array) {
michael@0:     memcpy(self->fMemArray, array, self->fCount * sizeof(T));
michael@0: }
michael@0: template<typename T>
michael@0: inline void copyAndDelete(SkTArray<T, true>* self, char* newMemArray) {
michael@0:     memcpy(newMemArray, self->fMemArray, self->fCount * sizeof(T));
michael@0: }
michael@0: 
michael@0: template<typename T>
michael@0: inline void copy(SkTArray<T, false>* self, const T* array) {
michael@0:     for (int i = 0; i < self->fCount; ++i) {
michael@0:         SkNEW_PLACEMENT_ARGS(self->fItemArray + i, T, (array[i]));
michael@0:     }
michael@0: }
michael@0: template<typename T>
michael@0: inline void copyAndDelete(SkTArray<T, false>* self, char* newMemArray) {
michael@0:     for (int i = 0; i < self->fCount; ++i) {
michael@0:         SkNEW_PLACEMENT_ARGS(newMemArray + sizeof(T) * i, T, (self->fItemArray[i]));
michael@0:         self->fItemArray[i].~T();
michael@0:     }
michael@0: }
michael@0: 
michael@0: }
michael@0: 
michael@0: template <typename T, bool MEM_COPY> void* operator new(size_t, SkTArray<T, MEM_COPY>*, int);
michael@0: 
michael@0: /** When MEM_COPY is true T will be bit copied when moved.
michael@0:     When MEM_COPY is false, T will be copy constructed / destructed.
michael@0:     In all cases T's constructor will be called on allocation,
michael@0:     and its destructor will be called from this object's destructor.
michael@0: */
michael@0: template <typename T, bool MEM_COPY> class SkTArray {
michael@0: public:
michael@0:     /**
michael@0:      * Creates an empty array with no initial storage
michael@0:      */
michael@0:     SkTArray() {
michael@0:         fCount = 0;
michael@0:         fReserveCount = gMIN_ALLOC_COUNT;
michael@0:         fAllocCount = 0;
michael@0:         fMemArray = NULL;
michael@0:         fPreAllocMemArray = NULL;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Creates an empty array that will preallocate space for reserveCount
michael@0:      * elements.
michael@0:      */
michael@0:     explicit SkTArray(int reserveCount) {
michael@0:         this->init(NULL, 0, NULL, reserveCount);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Copies one array to another. The new array will be heap allocated.
michael@0:      */
michael@0:     explicit SkTArray(const SkTArray& array) {
michael@0:         this->init(array.fItemArray, array.fCount, NULL, 0);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Creates a SkTArray by copying contents of a standard C array. The new
michael@0:      * array will be heap allocated. Be careful not to use this constructor
michael@0:      * when you really want the (void*, int) version.
michael@0:      */
michael@0:     SkTArray(const T* array, int count) {
michael@0:         this->init(array, count, NULL, 0);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * assign copy of array to this
michael@0:      */
michael@0:     SkTArray& operator =(const SkTArray& array) {
michael@0:         for (int i = 0; i < fCount; ++i) {
michael@0:             fItemArray[i].~T();
michael@0:         }
michael@0:         fCount = 0;
michael@0:         this->checkRealloc((int)array.count());
michael@0:         fCount = array.count();
michael@0:         SkTArrayExt::copy(this, static_cast<const T*>(array.fMemArray));
michael@0:         return *this;
michael@0:     }
michael@0: 
michael@0:     virtual ~SkTArray() {
michael@0:         for (int i = 0; i < fCount; ++i) {
michael@0:             fItemArray[i].~T();
michael@0:         }
michael@0:         if (fMemArray != fPreAllocMemArray) {
michael@0:             sk_free(fMemArray);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Resets to count() == 0
michael@0:      */
michael@0:     void reset() { this->pop_back_n(fCount); }
michael@0: 
michael@0:     /**
michael@0:      * Resets to count() = n newly constructed T objects.
michael@0:      */
michael@0:     void reset(int n) {
michael@0:         SkASSERT(n >= 0);
michael@0:         for (int i = 0; i < fCount; ++i) {
michael@0:             fItemArray[i].~T();
michael@0:         }
michael@0:         // set fCount to 0 before calling checkRealloc so that no copy cons. are called.
michael@0:         fCount = 0;
michael@0:         this->checkRealloc(n);
michael@0:         fCount = n;
michael@0:         for (int i = 0; i < fCount; ++i) {
michael@0:             SkNEW_PLACEMENT(fItemArray + i, T);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Resets to a copy of a C array.
michael@0:      */
michael@0:     void reset(const T* array, int count) {
michael@0:         for (int i = 0; i < fCount; ++i) {
michael@0:             fItemArray[i].~T();
michael@0:         }
michael@0:         int delta = count - fCount;
michael@0:         this->checkRealloc(delta);
michael@0:         fCount = count;
michael@0:         for (int i = 0; i < count; ++i) {
michael@0:             SkTArrayExt::copy(this, array);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Number of elements in the array.
michael@0:      */
michael@0:     int count() const { return fCount; }
michael@0: 
michael@0:     /**
michael@0:      * Is the array empty.
michael@0:      */
michael@0:     bool empty() const { return !fCount; }
michael@0: 
michael@0:     /**
michael@0:      * Adds 1 new default-constructed T value and returns in by reference. Note
michael@0:      * the reference only remains valid until the next call that adds or removes
michael@0:      * elements.
michael@0:      */
michael@0:     T& push_back() {
michael@0:         T* newT = reinterpret_cast<T*>(this->push_back_raw(1));
michael@0:         SkNEW_PLACEMENT(newT, T);
michael@0:         return *newT;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Version of above that uses a copy constructor to initialize the new item
michael@0:      */
michael@0:     T& push_back(const T& t) {
michael@0:         T* newT = reinterpret_cast<T*>(this->push_back_raw(1));
michael@0:         SkNEW_PLACEMENT_ARGS(newT, T, (t));
michael@0:         return *newT;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Allocates n more default T values, and returns the address of the start
michael@0:      * of that new range. Note: this address is only valid until the next API
michael@0:      * call made on the array that might add or remove elements.
michael@0:      */
michael@0:     T* push_back_n(int n) {
michael@0:         SkASSERT(n >= 0);
michael@0:         T* newTs = reinterpret_cast<T*>(this->push_back_raw(n));
michael@0:         for (int i = 0; i < n; ++i) {
michael@0:             SkNEW_PLACEMENT(newTs + i, T);
michael@0:         }
michael@0:         return newTs;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Version of above that uses a copy constructor to initialize all n items
michael@0:      * to the same T.
michael@0:      */
michael@0:     T* push_back_n(int n, const T& t) {
michael@0:         SkASSERT(n >= 0);
michael@0:         T* newTs = reinterpret_cast<T*>(this->push_back_raw(n));
michael@0:         for (int i = 0; i < n; ++i) {
michael@0:             SkNEW_PLACEMENT_ARGS(newTs[i], T, (t));
michael@0:         }
michael@0:         return newTs;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Version of above that uses a copy constructor to initialize the n items
michael@0:      * to separate T values.
michael@0:      */
michael@0:     T* push_back_n(int n, const T t[]) {
michael@0:         SkASSERT(n >= 0);
michael@0:         this->checkRealloc(n);
michael@0:         for (int i = 0; i < n; ++i) {
michael@0:             SkNEW_PLACEMENT_ARGS(fItemArray + fCount + i, T, (t[i]));
michael@0:         }
michael@0:         fCount += n;
michael@0:         return fItemArray + fCount - n;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Removes the last element. Not safe to call when count() == 0.
michael@0:      */
michael@0:     void pop_back() {
michael@0:         SkASSERT(fCount > 0);
michael@0:         --fCount;
michael@0:         fItemArray[fCount].~T();
michael@0:         this->checkRealloc(0);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Removes the last n elements. Not safe to call when count() < n.
michael@0:      */
michael@0:     void pop_back_n(int n) {
michael@0:         SkASSERT(n >= 0);
michael@0:         SkASSERT(fCount >= n);
michael@0:         fCount -= n;
michael@0:         for (int i = 0; i < n; ++i) {
michael@0:             fItemArray[fCount + i].~T();
michael@0:         }
michael@0:         this->checkRealloc(0);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Pushes or pops from the back to resize. Pushes will be default
michael@0:      * initialized.
michael@0:      */
michael@0:     void resize_back(int newCount) {
michael@0:         SkASSERT(newCount >= 0);
michael@0: 
michael@0:         if (newCount > fCount) {
michael@0:             this->push_back_n(newCount - fCount);
michael@0:         } else if (newCount < fCount) {
michael@0:             this->pop_back_n(fCount - newCount);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     T* begin() {
michael@0:         return fItemArray;
michael@0:     }
michael@0:     const T* begin() const {
michael@0:         return fItemArray;
michael@0:     }
michael@0:     T* end() {
michael@0:         return fItemArray ? fItemArray + fCount : NULL;
michael@0:     }
michael@0:     const T* end() const {
michael@0:         return fItemArray ? fItemArray + fCount : NULL;;
michael@0:     }
michael@0: 
michael@0:    /**
michael@0:      * Get the i^th element.
michael@0:      */
michael@0:     T& operator[] (int i) {
michael@0:         SkASSERT(i < fCount);
michael@0:         SkASSERT(i >= 0);
michael@0:         return fItemArray[i];
michael@0:     }
michael@0: 
michael@0:     const T& operator[] (int i) const {
michael@0:         SkASSERT(i < fCount);
michael@0:         SkASSERT(i >= 0);
michael@0:         return fItemArray[i];
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * equivalent to operator[](0)
michael@0:      */
michael@0:     T& front() { SkASSERT(fCount > 0); return fItemArray[0];}
michael@0: 
michael@0:     const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];}
michael@0: 
michael@0:     /**
michael@0:      * equivalent to operator[](count() - 1)
michael@0:      */
michael@0:     T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];}
michael@0: 
michael@0:     const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];}
michael@0: 
michael@0:     /**
michael@0:      * equivalent to operator[](count()-1-i)
michael@0:      */
michael@0:     T& fromBack(int i) {
michael@0:         SkASSERT(i >= 0);
michael@0:         SkASSERT(i < fCount);
michael@0:         return fItemArray[fCount - i - 1];
michael@0:     }
michael@0: 
michael@0:     const T& fromBack(int i) const {
michael@0:         SkASSERT(i >= 0);
michael@0:         SkASSERT(i < fCount);
michael@0:         return fItemArray[fCount - i - 1];
michael@0:     }
michael@0: 
michael@0:     bool operator==(const SkTArray<T, MEM_COPY>& right) const {
michael@0:         int leftCount = this->count();
michael@0:         if (leftCount != right.count()) {
michael@0:             return false;
michael@0:         }
michael@0:         for (int index = 0; index < leftCount; ++index) {
michael@0:             if (fItemArray[index] != right.fItemArray[index]) {
michael@0:                 return false;
michael@0:             }
michael@0:         }
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     bool operator!=(const SkTArray<T, MEM_COPY>& right) const {
michael@0:         return !(*this == right);
michael@0:     }
michael@0: 
michael@0: protected:
michael@0:     /**
michael@0:      * Creates an empty array that will use the passed storage block until it
michael@0:      * is insufficiently large to hold the entire array.
michael@0:      */
michael@0:     template <int N>
michael@0:     SkTArray(SkAlignedSTStorage<N,T>* storage) {
michael@0:         this->init(NULL, 0, storage->get(), N);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Copy another array, using preallocated storage if preAllocCount >=
michael@0:      * array.count(). Otherwise storage will only be used when array shrinks
michael@0:      * to fit.
michael@0:      */
michael@0:     template <int N>
michael@0:     SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) {
michael@0:         this->init(array.fItemArray, array.fCount, storage->get(), N);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Copy a C array, using preallocated storage if preAllocCount >=
michael@0:      * count. Otherwise storage will only be used when array shrinks
michael@0:      * to fit.
michael@0:      */
michael@0:     template <int N>
michael@0:     SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) {
michael@0:         this->init(array, count, storage->get(), N);
michael@0:     }
michael@0: 
michael@0:     void init(const T* array, int count,
michael@0:                void* preAllocStorage, int preAllocOrReserveCount) {
michael@0:         SkASSERT(count >= 0);
michael@0:         SkASSERT(preAllocOrReserveCount >= 0);
michael@0:         fCount              = count;
michael@0:         fReserveCount       = (preAllocOrReserveCount > 0) ?
michael@0:                                     preAllocOrReserveCount :
michael@0:                                     gMIN_ALLOC_COUNT;
michael@0:         fPreAllocMemArray   = preAllocStorage;
michael@0:         if (fReserveCount >= fCount &&
michael@0:             NULL != preAllocStorage) {
michael@0:             fAllocCount = fReserveCount;
michael@0:             fMemArray = preAllocStorage;
michael@0:         } else {
michael@0:             fAllocCount = SkMax32(fCount, fReserveCount);
michael@0:             fMemArray = sk_malloc_throw(fAllocCount * sizeof(T));
michael@0:         }
michael@0: 
michael@0:         SkTArrayExt::copy(this, array);
michael@0:     }
michael@0: 
michael@0: private:
michael@0: 
michael@0:     static const int gMIN_ALLOC_COUNT = 8;
michael@0: 
michael@0:     // Helper function that makes space for n objects, adjusts the count, but does not initialize
michael@0:     // the new objects.
michael@0:     void* push_back_raw(int n) {
michael@0:         this->checkRealloc(n);
michael@0:         void* ptr = fItemArray + fCount;
michael@0:         fCount += n;
michael@0:         return ptr;
michael@0:     }
michael@0: 
michael@0:     inline void checkRealloc(int delta) {
michael@0:         SkASSERT(fCount >= 0);
michael@0:         SkASSERT(fAllocCount >= 0);
michael@0: 
michael@0:         SkASSERT(-delta <= fCount);
michael@0: 
michael@0:         int newCount = fCount + delta;
michael@0:         int newAllocCount = fAllocCount;
michael@0: 
michael@0:         if (newCount > fAllocCount || newCount < (fAllocCount / 3)) {
michael@0:             // whether we're growing or shrinking, we leave at least 50% extra space for future
michael@0:             // growth (clamped to the reserve count).
michael@0:             newAllocCount = SkMax32(newCount + ((newCount + 1) >> 1), fReserveCount);
michael@0:         }
michael@0:         if (newAllocCount != fAllocCount) {
michael@0: 
michael@0:             fAllocCount = newAllocCount;
michael@0:             char* newMemArray;
michael@0: 
michael@0:             if (fAllocCount == fReserveCount && NULL != fPreAllocMemArray) {
michael@0:                 newMemArray = (char*) fPreAllocMemArray;
michael@0:             } else {
michael@0:                 newMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T));
michael@0:             }
michael@0: 
michael@0:             SkTArrayExt::copyAndDelete<T>(this, newMemArray);
michael@0: 
michael@0:             if (fMemArray != fPreAllocMemArray) {
michael@0:                 sk_free(fMemArray);
michael@0:             }
michael@0:             fMemArray = newMemArray;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     friend void* operator new<T>(size_t, SkTArray*, int);
michael@0: 
michael@0:     template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, const X*);
michael@0:     template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, true>* that, char*);
michael@0: 
michael@0:     template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, const X*);
michael@0:     template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, false>* that, char*);
michael@0: 
michael@0:     int fReserveCount;
michael@0:     int fCount;
michael@0:     int fAllocCount;
michael@0:     void*    fPreAllocMemArray;
michael@0:     union {
michael@0:         T*       fItemArray;
michael@0:         void*    fMemArray;
michael@0:     };
michael@0: };
michael@0: 
michael@0: // Use the below macro (SkNEW_APPEND_TO_TARRAY) rather than calling this directly
michael@0: template <typename T, bool MEM_COPY>
michael@0: void* operator new(size_t, SkTArray<T, MEM_COPY>* array, int atIndex) {
michael@0:     // Currently, we only support adding to the end of the array. When the array class itself
michael@0:     // supports random insertion then this should be updated.
michael@0:     // SkASSERT(atIndex >= 0 && atIndex <= array->count());
michael@0:     SkASSERT(atIndex == array->count());
michael@0:     return array->push_back_raw(1);
michael@0: }
michael@0: 
michael@0: // Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete
michael@0: // to match the op new silences warnings about missing op delete when a constructor throws an
michael@0: // exception.
michael@0: template <typename T, bool MEM_COPY>
michael@0: void operator delete(void*, SkTArray<T, MEM_COPY>* array, int atIndex) {
michael@0:     SK_CRASH();
michael@0: }
michael@0: 
michael@0: // Constructs a new object as the last element of an SkTArray.
michael@0: #define SkNEW_APPEND_TO_TARRAY(array_ptr, type_name, args)  \
michael@0:     (new ((array_ptr), (array_ptr)->count()) type_name args)
michael@0: 
michael@0: 
michael@0: /**
michael@0:  * Subclass of SkTArray that contains a preallocated memory block for the array.
michael@0:  */
michael@0: template <int N, typename T, bool MEM_COPY = false>
michael@0: class SkSTArray : public SkTArray<T, MEM_COPY> {
michael@0: private:
michael@0:     typedef SkTArray<T, MEM_COPY> INHERITED;
michael@0: 
michael@0: public:
michael@0:     SkSTArray() : INHERITED(&fStorage) {
michael@0:     }
michael@0: 
michael@0:     SkSTArray(const SkSTArray& array)
michael@0:         : INHERITED(array, &fStorage) {
michael@0:     }
michael@0: 
michael@0:     explicit SkSTArray(const INHERITED& array)
michael@0:         : INHERITED(array, &fStorage) {
michael@0:     }
michael@0: 
michael@0:     explicit SkSTArray(int reserveCount)
michael@0:         : INHERITED(reserveCount) {
michael@0:     }
michael@0: 
michael@0:     SkSTArray(const T* array, int count)
michael@0:         : INHERITED(array, count, &fStorage) {
michael@0:     }
michael@0: 
michael@0:     SkSTArray& operator= (const SkSTArray& array) {
michael@0:         return *this = *(const INHERITED*)&array;
michael@0:     }
michael@0: 
michael@0:     SkSTArray& operator= (const INHERITED& array) {
michael@0:         INHERITED::operator=(array);
michael@0:         return *this;
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     SkAlignedSTStorage<N,T> fStorage;
michael@0: };
michael@0: 
michael@0: #endif