1 /*
2 * Copyright 2018 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 #include "include/private/base/SkTDArray.h"
9
10 #include "include/private/base/SkMalloc.h"
11 #include "include/private/base/SkTFitsIn.h"
12 #include "include/private/base/SkTo.h"
13
14 #include <climits>
15 #include <cstddef>
16 #include <cstdint>
17 #include <cstring>
18 #include <new>
19
SkTDStorage(int sizeOfT)20 SkTDStorage::SkTDStorage(int sizeOfT) : fSizeOfT{sizeOfT} {}
21
SkTDStorage(const void * src,int size,int sizeOfT)22 SkTDStorage::SkTDStorage(const void* src, int size, int sizeOfT)
23 : fSizeOfT{sizeOfT}
24 , fCapacity{size}
25 , fSize{size} {
26 if (size > 0) {
27 SkASSERT(src != nullptr);
28 size_t storageSize = this->bytes(size);
29 fStorage = static_cast<std::byte*>(sk_malloc_throw(storageSize));
30 memcpy(fStorage, src, storageSize);
31 }
32 }
33
SkTDStorage(const SkTDStorage & that)34 SkTDStorage::SkTDStorage(const SkTDStorage& that)
35 : SkTDStorage{that.fStorage, that.fSize, that.fSizeOfT} {}
36
operator =(const SkTDStorage & that)37 SkTDStorage& SkTDStorage::operator=(const SkTDStorage& that) {
38 if (this != &that) {
39 if (that.fSize <= fCapacity) {
40 fSize = that.fSize;
41 if (fSize > 0) {
42 memcpy(fStorage, that.data(), that.size_bytes());
43 }
44 } else {
45 *this = SkTDStorage{that.data(), that.size(), that.fSizeOfT};
46 }
47 }
48 return *this;
49 }
50
SkTDStorage(SkTDStorage && that)51 SkTDStorage::SkTDStorage(SkTDStorage&& that)
52 : fSizeOfT{that.fSizeOfT}
53 , fStorage(std::exchange(that.fStorage, nullptr))
54 , fCapacity{that.fCapacity}
55 , fSize{that.fSize} {}
56
operator =(SkTDStorage && that)57 SkTDStorage& SkTDStorage::operator=(SkTDStorage&& that) {
58 if (this != &that) {
59 this->~SkTDStorage();
60 new (this) SkTDStorage{std::move(that)};
61 }
62 return *this;
63 }
64
~SkTDStorage()65 SkTDStorage::~SkTDStorage() {
66 sk_free(fStorage);
67 }
68
reset()69 void SkTDStorage::reset() {
70 const int sizeOfT = fSizeOfT;
71 this->~SkTDStorage();
72 new (this) SkTDStorage{sizeOfT};
73 }
74
swap(SkTDStorage & that)75 void SkTDStorage::swap(SkTDStorage& that) {
76 SkASSERT(fSizeOfT == that.fSizeOfT);
77 using std::swap;
78 swap(fStorage, that.fStorage);
79 swap(fCapacity, that.fCapacity);
80 swap(fSize, that.fSize);
81 }
82
resize(int newSize)83 void SkTDStorage::resize(int newSize) {
84 SkASSERT(newSize >= 0);
85 if (newSize > fCapacity) {
86 this->reserve(newSize);
87 }
88 fSize = newSize;
89 }
90
reserve(int newCapacity)91 void SkTDStorage::reserve(int newCapacity) {
92 SkASSERT(newCapacity >= 0);
93 if (newCapacity > fCapacity) {
94 // Establish the maximum number of elements that includes a valid count for end. In the
95 // largest case end() = &fArray[INT_MAX] which is 1 after the last indexable element.
96 static constexpr int kMaxCount = INT_MAX;
97
98 // Assume that the array will max out.
99 int expandedReserve = kMaxCount;
100 if (kMaxCount - newCapacity > 4) {
101 // Add 1/4 more than we need. Add 4 to ensure this grows by at least 1. Pin to
102 // kMaxCount if no room for 1/4 growth.
103 int growth = 4 + ((newCapacity + 4) >> 2);
104 // Read this line as: if (count + growth < kMaxCount) { ... }
105 // It's rewritten to avoid signed integer overflow.
106 if (kMaxCount - newCapacity > growth) {
107 expandedReserve = newCapacity + growth;
108 }
109 }
110
111
112 // With a T size of 1, the above allocator produces the progression of 7, 15, ... Since,
113 // the sizeof max_align_t is often 16, there is no reason to allocate anything less than
114 // 16 bytes. This eliminates a realloc when pushing back bytes to an SkTDArray.
115 if (fSizeOfT == 1) {
116 // Round up to the multiple of 16.
117 expandedReserve = (expandedReserve + 15) & ~15;
118 }
119
120 fCapacity = expandedReserve;
121 size_t newStorageSize = this->bytes(fCapacity);
122 fStorage = static_cast<std::byte*>(sk_realloc_throw(fStorage, newStorageSize));
123 }
124 }
125
shrink_to_fit()126 void SkTDStorage::shrink_to_fit() {
127 if (fCapacity != fSize) {
128 fCapacity = fSize;
129 // Because calling realloc with size of 0 is implementation defined, force to a good state
130 // by freeing fStorage.
131 if (fCapacity > 0) {
132 fStorage = static_cast<std::byte*>(sk_realloc_throw(fStorage, this->bytes(fCapacity)));
133 } else {
134 sk_free(fStorage);
135 fStorage = nullptr;
136 }
137 }
138 }
139
erase(int index,int count)140 void SkTDStorage::erase(int index, int count) {
141 SkASSERT(count >= 0);
142 SkASSERT(fSize >= count);
143 SkASSERT(0 <= index && index <= fSize);
144
145 if (count > 0) {
146 // Check that the resulting size fits in an int. This will abort if not.
147 const int newCount = this->calculateSizeOrDie(-count);
148 this->moveTail(index, index + count, fSize);
149 this->resize(newCount);
150 }
151 }
152
removeShuffle(int index)153 void SkTDStorage::removeShuffle(int index) {
154 SkASSERT(fSize > 0);
155 SkASSERT(0 <= index && index < fSize);
156 // Check that the new count is valid.
157 const int newCount = this->calculateSizeOrDie(-1);
158 this->moveTail(index, fSize - 1, fSize);
159 this->resize(newCount);
160 }
161
prepend()162 void* SkTDStorage::prepend() {
163 return this->insert(/*index=*/0);
164 }
165
append()166 void SkTDStorage::append() {
167 if (fSize < fCapacity) {
168 fSize++;
169 } else {
170 this->insert(fSize);
171 }
172 }
173
append(int count)174 void SkTDStorage::append(int count) {
175 SkASSERT(count >= 0);
176 // Read as: if (fSize + count <= fCapacity) {...}. This is a UB safe way to avoid the add.
177 if (fCapacity - fSize >= count) {
178 fSize += count;
179 } else {
180 this->insert(fSize, count, nullptr);
181 }
182 }
183
append(const void * src,int count)184 void* SkTDStorage::append(const void* src, int count) {
185 return this->insert(fSize, count, src);
186 }
187
insert(int index)188 void* SkTDStorage::insert(int index) {
189 return this->insert(index, /*count=*/1, nullptr);
190 }
191
insert(int index,int count,const void * src)192 void* SkTDStorage::insert(int index, int count, const void* src) {
193 SkASSERT(0 <= index && index <= fSize);
194 SkASSERT(count >= 0);
195
196 if (count > 0) {
197 const int oldCount = fSize;
198 const int newCount = this->calculateSizeOrDie(count);
199 this->resize(newCount);
200 this->moveTail(index + count, index, oldCount);
201
202 if (src != nullptr) {
203 this->copySrc(index, src, count);
204 }
205 }
206
207 return this->address(index);
208 }
209
operator ==(const SkTDStorage & a,const SkTDStorage & b)210 bool operator==(const SkTDStorage& a, const SkTDStorage& b) {
211 return a.size() == b.size() && (a.empty() || !memcmp(a.data(), b.data(), a.bytes(a.size())));
212 }
213
calculateSizeOrDie(int delta)214 int SkTDStorage::calculateSizeOrDie(int delta) {
215 // Check that count will not go negative.
216 SkASSERT_RELEASE(-fSize <= delta);
217
218 // We take care to avoid overflow here.
219 // Because count and delta are both signed 32-bit ints, the sum of count and delta is at
220 // most 4294967294, which fits fine in uint32_t. Proof follows in assert.
221 static_assert(UINT32_MAX >= (uint32_t)INT_MAX + (uint32_t)INT_MAX);
222 uint32_t testCount = (uint32_t)fSize + (uint32_t)delta;
223 SkASSERT_RELEASE(SkTFitsIn<int>(testCount));
224 return SkToInt(testCount);
225 }
226
moveTail(int to,int tailStart,int tailEnd)227 void SkTDStorage::moveTail(int to, int tailStart, int tailEnd) {
228 SkASSERT(0 <= to && to <= fSize);
229 SkASSERT(0 <= tailStart && tailStart <= tailEnd && tailEnd <= fSize);
230 if (to != tailStart && tailStart != tailEnd) {
231 this->copySrc(to, this->address(tailStart), tailEnd - tailStart);
232 }
233 }
234
copySrc(int dstIndex,const void * src,int count)235 void SkTDStorage::copySrc(int dstIndex, const void* src, int count) {
236 SkASSERT(count > 0);
237 memmove(this->address(dstIndex), src, this->bytes(count));
238 }
239