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