Home | History | Annotate | Download | only in include 
      1 /*
      2     Copyright 2010 Google Inc.
      3 
      4     Licensed under the Apache License, Version 2.0 (the "License");
      5     you may not use this file except in compliance with the License.
      6     You may obtain a copy of the License at
      7 
      8          http://www.apache.org/licenses/LICENSE-2.0
      9 
     10     Unless required by applicable law or agreed to in writing, software
     11     distributed under the License is distributed on an "AS IS" BASIS,
     12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13     See the License for the specific language governing permissions and
     14     limitations under the License.
     15  */
     16 
     17 
     18 #ifndef GrTDArray_DEFINED
     19 #define GrTDArray_DEFINED
     20 
     21 #include "GrTypes.h"
     22 
     23 static int GrInitialArrayAllocationCount() {
     24     return 4;
     25 }
     26 
     27 static int GrNextArrayAllocationCount(int count) {
     28     return count + ((count + 1) >> 1);
     29 }
     30 
     31 template <typename T> class GrTDArray {
     32 public:
     33     GrTDArray() : fArray(NULL), fAllocated(0), fCount(0) {}
     34     GrTDArray(const GrTDArray& src) {
     35         fCount = fAllocated = src.fCount;
     36         fArray = (T*)GrMalloc(fAllocated * sizeof(T));
     37         memcpy(fArray, src.fArray, fCount * sizeof(T));
     38     }
     39     ~GrTDArray() {
     40         if (fArray) {
     41             GrFree(fArray);
     42         }
     43     }
     44 
     45     bool isEmpty() const { return 0 == fCount; }
     46     int count() const { return fCount; }
     47 
     48     const T& at(int index) const {
     49         GrAssert((unsigned)index < (unsigned)fCount);
     50         return fArray[index];
     51     }
     52     T& at(int index) {
     53         GrAssert((unsigned)index < (unsigned)fCount);
     54         return fArray[index];
     55     }
     56 
     57     const T& operator[](int index) const { return this->at(index); }
     58     T& operator[](int index) { return this->at(index); }
     59 
     60     GrTDArray& operator=(const GrTDArray& src) {
     61         if (fAllocated < src.fCount) {
     62             fAllocated = src.fCount;
     63             GrFree(fArray);
     64             fArray = (T*)GrMalloc(fAllocated * sizeof(T));
     65         }
     66         fCount = src.fCount;
     67         memcpy(fArray, src.fArray, fCount * sizeof(T));
     68         return *this;
     69     }
     70 
     71     void reset() {
     72         if (fArray) {
     73             GrFree(fArray);
     74             fArray = NULL;
     75         }
     76         fAllocated = fCount = 0;
     77     }
     78 
     79     T* begin() const { return fArray; }
     80     T* end() const { return fArray + fCount; }
     81     T* back() const { GrAssert(fCount); return fArray + (fCount - 1); }
     82 
     83     T* prepend() {
     84         this->growAt(0);
     85         return fArray;
     86     }
     87 
     88     T* append() {
     89         this->growAt(fCount);
     90         return fArray + fCount - 1;
     91     }
     92 
     93     /**
     94      *  index may be [0..count], so that you can insert at the end (like append)
     95      */
     96     T* insert(int index) {
     97         GrAssert((unsigned)index <= (unsigned)fCount);
     98         this->growAt(index);
     99         return fArray + index;
    100     }
    101 
    102     void remove(int index) {
    103         GrAssert((unsigned)index < (unsigned)fCount);
    104         fCount -= 1;
    105         if (index < fCount) {
    106             int remaining = fCount - index;
    107             memmove(fArray + index, fArray + index + 1, remaining * sizeof(T));
    108         }
    109     }
    110 
    111     void removeShuffle(int index) {
    112         GrAssert((unsigned)index < (unsigned)fCount);
    113         fCount -= 1;
    114         if (index < fCount) {
    115             memmove(fArray + index, fArray + fCount, sizeof(T));
    116         }
    117     }
    118 
    119     // Utility iterators
    120 
    121     /**
    122      *  Calls GrFree() on each element. Assumes each is NULL or was allocated
    123      *  with GrMalloc().
    124      */
    125     void freeAll() {
    126         T* stop = this->end();
    127         for (T* curr = this->begin(); curr < stop; curr++) {
    128             GrFree(*curr);
    129         }
    130         this->reset();
    131     }
    132 
    133     /**
    134      *  Calls delete on each element. Assumes each is NULL or was allocated
    135      *  with new.
    136      */
    137     void deleteAll() {
    138         T* stop = this->end();
    139         for (T* curr = this->begin(); curr < stop; curr++) {
    140             delete *curr;
    141         }
    142         this->reset();
    143     }
    144 
    145     /**
    146      *  Calls GrSafeUnref() on each element. Assumes each is NULL or is a
    147      *  subclass of GrRefCnt.
    148      */
    149     void unrefAll() {
    150         T* stop = this->end();
    151         for (T* curr = this->begin(); curr < stop; curr++) {
    152             GrSafeUnref(*curr);
    153         }
    154         this->reset();
    155     }
    156 
    157     void visit(void visitor(T&)) const {
    158         T* stop = this->end();
    159         for (T* curr = this->begin(); curr < stop; curr++) {
    160             if (*curr) {
    161                 visitor(*curr);
    162             }
    163         }
    164     }
    165 
    166     int find(const T& elem) const {
    167         int count = this->count();
    168         T* curr = this->begin();
    169         for (int i = 0; i < count; i++) {
    170             if (elem == curr[i]) {
    171                 return i;
    172             }
    173         }
    174         return -1;
    175     }
    176 
    177     friend bool operator==(const GrTDArray<T>& a, const GrTDArray<T>& b) {
    178         return a.count() == b.count() &&
    179                (0 == a.count() ||
    180                 0 == memcmp(a.begin(), b.begin(), a.count() * sizeof(T)));
    181     }
    182     friend bool operator!=(const GrTDArray<T>& a, const GrTDArray<T>& b) {
    183         return !(a == b);
    184     }
    185 
    186 private:
    187     T*  fArray;
    188     int fAllocated, fCount;
    189 
    190     // growAt will increment fCount, reallocate fArray (as needed), and slide
    191     // the contents of fArray to make a hole for new data at index.
    192     void growAt(int index) {
    193         GrAssert(fCount <= fAllocated);
    194         if (0 == fAllocated) {
    195             fAllocated = GrInitialArrayAllocationCount();
    196             fArray = (T*)GrMalloc(fAllocated * sizeof(T));
    197         } else if (fCount == fAllocated) {
    198             fAllocated = GrNextArrayAllocationCount(fAllocated);
    199             T* newArray = (T*)GrMalloc(fAllocated * sizeof(T));
    200             memcpy(newArray, fArray, index * sizeof(T));
    201             memcpy(newArray + index + 1, fArray + index,
    202                    (fCount - index) * sizeof(T));
    203             GrFree(fArray);
    204             fArray = newArray;
    205         } else {
    206             // check that we're not just appending
    207             if (index < fCount) {
    208                 memmove(fArray + index + 1, fArray + index,
    209                         (fCount - index) * sizeof(T));
    210             }
    211         }
    212         GrAssert(fCount < fAllocated);
    213         fCount += 1;
    214     }
    215 };
    216 
    217 extern void* GrTDArray_growAt(void*, int* allocated, int& count, int index,
    218                               size_t);
    219 
    220 
    221 #endif
    222 
    223