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