Move fCount and fReserve to the common code
The common code is much more substantial now. The reduces the binary
size by another 8K.
herb@salt ~/s/skia (encapsulate-fArray-2)> ls -l *_skottie_tool.stripped
-rwxr-xr-x 1 herb primarygroup 6486584 new_skottie_tool.stripped*
-rwxr-xr-x 1 herb primarygroup 6494776 old_skottie_tool.stripped*
herb@salt ~/s/skia (encapsulate-fArray-2)> awk -e 'BEGIN {print 6494776 - 6486584}'
8192
Change-Id: I9ba30594f150d9ebd59ab2491b758fde3eb8449e
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/583777
Reviewed-by: John Stiles <johnstiles@google.com>
Commit-Queue: Herb Derby <herb@google.com>
diff --git a/include/private/SkTDArray.h b/include/private/SkTDArray.h
index 417aada..096b992 100644
--- a/include/private/SkTDArray.h
+++ b/include/private/SkTDArray.h
@@ -13,6 +13,7 @@
#include "include/private/SkTo.h"
#include <algorithm>
+#include <cstddef>
#include <climits>
#include <initializer_list>
#include <tuple>
@@ -27,22 +28,63 @@
SkTDStorage& operator= (SkTDStorage&& that);
~SkTDStorage();
- int assign(const void* src, int count, size_t sizeOfT);
+ void reset();
- int resizeStorageToAtLeast(int count, size_t sizeOfT);
- int shrinkToFit(int count, size_t sizeOfT);
+ void assign(const void* src, int count, size_t sizeOfT);
+
+ bool empty() const { return fCount == 0; }
+ void clear() { fCount = 0; }
+ int size() const { return fCount; }
+
+ // Resizes the array to store exactly `newCount` elements.
+ //
+ // This never shrinks the allocation, and it may increase the allocation by
+ // more than is strictly required, based on a private growth heuristic.
+ void resize(int newCount, size_t sizeOfT);
+
+ int decreaseCount() {
+ SkASSERT(fCount > 0);
+ fCount -= 1;
+ return fCount;
+ }
+
+ void* push_back(size_t sizeOfT) {
+ if (fCount < fReserve) {
+ return fStorage + SkToSizeT(fCount++) * sizeOfT;
+ } else {
+ return this->append(sizeOfT);
+ }
+ }
+
+ size_t size_bytes(size_t sizeOfT) const;
+
+ int capacity() const { return fReserve; }
+ void reserve(size_t newReserve, size_t sizeOfT);
+
+ void shrinkToFit(size_t sizeOfT);
void swap(SkTDStorage& that) {
using std::swap;
swap(fStorage, that.fStorage);
}
- template <typename T>
- T* data() const { return static_cast<T*>(fStorage); }
+ template <typename T> T* data() const { return reinterpret_cast<T*>(fStorage); }
- struct StateUpdate {int count, reserve;};
- StateUpdate append(
- const void* src, int count, size_t sizeOfT, int reserve, int oldCount);
+ void* erase(int index, int count, size_t sizeOfT);
+ // Removes the entry at 'index' and replaces it with the last array element
+ void* removeShuffle(int index, size_t sizeOfT);
+
+ void* prepend(size_t sizeOfT);
+ void* append(size_t sizeOfT);
+ void* append(const void* src, int count, size_t sizeOfT);
+
+ void* insert(int index, size_t sizeOfT);
+ void* insert(int index, const void* src, int count, size_t sizeOfT);
+
private:
- void* fStorage{nullptr};
+ int calculateSizeDeltaOrDie(int delta) const;
+
+ std::byte* fStorage{nullptr};
+ int fReserve{0}; // size of the allocation in fArray (#elements)
+ int fCount{0}; // logical number of elements (fCount <= fReserve)
};
template <typename T> static inline void swap(SkTDStorage& a, SkTDStorage& b) { a.swap(b); }
@@ -58,102 +100,87 @@
SkTDArray() = default;
SkTDArray(const T src[], int count) {
SkASSERT(src || count == 0);
- fReserve = fStorage.assign(src, count, sizeof(T));
- fCount = count;
+ fStorage.assign(src, count, sizeof(T));
}
SkTDArray(const std::initializer_list<T>& list) : SkTDArray(list.begin(), list.size()) {}
SkTDArray(const SkTDArray<T>& src) {
- fReserve = fStorage.assign(src.data(), src.fCount, sizeof(T));
- fCount = src.fCount;
+ fStorage.assign(src.data(), src.count(), sizeof(T));
}
SkTDArray<T>& operator=(const SkTDArray<T>& src) {
if (this != &src) {
- if (src.fCount > fReserve) {
- fReserve = fStorage.assign(src.data(), src.fCount, sizeof(T));
- } else {
- sk_careful_memcpy(this->data(), src.data(), sizeof(T) * SkToSizeT(src.fCount));
- }
- fCount = src.fCount;
+ fStorage.assign(src.data(), src.count(), sizeof(T));
}
return *this;
}
SkTDArray(SkTDArray<T>&& src)
- : fStorage{std::move(src.fStorage)}
- , fReserve{src.fReserve}
- , fCount{src.fCount} {}
+ : fStorage{std::move(src.fStorage)} {}
SkTDArray<T>& operator=(SkTDArray<T>&& src) {
if (this != &src) {
fStorage = std::move(src.fStorage);
- fReserve = std::exchange(src.fReserve, 0);
- fCount = std::exchange(src.fCount, 0);
}
return *this;
}
friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
- return a.fCount == b.fCount &&
- (a.fCount == 0 || !memcmp(a.data(), b.data(), SkToSizeT(a.fCount) * sizeof(T)));
+ return a.count() == b.count() &&
+ (a.count() == 0 || !memcmp(a.data(), b.data(), SkToSizeT(a.size()) * sizeof(T)));
}
friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) { return !(a == b); }
void swap(SkTDArray<T>& that) {
using std::swap;
swap(fStorage, that.fStorage);
- swap(fReserve, that.fReserve);
- swap(fCount, that.fCount);
}
- bool empty() const { return fCount == 0; }
+ bool empty() const { return fStorage.empty(); }
// Return the number of elements in the array
- int count() const { return fCount; }
- size_t size() const { return fCount; }
+ int count() const { return fStorage.size(); }
+ int size() const { return fStorage.size(); }
// 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; }
+ int reserved() const { return fStorage.capacity(); }
// return the number of bytes in the array: count * sizeof(T)
- size_t bytes() const { return fCount * sizeof(T); }
+ size_t bytes() const { return SkToSizeT(this->size()) * sizeof(T); }
T* data() { return fStorage.data<T>(); }
const T* data() const { return fStorage.data<T>(); }
T* begin() { return this->data(); }
const T* begin() const { return this->data(); }
- T* end() { return this->data() ? this->data() + fCount : nullptr; }
- const T* end() const { return this->data() ? this->data() + fCount : nullptr; }
+ T* end() { return this->data() ? this->data() + this->size() : nullptr; }
+ const T* end() const { return this->data() ? this->data() + this->size() : nullptr; }
T& operator[](int index) {
- SkASSERT(index < fCount);
+ SkASSERT(index < this->size());
return this->data()[index];
}
const T& operator[](int index) const {
- SkASSERT(index < fCount);
+ SkASSERT(index < this->size());
return this->data()[index];
}
T& getAt(int index) { return (*this)[index]; }
const T& back() const {
- SkASSERT(fCount > 0);
- return this->data()[fCount - 1];
+ SkASSERT(this->size() > 0);
+ return this->data()[this->size() - 1];
}
T& back() {
- SkASSERT(fCount > 0);
- return this->data()[fCount - 1];
+ SkASSERT(this->size() > 0);
+ return this->data()[this->size() - 1];
}
void reset() {
- this->~SkTDArray();
- new (this) SkTDArray{};
+ fStorage.reset();
}
void rewind() {
- // same as setCount(0)
- fCount = 0;
+ fStorage.clear();
}
// Sets the number of elements in the array.
@@ -161,155 +188,89 @@
// 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;
+ fStorage.resize(count, sizeof(T));
}
- void reserve(int newReserve) {
- SkASSERT(0 <= newReserve);
- if (fReserve < newReserve) {
- this->resizeStorageToAtLeast(newReserve);
- }
+ void reserve(size_t n) {
+ fStorage.reserve(n, sizeof(T));
}
- T* append() { return this->append(1, nullptr); }
+ T* append() {
+ return reinterpret_cast<T*>(fStorage.append(sizeof(T)));
+ }
T* append(int count, const T* src = nullptr) {
- int oldCount = fCount;
- auto [newCount, newReserve] = fStorage.append(src, count, sizeof(T), fReserve, fCount);
- fCount = newCount;
- fReserve = newReserve;
- return this->data() + oldCount;
+ return reinterpret_cast<T*>(fStorage.append(src, count, sizeof(T)));
}
- T* insert(int index) { return this->insert(index, 1, nullptr); }
+ T* insert(int index) {
+ return reinterpret_cast<T*>(fStorage.insert(index, sizeof(T)));
+ }
T* insert(int index, int count, const T* src = nullptr) {
- SkASSERT(count);
- SkASSERT(index <= fCount);
- size_t oldCount = fCount;
- this->adjustCount(count);
- T* dst = this->data() + index;
- memmove(dst + count, dst, sizeof(T) * (oldCount - index));
- if (src) {
- memcpy(dst, src, sizeof(T) * count);
- }
- return dst;
+ return reinterpret_cast<T*>(fStorage.insert(index, src, count, sizeof(T)));
}
void remove(int index, int count = 1) {
- SkASSERT(index + count <= fCount);
- fCount = fCount - count;
- memmove(this->data() + index, this->data() + index + count, sizeof(T) * (fCount - index));
+ fStorage.erase(index, count, sizeof(T));
}
void removeShuffle(int index) {
- SkASSERT(index < fCount);
- int newCount = fCount - 1;
- fCount = newCount;
- if (index != newCount) {
- memcpy(this->data() + index, this->data() + newCount, sizeof(T));
- }
+ fStorage.removeShuffle(index, sizeof(T));
}
int find(const T& elem) const {
- const T* iter = this->data();
- const T* stop = this->data() + fCount;
+ const T* iter = this->begin();
+ const T* stop = this->end();
for (; iter < stop; iter++) {
if (*iter == elem) {
- return SkToInt(iter - this->data());
+ return SkToInt(iter - this->begin());
}
}
return -1;
}
// routines to treat the array like a stack
- void push_back(const T& v) { *this->append() = v; }
+ void push_back(const T& v) { *reinterpret_cast<T*>(fStorage.push_back(sizeof(T))) = v; }
void pop(T* elem) {
- SkASSERT(fCount > 0);
- if (elem) *elem = (*this)[fCount - 1];
- --fCount;
+ SkASSERT(this->size() > 0);
+ if (elem) {
+ *elem = (*this)[this->size() - 1];
+ }
+ fStorage.decreaseCount();
}
void pop() {
- SkASSERT(fCount > 0);
- --fCount;
+ fStorage.decreaseCount();
}
void deleteAll() {
- T* iter = this->data();
- T* stop = this->data() + fCount;
- while (iter < stop) {
- delete *iter;
- iter += 1;
+ for (T p : *this) {
+ delete p;
}
this->reset();
}
void freeAll() {
- T* iter = this->data();
- T* stop = this->data() + fCount;
- while (iter < stop) {
- sk_free(*iter);
- iter += 1;
+ for (T p : *this) {
+ sk_free(p);
}
+
this->reset();
}
void unrefAll() {
- T* iter = this->data();
- T* stop = this->data() + fCount;
- while (iter < stop) {
- (*iter)->unref();
- iter += 1;
+ for (T p : *this) {
+ p->unref();
}
this->reset();
}
-#ifdef SK_DEBUG
- void validate() const {
- SkASSERT((fReserve == 0 && this->data() == nullptr) ||
- (fReserve > 0 && this->data() != nullptr));
- SkASSERT(fCount <= fReserve);
- }
-#endif
-
void shrinkToFit() {
- if (fReserve > fCount) {
- fReserve = fStorage.shrinkToFit(fCount, sizeof(T));
- }
+ fStorage.shrinkToFit(sizeof(T));
}
private:
- // Adjusts the number of elements in the array.
- // This is the same as calling setCount(count() + delta).
- void adjustCount(int delta) {
- SkASSERT(delta > 0);
-
- // We take care to avoid overflow here.
- // The sum of fCount and delta is at most 4294967294, which fits fine in uint32_t.
- uint32_t count = (uint32_t)fCount + (uint32_t)delta;
- SkASSERT_RELEASE(SkTFitsIn<int>(count));
-
- this->setCount(SkTo<int>(count));
- }
-
- // 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: this does NOT modify fCount
- void resizeStorageToAtLeast(int count) {
- SkASSERT(count > fReserve);
- fReserve = fStorage.resizeStorageToAtLeast(count, sizeof(T));
- }
-
SkTDStorage fStorage;
- int fReserve = 0; // size of the allocation in fArray (#elements)
- int fCount = 0; // logical number of elements (fCount <= fReserve)
};
template <typename T> static inline void swap(SkTDArray<T>& a, SkTDArray<T>& b) { a.swap(b); }
diff --git a/src/core/SkTDArray.cpp b/src/core/SkTDArray.cpp
index aeac67a..80bc700 100644
--- a/src/core/SkTDArray.cpp
+++ b/src/core/SkTDArray.cpp
@@ -5,11 +5,26 @@
* found in the LICENSE file.
*/
+#include "include/private/SkMalloc.h"
#include "include/private/SkTDArray.h"
#include "include/private/SkTo.h"
+#include <utility>
+
+namespace {
+size_t offset(int n, size_t sizeOfT) {
+ return SkToSizeT(n) * sizeOfT;
+}
+
+size_t mem_size(int n, size_t sizeOfT) {
+ return SkToSizeT(n) * sizeOfT;
+}
+} // namespace
+
SkTDStorage::SkTDStorage(SkTDStorage&& that)
- : fStorage{std::move(that.fStorage)} { that.fStorage = nullptr; }
+ : fStorage{std::move(std::exchange(that.fStorage, nullptr))}
+ , fReserve{std::exchange(that.fReserve, 0)}
+ , fCount{std::exchange(that.fCount, 0)} {}
SkTDStorage& SkTDStorage::operator=(SkTDStorage&& that) {
if (this != &that) {
@@ -23,60 +38,170 @@
sk_free(fStorage);
}
-int SkTDStorage::assign(const void* src, int count, size_t sizeOfT) {
- if (count > 0) {
- fStorage = sk_realloc_throw(fStorage, SkToSizeT(count) * sizeOfT);
- memcpy(fStorage, src, SkToSizeT(count) * sizeOfT);
- }
- return count;
+void SkTDStorage::reset() {
+ this->~SkTDStorage();
+ new (this) SkTDStorage{};
}
-int SkTDStorage::resizeStorageToAtLeast(int count, size_t sizeOfT) {
- SkASSERT(count > 0);
+void SkTDStorage::assign(const void* src, int count, size_t sizeOfT) {
+ SkASSERT(count >= 0);
+ if (count > 0) {
+ fCount = count;
+ size_t byteSize = this->size_bytes(sizeOfT);
+ if (fCount > fReserve) {
+ fStorage = static_cast<std::byte*>(sk_realloc_throw(fStorage, byteSize));
+ fReserve = fCount;
+ }
+ memcpy(fStorage, src, byteSize);
+ }
+}
+
+void SkTDStorage::resize(int newCount, size_t sizeOfT) {
+ SkASSERT(newCount >= 0);
+ if (fReserve < newCount) {
+ this->reserve(newCount, sizeOfT);
+ }
+ fCount = newCount;
+}
+
+size_t SkTDStorage::size_bytes(size_t sizeOfT) const {
+ return offset(fCount, sizeOfT);
+}
+
+void SkTDStorage::reserve(size_t reserveSize, size_t sizeOfT) {
+ // Note: this takes a size_t to centralize size checking.
+ SkASSERT_RELEASE(SkTFitsIn<int>(reserveSize));
+
// Establish the maximum number of elements that includes a valid count for end. In the
// largest case end() = &fArray[INT_MAX] which is 1 after the last indexable element.
static constexpr int kMaxCount = INT_MAX;
// Assume that the array will max out.
- int newReserve = kMaxCount;
- if (kMaxCount - count > 4) {
+ int expandedReserve = kMaxCount;
+ int newReserve = SkToInt(reserveSize);
+ if (kMaxCount - newReserve > 4) {
// Add 1/4 more than we need. Add 4 to ensure this grows by at least 1. Pin to
// kMaxCount if no room for 1/4 growth.
- int growth = 4 + ((count + 4) >> 2);
+ int growth = 4 + ((newReserve + 4) >> 2);
// Read this line as: if (count + growth < kMaxCount) { ... }
// It's rewritten to avoid signed integer overflow.
- if (kMaxCount - count > growth) {
- newReserve = count + growth;
+ if (kMaxCount - newReserve > growth) {
+ expandedReserve = newReserve + growth;
}
}
- fStorage = sk_realloc_throw(fStorage, SkToSizeT(newReserve) * sizeOfT);
- return newReserve;
+ fReserve = expandedReserve;
+ fStorage = static_cast<std::byte*>(sk_realloc_throw(fStorage, mem_size(fReserve, sizeOfT)));
}
-int SkTDStorage::shrinkToFit(int count, size_t sizeOfT) {
- fStorage = sk_realloc_throw(fStorage, SkToSizeT(count) * sizeOfT);
- return count;
+void SkTDStorage::shrinkToFit(size_t sizeOfT) {
+ // Because calling realloc with size of 0 is implementation defined, force to a good state by
+ // freeing fStorage and setting reserve to 0.
+ if (fCount != 0) {
+ fReserve = fCount;
+ fStorage = static_cast<std::byte*>(sk_realloc_throw(fStorage, mem_size(fReserve, sizeOfT)));
+ } else {
+ fReserve = 0;
+ sk_free(fStorage);
+ fStorage = nullptr;
+ }
}
-SkTDStorage::StateUpdate SkTDStorage::append(
- const void* src, int count, size_t sizeOfT, int reserve, int oldCount) {
+void* SkTDStorage::erase(int index, int count, size_t sizeOfT) {
+ SkASSERT(index >= 0);
SkASSERT(count >= 0);
- int newCount = oldCount;
- int newReserve = reserve;
+ SkASSERT(index + count <= fCount);
+
+ // Check that the resulting size fits in an int. This will abort if not.
+ const int newCount = this->calculateSizeDeltaOrDie(-count);
+
+ const int tailBegin = index + count;
+ const size_t tailBeginOffset = offset(tailBegin, sizeOfT);
if (count > 0) {
- // We take care to avoid overflow here.
- // The sum of fCount and delta is at most 4294967294, which fits fine in uint32_t.
- uint32_t testCount = (uint32_t)oldCount + (uint32_t)count;
- SkASSERT_RELEASE(SkTFitsIn<int>(testCount));
- newCount = testCount;
- if (newCount > reserve) {
- newReserve = this->resizeStorageToAtLeast(newCount, sizeOfT);
+ // Move the tail down if there is one.
+ if (tailBegin < fCount) {
+ const size_t headEndOffset = offset(index, sizeOfT);
+ const size_t gapSize = this->size_bytes(sizeOfT) - tailBeginOffset;
+ memmove(fStorage + headEndOffset, fStorage + tailBeginOffset, gapSize);
}
+ this->resize(newCount, sizeOfT);
+ }
+
+ return fStorage + tailBeginOffset;
+}
+
+void* SkTDStorage::removeShuffle(int index, size_t sizeOfT) {
+ SkASSERT(0 <= index && index < fCount);
+ // Check that the new count is valid.
+ int newCount = this->calculateSizeDeltaOrDie(-1);
+
+ const size_t indexOffset = offset(index, sizeOfT);
+ const size_t lastElementOffset = offset(newCount, sizeOfT);
+
+ // Fill the index if not the last element.
+ if (index < newCount) {
+ memmove(fStorage + indexOffset, fStorage + lastElementOffset, sizeOfT);
+ }
+ this->resize(newCount, sizeOfT);
+ return fStorage + lastElementOffset;
+}
+
+void* SkTDStorage::prepend(size_t sizeOfT) {
+ return this->insert(/*index=*/0, sizeOfT);
+}
+
+void* SkTDStorage::append(size_t sizeOfT) {
+ return this->insert(fCount, sizeOfT);
+}
+
+void* SkTDStorage::append(const void* src, int count, size_t sizeOfT) {
+ return this->insert(fCount, src, count, sizeOfT);
+}
+
+void* SkTDStorage::insert(int index, size_t sizeOfT) {
+ return this->insert(index, nullptr, /*count=*/1, sizeOfT);
+}
+
+void* SkTDStorage::insert(int index, const void* src, int count, size_t sizeOfT) {
+ SkASSERT(0 <= index && index <= fCount);
+ SkASSERT(count >= 0);
+ const size_t indexOffset = offset(index, sizeOfT);
+
+ if (count > 0) {
+ const int oldCount = fCount;
+
+ size_t oldCountOffset = this->size_bytes(sizeOfT);
+
+ const int newCount = this->calculateSizeDeltaOrDie(count);
+ this->resize(newCount, sizeOfT);
+
+ // Shift memory to make space.
+ if (index < oldCount) {
+ // Safe because index <= oldCount and oldCount + count is safe.
+ size_t shiftOffset = offset(index + count, sizeOfT);
+
+ // Move the tail of data from index to oldCount.
+ memmove(fStorage + shiftOffset, fStorage + indexOffset, oldCountOffset - indexOffset);
+ }
+
if (src != nullptr) {
- memcpy(this->data<char>() + sizeOfT *SkToSizeT(oldCount), src,
- sizeOfT *SkToSizeT(count));
+ memcpy(fStorage + indexOffset, src, mem_size(count, sizeOfT));
}
}
- return {newCount, newReserve};
+
+ return fStorage + indexOffset;
}
+
+int SkTDStorage::calculateSizeDeltaOrDie(int delta) const {
+ // Check that count will not go negative.
+ SkASSERT_RELEASE(-fCount <= delta);
+
+ // We take care to avoid overflow here.
+ // Because fCount and delta are both signed 32-bit ints, the sum of fCount and delta is at
+ // most 4294967294, which fits fine in uint32_t. Proof follows in assert.
+ static_assert(UINT32_MAX >= (uint32_t)INT_MAX + (uint32_t)INT_MAX);
+ uint32_t count = (uint32_t)this->size() + (uint32_t)delta;
+ SkASSERT_RELEASE(SkTFitsIn<int>(count));
+ return SkToInt(count);
+}
+
diff --git a/src/utils/SkCharToGlyphCache.cpp b/src/utils/SkCharToGlyphCache.cpp
index 5536047..7387ed1 100644
--- a/src/utils/SkCharToGlyphCache.cpp
+++ b/src/utils/SkCharToGlyphCache.cpp
@@ -108,7 +108,7 @@
void SkCharToGlyphCache::insertCharAndGlyph(int index, SkUnichar unichar, SkGlyphID glyph) {
SkASSERT(fK32.size() == fV16.size());
- SkASSERT((unsigned)index < fK32.size());
+ SkASSERT(index < fK32.size());
SkASSERT(unichar < fK32[index]);
*fK32.insert(index) = unichar;
