michael@0: 
michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
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: 
michael@0: #ifndef SkTDArray_DEFINED
michael@0: #define SkTDArray_DEFINED
michael@0: 
michael@0: #include "SkTypes.h"
michael@0: 
michael@0: template <typename T> class SK_API SkTDArray {
michael@0: public:
michael@0:     SkTDArray() {
michael@0:         fReserve = fCount = 0;
michael@0:         fArray = NULL;
michael@0: #ifdef SK_DEBUG
michael@0:         fData = NULL;
michael@0: #endif
michael@0:     }
michael@0:     SkTDArray(const T src[], int count) {
michael@0:         SkASSERT(src || count == 0);
michael@0: 
michael@0:         fReserve = fCount = 0;
michael@0:         fArray = NULL;
michael@0: #ifdef SK_DEBUG
michael@0:         fData = NULL;
michael@0: #endif
michael@0:         if (count) {
michael@0:             fArray = (T*)sk_malloc_throw(count * sizeof(T));
michael@0: #ifdef SK_DEBUG
michael@0:             fData = (ArrayT*)fArray;
michael@0: #endif
michael@0:             memcpy(fArray, src, sizeof(T) * count);
michael@0:             fReserve = fCount = count;
michael@0:         }
michael@0:     }
michael@0:     SkTDArray(const SkTDArray<T>& src) {
michael@0:         fReserve = fCount = 0;
michael@0:         fArray = NULL;
michael@0: #ifdef SK_DEBUG
michael@0:         fData = NULL;
michael@0: #endif
michael@0:         SkTDArray<T> tmp(src.fArray, src.fCount);
michael@0:         this->swap(tmp);
michael@0:     }
michael@0:     ~SkTDArray() {
michael@0:         sk_free(fArray);
michael@0:     }
michael@0: 
michael@0:     SkTDArray<T>& operator=(const SkTDArray<T>& src) {
michael@0:         if (this != &src) {
michael@0:             if (src.fCount > fReserve) {
michael@0:                 SkTDArray<T> tmp(src.fArray, src.fCount);
michael@0:                 this->swap(tmp);
michael@0:             } else {
michael@0:                 memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
michael@0:                 fCount = src.fCount;
michael@0:             }
michael@0:         }
michael@0:         return *this;
michael@0:     }
michael@0: 
michael@0:     friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
michael@0:         return  a.fCount == b.fCount &&
michael@0:                 (a.fCount == 0 ||
michael@0:                  !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
michael@0:     }
michael@0:     friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) {
michael@0:         return !(a == b);
michael@0:     }
michael@0: 
michael@0:     void swap(SkTDArray<T>& other) {
michael@0:         SkTSwap(fArray, other.fArray);
michael@0: #ifdef SK_DEBUG
michael@0:         SkTSwap(fData, other.fData);
michael@0: #endif
michael@0:         SkTSwap(fReserve, other.fReserve);
michael@0:         SkTSwap(fCount, other.fCount);
michael@0:     }
michael@0: 
michael@0:     /** Return a ptr to the array of data, to be freed with sk_free. This also
michael@0:         resets the SkTDArray to be empty.
michael@0:      */
michael@0:     T* detach() {
michael@0:         T* array = fArray;
michael@0:         fArray = NULL;
michael@0:         fReserve = fCount = 0;
michael@0:         SkDEBUGCODE(fData = NULL;)
michael@0:         return array;
michael@0:     }
michael@0: 
michael@0:     bool isEmpty() const { return fCount == 0; }
michael@0: 
michael@0:     /**
michael@0:      *  Return the number of elements in the array
michael@0:      */
michael@0:     int count() const { return fCount; }
michael@0: 
michael@0:     /**
michael@0:      *  Return the total number of elements allocated.
michael@0:      *  reserved() - count() gives you the number of elements you can add
michael@0:      *  without causing an allocation.
michael@0:      */
michael@0:     int reserved() const { return fReserve; }
michael@0: 
michael@0:     /**
michael@0:      *  return the number of bytes in the array: count * sizeof(T)
michael@0:      */
michael@0:     size_t bytes() const { return fCount * sizeof(T); }
michael@0: 
michael@0:     T*  begin() { return fArray; }
michael@0:     const T*  begin() const { return fArray; }
michael@0:     T*  end() { return fArray ? fArray + fCount : NULL; }
michael@0:     const T*  end() const { return fArray ? fArray + fCount : NULL; }
michael@0: 
michael@0:     T&  operator[](int index) {
michael@0:         SkASSERT(index < fCount);
michael@0:         return fArray[index];
michael@0:     }
michael@0:     const T&  operator[](int index) const {
michael@0:         SkASSERT(index < fCount);
michael@0:         return fArray[index];
michael@0:     }
michael@0: 
michael@0:     T&  getAt(int index)  {
michael@0:         return (*this)[index];
michael@0:     }
michael@0:     const T&  getAt(int index) const {
michael@0:         return (*this)[index];
michael@0:     }
michael@0: 
michael@0:     void reset() {
michael@0:         if (fArray) {
michael@0:             sk_free(fArray);
michael@0:             fArray = NULL;
michael@0: #ifdef SK_DEBUG
michael@0:             fData = NULL;
michael@0: #endif
michael@0:             fReserve = fCount = 0;
michael@0:         } else {
michael@0:             SkASSERT(fReserve == 0 && fCount == 0);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void rewind() {
michael@0:         // same as setCount(0)
michael@0:         fCount = 0;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      *  Sets the number of elements in the array.
michael@0:      *  If the array does not have space for count elements, it will increase
michael@0:      *  the storage allocated to some amount greater than that required.
michael@0:      *  It will never shrink the shrink the storage.
michael@0:      */
michael@0:     void setCount(int count) {
michael@0:         SkASSERT(count >= 0);
michael@0:         if (count > fReserve) {
michael@0:             this->resizeStorageToAtLeast(count);
michael@0:         }
michael@0:         fCount = count;
michael@0:     }
michael@0: 
michael@0:     void setReserve(int reserve) {
michael@0:         if (reserve > fReserve) {
michael@0:             this->resizeStorageToAtLeast(reserve);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     T* prepend() {
michael@0:         this->adjustCount(1);
michael@0:         memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
michael@0:         return fArray;
michael@0:     }
michael@0: 
michael@0:     T* append() {
michael@0:         return this->append(1, NULL);
michael@0:     }
michael@0:     T* append(int count, const T* src = NULL) {
michael@0:         int oldCount = fCount;
michael@0:         if (count)  {
michael@0:             SkASSERT(src == NULL || fArray == NULL ||
michael@0:                     src + count <= fArray || fArray + oldCount <= src);
michael@0: 
michael@0:             this->adjustCount(count);
michael@0:             if (src) {
michael@0:                 memcpy(fArray + oldCount, src, sizeof(T) * count);
michael@0:             }
michael@0:         }
michael@0:         return fArray + oldCount;
michael@0:     }
michael@0: 
michael@0:     T* appendClear() {
michael@0:         T* result = this->append();
michael@0:         *result = 0;
michael@0:         return result;
michael@0:     }
michael@0: 
michael@0:     T* insert(int index) {
michael@0:         return this->insert(index, 1, NULL);
michael@0:     }
michael@0:     T* insert(int index, int count, const T* src = NULL) {
michael@0:         SkASSERT(count);
michael@0:         SkASSERT(index <= fCount);
michael@0:         size_t oldCount = fCount;
michael@0:         this->adjustCount(count);
michael@0:         T* dst = fArray + index;
michael@0:         memmove(dst + count, dst, sizeof(T) * (oldCount - index));
michael@0:         if (src) {
michael@0:             memcpy(dst, src, sizeof(T) * count);
michael@0:         }
michael@0:         return dst;
michael@0:     }
michael@0: 
michael@0:     void remove(int index, int count = 1) {
michael@0:         SkASSERT(index + count <= fCount);
michael@0:         fCount = fCount - count;
michael@0:         memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
michael@0:     }
michael@0: 
michael@0:     void removeShuffle(int index) {
michael@0:         SkASSERT(index < fCount);
michael@0:         int newCount = fCount - 1;
michael@0:         fCount = newCount;
michael@0:         if (index != newCount) {
michael@0:             memcpy(fArray + index, fArray + newCount, sizeof(T));
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     int find(const T& elem) const {
michael@0:         const T* iter = fArray;
michael@0:         const T* stop = fArray + fCount;
michael@0: 
michael@0:         for (; iter < stop; iter++) {
michael@0:             if (*iter == elem) {
michael@0:                 return (int) (iter - fArray);
michael@0:             }
michael@0:         }
michael@0:         return -1;
michael@0:     }
michael@0: 
michael@0:     int rfind(const T& elem) const {
michael@0:         const T* iter = fArray + fCount;
michael@0:         const T* stop = fArray;
michael@0: 
michael@0:         while (iter > stop) {
michael@0:             if (*--iter == elem) {
michael@0:                 return SkToInt(iter - stop);
michael@0:             }
michael@0:         }
michael@0:         return -1;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Returns true iff the array contains this element.
michael@0:      */
michael@0:     bool contains(const T& elem) const {
michael@0:         return (this->find(elem) >= 0);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Copies up to max elements into dst. The number of items copied is
michael@0:      * capped by count - index. The actual number copied is returned.
michael@0:      */
michael@0:     int copyRange(T* dst, int index, int max) const {
michael@0:         SkASSERT(max >= 0);
michael@0:         SkASSERT(!max || dst);
michael@0:         if (index >= fCount) {
michael@0:             return 0;
michael@0:         }
michael@0:         int count = SkMin32(max, fCount - index);
michael@0:         memcpy(dst, fArray + index, sizeof(T) * count);
michael@0:         return count;
michael@0:     }
michael@0: 
michael@0:     void copy(T* dst) const {
michael@0:         this->copyRange(dst, 0, fCount);
michael@0:     }
michael@0: 
michael@0:     // routines to treat the array like a stack
michael@0:     T*          push() { return this->append(); }
michael@0:     void        push(const T& elem) { *this->append() = elem; }
michael@0:     const T&    top() const { return (*this)[fCount - 1]; }
michael@0:     T&          top() { return (*this)[fCount - 1]; }
michael@0:     void        pop(T* elem) { if (elem) *elem = (*this)[fCount - 1]; --fCount; }
michael@0:     void        pop() { --fCount; }
michael@0: 
michael@0:     void deleteAll() {
michael@0:         T*  iter = fArray;
michael@0:         T*  stop = fArray + fCount;
michael@0:         while (iter < stop) {
michael@0:             SkDELETE (*iter);
michael@0:             iter += 1;
michael@0:         }
michael@0:         this->reset();
michael@0:     }
michael@0: 
michael@0:     void freeAll() {
michael@0:         T*  iter = fArray;
michael@0:         T*  stop = fArray + fCount;
michael@0:         while (iter < stop) {
michael@0:             sk_free(*iter);
michael@0:             iter += 1;
michael@0:         }
michael@0:         this->reset();
michael@0:     }
michael@0: 
michael@0:     void unrefAll() {
michael@0:         T*  iter = fArray;
michael@0:         T*  stop = fArray + fCount;
michael@0:         while (iter < stop) {
michael@0:             (*iter)->unref();
michael@0:             iter += 1;
michael@0:         }
michael@0:         this->reset();
michael@0:     }
michael@0: 
michael@0:     void safeUnrefAll() {
michael@0:         T*  iter = fArray;
michael@0:         T*  stop = fArray + fCount;
michael@0:         while (iter < stop) {
michael@0:             SkSafeUnref(*iter);
michael@0:             iter += 1;
michael@0:         }
michael@0:         this->reset();
michael@0:     }
michael@0: 
michael@0:     void visitAll(void visitor(T&)) {
michael@0:         T* stop = this->end();
michael@0:         for (T* curr = this->begin(); curr < stop; curr++) {
michael@0:             if (*curr) {
michael@0:                 visitor(*curr);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     void validate() const {
michael@0:         SkASSERT((fReserve == 0 && fArray == NULL) ||
michael@0:                  (fReserve > 0 && fArray != NULL));
michael@0:         SkASSERT(fCount <= fReserve);
michael@0:         SkASSERT(fData == (ArrayT*)fArray);
michael@0:     }
michael@0: #endif
michael@0: 
michael@0: private:
michael@0: #ifdef SK_DEBUG
michael@0:     enum {
michael@0:         kDebugArraySize = 16
michael@0:     };
michael@0:     typedef T ArrayT[kDebugArraySize];
michael@0:     ArrayT* fData;
michael@0: #endif
michael@0:     T*      fArray;
michael@0:     int     fReserve;
michael@0:     int     fCount;
michael@0: 
michael@0:     /**
michael@0:      *  Adjusts the number of elements in the array.
michael@0:      *  This is the same as calling setCount(count() + delta).
michael@0:      */
michael@0:     void adjustCount(int delta) {
michael@0:         this->setCount(fCount + delta);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      *  Increase the storage allocation such that it can hold (fCount + extra)
michael@0:      *  elements.
michael@0:      *  It never shrinks the allocation, and it may increase the allocation by
michael@0:      *  more than is strictly required, based on a private growth heuristic.
michael@0:      *
michael@0:      *  note: does NOT modify fCount
michael@0:      */
michael@0:     void resizeStorageToAtLeast(int count) {
michael@0:         SkASSERT(count > fReserve);
michael@0:         fReserve = count + 4;
michael@0:         fReserve += fReserve / 4;
michael@0:         fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
michael@0: #ifdef SK_DEBUG
michael@0:         fData = (ArrayT*)fArray;
michael@0: #endif
michael@0:     }
michael@0: };
michael@0: 
michael@0: #endif