aboutsummaryrefslogtreecommitdiff
path: root/src/deps/skia/include/private/SkTArray.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/deps/skia/include/private/SkTArray.h')
-rw-r--r--src/deps/skia/include/private/SkTArray.h640
1 files changed, 640 insertions, 0 deletions
diff --git a/src/deps/skia/include/private/SkTArray.h b/src/deps/skia/include/private/SkTArray.h
new file mode 100644
index 000000000..9db5fd030
--- /dev/null
+++ b/src/deps/skia/include/private/SkTArray.h
@@ -0,0 +1,640 @@
+/*
+ * Copyright 2011 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkTArray_DEFINED
+#define SkTArray_DEFINED
+
+#include "include/core/SkMath.h"
+#include "include/core/SkTypes.h"
+#include "include/private/SkMalloc.h"
+#include "include/private/SkSafe32.h"
+#include "include/private/SkTLogic.h"
+#include "include/private/SkTemplates.h"
+#include "include/private/SkTo.h"
+
+#include <string.h>
+#include <initializer_list>
+#include <memory>
+#include <new>
+#include <utility>
+
+/** SkTArray<T> implements a typical, mostly std::vector-like array.
+ Each T will be default-initialized on allocation, and ~T will be called on destruction.
+
+ MEM_MOVE controls the behavior when a T needs to be moved (e.g. when the array is resized)
+ - true: T will be bit-copied via memcpy.
+ - false: T will be moved via move-constructors.
+
+ Modern implementations of std::vector<T> will generally provide similar performance
+ characteristics when used with appropriate care. Consider using std::vector<T> in new code.
+*/
+template <typename T, bool MEM_MOVE = false> class SkTArray {
+private:
+ enum ReallocType { kExactFit, kGrowing, kShrinking };
+
+public:
+ using value_type = T;
+
+ /**
+ * Creates an empty array with no initial storage
+ */
+ SkTArray() { this->init(0); }
+
+ /**
+ * Creates an empty array that will preallocate space for reserveCount
+ * elements.
+ */
+ explicit SkTArray(int reserveCount) : SkTArray() { this->reserve_back(reserveCount); }
+
+ /**
+ * Copies one array to another. The new array will be heap allocated.
+ */
+ SkTArray(const SkTArray& that)
+ : SkTArray(that.fItemArray, that.fCount) {}
+
+ SkTArray(SkTArray&& that) {
+ if (that.fOwnMemory) {
+ fItemArray = that.fItemArray;
+ fCount = that.fCount;
+ fAllocCount = that.fAllocCount;
+ fOwnMemory = true;
+ fReserved = that.fReserved;
+
+ that.fItemArray = nullptr;
+ that.fCount = 0;
+ that.fAllocCount = 0;
+ that.fOwnMemory = true;
+ that.fReserved = false;
+ } else {
+ this->init(that.fCount);
+ that.move(fItemArray);
+ that.fCount = 0;
+ }
+ }
+
+ /**
+ * Creates a SkTArray by copying contents of a standard C array. The new
+ * array will be heap allocated. Be careful not to use this constructor
+ * when you really want the (void*, int) version.
+ */
+ SkTArray(const T* array, int count) {
+ this->init(count);
+ this->copy(array);
+ }
+ /**
+ * Creates a SkTArray by copying contents of an initializer list.
+ */
+ SkTArray(std::initializer_list<T> data)
+ : SkTArray(data.begin(), data.size()) {}
+
+ SkTArray& operator=(const SkTArray& that) {
+ if (this == &that) {
+ return *this;
+ }
+ for (int i = 0; i < this->count(); ++i) {
+ fItemArray[i].~T();
+ }
+ fCount = 0;
+ this->checkRealloc(that.count(), kExactFit);
+ fCount = that.fCount;
+ this->copy(that.fItemArray);
+ return *this;
+ }
+ SkTArray& operator=(SkTArray&& that) {
+ if (this == &that) {
+ return *this;
+ }
+ for (int i = 0; i < this->count(); ++i) {
+ fItemArray[i].~T();
+ }
+ fCount = 0;
+ this->checkRealloc(that.count(), kExactFit);
+ fCount = that.fCount;
+ that.move(fItemArray);
+ that.fCount = 0;
+ return *this;
+ }
+
+ ~SkTArray() {
+ for (int i = 0; i < this->count(); ++i) {
+ fItemArray[i].~T();
+ }
+ if (fOwnMemory) {
+ sk_free(fItemArray);
+ }
+ }
+
+ /**
+ * Resets to count() == 0 and resets any reserve count.
+ */
+ void reset() {
+ this->pop_back_n(fCount);
+ fReserved = false;
+ }
+
+ /**
+ * Resets to count() = n newly constructed T objects and resets any reserve count.
+ */
+ void reset(int n) {
+ SkASSERT(n >= 0);
+ for (int i = 0; i < this->count(); ++i) {
+ fItemArray[i].~T();
+ }
+ // Set fCount to 0 before calling checkRealloc so that no elements are moved.
+ fCount = 0;
+ this->checkRealloc(n, kExactFit);
+ fCount = n;
+ for (int i = 0; i < this->count(); ++i) {
+ new (fItemArray + i) T;
+ }
+ fReserved = false;
+ }
+
+ /**
+ * Resets to a copy of a C array and resets any reserve count.
+ */
+ void reset(const T* array, int count) {
+ for (int i = 0; i < this->count(); ++i) {
+ fItemArray[i].~T();
+ }
+ fCount = 0;
+ this->checkRealloc(count, kExactFit);
+ fCount = count;
+ this->copy(array);
+ fReserved = false;
+ }
+
+ /**
+ * Ensures there is enough reserved space for n additional elements. The is guaranteed at least
+ * until the array size grows above n and subsequently shrinks below n, any version of reset()
+ * is called, or reserve_back() is called again.
+ */
+ void reserve_back(int n) {
+ SkASSERT(n >= 0);
+ if (n > 0) {
+ this->checkRealloc(n, kExactFit);
+ fReserved = fOwnMemory;
+ } else {
+ fReserved = false;
+ }
+ }
+
+ void removeShuffle(int n) {
+ SkASSERT(n < this->count());
+ int newCount = fCount - 1;
+ fCount = newCount;
+ fItemArray[n].~T();
+ if (n != newCount) {
+ this->move(n, newCount);
+ }
+ }
+
+ /**
+ * Number of elements in the array.
+ */
+ int count() const { return fCount; }
+
+ /**
+ * Is the array empty.
+ */
+ bool empty() const { return !fCount; }
+
+ /**
+ * Adds 1 new default-initialized T value and returns it by reference. Note
+ * the reference only remains valid until the next call that adds or removes
+ * elements.
+ */
+ T& push_back() {
+ void* newT = this->push_back_raw(1);
+ return *new (newT) T;
+ }
+
+ /**
+ * Version of above that uses a copy constructor to initialize the new item
+ */
+ T& push_back(const T& t) {
+ void* newT = this->push_back_raw(1);
+ return *new (newT) T(t);
+ }
+
+ /**
+ * Version of above that uses a move constructor to initialize the new item
+ */
+ T& push_back(T&& t) {
+ void* newT = this->push_back_raw(1);
+ return *new (newT) T(std::move(t));
+ }
+
+ /**
+ * Construct a new T at the back of this array.
+ */
+ template<class... Args> T& emplace_back(Args&&... args) {
+ void* newT = this->push_back_raw(1);
+ return *new (newT) T(std::forward<Args>(args)...);
+ }
+
+ /**
+ * Allocates n more default-initialized T values, and returns the address of
+ * the start of that new range. Note: this address is only valid until the
+ * next API call made on the array that might add or remove elements.
+ */
+ T* push_back_n(int n) {
+ SkASSERT(n >= 0);
+ void* newTs = this->push_back_raw(n);
+ for (int i = 0; i < n; ++i) {
+ new (static_cast<char*>(newTs) + i * sizeof(T)) T;
+ }
+ return static_cast<T*>(newTs);
+ }
+
+ /**
+ * Version of above that uses a copy constructor to initialize all n items
+ * to the same T.
+ */
+ T* push_back_n(int n, const T& t) {
+ SkASSERT(n >= 0);
+ void* newTs = this->push_back_raw(n);
+ for (int i = 0; i < n; ++i) {
+ new (static_cast<char*>(newTs) + i * sizeof(T)) T(t);
+ }
+ return static_cast<T*>(newTs);
+ }
+
+ /**
+ * Version of above that uses a copy constructor to initialize the n items
+ * to separate T values.
+ */
+ T* push_back_n(int n, const T t[]) {
+ SkASSERT(n >= 0);
+ this->checkRealloc(n, kGrowing);
+ for (int i = 0; i < n; ++i) {
+ new (fItemArray + fCount + i) T(t[i]);
+ }
+ fCount += n;
+ return fItemArray + fCount - n;
+ }
+
+ /**
+ * Version of above that uses the move constructor to set n items.
+ */
+ T* move_back_n(int n, T* t) {
+ SkASSERT(n >= 0);
+ this->checkRealloc(n, kGrowing);
+ for (int i = 0; i < n; ++i) {
+ new (fItemArray + fCount + i) T(std::move(t[i]));
+ }
+ fCount += n;
+ return fItemArray + fCount - n;
+ }
+
+ /**
+ * Removes the last element. Not safe to call when count() == 0.
+ */
+ void pop_back() {
+ SkASSERT(fCount > 0);
+ --fCount;
+ fItemArray[fCount].~T();
+ this->checkRealloc(0, kShrinking);
+ }
+
+ /**
+ * Removes the last n elements. Not safe to call when count() < n.
+ */
+ void pop_back_n(int n) {
+ SkASSERT(n >= 0);
+ SkASSERT(this->count() >= n);
+ fCount -= n;
+ for (int i = 0; i < n; ++i) {
+ fItemArray[fCount + i].~T();
+ }
+ this->checkRealloc(0, kShrinking);
+ }
+
+ /**
+ * Pushes or pops from the back to resize. Pushes will be default
+ * initialized.
+ */
+ void resize_back(int newCount) {
+ SkASSERT(newCount >= 0);
+
+ if (newCount > this->count()) {
+ this->push_back_n(newCount - fCount);
+ } else if (newCount < this->count()) {
+ this->pop_back_n(fCount - newCount);
+ }
+ }
+
+ /** Swaps the contents of this array with that array. Does a pointer swap if possible,
+ otherwise copies the T values. */
+ void swap(SkTArray& that) {
+ using std::swap;
+ if (this == &that) {
+ return;
+ }
+ if (fOwnMemory && that.fOwnMemory) {
+ swap(fItemArray, that.fItemArray);
+
+ auto count = fCount;
+ fCount = that.fCount;
+ that.fCount = count;
+
+ auto allocCount = fAllocCount;
+ fAllocCount = that.fAllocCount;
+ that.fAllocCount = allocCount;
+ } else {
+ // This could be more optimal...
+ SkTArray copy(std::move(that));
+ that = std::move(*this);
+ *this = std::move(copy);
+ }
+ }
+
+ T* begin() {
+ return fItemArray;
+ }
+ const T* begin() const {
+ return fItemArray;
+ }
+ T* end() {
+ return fItemArray ? fItemArray + fCount : nullptr;
+ }
+ const T* end() const {
+ return fItemArray ? fItemArray + fCount : nullptr;
+ }
+ T* data() { return fItemArray; }
+ const T* data() const { return fItemArray; }
+ size_t size() const { return (size_t)fCount; }
+ void resize(size_t count) { this->resize_back((int)count); }
+
+ /**
+ * Get the i^th element.
+ */
+ T& operator[] (int i) {
+ SkASSERT(i < this->count());
+ SkASSERT(i >= 0);
+ return fItemArray[i];
+ }
+
+ const T& operator[] (int i) const {
+ SkASSERT(i < this->count());
+ SkASSERT(i >= 0);
+ return fItemArray[i];
+ }
+
+ T& at(int i) { return (*this)[i]; }
+ const T& at(int i) const { return (*this)[i]; }
+
+ /**
+ * equivalent to operator[](0)
+ */
+ T& front() { SkASSERT(fCount > 0); return fItemArray[0];}
+
+ const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];}
+
+ /**
+ * equivalent to operator[](count() - 1)
+ */
+ T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];}
+
+ const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];}
+
+ /**
+ * equivalent to operator[](count()-1-i)
+ */
+ T& fromBack(int i) {
+ SkASSERT(i >= 0);
+ SkASSERT(i < this->count());
+ return fItemArray[fCount - i - 1];
+ }
+
+ const T& fromBack(int i) const {
+ SkASSERT(i >= 0);
+ SkASSERT(i < this->count());
+ return fItemArray[fCount - i - 1];
+ }
+
+ bool operator==(const SkTArray<T, MEM_MOVE>& right) const {
+ int leftCount = this->count();
+ if (leftCount != right.count()) {
+ return false;
+ }
+ for (int index = 0; index < leftCount; ++index) {
+ if (fItemArray[index] != right.fItemArray[index]) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ bool operator!=(const SkTArray<T, MEM_MOVE>& right) const {
+ return !(*this == right);
+ }
+
+ int capacity() const {
+ return fAllocCount;
+ }
+
+protected:
+ /**
+ * Creates an empty array that will use the passed storage block until it
+ * is insufficiently large to hold the entire array.
+ */
+ template <int N>
+ SkTArray(SkAlignedSTStorage<N,T>* storage) {
+ this->initWithPreallocatedStorage(0, storage->get(), N);
+ }
+
+ /**
+ * Copy a C array, using preallocated storage if preAllocCount >=
+ * count. Otherwise storage will only be used when array shrinks
+ * to fit.
+ */
+ template <int N>
+ SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) {
+ this->initWithPreallocatedStorage(count, storage->get(), N);
+ this->copy(array);
+ }
+
+private:
+ void init(int count) {
+ fCount = SkToU32(count);
+ if (!count) {
+ fAllocCount = 0;
+ fItemArray = nullptr;
+ } else {
+ fAllocCount = SkToU32(std::max(count, kMinHeapAllocCount));
+ fItemArray = (T*)sk_malloc_throw((size_t)fAllocCount, sizeof(T));
+ }
+ fOwnMemory = true;
+ fReserved = false;
+ }
+
+ void initWithPreallocatedStorage(int count, void* preallocStorage, int preallocCount) {
+ SkASSERT(count >= 0);
+ SkASSERT(preallocCount > 0);
+ SkASSERT(preallocStorage);
+ fCount = count;
+ fItemArray = nullptr;
+ fReserved = false;
+ if (count > preallocCount) {
+ fAllocCount = std::max(count, kMinHeapAllocCount);
+ fItemArray = (T*)sk_malloc_throw(fAllocCount, sizeof(T));
+ fOwnMemory = true;
+ } else {
+ fAllocCount = preallocCount;
+ fItemArray = (T*)preallocStorage;
+ fOwnMemory = false;
+ }
+ }
+
+ /** In the following move and copy methods, 'dst' is assumed to be uninitialized raw storage.
+ * In the following move methods, 'src' is destroyed leaving behind uninitialized raw storage.
+ */
+ void copy(const T* src) {
+ // Some types may be trivially copyable, in which case we *could* use memcopy; but
+ // MEM_MOVE == true implies that the type is trivially movable, and not necessarily
+ // trivially copyable (think sk_sp<>). So short of adding another template arg, we
+ // must be conservative and use copy construction.
+ for (int i = 0; i < this->count(); ++i) {
+ new (fItemArray + i) T(src[i]);
+ }
+ }
+
+ template <bool E = MEM_MOVE> std::enable_if_t<E, void> move(int dst, int src) {
+ memcpy(&fItemArray[dst], &fItemArray[src], sizeof(T));
+ }
+ template <bool E = MEM_MOVE> std::enable_if_t<E, void> move(void* dst) {
+ sk_careful_memcpy(dst, fItemArray, fCount * sizeof(T));
+ }
+
+ template <bool E = MEM_MOVE> std::enable_if_t<!E, void> move(int dst, int src) {
+ new (&fItemArray[dst]) T(std::move(fItemArray[src]));
+ fItemArray[src].~T();
+ }
+ template <bool E = MEM_MOVE> std::enable_if_t<!E, void> move(void* dst) {
+ for (int i = 0; i < this->count(); ++i) {
+ new (static_cast<char*>(dst) + sizeof(T) * (size_t)i) T(std::move(fItemArray[i]));
+ fItemArray[i].~T();
+ }
+ }
+
+ static constexpr int kMinHeapAllocCount = 8;
+
+ // Helper function that makes space for n objects, adjusts the count, but does not initialize
+ // the new objects.
+ void* push_back_raw(int n) {
+ this->checkRealloc(n, kGrowing);
+ void* ptr = fItemArray + fCount;
+ fCount += n;
+ return ptr;
+ }
+
+ void checkRealloc(int delta, ReallocType reallocType) {
+ SkASSERT(fCount >= 0);
+ SkASSERT(fAllocCount >= 0);
+ SkASSERT(-delta <= this->count());
+
+ // Move into 64bit math temporarily, to avoid local overflows
+ int64_t newCount = fCount + delta;
+
+ // We allow fAllocCount to be in the range [newCount, 3*newCount]. We also never shrink
+ // when we're currently using preallocated memory, would allocate less than
+ // kMinHeapAllocCount, or a reserve count was specified that has yet to be exceeded.
+ bool mustGrow = newCount > fAllocCount;
+ bool shouldShrink = fAllocCount > 3 * newCount && fOwnMemory && !fReserved;
+ if (!mustGrow && !shouldShrink) {
+ return;
+ }
+
+ int64_t newAllocCount = newCount;
+ if (reallocType != kExactFit) {
+ // Whether we're growing or shrinking, leave at least 50% extra space for future growth.
+ newAllocCount += ((newCount + 1) >> 1);
+ // Align the new allocation count to kMinHeapAllocCount.
+ static_assert(SkIsPow2(kMinHeapAllocCount), "min alloc count not power of two.");
+ newAllocCount = (newAllocCount + (kMinHeapAllocCount - 1)) & ~(kMinHeapAllocCount - 1);
+ }
+
+ // At small sizes the old and new alloc count can both be kMinHeapAllocCount.
+ if (newAllocCount == fAllocCount) {
+ return;
+ }
+
+ fAllocCount = SkToU32(Sk64_pin_to_s32(newAllocCount));
+ SkASSERT(fAllocCount >= newCount);
+ T* newItemArray = (T*)sk_malloc_throw((size_t)fAllocCount, sizeof(T));
+ this->move(newItemArray);
+ if (fOwnMemory) {
+ sk_free(fItemArray);
+ }
+ fItemArray = newItemArray;
+ fOwnMemory = true;
+ fReserved = false;
+ }
+
+ T* fItemArray;
+ uint32_t fOwnMemory : 1;
+ uint32_t fCount : 31;
+ uint32_t fReserved : 1;
+ uint32_t fAllocCount : 31;
+};
+
+template <typename T, bool M> static inline void swap(SkTArray<T, M>& a, SkTArray<T, M>& b) {
+ a.swap(b);
+}
+
+template<typename T, bool MEM_MOVE> constexpr int SkTArray<T, MEM_MOVE>::kMinHeapAllocCount;
+
+/**
+ * Subclass of SkTArray that contains a preallocated memory block for the array.
+ */
+template <int N, typename T, bool MEM_MOVE = false>
+class SkSTArray : private SkAlignedSTStorage<N,T>, public SkTArray<T, MEM_MOVE> {
+private:
+ using STORAGE = SkAlignedSTStorage<N,T>;
+ using INHERITED = SkTArray<T, MEM_MOVE>;
+
+public:
+ SkSTArray()
+ : STORAGE{}, INHERITED(static_cast<STORAGE*>(this)) {}
+
+ SkSTArray(const T* array, int count)
+ : STORAGE{}, INHERITED(array, count, static_cast<STORAGE*>(this)) {}
+
+ SkSTArray(std::initializer_list<T> data)
+ : SkSTArray(data.begin(), data.size()) {}
+
+ explicit SkSTArray(int reserveCount)
+ : SkSTArray() {
+ this->reserve_back(reserveCount);
+ }
+
+ SkSTArray (const SkSTArray& that) : SkSTArray() { *this = that; }
+ explicit SkSTArray(const INHERITED& that) : SkSTArray() { *this = that; }
+ SkSTArray ( SkSTArray&& that) : SkSTArray() { *this = std::move(that); }
+ explicit SkSTArray( INHERITED&& that) : SkSTArray() { *this = std::move(that); }
+
+ SkSTArray& operator=(const SkSTArray& that) {
+ INHERITED::operator=(that);
+ return *this;
+ }
+ SkSTArray& operator=(const INHERITED& that) {
+ INHERITED::operator=(that);
+ return *this;
+ }
+
+ SkSTArray& operator=(SkSTArray&& that) {
+ INHERITED::operator=(std::move(that));
+ return *this;
+ }
+ SkSTArray& operator=(INHERITED&& that) {
+ INHERITED::operator=(std::move(that));
+ return *this;
+ }
+};
+
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2025-06-27 05:09:07 +0000