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