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 "../private/SkTLogic.h" 12 #include "../private/SkTemplates.h" 13 #include "SkTypes.h" 14 15 #include <new> 16 #include <utility> 17 18 /** When MEM_MOVE is true T will be bit copied when moved. 19 When MEM_MOVE is false, T will be copy constructed / destructed. 20 In all cases T will be default-initialized on allocation, 21 and its destructor will be called from this object's destructor. 22 */ 23 template <typename T, bool MEM_MOVE = false> class SkTArray { 24 public: 25 /** 26 * Creates an empty array with no initial storage 27 */ 28 SkTArray() { this->init(); } 29 30 /** 31 * Creates an empty array that will preallocate space for reserveCount 32 * elements. 33 */ 34 explicit SkTArray(int reserveCount) { this->init(0, reserveCount); } 35 36 /** 37 * Copies one array to another. The new array will be heap allocated. 38 */ 39 explicit SkTArray(const SkTArray& that) { 40 this->init(that.fCount); 41 this->copy(that.fItemArray); 42 } 43 44 explicit SkTArray(SkTArray&& that) { 45 // TODO: If 'that' owns its memory why don't we just steal the pointer? 46 this->init(that.fCount); 47 that.move(fMemArray); 48 that.fCount = 0; 49 } 50 51 /** 52 * Creates a SkTArray by copying contents of a standard C array. The new 53 * array will be heap allocated. Be careful not to use this constructor 54 * when you really want the (void*, int) version. 55 */ 56 SkTArray(const T* array, int count) { 57 this->init(count); 58 this->copy(array); 59 } 60 61 SkTArray& operator=(const SkTArray& that) { 62 if (this == &that) { 63 return *this; 64 } 65 for (int i = 0; i < fCount; ++i) { 66 fItemArray[i].~T(); 67 } 68 fCount = 0; 69 this->checkRealloc(that.count()); 70 fCount = that.count(); 71 this->copy(that.fItemArray); 72 return *this; 73 } 74 SkTArray& operator=(SkTArray&& that) { 75 if (this == &that) { 76 return *this; 77 } 78 for (int i = 0; i < fCount; ++i) { 79 fItemArray[i].~T(); 80 } 81 fCount = 0; 82 this->checkRealloc(that.count()); 83 fCount = that.count(); 84 that.move(fMemArray); 85 that.fCount = 0; 86 return *this; 87 } 88 89 ~SkTArray() { 90 for (int i = 0; i < fCount; ++i) { 91 fItemArray[i].~T(); 92 } 93 if (fOwnMemory) { 94 sk_free(fMemArray); 95 } 96 } 97 98 /** 99 * Resets to count() == 0 100 */ 101 void reset() { this->pop_back_n(fCount); } 102 103 /** 104 * Resets to count() = n newly constructed T objects. 105 */ 106 void reset(int n) { 107 SkASSERT(n >= 0); 108 for (int i = 0; i < fCount; ++i) { 109 fItemArray[i].~T(); 110 } 111 // Set fCount to 0 before calling checkRealloc so that no elements are moved. 112 fCount = 0; 113 this->checkRealloc(n); 114 fCount = n; 115 for (int i = 0; i < fCount; ++i) { 116 new (fItemArray + i) T; 117 } 118 } 119 120 /** 121 * Ensures there is enough reserved space for n elements. 122 */ 123 void reserve(int n) { 124 if (fCount < n) { 125 this->checkRealloc(n - fCount); 126 } 127 } 128 129 /** 130 * Resets to a copy of a C array. 131 */ 132 void reset(const T* array, int count) { 133 for (int i = 0; i < fCount; ++i) { 134 fItemArray[i].~T(); 135 } 136 fCount = 0; 137 this->checkRealloc(count); 138 fCount = count; 139 this->copy(array); 140 } 141 142 void removeShuffle(int n) { 143 SkASSERT(n < fCount); 144 int newCount = fCount - 1; 145 fCount = newCount; 146 fItemArray[n].~T(); 147 if (n != newCount) { 148 this->move(n, newCount); 149 } 150 } 151 152 /** 153 * Number of elements in the array. 154 */ 155 int count() const { return fCount; } 156 157 /** 158 * Is the array empty. 159 */ 160 bool empty() const { return !fCount; } 161 162 /** 163 * Adds 1 new default-initialized T value and returns it by reference. Note 164 * the reference only remains valid until the next call that adds or removes 165 * elements. 166 */ 167 T& push_back() { 168 void* newT = this->push_back_raw(1); 169 return *new (newT) T; 170 } 171 172 /** 173 * Version of above that uses a copy constructor to initialize the new item 174 */ 175 T& push_back(const T& t) { 176 void* newT = this->push_back_raw(1); 177 return *new (newT) T(t); 178 } 179 180 /** 181 * Version of above that uses a move constructor to initialize the new item 182 */ 183 T& push_back(T&& t) { 184 void* newT = this->push_back_raw(1); 185 return *new (newT) T(std::move(t)); 186 } 187 188 /** 189 * Construct a new T at the back of this array. 190 */ 191 template<class... Args> T& emplace_back(Args&&... args) { 192 void* newT = this->push_back_raw(1); 193 return *new (newT) T(std::forward<Args>(args)...); 194 } 195 196 /** 197 * Allocates n more default-initialized T values, and returns the address of 198 * the start of that new range. Note: this address is only valid until the 199 * next API call made on the array that might add or remove elements. 200 */ 201 T* push_back_n(int n) { 202 SkASSERT(n >= 0); 203 void* newTs = this->push_back_raw(n); 204 for (int i = 0; i < n; ++i) { 205 new (static_cast<char*>(newTs) + i * sizeof(T)) T; 206 } 207 return static_cast<T*>(newTs); 208 } 209 210 /** 211 * Version of above that uses a copy constructor to initialize all n items 212 * to the same T. 213 */ 214 T* push_back_n(int n, const T& t) { 215 SkASSERT(n >= 0); 216 void* newTs = this->push_back_raw(n); 217 for (int i = 0; i < n; ++i) { 218 new (static_cast<char*>(newTs) + i * sizeof(T)) T(t); 219 } 220 return static_cast<T*>(newTs); 221 } 222 223 /** 224 * Version of above that uses a copy constructor to initialize the n items 225 * to separate T values. 226 */ 227 T* push_back_n(int n, const T t[]) { 228 SkASSERT(n >= 0); 229 this->checkRealloc(n); 230 for (int i = 0; i < n; ++i) { 231 new (fItemArray + fCount + i) T(t[i]); 232 } 233 fCount += n; 234 return fItemArray + fCount - n; 235 } 236 237 /** 238 * Version of above that uses the move constructor to set n items. 239 */ 240 T* move_back_n(int n, T* t) { 241 SkASSERT(n >= 0); 242 this->checkRealloc(n); 243 for (int i = 0; i < n; ++i) { 244 new (fItemArray + fCount + i) T(std::move(t[i])); 245 } 246 fCount += n; 247 return fItemArray + fCount - n; 248 } 249 250 /** 251 * Removes the last element. Not safe to call when count() == 0. 252 */ 253 void pop_back() { 254 SkASSERT(fCount > 0); 255 --fCount; 256 fItemArray[fCount].~T(); 257 this->checkRealloc(0); 258 } 259 260 /** 261 * Removes the last n elements. Not safe to call when count() < n. 262 */ 263 void pop_back_n(int n) { 264 SkASSERT(n >= 0); 265 SkASSERT(fCount >= n); 266 fCount -= n; 267 for (int i = 0; i < n; ++i) { 268 fItemArray[fCount + i].~T(); 269 } 270 this->checkRealloc(0); 271 } 272 273 /** 274 * Pushes or pops from the back to resize. Pushes will be default 275 * initialized. 276 */ 277 void resize_back(int newCount) { 278 SkASSERT(newCount >= 0); 279 280 if (newCount > fCount) { 281 this->push_back_n(newCount - fCount); 282 } else if (newCount < fCount) { 283 this->pop_back_n(fCount - newCount); 284 } 285 } 286 287 /** Swaps the contents of this array with that array. Does a pointer swap if possible, 288 otherwise copies the T values. */ 289 void swap(SkTArray* that) { 290 if (this == that) { 291 return; 292 } 293 if (fOwnMemory && that->fOwnMemory) { 294 SkTSwap(fItemArray, that->fItemArray); 295 SkTSwap(fCount, that->fCount); 296 SkTSwap(fAllocCount, that->fAllocCount); 297 } else { 298 // This could be more optimal... 299 SkTArray copy(std::move(*that)); 300 *that = std::move(*this); 301 *this = std::move(copy); 302 } 303 } 304 305 T* begin() { 306 return fItemArray; 307 } 308 const T* begin() const { 309 return fItemArray; 310 } 311 T* end() { 312 return fItemArray ? fItemArray + fCount : NULL; 313 } 314 const T* end() const { 315 return fItemArray ? fItemArray + fCount : NULL; 316 } 317 318 /** 319 * Get the i^th element. 320 */ 321 T& operator[] (int i) { 322 SkASSERT(i < fCount); 323 SkASSERT(i >= 0); 324 return fItemArray[i]; 325 } 326 327 const T& operator[] (int i) const { 328 SkASSERT(i < fCount); 329 SkASSERT(i >= 0); 330 return fItemArray[i]; 331 } 332 333 /** 334 * equivalent to operator[](0) 335 */ 336 T& front() { SkASSERT(fCount > 0); return fItemArray[0];} 337 338 const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];} 339 340 /** 341 * equivalent to operator[](count() - 1) 342 */ 343 T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];} 344 345 const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];} 346 347 /** 348 * equivalent to operator[](count()-1-i) 349 */ 350 T& fromBack(int i) { 351 SkASSERT(i >= 0); 352 SkASSERT(i < fCount); 353 return fItemArray[fCount - i - 1]; 354 } 355 356 const T& fromBack(int i) const { 357 SkASSERT(i >= 0); 358 SkASSERT(i < fCount); 359 return fItemArray[fCount - i - 1]; 360 } 361 362 bool operator==(const SkTArray<T, MEM_MOVE>& right) const { 363 int leftCount = this->count(); 364 if (leftCount != right.count()) { 365 return false; 366 } 367 for (int index = 0; index < leftCount; ++index) { 368 if (fItemArray[index] != right.fItemArray[index]) { 369 return false; 370 } 371 } 372 return true; 373 } 374 375 bool operator!=(const SkTArray<T, MEM_MOVE>& right) const { 376 return !(*this == right); 377 } 378 379 inline int allocCntForTest() const; 380 381 protected: 382 /** 383 * Creates an empty array that will use the passed storage block until it 384 * is insufficiently large to hold the entire array. 385 */ 386 template <int N> 387 SkTArray(SkAlignedSTStorage<N,T>* storage) { 388 this->initWithPreallocatedStorage(0, storage->get(), N); 389 } 390 391 /** 392 * Copy another array, using preallocated storage if preAllocCount >= 393 * array.count(). Otherwise storage will only be used when array shrinks 394 * to fit. 395 */ 396 template <int N> 397 SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) { 398 this->initWithPreallocatedStorage(array.fCount, storage->get(), N); 399 this->copy(array.fItemArray); 400 } 401 402 /** 403 * Move another array, using preallocated storage if preAllocCount >= 404 * array.count(). Otherwise storage will only be used when array shrinks 405 * to fit. 406 */ 407 template <int N> 408 SkTArray(SkTArray&& array, SkAlignedSTStorage<N,T>* storage) { 409 this->initWithPreallocatedStorage(array.fCount, storage->get(), N); 410 array.move(fMemArray); 411 array.fCount = 0; 412 } 413 414 /** 415 * Copy a C array, using preallocated storage if preAllocCount >= 416 * count. Otherwise storage will only be used when array shrinks 417 * to fit. 418 */ 419 template <int N> 420 SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) { 421 this->initWithPreallocatedStorage(count, storage->get(), N); 422 this->copy(array); 423 } 424 425 private: 426 void init(int count = 0, int reserveCount = 0) { 427 SkASSERT(count >= 0); 428 SkASSERT(reserveCount >= 0); 429 fCount = count; 430 if (!count && !reserveCount) { 431 fAllocCount = 0; 432 fMemArray = nullptr; 433 fOwnMemory = false; 434 } else { 435 fAllocCount = SkTMax(count, SkTMax(kMinHeapAllocCount, reserveCount)); 436 fMemArray = sk_malloc_throw(fAllocCount * sizeof(T)); 437 fOwnMemory = true; 438 } 439 } 440 441 void initWithPreallocatedStorage(int count, void* preallocStorage, int preallocCount) { 442 SkASSERT(count >= 0); 443 SkASSERT(preallocCount > 0); 444 SkASSERT(preallocStorage); 445 fCount = count; 446 fMemArray = nullptr; 447 if (count > preallocCount) { 448 fAllocCount = SkTMax(count, kMinHeapAllocCount); 449 fMemArray = sk_malloc_throw(fAllocCount * sizeof(T)); 450 fOwnMemory = true; 451 } else { 452 fAllocCount = preallocCount; 453 fMemArray = preallocStorage; 454 fOwnMemory = false; 455 } 456 } 457 458 /** In the following move and copy methods, 'dst' is assumed to be uninitialized raw storage. 459 * In the following move methods, 'src' is destroyed leaving behind uninitialized raw storage. 460 */ 461 void copy(const T* src) { 462 // Some types may be trivially copyable, in which case we *could* use memcopy; but 463 // MEM_MOVE == true implies that the type is trivially movable, and not necessarily 464 // trivially copyable (think sk_sp<>). So short of adding another template arg, we 465 // must be conservative and use copy construction. 466 for (int i = 0; i < fCount; ++i) { 467 new (fItemArray + i) T(src[i]); 468 } 469 } 470 471 template <bool E = MEM_MOVE> SK_WHEN(E, void) move(int dst, int src) { 472 memcpy(&fItemArray[dst], &fItemArray[src], sizeof(T)); 473 } 474 template <bool E = MEM_MOVE> SK_WHEN(E, void) move(void* dst) { 475 sk_careful_memcpy(dst, fMemArray, fCount * sizeof(T)); 476 } 477 478 template <bool E = MEM_MOVE> SK_WHEN(!E, void) move(int dst, int src) { 479 new (&fItemArray[dst]) T(std::move(fItemArray[src])); 480 fItemArray[src].~T(); 481 } 482 template <bool E = MEM_MOVE> SK_WHEN(!E, void) move(void* dst) { 483 for (int i = 0; i < fCount; ++i) { 484 new (static_cast<char*>(dst) + sizeof(T) * i) T(std::move(fItemArray[i])); 485 fItemArray[i].~T(); 486 } 487 } 488 489 static constexpr int kMinHeapAllocCount = 8; 490 491 // Helper function that makes space for n objects, adjusts the count, but does not initialize 492 // the new objects. 493 void* push_back_raw(int n) { 494 this->checkRealloc(n); 495 void* ptr = fItemArray + fCount; 496 fCount += n; 497 return ptr; 498 } 499 500 void checkRealloc(int delta) { 501 SkASSERT(fCount >= 0); 502 SkASSERT(fAllocCount >= 0); 503 SkASSERT(-delta <= fCount); 504 505 int newCount = fCount + delta; 506 507 // We allow fAllocCount to be in the range [newCount, 3*newCount]. We also never shrink 508 // when we're currently using preallocated memory or would allocate less than 509 // kMinHeapAllocCount. 510 bool mustGrow = newCount > fAllocCount; 511 bool shouldShrink = fAllocCount > 3 * newCount && fOwnMemory; 512 if (!mustGrow && !shouldShrink) { 513 return; 514 } 515 516 // Whether we're growing or shrinking, we leave at least 50% extra space for future growth. 517 int newAllocCount = newCount + ((newCount + 1) >> 1); 518 // Align the new allocation count to kMinHeapAllocCount. 519 static_assert(SkIsPow2(kMinHeapAllocCount), "min alloc count not power of two."); 520 newAllocCount = (newAllocCount + (kMinHeapAllocCount - 1)) & ~(kMinHeapAllocCount - 1); 521 // At small sizes the old and new alloc count can both be kMinHeapAllocCount. 522 if (newAllocCount == fAllocCount) { 523 return; 524 } 525 fAllocCount = newAllocCount; 526 void* newMemArray = sk_malloc_throw(fAllocCount * sizeof(T)); 527 this->move(newMemArray); 528 if (fOwnMemory) { 529 sk_free(fMemArray); 530 531 } 532 fMemArray = newMemArray; 533 fOwnMemory = true; 534 } 535 536 int fCount; 537 int fAllocCount; 538 bool fOwnMemory; 539 union { 540 T* fItemArray; 541 void* fMemArray; 542 }; 543 }; 544 545 template<typename T, bool MEM_MOVE> constexpr int SkTArray<T, MEM_MOVE>::kMinHeapAllocCount; 546 547 /** 548 * Subclass of SkTArray that contains a preallocated memory block for the array. 549 */ 550 template <int N, typename T, bool MEM_MOVE= false> 551 class SkSTArray : public SkTArray<T, MEM_MOVE> { 552 private: 553 typedef SkTArray<T, MEM_MOVE> INHERITED; 554 555 public: 556 SkSTArray() : INHERITED(&fStorage) { 557 } 558 559 SkSTArray(const SkSTArray& array) 560 : INHERITED(array, &fStorage) { 561 } 562 563 SkSTArray(SkSTArray&& array) 564 : INHERITED(std::move(array), &fStorage) { 565 } 566 567 explicit SkSTArray(const INHERITED& array) 568 : INHERITED(array, &fStorage) { 569 } 570 571 explicit SkSTArray(INHERITED&& array) 572 : INHERITED(std::move(array), &fStorage) { 573 } 574 575 explicit SkSTArray(int reserveCount) 576 : INHERITED(reserveCount) { 577 } 578 579 SkSTArray(const T* array, int count) 580 : INHERITED(array, count, &fStorage) { 581 } 582 583 SkSTArray& operator=(const SkSTArray& array) { 584 INHERITED::operator=(array); 585 return *this; 586 } 587 588 SkSTArray& operator=(SkSTArray&& array) { 589 INHERITED::operator=(std::move(array)); 590 return *this; 591 } 592 593 SkSTArray& operator=(const INHERITED& array) { 594 INHERITED::operator=(array); 595 return *this; 596 } 597 598 SkSTArray& operator=(INHERITED&& array) { 599 INHERITED::operator=(std::move(array)); 600 return *this; 601 } 602 603 private: 604 SkAlignedSTStorage<N,T> fStorage; 605 }; 606 607 #endif 608