8#ifndef SkTArray_DEFINED
9#define SkTArray_DEFINED
28#include <initializer_list>
40template <
typename T,
bool MEM_MOVE = sk_is_trivially_relocatable_v<T>>
class TArray {
60 if (that.fOwnMemory) {
64 this->initData(that.fSize);
67 this->changeSize(that.fSize);
77 this->initData(
count);
91 this->checkRealloc(that.
size(), kExactFit);
92 this->changeSize(that.fSize);
93 this->
copy(that.fData);
102 if (that.fOwnMemory) {
108 fData = std::exchange(that.fData,
nullptr);
111 fCapacity = that.fCapacity;
116 this->changeSize(that.fSize);
119 this->checkRealloc(that.size(), kExactFit);
120 this->changeSize(that.fSize);
142 this->checkRealloc(n, kExactFit);
144 for (
int i = 0; i < this->
size(); ++i) {
155 this->checkRealloc(
count, kExactFit);
156 this->changeSize(
count);
167 if (n > this->
size()) {
168 this->checkRealloc(n - this->
size(), kGrowing);
178 if (n > this->
size()) {
179 this->checkRealloc(n - this->
size(), kExactFit);
185 int newCount = fSize - 1;
188 this->move(n, newCount);
190 this->changeSize(newCount);
194 bool empty()
const {
return fSize == 0; }
201 void* newT = this->push_back_raw(1);
202 return *
new (newT)
T;
214 newT =
new (fData + fSize)
T(t);
216 newT = this->growAndConstructAtEnd(t);
219 this->changeSize(fSize + 1);
231 newT =
new (fData + fSize)
T(std::move(t));
233 newT = this->growAndConstructAtEnd(std::move(t));
236 this->changeSize(fSize + 1);
248 newT =
new (fData + fSize)
T(std::forward<Args>(
args)...);
250 newT = this->growAndConstructAtEnd(std::forward<Args>(
args)...);
253 this->changeSize(fSize + 1);
264 T* newTs = TCast(this->push_back_raw(n));
265 for (
int i = 0; i < n; ++i) {
277 T* newTs = TCast(this->push_back_raw(n));
278 for (
int i = 0; i < n; ++i) {
279 new (&newTs[i])
T(t);
281 return static_cast<T*
>(newTs);
290 this->checkRealloc(n, kGrowing);
292 this->changeSize(fSize + n);
293 for (
int i = 0; i < n; ++i) {
294 new (
end + i)
T(t[i]);
304 this->checkRealloc(n, kGrowing);
306 this->changeSize(fSize + n);
307 for (
int i = 0; i < n; ++i) {
308 new (
end + i)
T(std::move(t[i]));
318 fData[fSize - 1].~T();
319 this->changeSize(fSize - 1);
329 while (i-- > fSize - n) {
332 this->changeSize(fSize - n);
340 if (newCount > this->
size()) {
343 this->checkRealloc(newCount, kExactFit);
346 }
else if (newCount < this->
size()) {
358 if (fOwnMemory && that.fOwnMemory) {
359 swap(fData, that.fData);
360 swap(fSize, that.fSize);
363 auto allocCount = fCapacity;
364 fCapacity = that.fCapacity;
365 that.fCapacity = allocCount;
369 that = std::move(*
this);
370 *
this = std::move(
copy);
379 if (that.
empty() || &that ==
this) {
382 void* dst = this->push_back_raw(that.
size());
403 if (fData ==
nullptr) {
406 return fData + fSize;
409 if (fData ==
nullptr) {
412 return fData + fSize;
415 const T*
data()
const {
return fData; }
416 int size()
const {
return fSize; }
426 if (!fOwnMemory || fSize == fCapacity) {
436 this->move(TCast(allocation.
data()));
441 this->setDataFromBytes(allocation);
456 T&
at(
int i) {
return (*
this)[i]; }
457 const T&
at(
int i)
const {
return (*
this)[i]; }
477 return fData[fSize - 1];
482 return fData[fSize - 1];
489 return (*
this)[fSize - i - 1];
493 return (*
this)[fSize - i - 1];
497 int leftCount = this->
size();
498 if (leftCount !=
right.size()) {
501 for (
int index = 0; index < leftCount; ++index) {
502 if (fData[index] !=
right.fData[index]) {
510 return !(*
this ==
right);
520 template <
int InitialCapacity>
522 static_assert(InitialCapacity >= 0);
525 if (
size > InitialCapacity) {
526 this->initData(
size);
528 this->setDataFromBytes(*storage);
529 this->changeSize(
size);
539 template <
int InitialCapacity>
547 static constexpr double kExactFit = 1.0;
548 static constexpr double kGrowing = 1.5;
550 static constexpr int kMinHeapAllocCount = 8;
551 static_assert(
SkIsPow2(kMinHeapAllocCount),
"min alloc count not power of two.");
555 static constexpr int kMaxCapacity =
SkToInt(std::min(SIZE_MAX /
sizeof(
T), (
size_t)INT_MAX));
570 fData = array.
data();
578#ifdef SK_SANITIZE_ADDRESS
587#ifdef SK_SANITIZE_ADDRESS
588 if (fData && fCapacity > fSize) {
595 void changeSize(
int n) {
609 static
T* TCast(
void*
buffer) {
613 static size_t Bytes(
int n) {
622 void initData(
int count) {
623 this->setDataFromBytes(Allocate(
count));
624 this->changeSize(
count);
628 if (!this->
empty()) {
629 T* cursor = this->
begin();
634 }
while (cursor <
end);
641 void copy(
const T* src) {
642 if constexpr (std::is_trivially_copyable_v<T>) {
643 if (!this->
empty() && src !=
nullptr) {
647 for (
int i = 0; i < this->
size(); ++i) {
648 new (fData + i)
T(src[i]);
653 void move(
int dst,
int src) {
654 if constexpr (MEM_MOVE) {
655 memcpy(
static_cast<void*
>(&fData[dst]),
656 static_cast<const void*
>(&fData[src]),
659 new (&fData[
dst])
T(std::move(fData[src]));
664 void move(
void* dst) {
665 if constexpr (MEM_MOVE) {
668 for (
int i = 0; i < this->
size(); ++i) {
669 new (
static_cast<char*
>(
dst) + Bytes(i))
T(std::move(fData[i]));
677 void* push_back_raw(
int n) {
678 this->checkRealloc(n, kGrowing);
679 void* ptr = fData + fSize;
680 this->changeSize(fSize + n);
684 template <
typename... Args>
687 T* newT =
new (TCast(
buffer.data()) + fSize)
T(std::forward<Args>(
args)...);
688 this->installDataAndUpdateCapacity(
buffer);
693 void checkRealloc(
int delta,
double growthFactor) {
699 if (this->
capacity() - fSize < delta) {
701 this->installDataAndUpdateCapacity(this->preallocateNewData(delta, growthFactor));
714 if (delta > kMaxCapacity - fSize) {
717 const int newCount = fSize +
delta;
719 return Allocate(newCount, growthFactor);
723 this->move(TCast(allocation.
data()));
727 this->setDataFromBytes(allocation);
733 uint32_t fOwnMemory : 1;
734 uint32_t fCapacity : 31;
742template <
int Nreq,
typename T,
bool MEM_MOVE = sk_is_trivially_relocatable_v<T>>
744 public TArray<T, MEM_MOVE> {
747 static constexpr int N = SkContainerAllocator::RoundUp<T>(Nreq);
748 static_assert(Nreq > 0);
749 static_assert(
N >= Nreq);
776 :
STArray() { *
this = std::move(that); }
779 :
STArray() { *
this = std::move(that); }
static void sk_asan_poison_memory_region(void const volatile *addr, size_t size)
static void sk_asan_unpoison_memory_region(void const volatile *addr, size_t size)
SK_API void sk_collection_not_empty(bool empty)
SK_API T sk_collection_check_bounds(T i, T size)
#define SK_CLANG_NO_SANITIZE(A)
SK_SPI void sk_report_container_overflow_and_die()
SK_API void sk_free(void *)
static void * sk_careful_memcpy(void *dst, const void *src, size_t len)
constexpr bool SkIsPow2(T value)
static bool right(const SkPoint &p0, const SkPoint &p1)
constexpr size_t SkToSizeT(S x)
constexpr int SkToInt(S x)
constexpr uint32_t SkToU32(S x)
SkSpan< std::byte > allocate(int capacity, double growthFactor=1.0)
constexpr T * data() const
constexpr size_t size() const
STArray(const STArray &that)
STArray & operator=(TArray< T, MEM_MOVE > &&that)
STArray & operator=(const TArray< T, MEM_MOVE > &that)
STArray(std::initializer_list< T > data)
STArray & operator=(STArray &&that)
STArray & operator=(const STArray &that)
STArray(int reserveCount)
STArray(const TArray< T, MEM_MOVE > &that)
STArray(TArray< T, MEM_MOVE > &&that)
STArray(const T *array, int count)
TArray(const TArray &that)
T * push_back_n(int n, const T &t)
T * push_back_n(int n, const T t[])
TArray(SkAlignedSTStorage< InitialCapacity, T > *storage, int size=0)
size_t size_bytes() const
void move_back(TArray &that)
void reset(const T *array, int count)
void resize_back(int newCount)
const T & at(int i) const
TArray(const T *array, int count)
const T & fromBack(int i) const
void resize(size_t count)
TArray & operator=(TArray &&that)
T * move_back_n(int n, T *t)
void removeShuffle(int n)
T & push_back(const T &t)
bool operator!=(const TArray< T, MEM_MOVE > &right) const
void reserve_exact(int n)
bool operator==(const TArray< T, MEM_MOVE > &right) const
T & emplace_back(Args &&... args)
TArray(std::initializer_list< T > data)
TArray & operator=(const TArray &that)
TArray(const T *array, int size, SkAlignedSTStorage< InitialCapacity, T > *storage)
G_BEGIN_DECLS G_MODULE_EXPORT FlValue * args
static const uint8_t buffer[]
static void swap(TArray< T, M > &a, TArray< T, M > &b)