Line data Source code
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 3 : SkTArray() { this->init(); }
29 :
30 : /**
31 : * Creates an empty array that will preallocate space for reserveCount
32 : * elements.
33 : */
34 0 : 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 0 : explicit SkTArray(const SkTArray& that) {
40 0 : this->init(that.fCount);
41 0 : this->copy(that.fItemArray);
42 0 : }
43 :
44 0 : SkTArray(SkTArray&& that) {
45 : // TODO: If 'that' owns its memory why don't we just steal the pointer?
46 0 : this->init(that.fCount);
47 0 : that.move(fMemArray);
48 0 : that.fCount = 0;
49 0 : }
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 0 : SkTArray& operator=(const SkTArray& that) {
62 0 : if (this == &that) {
63 0 : return *this;
64 : }
65 0 : for (int i = 0; i < fCount; ++i) {
66 0 : fItemArray[i].~T();
67 : }
68 0 : fCount = 0;
69 0 : this->checkRealloc(that.count());
70 0 : fCount = that.count();
71 0 : this->copy(that.fItemArray);
72 0 : return *this;
73 : }
74 0 : SkTArray& operator=(SkTArray&& that) {
75 0 : if (this == &that) {
76 0 : return *this;
77 : }
78 0 : for (int i = 0; i < fCount; ++i) {
79 0 : fItemArray[i].~T();
80 : }
81 0 : fCount = 0;
82 0 : this->checkRealloc(that.count());
83 0 : fCount = that.count();
84 0 : that.move(fMemArray);
85 0 : that.fCount = 0;
86 0 : return *this;
87 : }
88 :
89 25 : ~SkTArray() {
90 25 : for (int i = 0; i < fCount; ++i) {
91 0 : fItemArray[i].~T();
92 : }
93 25 : if (fOwnMemory) {
94 15 : sk_free(fMemArray);
95 : }
96 25 : }
97 :
98 : /**
99 : * Resets to count() == 0
100 : */
101 0 : void reset() { this->pop_back_n(fCount); }
102 :
103 : /**
104 : * Resets to count() = n newly constructed T objects.
105 : */
106 0 : void reset(int n) {
107 0 : SkASSERT(n >= 0);
108 0 : for (int i = 0; i < fCount; ++i) {
109 0 : fItemArray[i].~T();
110 : }
111 : // Set fCount to 0 before calling checkRealloc so that no elements are moved.
112 0 : fCount = 0;
113 0 : this->checkRealloc(n);
114 0 : fCount = n;
115 0 : for (int i = 0; i < fCount; ++i) {
116 0 : new (fItemArray + i) T;
117 : }
118 0 : }
119 :
120 : /**
121 : * Ensures there is enough reserved space for n elements.
122 : */
123 0 : void reserve(int n) {
124 0 : if (fCount < n) {
125 0 : this->checkRealloc(n - fCount);
126 : }
127 0 : }
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 0 : void removeShuffle(int n) {
143 0 : SkASSERT(n < fCount);
144 0 : int newCount = fCount - 1;
145 0 : fCount = newCount;
146 0 : fItemArray[n].~T();
147 0 : if (n != newCount) {
148 0 : this->move(n, newCount);
149 : }
150 0 : }
151 :
152 : /**
153 : * Number of elements in the array.
154 : */
155 8 : int count() const { return fCount; }
156 :
157 : /**
158 : * Is the array empty.
159 : */
160 0 : 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 0 : T& push_back() {
168 0 : void* newT = this->push_back_raw(1);
169 0 : return *new (newT) T;
170 : }
171 :
172 : /**
173 : * Version of above that uses a copy constructor to initialize the new item
174 : */
175 0 : T& push_back(const T& t) {
176 0 : void* newT = this->push_back_raw(1);
177 0 : return *new (newT) T(t);
178 : }
179 :
180 : /**
181 : * Version of above that uses a move constructor to initialize the new item
182 : */
183 81 : T& push_back(T&& t) {
184 81 : void* newT = this->push_back_raw(1);
185 81 : return *new (newT) T(std::move(t));
186 : }
187 :
188 : /**
189 : * Construct a new T at the back of this array.
190 : */
191 2 : template<class... Args> T& emplace_back(Args&&... args) {
192 2 : void* newT = this->push_back_raw(1);
193 2 : 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 0 : T* push_back_n(int n) {
202 0 : SkASSERT(n >= 0);
203 0 : void* newTs = this->push_back_raw(n);
204 0 : for (int i = 0; i < n; ++i) {
205 0 : new (static_cast<char*>(newTs) + i * sizeof(T)) T;
206 : }
207 0 : 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 0 : T* push_back_n(int n, const T t[]) {
228 0 : SkASSERT(n >= 0);
229 0 : this->checkRealloc(n);
230 0 : for (int i = 0; i < n; ++i) {
231 0 : new (fItemArray + fCount + i) T(t[i]);
232 : }
233 0 : fCount += n;
234 0 : return fItemArray + fCount - n;
235 : }
236 :
237 : /**
238 : * Version of above that uses the move constructor to set n items.
239 : */
240 0 : T* move_back_n(int n, T* t) {
241 0 : SkASSERT(n >= 0);
242 0 : this->checkRealloc(n);
243 0 : for (int i = 0; i < n; ++i) {
244 0 : new (fItemArray + fCount + i) T(std::move(t[i]));
245 : }
246 0 : fCount += n;
247 0 : return fItemArray + fCount - n;
248 : }
249 :
250 : /**
251 : * Removes the last element. Not safe to call when count() == 0.
252 : */
253 0 : void pop_back() {
254 0 : SkASSERT(fCount > 0);
255 0 : --fCount;
256 0 : fItemArray[fCount].~T();
257 0 : this->checkRealloc(0);
258 0 : }
259 :
260 : /**
261 : * Removes the last n elements. Not safe to call when count() < n.
262 : */
263 0 : void pop_back_n(int n) {
264 0 : SkASSERT(n >= 0);
265 0 : SkASSERT(fCount >= n);
266 0 : fCount -= n;
267 0 : for (int i = 0; i < n; ++i) {
268 0 : fItemArray[fCount + i].~T();
269 : }
270 0 : this->checkRealloc(0);
271 0 : }
272 :
273 : /**
274 : * Pushes or pops from the back to resize. Pushes will be default
275 : * initialized.
276 : */
277 0 : void resize_back(int newCount) {
278 0 : SkASSERT(newCount >= 0);
279 :
280 0 : if (newCount > fCount) {
281 0 : this->push_back_n(newCount - fCount);
282 0 : } else if (newCount < fCount) {
283 0 : this->pop_back_n(fCount - newCount);
284 : }
285 0 : }
286 :
287 : /** Swaps the contents of this array with that array. Does a pointer swap if possible,
288 : otherwise copies the T values. */
289 0 : void swap(SkTArray* that) {
290 0 : if (this == that) {
291 0 : return;
292 : }
293 0 : if (fOwnMemory && that->fOwnMemory) {
294 0 : SkTSwap(fItemArray, that->fItemArray);
295 0 : SkTSwap(fCount, that->fCount);
296 0 : SkTSwap(fAllocCount, that->fAllocCount);
297 : } else {
298 : // This could be more optimal...
299 0 : SkTArray copy(std::move(*that));
300 0 : *that = std::move(*this);
301 0 : *this = std::move(copy);
302 : }
303 : }
304 :
305 25 : T* begin() {
306 25 : return fItemArray;
307 : }
308 0 : const T* begin() const {
309 0 : return fItemArray;
310 : }
311 0 : T* end() {
312 0 : return fItemArray ? fItemArray + fCount : NULL;
313 : }
314 0 : const T* end() const {
315 0 : return fItemArray ? fItemArray + fCount : NULL;
316 : }
317 :
318 : /**
319 : * Get the i^th element.
320 : */
321 0 : T& operator[] (int i) {
322 0 : SkASSERT(i < fCount);
323 0 : SkASSERT(i >= 0);
324 0 : return fItemArray[i];
325 : }
326 :
327 0 : const T& operator[] (int i) const {
328 0 : SkASSERT(i < fCount);
329 0 : SkASSERT(i >= 0);
330 0 : return fItemArray[i];
331 : }
332 :
333 : /**
334 : * equivalent to operator[](0)
335 : */
336 0 : T& front() { SkASSERT(fCount > 0); return fItemArray[0];}
337 :
338 0 : const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];}
339 :
340 : /**
341 : * equivalent to operator[](count() - 1)
342 : */
343 0 : T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];}
344 :
345 0 : const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];}
346 :
347 : /**
348 : * equivalent to operator[](count()-1-i)
349 : */
350 0 : T& fromBack(int i) {
351 0 : SkASSERT(i >= 0);
352 0 : SkASSERT(i < fCount);
353 0 : 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 0 : bool operator==(const SkTArray<T, MEM_MOVE>& right) const {
363 0 : int leftCount = this->count();
364 0 : if (leftCount != right.count()) {
365 0 : return false;
366 : }
367 0 : for (int index = 0; index < leftCount; ++index) {
368 0 : if (fItemArray[index] != right.fItemArray[index]) {
369 0 : return false;
370 : }
371 : }
372 0 : 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 25 : SkTArray(SkAlignedSTStorage<N,T>* storage) {
388 25 : this->initWithPreallocatedStorage(0, storage->get(), N);
389 25 : }
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 0 : SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) {
398 0 : this->initWithPreallocatedStorage(array.fCount, storage->get(), N);
399 0 : this->copy(array.fItemArray);
400 0 : }
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 0 : SkTArray(SkTArray&& array, SkAlignedSTStorage<N,T>* storage) {
409 0 : this->initWithPreallocatedStorage(array.fCount, storage->get(), N);
410 0 : array.move(fMemArray);
411 0 : array.fCount = 0;
412 0 : }
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 0 : SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) {
421 0 : this->initWithPreallocatedStorage(count, storage->get(), N);
422 0 : this->copy(array);
423 0 : }
424 :
425 : private:
426 3 : void init(int count = 0, int reserveCount = 0) {
427 3 : SkASSERT(count >= 0);
428 3 : SkASSERT(reserveCount >= 0);
429 3 : fCount = count;
430 3 : if (!count && !reserveCount) {
431 3 : fAllocCount = 0;
432 3 : fMemArray = nullptr;
433 3 : fOwnMemory = false;
434 : } else {
435 0 : fAllocCount = SkTMax(count, SkTMax(kMinHeapAllocCount, reserveCount));
436 0 : fMemArray = sk_malloc_throw(fAllocCount * sizeof(T));
437 0 : fOwnMemory = true;
438 : }
439 3 : }
440 :
441 25 : void initWithPreallocatedStorage(int count, void* preallocStorage, int preallocCount) {
442 25 : SkASSERT(count >= 0);
443 25 : SkASSERT(preallocCount > 0);
444 25 : SkASSERT(preallocStorage);
445 25 : fCount = count;
446 25 : fMemArray = nullptr;
447 25 : if (count > preallocCount) {
448 0 : fAllocCount = SkTMax(count, kMinHeapAllocCount);
449 0 : fMemArray = sk_malloc_throw(fAllocCount * sizeof(T));
450 0 : fOwnMemory = true;
451 : } else {
452 25 : fAllocCount = preallocCount;
453 25 : fMemArray = preallocStorage;
454 25 : fOwnMemory = false;
455 : }
456 25 : }
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 0 : 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 0 : for (int i = 0; i < fCount; ++i) {
467 0 : new (fItemArray + i) T(src[i]);
468 : }
469 0 : }
470 :
471 0 : template <bool E = MEM_MOVE> SK_WHEN(E, void) move(int dst, int src) {
472 0 : memcpy(&fItemArray[dst], &fItemArray[src], sizeof(T));
473 0 : }
474 15 : template <bool E = MEM_MOVE> SK_WHEN(E, void) move(void* dst) {
475 15 : sk_careful_memcpy(dst, fMemArray, fCount * sizeof(T));
476 15 : }
477 :
478 0 : template <bool E = MEM_MOVE> SK_WHEN(!E, void) move(int dst, int src) {
479 0 : new (&fItemArray[dst]) T(std::move(fItemArray[src]));
480 0 : fItemArray[src].~T();
481 0 : }
482 2 : template <bool E = MEM_MOVE> SK_WHEN(!E, void) move(void* dst) {
483 2 : for (int i = 0; i < fCount; ++i) {
484 0 : new (static_cast<char*>(dst) + sizeof(T) * i) T(std::move(fItemArray[i]));
485 0 : fItemArray[i].~T();
486 : }
487 2 : }
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 83 : void* push_back_raw(int n) {
494 83 : this->checkRealloc(n);
495 83 : void* ptr = fItemArray + fCount;
496 83 : fCount += n;
497 83 : return ptr;
498 : }
499 :
500 83 : void checkRealloc(int delta) {
501 83 : SkASSERT(fCount >= 0);
502 83 : SkASSERT(fAllocCount >= 0);
503 83 : SkASSERT(-delta <= fCount);
504 :
505 83 : 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 83 : bool mustGrow = newCount > fAllocCount;
511 83 : bool shouldShrink = fAllocCount > 3 * newCount && fOwnMemory;
512 83 : if (!mustGrow && !shouldShrink) {
513 66 : return;
514 : }
515 :
516 : // Whether we're growing or shrinking, we leave at least 50% extra space for future growth.
517 17 : 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 17 : newAllocCount = (newAllocCount + (kMinHeapAllocCount - 1)) & ~(kMinHeapAllocCount - 1);
521 : // At small sizes the old and new alloc count can both be kMinHeapAllocCount.
522 17 : if (newAllocCount == fAllocCount) {
523 0 : return;
524 : }
525 17 : fAllocCount = newAllocCount;
526 17 : void* newMemArray = sk_malloc_throw(fAllocCount * sizeof(T));
527 17 : this->move(newMemArray);
528 17 : if (fOwnMemory) {
529 0 : sk_free(fMemArray);
530 :
531 : }
532 17 : fMemArray = newMemArray;
533 17 : 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 25 : class SkSTArray : public SkTArray<T, MEM_MOVE> {
552 : private:
553 : typedef SkTArray<T, MEM_MOVE> INHERITED;
554 :
555 : public:
556 25 : SkSTArray() : INHERITED(&fStorage) {
557 25 : }
558 :
559 0 : SkSTArray(const SkSTArray& array)
560 0 : : INHERITED(array, &fStorage) {
561 0 : }
562 :
563 0 : SkSTArray(SkSTArray&& array)
564 0 : : INHERITED(std::move(array), &fStorage) {
565 0 : }
566 :
567 0 : explicit SkSTArray(const INHERITED& array)
568 0 : : INHERITED(array, &fStorage) {
569 0 : }
570 :
571 : explicit SkSTArray(INHERITED&& array)
572 : : INHERITED(std::move(array), &fStorage) {
573 : }
574 :
575 0 : explicit SkSTArray(int reserveCount)
576 0 : : INHERITED(reserveCount) {
577 0 : }
578 :
579 0 : SkSTArray(const T* array, int count)
580 0 : : INHERITED(array, count, &fStorage) {
581 0 : }
582 :
583 : SkSTArray& operator=(const SkSTArray& array) {
584 : INHERITED::operator=(array);
585 : return *this;
586 : }
587 :
588 0 : SkSTArray& operator=(SkSTArray&& array) {
589 0 : INHERITED::operator=(std::move(array));
590 0 : 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
|
