Revert "implement SkTDArray with std::vector"
This reverts commit 80e1d56e198c5fd9fe6db0c945bd558053a8dc6a.
Reason for revert: SkRTree.cpp:57 asserting, probably this?
Original change's description:
> implement SkTDArray with std::vector
>
> It's always worth seeing if we can get away with replacing custom data
> structures with ones from the standard library. Our array-like types
> are all good candidates to replace with std::vector, and it's especially
> easy to start with SkTDArray. Unlike the others, it has no preallocated
> S-variant, which is tricky to make work with std::vector.
>
> SkTDArray also has known integer overflow bugs, leading to out of range
> writes. It'd be _very_ nice to ditch it for a better standard vector.
>
> I removed a bunch of unused or little-used methods, and updated a couple
> call sites that used methods in unusual or dangerous ways.
>
> I've had to tweak GrAAConvexTessellator and SkBaseShadowTessellator just
> a touch to work within the constraints of an std::vector impl. It's not
> intended to be legal to write to the reserved-but-not-counted elements
> of an SkTDArray, but you can get away with it in our old implementation.
> This version now uses setCount() to actually reserve and count them, and
> should have the same performance and use the same amount of memory.
>
> The PathMeasure_explosion GM I added recently to reproduce this bug now
> draws without triggering undefined behavior or ASAN errors, provided you
> have ~40GB of RAM.
>
> Bug: skia:7674
>
> Change-Id: I4eacae18a976cd4a6d218102f8ca5d973d4d7d0e
> Reviewed-on: https://skia-review.googlesource.com/115982
> Reviewed-by: Brian Osman <brianosman@google.com>
> Commit-Queue: Mike Klein <mtklein@chromium.org>
TBR=mtklein@chromium.org,bungeman@google.com,brianosman@google.com
Change-Id: Icffd9f22fe89746a970ff598e1a05c774960bc0e
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Bug: skia:7674
Reviewed-on: https://skia-review.googlesource.com/117901
Reviewed-by: Mike Klein <mtklein@chromium.org>
Commit-Queue: Mike Klein <mtklein@chromium.org>
diff --git a/include/private/SkTDArray.h b/include/private/SkTDArray.h
index e9660d8..2ba3354 100644
--- a/include/private/SkTDArray.h
+++ b/include/private/SkTDArray.h
@@ -1,3 +1,4 @@
+
/*
* Copyright 2006 The Android Open Source Project
*
@@ -10,125 +11,362 @@
#define SkTDArray_DEFINED
#include "SkTypes.h"
-#include <vector>
+#include "SkMalloc.h"
-// SkTDArray is now a thin wrapper over std::vector.
-// Please feel free to use either.
-
-// Implementation notes:
-// 1) We take care to use SkToInt(size_t) and SkToSizeT(int) to do conversions that
-// assert the value fits either direction. The SkToInt(size_t) should be obvious,
-// but even SkToSizeT(int) has caught negative values passed in where you'd expect
-// >= 0.
-//
-// 2) We try to add yet-undefined items to the array with default initialization.
-// This can look funny, as the only really good way to get that is to write
-// "T v;", a T default-intialized on the stack, often meaning uninitialized.
-// This avoids the slightly more expensive value initialization (like, floats
-// to 0.0f) that std::vector normally provides.
-//
-// 3) See the end of the file for how we avoid std::vector<bool>.
-
-template <typename T>
-class SkTDArray {
+template <typename T> class SkTDArray {
public:
- SkTDArray() = default;
- ~SkTDArray() = default;
- SkTDArray(const SkTDArray&) = default;
- SkTDArray(SkTDArray&&) = default;
- SkTDArray& operator=(const SkTDArray&) = default;
- SkTDArray& operator=(SkTDArray&&) = default;
+ SkTDArray() : fArray(nullptr), fReserve(0), fCount(0) {}
+ SkTDArray(const T src[], int count) {
+ SkASSERT(src || count == 0);
- SkTDArray(const T* src, int n) : fVec(src, src+SkToSizeT(n)) {}
-
- friend bool operator==(const SkTDArray& a, const SkTDArray& b) { return a.fVec == b.fVec; }
- friend bool operator!=(const SkTDArray& a, const SkTDArray& b) { return a.fVec != b.fVec; }
-
- void swap(SkTDArray& that) { std::swap(fVec, that.fVec); }
-
- bool isEmpty() const { return fVec.empty(); }
- int count() const { return SkToInt(fVec.size()); }
- int reserved() const { return SkToInt(fVec.capacity()); }
- size_t bytes() const { return sizeof(T) * fVec.size(); }
-
- const T* begin() const { return fVec.data(); }
- T* begin() { return fVec.data(); }
- const T* end() const { return this->begin() + fVec.size(); }
- T* end() { return this->begin() + fVec.size(); }
-
- const T& operator[](int k) const { return fVec[SkToSizeT(k)]; }
- T& operator[](int k) { return fVec[SkToSizeT(k)]; }
- const T& getAt(int k) const { return fVec[SkToSizeT(k)]; }
- T& getAt(int k) { return fVec[SkToSizeT(k)]; }
-
- void reset() { this->~SkTDArray(); new (this) SkTDArray(); }
- void rewind() { fVec.clear(); }
- void setCount (int n) { T v; fVec.resize(SkToSizeT(n), v); }
- void setReserve(int n) { fVec.reserve(SkToSizeT(n)); }
- void shrinkToFit() { fVec.shrink_to_fit(); }
-
- T* append(int n = 1, const T* src = nullptr) {
- return this->insert(this->count(), n, src);
- }
- T* insert(int ix, int n = 1, const T* src = nullptr) {
- if (src) {
- return &*fVec.insert(fVec.begin() + SkToSizeT(ix), src, src+SkToSizeT(n));
+ fReserve = fCount = 0;
+ fArray = nullptr;
+ if (count) {
+ fArray = (T*)sk_malloc_throw(count * sizeof(T));
+ memcpy(fArray, src, sizeof(T) * count);
+ fReserve = fCount = count;
}
- T v;
- return &*fVec.insert(fVec.begin() + SkToSizeT(ix), SkToSizeT(n), v);
+ }
+ SkTDArray(const SkTDArray<T>& src) : fArray(nullptr), fReserve(0), fCount(0) {
+ SkTDArray<T> tmp(src.fArray, src.fCount);
+ this->swap(tmp);
+ }
+ SkTDArray(SkTDArray<T>&& src) : fArray(nullptr), fReserve(0), fCount(0) {
+ this->swap(src);
+ }
+ ~SkTDArray() {
+ sk_free(fArray);
}
- void remove(int ix, int n = 1) {
- fVec.erase(fVec.begin() + SkToSizeT(ix),
- fVec.begin() + SkToSizeT(ix) + SkToSizeT(n));
+ SkTDArray<T>& operator=(const SkTDArray<T>& src) {
+ if (this != &src) {
+ if (src.fCount > fReserve) {
+ SkTDArray<T> tmp(src.fArray, src.fCount);
+ this->swap(tmp);
+ } else {
+ sk_careful_memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
+ fCount = src.fCount;
+ }
+ }
+ return *this;
}
- void removeShuffle(int ix) {
- std::swap(fVec[SkToSizeT(ix)], fVec.back());
- fVec.pop_back();
+ SkTDArray<T>& operator=(SkTDArray<T>&& src) {
+ if (this != &src) {
+ this->swap(src);
+ src.reset();
+ }
+ return *this;
}
- int find(const T& value) const {
- for (int i = 0; i < this->count(); i++) {
- if (fVec[i] == value) {
- return i;
+ friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
+ return a.fCount == b.fCount &&
+ (a.fCount == 0 ||
+ !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
+ }
+ friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) {
+ return !(a == b);
+ }
+
+ void swap(SkTDArray<T>& other) {
+ SkTSwap(fArray, other.fArray);
+ SkTSwap(fReserve, other.fReserve);
+ SkTSwap(fCount, other.fCount);
+ }
+
+ bool isEmpty() const { return fCount == 0; }
+
+ /**
+ * Return the number of elements in the array
+ */
+ int count() const { return fCount; }
+
+ /**
+ * Return the total number of elements allocated.
+ * reserved() - count() gives you the number of elements you can add
+ * without causing an allocation.
+ */
+ int reserved() const { return fReserve; }
+
+ /**
+ * return the number of bytes in the array: count * sizeof(T)
+ */
+ size_t bytes() const { return fCount * sizeof(T); }
+
+ T* begin() { return fArray; }
+ const T* begin() const { return fArray; }
+ T* end() { return fArray ? fArray + fCount : nullptr; }
+ const T* end() const { return fArray ? fArray + fCount : nullptr; }
+
+ T& operator[](int index) {
+ SkASSERT(index < fCount);
+ return fArray[index];
+ }
+ const T& operator[](int index) const {
+ SkASSERT(index < fCount);
+ return fArray[index];
+ }
+
+ T& getAt(int index) {
+ return (*this)[index];
+ }
+ const T& getAt(int index) const {
+ return (*this)[index];
+ }
+
+ void reset() {
+ if (fArray) {
+ sk_free(fArray);
+ fArray = nullptr;
+ fReserve = fCount = 0;
+ } else {
+ SkASSERT(fReserve == 0 && fCount == 0);
+ }
+ }
+
+ void rewind() {
+ // same as setCount(0)
+ fCount = 0;
+ }
+
+ /**
+ * Sets the number of elements in the array.
+ * If the array does not have space for count elements, it will increase
+ * the storage allocated to some amount greater than that required.
+ * It will never shrink the storage.
+ */
+ void setCount(int count) {
+ SkASSERT(count >= 0);
+ if (count > fReserve) {
+ this->resizeStorageToAtLeast(count);
+ }
+ fCount = count;
+ }
+
+ void setReserve(int reserve) {
+ if (reserve > fReserve) {
+ this->resizeStorageToAtLeast(reserve);
+ }
+ }
+
+ T* prepend() {
+ this->adjustCount(1);
+ memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
+ return fArray;
+ }
+
+ T* append() {
+ return this->append(1, nullptr);
+ }
+ T* append(int count, const T* src = nullptr) {
+ int oldCount = fCount;
+ if (count) {
+ SkASSERT(src == nullptr || fArray == nullptr ||
+ src + count <= fArray || fArray + oldCount <= src);
+
+ this->adjustCount(count);
+ if (src) {
+ memcpy(fArray + oldCount, src, sizeof(T) * count);
+ }
+ }
+ return fArray + oldCount;
+ }
+
+ T* appendClear() {
+ T* result = this->append();
+ *result = 0;
+ return result;
+ }
+
+ T* insert(int index) {
+ return this->insert(index, 1, nullptr);
+ }
+ T* insert(int index, int count, const T* src = nullptr) {
+ SkASSERT(count);
+ SkASSERT(index <= fCount);
+ size_t oldCount = fCount;
+ this->adjustCount(count);
+ T* dst = fArray + index;
+ memmove(dst + count, dst, sizeof(T) * (oldCount - index));
+ if (src) {
+ memcpy(dst, src, sizeof(T) * count);
+ }
+ return dst;
+ }
+
+ void remove(int index, int count = 1) {
+ SkASSERT(index + count <= fCount);
+ fCount = fCount - count;
+ memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
+ }
+
+ void removeShuffle(int index) {
+ SkASSERT(index < fCount);
+ int newCount = fCount - 1;
+ fCount = newCount;
+ if (index != newCount) {
+ memcpy(fArray + index, fArray + newCount, sizeof(T));
+ }
+ }
+
+ template <typename S> int select(S&& selector) const {
+ const T* iter = fArray;
+ const T* stop = fArray + fCount;
+
+ for (; iter < stop; iter++) {
+ if (selector(*iter)) {
+ return SkToInt(iter - fArray);
}
}
return -1;
}
- bool contains(const T& value) const {
- return this->find(value) >= 0;
+
+ int find(const T& elem) const {
+ const T* iter = fArray;
+ const T* stop = fArray + fCount;
+
+ for (; iter < stop; iter++) {
+ if (*iter == elem) {
+ return SkToInt(iter - fArray);
+ }
+ }
+ return -1;
}
- void push(const T& value) { fVec.push_back(value); }
- T* push() { T v; fVec.push_back(v); return &fVec.back(); }
- void pop(T* value = nullptr) { if (value) { *value = fVec.back(); } fVec.pop_back(); }
- const T& top() const { return fVec.back(); }
- T& top() { return fVec.back(); }
+ int rfind(const T& elem) const {
+ const T* iter = fArray + fCount;
+ const T* stop = fArray;
- void deleteAll() { for (T ptr : fVec) { delete ptr; } this->reset(); }
- void freeAll() { for (T ptr : fVec) { sk_free(ptr); } this->reset(); }
- void unrefAll() { for (T ptr : fVec) { ptr->unref(); } this->reset(); }
- void safeUnrefAll() { for (T ptr : fVec) { SkSafeUnref(ptr); } this->reset(); }
+ while (iter > stop) {
+ if (*--iter == elem) {
+ return SkToInt(iter - stop);
+ }
+ }
+ return -1;
+ }
-#if defined(SK_DEBUG)
- void validate() const {}
+ /**
+ * Returns true iff the array contains this element.
+ */
+ bool contains(const T& elem) const {
+ return (this->find(elem) >= 0);
+ }
+
+ /**
+ * Copies up to max elements into dst. The number of items copied is
+ * capped by count - index. The actual number copied is returned.
+ */
+ int copyRange(T* dst, int index, int max) const {
+ SkASSERT(max >= 0);
+ SkASSERT(!max || dst);
+ if (index >= fCount) {
+ return 0;
+ }
+ int count = SkMin32(max, fCount - index);
+ memcpy(dst, fArray + index, sizeof(T) * count);
+ return count;
+ }
+
+ void copy(T* dst) const {
+ this->copyRange(dst, 0, fCount);
+ }
+
+ // routines to treat the array like a stack
+ T* push() { return this->append(); }
+ void push(const T& elem) { *this->append() = elem; }
+ const T& top() const { return (*this)[fCount - 1]; }
+ T& top() { return (*this)[fCount - 1]; }
+ void pop(T* elem) { SkASSERT(fCount > 0); if (elem) *elem = (*this)[fCount - 1]; --fCount; }
+ void pop() { SkASSERT(fCount > 0); --fCount; }
+
+ void deleteAll() {
+ T* iter = fArray;
+ T* stop = fArray + fCount;
+ while (iter < stop) {
+ delete *iter;
+ iter += 1;
+ }
+ this->reset();
+ }
+
+ void freeAll() {
+ T* iter = fArray;
+ T* stop = fArray + fCount;
+ while (iter < stop) {
+ sk_free(*iter);
+ iter += 1;
+ }
+ this->reset();
+ }
+
+ void unrefAll() {
+ T* iter = fArray;
+ T* stop = fArray + fCount;
+ while (iter < stop) {
+ (*iter)->unref();
+ iter += 1;
+ }
+ this->reset();
+ }
+
+ void safeUnrefAll() {
+ T* iter = fArray;
+ T* stop = fArray + fCount;
+ while (iter < stop) {
+ SkSafeUnref(*iter);
+ iter += 1;
+ }
+ this->reset();
+ }
+
+ void visitAll(void visitor(T&)) {
+ T* stop = this->end();
+ for (T* curr = this->begin(); curr < stop; curr++) {
+ if (*curr) {
+ visitor(*curr);
+ }
+ }
+ }
+
+#ifdef SK_DEBUG
+ void validate() const {
+ SkASSERT((fReserve == 0 && fArray == nullptr) ||
+ (fReserve > 0 && fArray != nullptr));
+ SkASSERT(fCount <= fReserve);
+ }
#endif
+ void shrinkToFit() {
+ fReserve = fCount;
+ fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
+ }
+
private:
- std::vector<T> fVec;
+ T* fArray;
+ int fReserve;
+ int fCount;
+
+ /**
+ * Adjusts the number of elements in the array.
+ * This is the same as calling setCount(count() + delta).
+ */
+ void adjustCount(int delta) {
+ this->setCount(fCount + delta);
+ }
+
+ /**
+ * Increase the storage allocation such that it can hold (fCount + extra)
+ * elements.
+ * It never shrinks the allocation, and it may increase the allocation by
+ * more than is strictly required, based on a private growth heuristic.
+ *
+ * note: does NOT modify fCount
+ */
+ void resizeStorageToAtLeast(int count) {
+ SkASSERT(count > fReserve);
+ fReserve = count + 4;
+ fReserve += fReserve / 4;
+ fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
+ }
};
-// Avoid using std::vector<bool> (annoying weird bitvector specialization).
-
-struct SkTDArray_bool {
- bool value;
-
- SkTDArray_bool() = default;
- SkTDArray_bool(bool v) : value(v) {}
- operator bool() const { return value; }
-};
-
-template <>
-class SkTDArray<bool> : public SkTDArray<SkTDArray_bool> {};
-
#endif
diff --git a/src/core/SkPictureRecord.cpp b/src/core/SkPictureRecord.cpp
index f9d6bcc..6268584 100644
--- a/src/core/SkPictureRecord.cpp
+++ b/src/core/SkPictureRecord.cpp
@@ -805,14 +805,14 @@
///////////////////////////////////////////////////////////////////////////////
template <typename T> int find_or_append_uniqueID(SkTDArray<const T*>& array, const T* obj) {
- for (int i = 0; i < array.count(); i++) {
- if (array[i]->uniqueID() == obj->uniqueID()) {
- return i;
- }
+ int index = array.select([&](const T* elem) {
+ return elem->uniqueID() == obj->uniqueID();
+ });
+ if (index < 0) {
+ index = array.count();
+ *array.append() = SkRef(obj);
}
- int i = array.count();
- *array.append() = SkRef(obj);
- return i;
+ return index;
}
sk_sp<SkSurface> SkPictureRecord::onNewSurface(const SkImageInfo& info, const SkSurfaceProps&) {
diff --git a/src/gpu/ops/GrAAConvexTessellator.cpp b/src/gpu/ops/GrAAConvexTessellator.cpp
index c3840ea..9927d98 100644
--- a/src/gpu/ops/GrAAConvexTessellator.cpp
+++ b/src/gpu/ops/GrAAConvexTessellator.cpp
@@ -934,7 +934,7 @@
void GrAAConvexTessellator::quadTo(const SkPoint pts[3]) {
int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance);
- fPointBuffer.setCount(maxCount);
+ fPointBuffer.setReserve(maxCount);
SkPoint* target = fPointBuffer.begin();
int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
kQuadTolerance, &target, maxCount);
@@ -953,7 +953,7 @@
void GrAAConvexTessellator::cubicTo(const SkMatrix& m, SkPoint pts[4]) {
m.mapPoints(pts, 4);
int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance);
- fPointBuffer.setCount(maxCount);
+ fPointBuffer.setReserve(maxCount);
SkPoint* target = fPointBuffer.begin();
int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
kCubicTolerance, &target, maxCount);
diff --git a/src/utils/SkOffsetPolygon.cpp b/src/utils/SkOffsetPolygon.cpp
index 1bef50c..c8ebbeb 100755
--- a/src/utils/SkOffsetPolygon.cpp
+++ b/src/utils/SkOffsetPolygon.cpp
@@ -274,9 +274,7 @@
static constexpr SkScalar kCleanupTolerance = 0.01f;
insetPolygon->reset();
- if (insetVertexCount >= 0) {
- insetPolygon->setReserve(insetVertexCount);
- }
+ insetPolygon->setReserve(insetVertexCount);
currIndex = -1;
for (int i = 0; i < inputPolygonSize; ++i) {
if (edgeData[i].fValid && (currIndex == -1 ||
diff --git a/src/utils/SkShadowTessellator.cpp b/src/utils/SkShadowTessellator.cpp
index 0d3746a..75e4059 100755
--- a/src/utils/SkShadowTessellator.cpp
+++ b/src/utils/SkShadowTessellator.cpp
@@ -185,7 +185,7 @@
}
// TODO: Pull PathUtils out of Ganesh?
int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance);
- fPointBuffer.setCount(maxCount);
+ fPointBuffer.setReserve(maxCount);
SkPoint* target = fPointBuffer.begin();
int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
kQuadTolerance, &target, maxCount);
@@ -210,7 +210,7 @@
#if SK_SUPPORT_GPU
// TODO: Pull PathUtils out of Ganesh?
int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance);
- fPointBuffer.setCount(maxCount);
+ fPointBuffer.setReserve(maxCount);
SkPoint* target = fPointBuffer.begin();
int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
kCubicTolerance, &target, maxCount);
diff --git a/tests/SubsetPath.cpp b/tests/SubsetPath.cpp
index c1f2a62..6a7660e 100644
--- a/tests/SubsetPath.cpp
+++ b/tests/SubsetPath.cpp
@@ -193,7 +193,7 @@
bool addLineTo = false;
while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
bool enabled = SkPath::kLine_Verb <= verb && verb <= SkPath::kCubic_Verb
- ? (bool)fSelected[verbIndex++] : false;
+ ? fSelected[verbIndex++] : false;
if (enabled) {
if (addMoveTo) {
result.moveTo(pts[0]);