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, int dst, int src) { 21 memcpy(&self->fItemArray[dst], &self->fItemArray[src], sizeof(T)); 22} 23template<typename T> 24inline void copy(SkTArray<T, true>* self, const T* array) { 25 memcpy(self->fMemArray, array, self->fCount * sizeof(T)); 26} 27template<typename T> 28inline void copyAndDelete(SkTArray<T, true>* self, char* newMemArray) { 29 memcpy(newMemArray, self->fMemArray, self->fCount * sizeof(T)); 30} 31 32template<typename T> 33inline void copy(SkTArray<T, false>* self, int dst, int src) { 34 SkNEW_PLACEMENT_ARGS(&self->fItemArray[dst], T, (self->fItemArray[src])); 35} 36template<typename T> 37inline void copy(SkTArray<T, false>* self, const T* array) { 38 for (int i = 0; i < self->fCount; ++i) { 39 SkNEW_PLACEMENT_ARGS(self->fItemArray + i, T, (array[i])); 40 } 41} 42template<typename T> 43inline void copyAndDelete(SkTArray<T, false>* self, char* newMemArray) { 44 for (int i = 0; i < self->fCount; ++i) { 45 SkNEW_PLACEMENT_ARGS(newMemArray + sizeof(T) * i, T, (self->fItemArray[i])); 46 self->fItemArray[i].~T(); 47 } 48} 49 50} 51 52template <typename T, bool MEM_COPY> void* operator new(size_t, SkTArray<T, MEM_COPY>*, int); 53 54/** When MEM_COPY is true T will be bit copied when moved. 55 When MEM_COPY is false, T will be copy constructed / destructed. 56 In all cases T will be default-initialized on allocation, 57 and its destructor will be called from this object's destructor. 58*/ 59template <typename T, bool MEM_COPY> class SkTArray { 60public: 61 /** 62 * Creates an empty array with no initial storage 63 */ 64 SkTArray() { 65 fCount = 0; 66 fReserveCount = gMIN_ALLOC_COUNT; 67 fAllocCount = 0; 68 fMemArray = NULL; 69 fPreAllocMemArray = NULL; 70 } 71 72 /** 73 * Creates an empty array that will preallocate space for reserveCount 74 * elements. 75 */ 76 explicit SkTArray(int reserveCount) { 77 this->init(NULL, 0, NULL, reserveCount); 78 } 79 80 /** 81 * Copies one array to another. The new array will be heap allocated. 82 */ 83 explicit SkTArray(const SkTArray& array) { 84 this->init(array.fItemArray, array.fCount, NULL, 0); 85 } 86 87 /** 88 * Creates a SkTArray by copying contents of a standard C array. The new 89 * array will be heap allocated. Be careful not to use this constructor 90 * when you really want the (void*, int) version. 91 */ 92 SkTArray(const T* array, int count) { 93 this->init(array, count, NULL, 0); 94 } 95 96 /** 97 * assign copy of array to this 98 */ 99 SkTArray& operator =(const SkTArray& array) { 100 for (int i = 0; i < fCount; ++i) { 101 fItemArray[i].~T(); 102 } 103 fCount = 0; 104 this->checkRealloc((int)array.count()); 105 fCount = array.count(); 106 SkTArrayExt::copy(this, static_cast<const T*>(array.fMemArray)); 107 return *this; 108 } 109 110 virtual ~SkTArray() { 111 for (int i = 0; i < fCount; ++i) { 112 fItemArray[i].~T(); 113 } 114 if (fMemArray != fPreAllocMemArray) { 115 sk_free(fMemArray); 116 } 117 } 118 119 /** 120 * Resets to count() == 0 121 */ 122 void reset() { this->pop_back_n(fCount); } 123 124 /** 125 * Resets to count() = n newly constructed T objects. 126 */ 127 void reset(int n) { 128 SkASSERT(n >= 0); 129 for (int i = 0; i < fCount; ++i) { 130 fItemArray[i].~T(); 131 } 132 // set fCount to 0 before calling checkRealloc so that no copy cons. are called. 133 fCount = 0; 134 this->checkRealloc(n); 135 fCount = n; 136 for (int i = 0; i < fCount; ++i) { 137 SkNEW_PLACEMENT(fItemArray + i, T); 138 } 139 } 140 141 /** 142 * Resets to a copy of a C array. 143 */ 144 void reset(const T* array, int count) { 145 for (int i = 0; i < fCount; ++i) { 146 fItemArray[i].~T(); 147 } 148 int delta = count - fCount; 149 this->checkRealloc(delta); 150 fCount = count; 151 SkTArrayExt::copy(this, array); 152 } 153 154 void removeShuffle(int n) { 155 SkASSERT(n < fCount); 156 int newCount = fCount - 1; 157 fCount = newCount; 158 fItemArray[n].~T(); 159 if (n != newCount) { 160 SkTArrayExt::copy(this, n, newCount); 161 fItemArray[newCount].~T(); 162 } 163 } 164 165 /** 166 * Number of elements in the array. 167 */ 168 int count() const { return fCount; } 169 170 /** 171 * Is the array empty. 172 */ 173 bool empty() const { return !fCount; } 174 175 /** 176 * Adds 1 new default-initialized T value and returns it by reference. Note 177 * the reference only remains valid until the next call that adds or removes 178 * elements. 179 */ 180 T& push_back() { 181 T* newT = reinterpret_cast<T*>(this->push_back_raw(1)); 182 SkNEW_PLACEMENT(newT, T); 183 return *newT; 184 } 185 186 /** 187 * Version of above that uses a copy constructor to initialize the new item 188 */ 189 T& push_back(const T& t) { 190 T* newT = reinterpret_cast<T*>(this->push_back_raw(1)); 191 SkNEW_PLACEMENT_ARGS(newT, T, (t)); 192 return *newT; 193 } 194 195 /** 196 * Allocates n more default-initialized T values, and returns the address of 197 * the start of that new range. Note: this address is only valid until the 198 * next API call made on the array that might add or remove elements. 199 */ 200 T* push_back_n(int n) { 201 SkASSERT(n >= 0); 202 T* newTs = reinterpret_cast<T*>(this->push_back_raw(n)); 203 for (int i = 0; i < n; ++i) { 204 SkNEW_PLACEMENT(newTs + i, T); 205 } 206 return newTs; 207 } 208 209 /** 210 * Version of above that uses a copy constructor to initialize all n items 211 * to the same T. 212 */ 213 T* push_back_n(int n, const T& t) { 214 SkASSERT(n >= 0); 215 T* newTs = reinterpret_cast<T*>(this->push_back_raw(n)); 216 for (int i = 0; i < n; ++i) { 217 SkNEW_PLACEMENT_ARGS(newTs[i], T, (t)); 218 } 219 return newTs; 220 } 221 222 /** 223 * Version of above that uses a copy constructor to initialize the n items 224 * to separate T values. 225 */ 226 T* push_back_n(int n, const T t[]) { 227 SkASSERT(n >= 0); 228 this->checkRealloc(n); 229 for (int i = 0; i < n; ++i) { 230 SkNEW_PLACEMENT_ARGS(fItemArray + fCount + i, T, (t[i])); 231 } 232 fCount += n; 233 return fItemArray + fCount - n; 234 } 235 236 /** 237 * Removes the last element. Not safe to call when count() == 0. 238 */ 239 void pop_back() { 240 SkASSERT(fCount > 0); 241 --fCount; 242 fItemArray[fCount].~T(); 243 this->checkRealloc(0); 244 } 245 246 /** 247 * Removes the last n elements. Not safe to call when count() < n. 248 */ 249 void pop_back_n(int n) { 250 SkASSERT(n >= 0); 251 SkASSERT(fCount >= n); 252 fCount -= n; 253 for (int i = 0; i < n; ++i) { 254 fItemArray[fCount + i].~T(); 255 } 256 this->checkRealloc(0); 257 } 258 259 /** 260 * Pushes or pops from the back to resize. Pushes will be default 261 * initialized. 262 */ 263 void resize_back(int newCount) { 264 SkASSERT(newCount >= 0); 265 266 if (newCount > fCount) { 267 this->push_back_n(newCount - fCount); 268 } else if (newCount < fCount) { 269 this->pop_back_n(fCount - newCount); 270 } 271 } 272 273 /** Swaps the contents of this array with that array. Does a pointer swap if possible, 274 otherwise copies the T values. */ 275 void swap(SkTArray* that) { 276 if (this == that) { 277 return; 278 } 279 if (this->fPreAllocMemArray != this->fItemArray && 280 that->fPreAllocMemArray != that->fItemArray) { 281 // If neither is using a preallocated array then just swap. 282 SkTSwap(fItemArray, that->fItemArray); 283 SkTSwap(fCount, that->fCount); 284 SkTSwap(fAllocCount, that->fAllocCount); 285 } else { 286 // This could be more optimal... 287 SkTArray copy(*that); 288 *that = *this; 289 *this = copy; 290 } 291 } 292 293 T* begin() { 294 return fItemArray; 295 } 296 const T* begin() const { 297 return fItemArray; 298 } 299 T* end() { 300 return fItemArray ? fItemArray + fCount : NULL; 301 } 302 const T* end() const { 303 return fItemArray ? fItemArray + fCount : NULL; 304 } 305 306 /** 307 * Get the i^th element. 308 */ 309 T& operator[] (int i) { 310 SkASSERT(i < fCount); 311 SkASSERT(i >= 0); 312 return fItemArray[i]; 313 } 314 315 const T& operator[] (int i) const { 316 SkASSERT(i < fCount); 317 SkASSERT(i >= 0); 318 return fItemArray[i]; 319 } 320 321 /** 322 * equivalent to operator[](0) 323 */ 324 T& front() { SkASSERT(fCount > 0); return fItemArray[0];} 325 326 const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];} 327 328 /** 329 * equivalent to operator[](count() - 1) 330 */ 331 T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];} 332 333 const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];} 334 335 /** 336 * equivalent to operator[](count()-1-i) 337 */ 338 T& fromBack(int i) { 339 SkASSERT(i >= 0); 340 SkASSERT(i < fCount); 341 return fItemArray[fCount - i - 1]; 342 } 343 344 const T& fromBack(int i) const { 345 SkASSERT(i >= 0); 346 SkASSERT(i < fCount); 347 return fItemArray[fCount - i - 1]; 348 } 349 350 bool operator==(const SkTArray<T, MEM_COPY>& right) const { 351 int leftCount = this->count(); 352 if (leftCount != right.count()) { 353 return false; 354 } 355 for (int index = 0; index < leftCount; ++index) { 356 if (fItemArray[index] != right.fItemArray[index]) { 357 return false; 358 } 359 } 360 return true; 361 } 362 363 bool operator!=(const SkTArray<T, MEM_COPY>& right) const { 364 return !(*this == right); 365 } 366 367protected: 368 /** 369 * Creates an empty array that will use the passed storage block until it 370 * is insufficiently large to hold the entire array. 371 */ 372 template <int N> 373 SkTArray(SkAlignedSTStorage<N,T>* storage) { 374 this->init(NULL, 0, storage->get(), N); 375 } 376 377 /** 378 * Copy another array, using preallocated storage if preAllocCount >= 379 * array.count(). Otherwise storage will only be used when array shrinks 380 * to fit. 381 */ 382 template <int N> 383 SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) { 384 this->init(array.fItemArray, array.fCount, storage->get(), N); 385 } 386 387 /** 388 * Copy a C array, using preallocated storage if preAllocCount >= 389 * count. Otherwise storage will only be used when array shrinks 390 * to fit. 391 */ 392 template <int N> 393 SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) { 394 this->init(array, count, storage->get(), N); 395 } 396 397 void init(const T* array, int count, 398 void* preAllocStorage, int preAllocOrReserveCount) { 399 SkASSERT(count >= 0); 400 SkASSERT(preAllocOrReserveCount >= 0); 401 fCount = count; 402 fReserveCount = (preAllocOrReserveCount > 0) ? 403 preAllocOrReserveCount : 404 gMIN_ALLOC_COUNT; 405 fPreAllocMemArray = preAllocStorage; 406 if (fReserveCount >= fCount && 407 preAllocStorage) { 408 fAllocCount = fReserveCount; 409 fMemArray = preAllocStorage; 410 } else { 411 fAllocCount = SkMax32(fCount, fReserveCount); 412 fMemArray = sk_malloc_throw(fAllocCount * sizeof(T)); 413 } 414 415 SkTArrayExt::copy(this, array); 416 } 417 418private: 419 420 static const int gMIN_ALLOC_COUNT = 8; 421 422 // Helper function that makes space for n objects, adjusts the count, but does not initialize 423 // the new objects. 424 void* push_back_raw(int n) { 425 this->checkRealloc(n); 426 void* ptr = fItemArray + fCount; 427 fCount += n; 428 return ptr; 429 } 430 431 inline void checkRealloc(int delta) { 432 SkASSERT(fCount >= 0); 433 SkASSERT(fAllocCount >= 0); 434 435 SkASSERT(-delta <= fCount); 436 437 int newCount = fCount + delta; 438 int newAllocCount = fAllocCount; 439 440 if (newCount > fAllocCount || newCount < (fAllocCount / 3)) { 441 // whether we're growing or shrinking, we leave at least 50% extra space for future 442 // growth (clamped to the reserve count). 443 newAllocCount = SkMax32(newCount + ((newCount + 1) >> 1), fReserveCount); 444 } 445 if (newAllocCount != fAllocCount) { 446 447 fAllocCount = newAllocCount; 448 char* newMemArray; 449 450 if (fAllocCount == fReserveCount && fPreAllocMemArray) { 451 newMemArray = (char*) fPreAllocMemArray; 452 } else { 453 newMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T)); 454 } 455 456 SkTArrayExt::copyAndDelete<T>(this, newMemArray); 457 458 if (fMemArray != fPreAllocMemArray) { 459 sk_free(fMemArray); 460 } 461 fMemArray = newMemArray; 462 } 463 } 464 465 friend void* operator new<T>(size_t, SkTArray*, int); 466 467 template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, int dst, int src); 468 template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, const X*); 469 template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, true>* that, char*); 470 471 template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, int dst, int src); 472 template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, const X*); 473 template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, false>* that, char*); 474 475 int fReserveCount; 476 int fCount; 477 int fAllocCount; 478 void* fPreAllocMemArray; 479 union { 480 T* fItemArray; 481 void* fMemArray; 482 }; 483}; 484 485// Use the below macro (SkNEW_APPEND_TO_TARRAY) rather than calling this directly 486template <typename T, bool MEM_COPY> 487void* operator new(size_t, SkTArray<T, MEM_COPY>* array, int SkDEBUGCODE(atIndex)) { 488 // Currently, we only support adding to the end of the array. When the array class itself 489 // supports random insertion then this should be updated. 490 // SkASSERT(atIndex >= 0 && atIndex <= array->count()); 491 SkASSERT(atIndex == array->count()); 492 return array->push_back_raw(1); 493} 494 495// Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete 496// to match the op new silences warnings about missing op delete when a constructor throws an 497// exception. 498template <typename T, bool MEM_COPY> 499void operator delete(void*, SkTArray<T, MEM_COPY>* /*array*/, int /*atIndex*/) { 500 SK_CRASH(); 501} 502 503// Constructs a new object as the last element of an SkTArray. 504#define SkNEW_APPEND_TO_TARRAY(array_ptr, type_name, args) \ 505 (new ((array_ptr), (array_ptr)->count()) type_name args) 506 507 508/** 509 * Subclass of SkTArray that contains a preallocated memory block for the array. 510 */ 511template <int N, typename T, bool MEM_COPY = false> 512class SkSTArray : public SkTArray<T, MEM_COPY> { 513private: 514 typedef SkTArray<T, MEM_COPY> INHERITED; 515 516public: 517 SkSTArray() : INHERITED(&fStorage) { 518 } 519 520 SkSTArray(const SkSTArray& array) 521 : INHERITED(array, &fStorage) { 522 } 523 524 explicit SkSTArray(const INHERITED& array) 525 : INHERITED(array, &fStorage) { 526 } 527 528 explicit SkSTArray(int reserveCount) 529 : INHERITED(reserveCount) { 530 } 531 532 SkSTArray(const T* array, int count) 533 : INHERITED(array, count, &fStorage) { 534 } 535 536 SkSTArray& operator= (const SkSTArray& array) { 537 return *this = *(const INHERITED*)&array; 538 } 539 540 SkSTArray& operator= (const INHERITED& array) { 541 INHERITED::operator=(array); 542 return *this; 543 } 544 545private: 546 SkAlignedSTStorage<N,T> fStorage; 547}; 548 549#endif 550