1 2 /* 3 * Copyright 2006 The Android Open Source Project 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 #ifndef SkTDArray_DEFINED 11 #define SkTDArray_DEFINED 12 13 #include "SkTypes.h" 14 15 template <typename T> class SK_API SkTDArray { 16 public: 17 SkTDArray() { 18 fReserve = fCount = 0; 19 fArray = NULL; 20 #ifdef SK_DEBUG 21 fData = NULL; 22 #endif 23 } 24 SkTDArray(const T src[], size_t count) { 25 SkASSERT(src || count == 0); 26 27 fReserve = fCount = 0; 28 fArray = NULL; 29 #ifdef SK_DEBUG 30 fData = NULL; 31 #endif 32 if (count) { 33 fArray = (T*)sk_malloc_throw(count * sizeof(T)); 34 #ifdef SK_DEBUG 35 fData = (ArrayT*)fArray; 36 #endif 37 memcpy(fArray, src, sizeof(T) * count); 38 fReserve = fCount = count; 39 } 40 } 41 SkTDArray(const SkTDArray<T>& src) { 42 fReserve = fCount = 0; 43 fArray = NULL; 44 #ifdef SK_DEBUG 45 fData = NULL; 46 #endif 47 SkTDArray<T> tmp(src.fArray, src.fCount); 48 this->swap(tmp); 49 } 50 ~SkTDArray() { 51 sk_free(fArray); 52 } 53 54 SkTDArray<T>& operator=(const SkTDArray<T>& src) { 55 if (this != &src) { 56 if (src.fCount > fReserve) { 57 SkTDArray<T> tmp(src.fArray, src.fCount); 58 this->swap(tmp); 59 } else { 60 memcpy(fArray, src.fArray, sizeof(T) * src.fCount); 61 fCount = src.fCount; 62 } 63 } 64 return *this; 65 } 66 67 friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) { 68 return a.fCount == b.fCount && 69 (a.fCount == 0 || 70 !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T))); 71 } 72 73 void swap(SkTDArray<T>& other) { 74 SkTSwap(fArray, other.fArray); 75 #ifdef SK_DEBUG 76 SkTSwap(fData, other.fData); 77 #endif 78 SkTSwap(fReserve, other.fReserve); 79 SkTSwap(fCount, other.fCount); 80 } 81 82 /** Return a ptr to the array of data, to be freed with sk_free. This also 83 resets the SkTDArray to be empty. 84 */ 85 T* detach() { 86 T* array = fArray; 87 fArray = NULL; 88 fReserve = fCount = 0; 89 SkDEBUGCODE(fData = NULL;) 90 return array; 91 } 92 93 bool isEmpty() const { return fCount == 0; } 94 95 /** 96 * Return the number of elements in the array 97 */ 98 int count() const { return fCount; } 99 100 /** 101 * return the number of bytes in the array: count * sizeof(T) 102 */ 103 size_t bytes() const { return fCount * sizeof(T); } 104 105 T* begin() const { return fArray; } 106 T* end() const { return fArray ? fArray + fCount : NULL; } 107 T& operator[](int index) const { 108 SkASSERT((unsigned)index < fCount); 109 return fArray[index]; 110 } 111 112 void reset() { 113 if (fArray) { 114 sk_free(fArray); 115 fArray = NULL; 116 #ifdef SK_DEBUG 117 fData = NULL; 118 #endif 119 fReserve = fCount = 0; 120 } else { 121 SkASSERT(fReserve == 0 && fCount == 0); 122 } 123 } 124 125 void rewind() { 126 // same as setCount(0) 127 fCount = 0; 128 } 129 130 void setCount(size_t count) { 131 if (count > fReserve) { 132 this->growBy(count - fCount); 133 } else { 134 fCount = count; 135 } 136 } 137 138 void setReserve(size_t reserve) { 139 if (reserve > fReserve) { 140 SkASSERT(reserve > fCount); 141 size_t count = fCount; 142 this->growBy(reserve - fCount); 143 fCount = count; 144 } 145 } 146 147 T* prepend() { 148 this->growBy(1); 149 memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T)); 150 return fArray; 151 } 152 153 T* append() { 154 return this->append(1, NULL); 155 } 156 T* append(size_t count, const T* src = NULL) { 157 unsigned oldCount = fCount; 158 if (count) { 159 SkASSERT(src == NULL || fArray == NULL || 160 src + count <= fArray || fArray + oldCount <= src); 161 162 this->growBy(count); 163 if (src) { 164 memcpy(fArray + oldCount, src, sizeof(T) * count); 165 } 166 } 167 return fArray + oldCount; 168 } 169 170 T* appendClear() { 171 T* result = this->append(); 172 *result = 0; 173 return result; 174 } 175 176 T* insert(size_t index) { 177 return this->insert(index, 1, NULL); 178 } 179 T* insert(size_t index, size_t count, const T* src = NULL) { 180 SkASSERT(count); 181 SkASSERT(index <= fCount); 182 int oldCount = fCount; 183 this->growBy(count); 184 T* dst = fArray + index; 185 memmove(dst + count, dst, sizeof(T) * (oldCount - index)); 186 if (src) { 187 memcpy(dst, src, sizeof(T) * count); 188 } 189 return dst; 190 } 191 192 void remove(size_t index, size_t count = 1) { 193 SkASSERT(index + count <= fCount); 194 fCount = fCount - count; 195 memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index)); 196 } 197 198 void removeShuffle(size_t index) { 199 SkASSERT(index < fCount); 200 unsigned newCount = fCount - 1; 201 fCount = newCount; 202 if (index != newCount) { 203 memcpy(fArray + index, fArray + newCount, sizeof(T)); 204 } 205 } 206 207 int find(const T& elem) const { 208 const T* iter = fArray; 209 const T* stop = fArray + fCount; 210 211 for (; iter < stop; iter++) { 212 if (*iter == elem) { 213 return (int) (iter - fArray); 214 } 215 } 216 return -1; 217 } 218 219 int rfind(const T& elem) const { 220 const T* iter = fArray + fCount; 221 const T* stop = fArray; 222 223 while (iter > stop) { 224 if (*--iter == elem) { 225 return iter - stop; 226 } 227 } 228 return -1; 229 } 230 231 // routines to treat the array like a stack 232 T* push() { return this->append(); } 233 void push(const T& elem) { *this->append() = elem; } 234 const T& top() const { return (*this)[fCount - 1]; } 235 T& top() { return (*this)[fCount - 1]; } 236 void pop(T* elem) { if (elem) *elem = (*this)[fCount - 1]; --fCount; } 237 void pop() { --fCount; } 238 239 void deleteAll() { 240 T* iter = fArray; 241 T* stop = fArray + fCount; 242 while (iter < stop) { 243 delete (*iter); 244 iter += 1; 245 } 246 this->reset(); 247 } 248 249 void freeAll() { 250 T* iter = fArray; 251 T* stop = fArray + fCount; 252 while (iter < stop) { 253 sk_free(*iter); 254 iter += 1; 255 } 256 this->reset(); 257 } 258 259 void unrefAll() { 260 T* iter = fArray; 261 T* stop = fArray + fCount; 262 while (iter < stop) { 263 (*iter)->unref(); 264 iter += 1; 265 } 266 this->reset(); 267 } 268 269 void safeUnrefAll() { 270 T* iter = fArray; 271 T* stop = fArray + fCount; 272 while (iter < stop) { 273 SkSafeUnref(*iter); 274 iter += 1; 275 } 276 this->reset(); 277 } 278 279 #ifdef SK_DEBUG 280 void validate() const { 281 SkASSERT((fReserve == 0 && fArray == NULL) || 282 (fReserve > 0 && fArray != NULL)); 283 SkASSERT(fCount <= fReserve); 284 SkASSERT(fData == (ArrayT*)fArray); 285 } 286 #endif 287 288 private: 289 #ifdef SK_DEBUG 290 enum { 291 kDebugArraySize = 16 292 }; 293 typedef T ArrayT[kDebugArraySize]; 294 ArrayT* fData; 295 #endif 296 T* fArray; 297 size_t fReserve, fCount; 298 299 void growBy(size_t extra) { 300 SkASSERT(extra); 301 302 if (fCount + extra > fReserve) { 303 size_t size = fCount + extra + 4; 304 size += size >> 2; 305 306 fArray = (T*)sk_realloc_throw(fArray, size * sizeof(T)); 307 #ifdef SK_DEBUG 308 fData = (ArrayT*)fArray; 309 #endif 310 fReserve = size; 311 } 312 fCount += extra; 313 } 314 }; 315 316 #endif 317 318
