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#include "SkMalloc.h" 15 16template <typename T> class SkTDArray { 17public: 18 SkTDArray() : fArray(nullptr), fReserve(0), fCount(0) {} 19 SkTDArray(const T src[], int count) { 20 SkASSERT(src || count == 0); 21 22 fReserve = fCount = 0; 23 fArray = nullptr; 24 if (count) { 25 fArray = (T*)sk_malloc_throw(count * sizeof(T)); 26 memcpy(fArray, src, sizeof(T) * count); 27 fReserve = fCount = count; 28 } 29 } 30 SkTDArray(const SkTDArray<T>& src) : fArray(nullptr), fReserve(0), fCount(0) { 31 SkTDArray<T> tmp(src.fArray, src.fCount); 32 this->swap(tmp); 33 } 34 SkTDArray(SkTDArray<T>&& src) : fArray(nullptr), fReserve(0), fCount(0) { 35 this->swap(src); 36 } 37 ~SkTDArray() { 38 sk_free(fArray); 39 } 40 41 SkTDArray<T>& operator=(const SkTDArray<T>& src) { 42 if (this != &src) { 43 if (src.fCount > fReserve) { 44 SkTDArray<T> tmp(src.fArray, src.fCount); 45 this->swap(tmp); 46 } else { 47 sk_careful_memcpy(fArray, src.fArray, sizeof(T) * src.fCount); 48 fCount = src.fCount; 49 } 50 } 51 return *this; 52 } 53 SkTDArray<T>& operator=(SkTDArray<T>&& src) { 54 if (this != &src) { 55 this->swap(src); 56 src.reset(); 57 } 58 return *this; 59 } 60 61 friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) { 62 return a.fCount == b.fCount && 63 (a.fCount == 0 || 64 !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T))); 65 } 66 friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) { 67 return !(a == b); 68 } 69 70 void swap(SkTDArray<T>& other) { 71 SkTSwap(fArray, other.fArray); 72 SkTSwap(fReserve, other.fReserve); 73 SkTSwap(fCount, other.fCount); 74 } 75 76 // The deleter that ought to be used for a std:: smart pointer that takes ownership from 77 // release(). 78 struct Deleter { 79 void operator()(const void* p) { sk_free((void*)p); } 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* release() { 86 T* array = fArray; 87 fArray = nullptr; 88 fReserve = fCount = 0; 89 return array; 90 } 91 92 bool isEmpty() const { return fCount == 0; } 93 94 /** 95 * Return the number of elements in the array 96 */ 97 int count() const { return fCount; } 98 99 /** 100 * Return the total number of elements allocated. 101 * reserved() - count() gives you the number of elements you can add 102 * without causing an allocation. 103 */ 104 int reserved() const { return fReserve; } 105 106 /** 107 * return the number of bytes in the array: count * sizeof(T) 108 */ 109 size_t bytes() const { return fCount * sizeof(T); } 110 111 T* begin() { return fArray; } 112 const T* begin() const { return fArray; } 113 T* end() { return fArray ? fArray + fCount : nullptr; } 114 const T* end() const { return fArray ? fArray + fCount : nullptr; } 115 116 T& operator[](int index) { 117 SkASSERT(index < fCount); 118 return fArray[index]; 119 } 120 const T& operator[](int index) const { 121 SkASSERT(index < fCount); 122 return fArray[index]; 123 } 124 125 T& getAt(int index) { 126 return (*this)[index]; 127 } 128 const T& getAt(int index) const { 129 return (*this)[index]; 130 } 131 132 void reset() { 133 if (fArray) { 134 sk_free(fArray); 135 fArray = nullptr; 136 fReserve = fCount = 0; 137 } else { 138 SkASSERT(fReserve == 0 && fCount == 0); 139 } 140 } 141 142 void rewind() { 143 // same as setCount(0) 144 fCount = 0; 145 } 146 147 /** 148 * Sets the number of elements in the array. 149 * If the array does not have space for count elements, it will increase 150 * the storage allocated to some amount greater than that required. 151 * It will never shrink the storage. 152 */ 153 void setCount(int count) { 154 SkASSERT(count >= 0); 155 if (count > fReserve) { 156 this->resizeStorageToAtLeast(count); 157 } 158 fCount = count; 159 } 160 161 void setReserve(int reserve) { 162 if (reserve > fReserve) { 163 this->resizeStorageToAtLeast(reserve); 164 } 165 } 166 167 T* prepend() { 168 this->adjustCount(1); 169 memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T)); 170 return fArray; 171 } 172 173 T* append() { 174 return this->append(1, nullptr); 175 } 176 T* append(int count, const T* src = nullptr) { 177 int oldCount = fCount; 178 if (count) { 179 SkASSERT(src == nullptr || fArray == nullptr || 180 src + count <= fArray || fArray + oldCount <= src); 181 182 this->adjustCount(count); 183 if (src) { 184 memcpy(fArray + oldCount, src, sizeof(T) * count); 185 } 186 } 187 return fArray + oldCount; 188 } 189 190 T* appendClear() { 191 T* result = this->append(); 192 *result = 0; 193 return result; 194 } 195 196 T* insert(int index) { 197 return this->insert(index, 1, nullptr); 198 } 199 T* insert(int index, int count, const T* src = nullptr) { 200 SkASSERT(count); 201 SkASSERT(index <= fCount); 202 size_t oldCount = fCount; 203 this->adjustCount(count); 204 T* dst = fArray + index; 205 memmove(dst + count, dst, sizeof(T) * (oldCount - index)); 206 if (src) { 207 memcpy(dst, src, sizeof(T) * count); 208 } 209 return dst; 210 } 211 212 void remove(int index, int count = 1) { 213 SkASSERT(index + count <= fCount); 214 fCount = fCount - count; 215 memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index)); 216 } 217 218 void removeShuffle(int index) { 219 SkASSERT(index < fCount); 220 int newCount = fCount - 1; 221 fCount = newCount; 222 if (index != newCount) { 223 memcpy(fArray + index, fArray + newCount, sizeof(T)); 224 } 225 } 226 227 template <typename S> int select(S&& selector) const { 228 const T* iter = fArray; 229 const T* stop = fArray + fCount; 230 231 for (; iter < stop; iter++) { 232 if (selector(*iter)) { 233 return SkToInt(iter - fArray); 234 } 235 } 236 return -1; 237 } 238 239 int find(const T& elem) const { 240 const T* iter = fArray; 241 const T* stop = fArray + fCount; 242 243 for (; iter < stop; iter++) { 244 if (*iter == elem) { 245 return SkToInt(iter - fArray); 246 } 247 } 248 return -1; 249 } 250 251 int rfind(const T& elem) const { 252 const T* iter = fArray + fCount; 253 const T* stop = fArray; 254 255 while (iter > stop) { 256 if (*--iter == elem) { 257 return SkToInt(iter - stop); 258 } 259 } 260 return -1; 261 } 262 263 /** 264 * Returns true iff the array contains this element. 265 */ 266 bool contains(const T& elem) const { 267 return (this->find(elem) >= 0); 268 } 269 270 /** 271 * Copies up to max elements into dst. The number of items copied is 272 * capped by count - index. The actual number copied is returned. 273 */ 274 int copyRange(T* dst, int index, int max) const { 275 SkASSERT(max >= 0); 276 SkASSERT(!max || dst); 277 if (index >= fCount) { 278 return 0; 279 } 280 int count = SkMin32(max, fCount - index); 281 memcpy(dst, fArray + index, sizeof(T) * count); 282 return count; 283 } 284 285 void copy(T* dst) const { 286 this->copyRange(dst, 0, fCount); 287 } 288 289 // routines to treat the array like a stack 290 T* push() { return this->append(); } 291 void push(const T& elem) { *this->append() = elem; } 292 const T& top() const { return (*this)[fCount - 1]; } 293 T& top() { return (*this)[fCount - 1]; } 294 void pop(T* elem) { SkASSERT(fCount > 0); if (elem) *elem = (*this)[fCount - 1]; --fCount; } 295 void pop() { SkASSERT(fCount > 0); --fCount; } 296 297 void deleteAll() { 298 T* iter = fArray; 299 T* stop = fArray + fCount; 300 while (iter < stop) { 301 delete *iter; 302 iter += 1; 303 } 304 this->reset(); 305 } 306 307 void freeAll() { 308 T* iter = fArray; 309 T* stop = fArray + fCount; 310 while (iter < stop) { 311 sk_free(*iter); 312 iter += 1; 313 } 314 this->reset(); 315 } 316 317 void unrefAll() { 318 T* iter = fArray; 319 T* stop = fArray + fCount; 320 while (iter < stop) { 321 (*iter)->unref(); 322 iter += 1; 323 } 324 this->reset(); 325 } 326 327 void safeUnrefAll() { 328 T* iter = fArray; 329 T* stop = fArray + fCount; 330 while (iter < stop) { 331 SkSafeUnref(*iter); 332 iter += 1; 333 } 334 this->reset(); 335 } 336 337 void visitAll(void visitor(T&)) { 338 T* stop = this->end(); 339 for (T* curr = this->begin(); curr < stop; curr++) { 340 if (*curr) { 341 visitor(*curr); 342 } 343 } 344 } 345 346#ifdef SK_DEBUG 347 void validate() const { 348 SkASSERT((fReserve == 0 && fArray == nullptr) || 349 (fReserve > 0 && fArray != nullptr)); 350 SkASSERT(fCount <= fReserve); 351 } 352#endif 353 354 void shrinkToFit() { 355 fReserve = fCount; 356 fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T)); 357 } 358 359private: 360 T* fArray; 361 int fReserve; 362 int fCount; 363 364 /** 365 * Adjusts the number of elements in the array. 366 * This is the same as calling setCount(count() + delta). 367 */ 368 void adjustCount(int delta) { 369 this->setCount(fCount + delta); 370 } 371 372 /** 373 * Increase the storage allocation such that it can hold (fCount + extra) 374 * elements. 375 * It never shrinks the allocation, and it may increase the allocation by 376 * more than is strictly required, based on a private growth heuristic. 377 * 378 * note: does NOT modify fCount 379 */ 380 void resizeStorageToAtLeast(int count) { 381 SkASSERT(count > fReserve); 382 fReserve = count + 4; 383 fReserve += fReserve / 4; 384 fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T)); 385 } 386}; 387 388#endif 389