1/* 2 * Copyright 2011 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8#ifndef SkTArray_DEFINED 9#define SkTArray_DEFINED 10 11#include <new> 12#include "SkTypes.h" 13#include "SkTemplates.h" 14 15template <typename T, bool MEM_COPY = false> class SkTArray; 16 17namespace SkTArrayExt { 18 19template<typename T> 20inline void copy(SkTArray<T, true>* self, const T* array) { 21 memcpy(self->fMemArray, array, self->fCount * sizeof(T)); 22} 23template<typename T> 24inline void copyAndDelete(SkTArray<T, true>* self, char* newMemArray) { 25 memcpy(newMemArray, self->fMemArray, self->fCount * sizeof(T)); 26} 27 28template<typename T> 29inline void copy(SkTArray<T, false>* self, const T* array) { 30 for (int i = 0; i < self->fCount; ++i) { 31 new (self->fItemArray + i) T(array[i]); 32 } 33} 34template<typename T> 35inline void copyAndDelete(SkTArray<T, false>* self, char* newMemArray) { 36 for (int i = 0; i < self->fCount; ++i) { 37 new (newMemArray + sizeof(T) * i) T(self->fItemArray[i]); 38 self->fItemArray[i].~T(); 39 } 40} 41 42} 43 44/** When MEM_COPY is true T will be bit copied when moved. 45 When MEM_COPY is false, T will be copy constructed / destructed. 46 In all cases T's constructor will be called on allocation, 47 and its destructor will be called from this object's destructor. 48*/ 49template <typename T, bool MEM_COPY> class SkTArray { 50public: 51 /** 52 * Creates an empty array with no initial storage 53 */ 54 SkTArray() { 55 fCount = 0; 56 fReserveCount = gMIN_ALLOC_COUNT; 57 fAllocCount = 0; 58 fMemArray = NULL; 59 fPreAllocMemArray = NULL; 60 } 61 62 /** 63 * Creates an empty array that will preallocate space for reserveCount 64 * elements. 65 */ 66 explicit SkTArray(int reserveCount) { 67 this->init(NULL, 0, NULL, reserveCount); 68 } 69 70 /** 71 * Copies one array to another. The new array will be heap allocated. 72 */ 73 explicit SkTArray(const SkTArray& array) { 74 this->init(array.fItemArray, array.fCount, NULL, 0); 75 } 76 77 /** 78 * Creates a SkTArray by copying contents of a standard C array. The new 79 * array will be heap allocated. Be careful not to use this constructor 80 * when you really want the (void*, int) version. 81 */ 82 SkTArray(const T* array, int count) { 83 this->init(array, count, NULL, 0); 84 } 85 86 /** 87 * assign copy of array to this 88 */ 89 SkTArray& operator =(const SkTArray& array) { 90 for (int i = 0; i < fCount; ++i) { 91 fItemArray[i].~T(); 92 } 93 fCount = 0; 94 checkRealloc((int)array.count()); 95 fCount = array.count(); 96 SkTArrayExt::copy(this, static_cast<const T*>(array.fMemArray)); 97 return *this; 98 } 99 100 virtual ~SkTArray() { 101 for (int i = 0; i < fCount; ++i) { 102 fItemArray[i].~T(); 103 } 104 if (fMemArray != fPreAllocMemArray) { 105 sk_free(fMemArray); 106 } 107 } 108 109 /** 110 * Resets to count() == 0 111 */ 112 void reset() { this->pop_back_n(fCount); } 113 114 /** 115 * Number of elements in the array. 116 */ 117 int count() const { return fCount; } 118 119 /** 120 * Is the array empty. 121 */ 122 bool empty() const { return !fCount; } 123 124 /** 125 * Adds 1 new default-constructed T value and returns in by reference. Note 126 * the reference only remains valid until the next call that adds or removes 127 * elements. 128 */ 129 T& push_back() { 130 checkRealloc(1); 131 new ((char*)fMemArray+sizeof(T)*fCount) T; 132 ++fCount; 133 return fItemArray[fCount-1]; 134 } 135 136 /** 137 * Version of above that uses a copy constructor to initialize the new item 138 */ 139 T& push_back(const T& t) { 140 checkRealloc(1); 141 new ((char*)fMemArray+sizeof(T)*fCount) T(t); 142 ++fCount; 143 return fItemArray[fCount-1]; 144 } 145 146 /** 147 * Allocates n more default T values, and returns the address of the start 148 * of that new range. Note: this address is only valid until the next API 149 * call made on the array that might add or remove elements. 150 */ 151 T* push_back_n(int n) { 152 SkASSERT(n >= 0); 153 checkRealloc(n); 154 for (int i = 0; i < n; ++i) { 155 new (fItemArray + fCount + i) T; 156 } 157 fCount += n; 158 return fItemArray + fCount - n; 159 } 160 161 /** 162 * Version of above that uses a copy constructor to initialize all n items 163 * to the same T. 164 */ 165 T* push_back_n(int n, const T& t) { 166 SkASSERT(n >= 0); 167 checkRealloc(n); 168 for (int i = 0; i < n; ++i) { 169 new (fItemArray + fCount + i) T(t); 170 } 171 fCount += n; 172 return fItemArray + fCount - n; 173 } 174 175 /** 176 * Version of above that uses a copy constructor to initialize the n items 177 * to separate T values. 178 */ 179 T* push_back_n(int n, const T t[]) { 180 SkASSERT(n >= 0); 181 checkRealloc(n); 182 for (int i = 0; i < n; ++i) { 183 new (fItemArray + fCount + i) T(t[i]); 184 } 185 fCount += n; 186 return fItemArray + fCount - n; 187 } 188 189 /** 190 * Removes the last element. Not safe to call when count() == 0. 191 */ 192 void pop_back() { 193 SkASSERT(fCount > 0); 194 --fCount; 195 fItemArray[fCount].~T(); 196 checkRealloc(0); 197 } 198 199 /** 200 * Removes the last n elements. Not safe to call when count() < n. 201 */ 202 void pop_back_n(int n) { 203 SkASSERT(n >= 0); 204 SkASSERT(fCount >= n); 205 fCount -= n; 206 for (int i = 0; i < n; ++i) { 207 fItemArray[i].~T(); 208 } 209 checkRealloc(0); 210 } 211 212 /** 213 * Pushes or pops from the back to resize. Pushes will be default 214 * initialized. 215 */ 216 void resize_back(int newCount) { 217 SkASSERT(newCount >= 0); 218 219 if (newCount > fCount) { 220 push_back_n(newCount - fCount); 221 } else if (newCount < fCount) { 222 pop_back_n(fCount - newCount); 223 } 224 } 225 226 /** 227 * Get the i^th element. 228 */ 229 T& operator[] (int i) { 230 SkASSERT(i < fCount); 231 SkASSERT(i >= 0); 232 return fItemArray[i]; 233 } 234 235 const T& operator[] (int i) const { 236 SkASSERT(i < fCount); 237 SkASSERT(i >= 0); 238 return fItemArray[i]; 239 } 240 241 /** 242 * equivalent to operator[](0) 243 */ 244 T& front() { SkASSERT(fCount > 0); return fItemArray[0];} 245 246 const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];} 247 248 /** 249 * equivalent to operator[](count() - 1) 250 */ 251 T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];} 252 253 const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];} 254 255 /** 256 * equivalent to operator[](count()-1-i) 257 */ 258 T& fromBack(int i) { 259 SkASSERT(i >= 0); 260 SkASSERT(i < fCount); 261 return fItemArray[fCount - i - 1]; 262 } 263 264 const T& fromBack(int i) const { 265 SkASSERT(i >= 0); 266 SkASSERT(i < fCount); 267 return fItemArray[fCount - i - 1]; 268 } 269 270protected: 271 /** 272 * Creates an empty array that will use the passed storage block until it 273 * is insufficiently large to hold the entire array. 274 */ 275 template <int N> 276 SkTArray(SkAlignedSTStorage<N,T>* storage) { 277 this->init(NULL, 0, storage->get(), N); 278 } 279 280 /** 281 * Copy another array, using preallocated storage if preAllocCount >= 282 * array.count(). Otherwise storage will only be used when array shrinks 283 * to fit. 284 */ 285 template <int N> 286 SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) { 287 this->init(array.fItemArray, array.fCount, storage->get(), N); 288 } 289 290 /** 291 * Copy a C array, using preallocated storage if preAllocCount >= 292 * count. Otherwise storage will only be used when array shrinks 293 * to fit. 294 */ 295 template <int N> 296 SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) { 297 this->init(array, count, storage->get(), N); 298 } 299 300 void init(const T* array, int count, 301 void* preAllocStorage, int preAllocOrReserveCount) { 302 SkASSERT(count >= 0); 303 SkASSERT(preAllocOrReserveCount >= 0); 304 fCount = count; 305 fReserveCount = (preAllocOrReserveCount > 0) ? 306 preAllocOrReserveCount : 307 gMIN_ALLOC_COUNT; 308 fPreAllocMemArray = preAllocStorage; 309 if (fReserveCount >= fCount && 310 NULL != preAllocStorage) { 311 fAllocCount = fReserveCount; 312 fMemArray = preAllocStorage; 313 } else { 314 fAllocCount = SkMax32(fCount, fReserveCount); 315 fMemArray = sk_malloc_throw(fAllocCount * sizeof(T)); 316 } 317 318 SkTArrayExt::copy(this, array); 319 } 320 321private: 322 323 static const int gMIN_ALLOC_COUNT = 8; 324 325 inline void checkRealloc(int delta) { 326 SkASSERT(fCount >= 0); 327 SkASSERT(fAllocCount >= 0); 328 329 SkASSERT(-delta <= fCount); 330 331 int newCount = fCount + delta; 332 int newAllocCount = fAllocCount; 333 334 if (newCount > fAllocCount) { 335 newAllocCount = SkMax32(newCount + ((newCount + 1) >> 1), 336 fReserveCount); 337 } else if (newCount < fAllocCount / 3) { 338 newAllocCount = SkMax32(fAllocCount / 2, fReserveCount); 339 } 340 341 if (newAllocCount != fAllocCount) { 342 343 fAllocCount = newAllocCount; 344 char* newMemArray; 345 346 if (fAllocCount == fReserveCount && NULL != fPreAllocMemArray) { 347 newMemArray = (char*) fPreAllocMemArray; 348 } else { 349 newMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T)); 350 } 351 352 SkTArrayExt::copyAndDelete<T>(this, newMemArray); 353 354 if (fMemArray != fPreAllocMemArray) { 355 sk_free(fMemArray); 356 } 357 fMemArray = newMemArray; 358 } 359 } 360 361 template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, const X*); 362 template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, true>* that, char*); 363 364 template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, const X*); 365 template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, false>* that, char*); 366 367 int fReserveCount; 368 int fCount; 369 int fAllocCount; 370 void* fPreAllocMemArray; 371 union { 372 T* fItemArray; 373 void* fMemArray; 374 }; 375}; 376 377/** 378 * Subclass of SkTArray that contains a preallocated memory block for the array. 379 */ 380template <int N, typename T, bool DATA_TYPE = false> 381class SkSTArray : public SkTArray<T, DATA_TYPE> { 382private: 383 typedef SkTArray<T, DATA_TYPE> INHERITED; 384 385public: 386 SkSTArray() : INHERITED(&fStorage) { 387 } 388 389 SkSTArray(const SkSTArray& array) 390 : INHERITED(array, &fStorage) { 391 } 392 393 explicit SkSTArray(const INHERITED& array) 394 : INHERITED(array, &fStorage) { 395 } 396 397 SkSTArray(const T* array, int count) 398 : INHERITED(array, count, &fStorage) { 399 } 400 401 SkSTArray& operator= (const SkSTArray& array) { 402 return *this = *(const INHERITED*)&array; 403 } 404 405 SkSTArray& operator= (const INHERITED& array) { 406 INHERITED::operator=(array); 407 return *this; 408 } 409 410private: 411 SkAlignedSTStorage<N,T> fStorage; 412}; 413 414#endif 415 416