1/*
2 * Copyright 2006 The Android Open Source Project
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
9#ifndef SkTDArray_DEFINED
10#define SkTDArray_DEFINED
11
12#include "include/core/SkTypes.h"
13#include "include/private/SkMalloc.h"
14#include "include/private/SkTo.h"
15
16#include <algorithm>
17#include <initializer_list>
18#include <utility>
19
20/** SkTDArray<T> implements a std::vector-like array for raw data-only objects that do not require
21 construction or destruction. The constructor and destructor for T will not be called; T objects
22 will always be moved via raw memcpy. Newly created T objects will contain uninitialized memory.
23
24 In most cases, std::vector<T> can provide a similar level of performance for POD objects when
25 used with appropriate care. In new code, consider std::vector<T> instead.
26*/
27template <typename T> class SkTDArray {
28public:
29 SkTDArray() : fArray(nullptr), fReserve(0), fCount(0) {}
30 SkTDArray(const T src[], int count) {
31 SkASSERT(src || count == 0);
32
33 fReserve = fCount = 0;
34 fArray = nullptr;
35 if (count) {
36 fArray = (T*)sk_malloc_throw(count * sizeof(T));
37 memcpy(fArray, src, sizeof(T) * count);
38 fReserve = fCount = count;
39 }
40 }
41 SkTDArray(const std::initializer_list<T>& list) : SkTDArray(list.begin(), list.size()) {}
42 SkTDArray(const SkTDArray<T>& src) : fArray(nullptr), fReserve(0), fCount(0) {
43 SkTDArray<T> tmp(src.fArray, src.fCount);
44 this->swap(tmp);
45 }
46 SkTDArray(SkTDArray<T>&& src) : fArray(nullptr), fReserve(0), fCount(0) {
47 this->swap(src);
48 }
49 ~SkTDArray() {
50 sk_free(fArray);
51 }
52
53 SkTDArray<T>& operator=(const SkTDArray<T>& src) {
54 if (this != &src) {
55 if (src.fCount > fReserve) {
56 SkTDArray<T> tmp(src.fArray, src.fCount);
57 this->swap(tmp);
58 } else {
59 sk_careful_memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
60 fCount = src.fCount;
61 }
62 }
63 return *this;
64 }
65 SkTDArray<T>& operator=(SkTDArray<T>&& src) {
66 if (this != &src) {
67 this->swap(src);
68 src.reset();
69 }
70 return *this;
71 }
72
73 friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
74 return a.fCount == b.fCount &&
75 (a.fCount == 0 ||
76 !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
77 }
78 friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) {
79 return !(a == b);
80 }
81
82 void swap(SkTDArray<T>& that) {
83 using std::swap;
84 swap(fArray, that.fArray);
85 swap(fReserve, that.fReserve);
86 swap(fCount, that.fCount);
87 }
88
89 bool isEmpty() const { return fCount == 0; }
90 bool empty() const { return this->isEmpty(); }
91
92 /**
93 * Return the number of elements in the array
94 */
95 int count() const { return fCount; }
96 size_t size() const { return fCount; }
97
98 /**
99 * Return the total number of elements allocated.
100 * reserved() - count() gives you the number of elements you can add
101 * without causing an allocation.
102 */
103 int reserved() const { return fReserve; }
104
105 /**
106 * return the number of bytes in the array: count * sizeof(T)
107 */
108 size_t bytes() const { return fCount * sizeof(T); }
109
110 T* begin() { return fArray; }
111 const T* begin() const { return fArray; }
112 T* end() { return fArray ? fArray + fCount : nullptr; }
113 const T* end() const { return fArray ? fArray + fCount : nullptr; }
114
115 T& operator[](int index) {
116 SkASSERT(index < fCount);
117 return fArray[index];
118 }
119 const T& operator[](int index) const {
120 SkASSERT(index < fCount);
121 return fArray[index];
122 }
123
124 T& getAt(int index) {
125 return (*this)[index];
126 }
127
128 const T& back() const { SkASSERT(fCount > 0); return fArray[fCount-1]; }
129 T& back() { SkASSERT(fCount > 0); return fArray[fCount-1]; }
130
131 void reset() {
132 if (fArray) {
133 sk_free(fArray);
134 fArray = nullptr;
135 fReserve = fCount = 0;
136 } else {
137 SkASSERT(fReserve == 0 && fCount == 0);
138 }
139 }
140
141 void rewind() {
142 // same as setCount(0)
143 fCount = 0;
144 }
145
146 /**
147 * Sets the number of elements in the array.
148 * If the array does not have space for count elements, it will increase
149 * the storage allocated to some amount greater than that required.
150 * It will never shrink the storage.
151 */
152 void setCount(int count) {
153 SkASSERT(count >= 0);
154 if (count > fReserve) {
155 this->resizeStorageToAtLeast(count);
156 }
157 fCount = count;
158 }
159
160 void setReserve(int reserve) {
161 SkASSERT(reserve >= 0);
162 if (reserve > fReserve) {
163 this->resizeStorageToAtLeast(reserve);
164 }
165 }
166 void reserve(size_t n) {
167 SkASSERT_RELEASE(SkTFitsIn<int>(n));
168 this->setReserve(SkToInt(n));
169 }
170
171 T* prepend() {
172 this->adjustCount(1);
173 memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
174 return fArray;
175 }
176
177 T* append() {
178 return this->append(1, nullptr);
179 }
180 T* append(int count, const T* src = nullptr) {
181 int oldCount = fCount;
182 if (count) {
183 SkASSERT(src == nullptr || fArray == nullptr ||
184 src + count <= fArray || fArray + oldCount <= src);
185
186 this->adjustCount(count);
187 if (src) {
188 memcpy(fArray + oldCount, src, sizeof(T) * count);
189 }
190 }
191 return fArray + oldCount;
192 }
193
194 T* insert(int index) {
195 return this->insert(index, 1, nullptr);
196 }
197 T* insert(int index, int count, const T* src = nullptr) {
198 SkASSERT(count);
199 SkASSERT(index <= fCount);
200 size_t oldCount = fCount;
201 this->adjustCount(count);
202 T* dst = fArray + index;
203 memmove(dst + count, dst, sizeof(T) * (oldCount - index));
204 if (src) {
205 memcpy(dst, src, sizeof(T) * count);
206 }
207 return dst;
208 }
209
210 void remove(int index, int count = 1) {
211 SkASSERT(index + count <= fCount);
212 fCount = fCount - count;
213 memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
214 }
215
216 void removeShuffle(int index) {
217 SkASSERT(index < fCount);
218 int newCount = fCount - 1;
219 fCount = newCount;
220 if (index != newCount) {
221 memcpy(fArray + index, fArray + newCount, sizeof(T));
222 }
223 }
224
225 int find(const T& elem) const {
226 const T* iter = fArray;
227 const T* stop = fArray + fCount;
228
229 for (; iter < stop; iter++) {
230 if (*iter == elem) {
231 return SkToInt(iter - fArray);
232 }
233 }
234 return -1;
235 }
236
237 int rfind(const T& elem) const {
238 const T* iter = fArray + fCount;
239 const T* stop = fArray;
240
241 while (iter > stop) {
242 if (*--iter == elem) {
243 return SkToInt(iter - stop);
244 }
245 }
246 return -1;
247 }
248
249 /**
250 * Returns true iff the array contains this element.
251 */
252 bool contains(const T& elem) const {
253 return (this->find(elem) >= 0);
254 }
255
256 /**
257 * Copies up to max elements into dst. The number of items copied is
258 * capped by count - index. The actual number copied is returned.
259 */
260 int copyRange(T* dst, int index, int max) const {
261 SkASSERT(max >= 0);
262 SkASSERT(!max || dst);
263 if (index >= fCount) {
264 return 0;
265 }
266 int count = std::min(max, fCount - index);
267 memcpy(dst, fArray + index, sizeof(T) * count);
268 return count;
269 }
270
271 void copy(T* dst) const {
272 this->copyRange(dst, 0, fCount);
273 }
274
275 // routines to treat the array like a stack
276 void push_back(const T& v) { *this->append() = v; }
277 T* push() { return this->append(); }
278 const T& top() const { return (*this)[fCount - 1]; }
279 T& top() { return (*this)[fCount - 1]; }
280 void pop(T* elem) { SkASSERT(fCount > 0); if (elem) *elem = (*this)[fCount - 1]; --fCount; }
281 void pop() { SkASSERT(fCount > 0); --fCount; }
282
283 void deleteAll() {
284 T* iter = fArray;
285 T* stop = fArray + fCount;
286 while (iter < stop) {
287 delete *iter;
288 iter += 1;
289 }
290 this->reset();
291 }
292
293 void freeAll() {
294 T* iter = fArray;
295 T* stop = fArray + fCount;
296 while (iter < stop) {
297 sk_free(*iter);
298 iter += 1;
299 }
300 this->reset();
301 }
302
303 void unrefAll() {
304 T* iter = fArray;
305 T* stop = fArray + fCount;
306 while (iter < stop) {
307 (*iter)->unref();
308 iter += 1;
309 }
310 this->reset();
311 }
312
313 void safeUnrefAll() {
314 T* iter = fArray;
315 T* stop = fArray + fCount;
316 while (iter < stop) {
317 SkSafeUnref(*iter);
318 iter += 1;
319 }
320 this->reset();
321 }
322
323#ifdef SK_DEBUG
324 void validate() const {
325 SkASSERT((fReserve == 0 && fArray == nullptr) ||
326 (fReserve > 0 && fArray != nullptr));
327 SkASSERT(fCount <= fReserve);
328 }
329#endif
330
331 void shrinkToFit() {
332 if (fReserve != fCount) {
333 SkASSERT(fReserve > fCount);
334 fReserve = fCount;
335 fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
336 }
337 }
338
339private:
340 T* fArray;
341 int fReserve; // size of the allocation in fArray (#elements)
342 int fCount; // logical number of elements (fCount <= fReserve)
343
344 /**
345 * Adjusts the number of elements in the array.
346 * This is the same as calling setCount(count() + delta).
347 */
348 void adjustCount(int delta) {
349 SkASSERT(delta > 0);
350
351 // We take care to avoid overflow here.
352 // The sum of fCount and delta is at most 4294967294, which fits fine in uint32_t.
353 uint32_t count = (uint32_t)fCount + (uint32_t)delta;
354 SkASSERT_RELEASE( SkTFitsIn<int>(count) );
355
356 this->setCount(SkTo<int>(count));
357 }
358
359 /**
360 * Increase the storage allocation such that it can hold (fCount + extra)
361 * elements.
362 * It never shrinks the allocation, and it may increase the allocation by
363 * more than is strictly required, based on a private growth heuristic.
364 *
365 * note: does NOT modify fCount
366 */
367 void resizeStorageToAtLeast(int count) {
368 SkASSERT(count > fReserve);
369
370 // We take care to avoid overflow here.
371 // The maximum value we can get for reserve here is 2684354563, which fits in uint32_t.
372 uint32_t reserve = (uint32_t)count + 4;
373 reserve += reserve / 4;
374 SkASSERT_RELEASE( SkTFitsIn<int>(reserve) );
375
376 fReserve = SkTo<int>(reserve);
377 fArray = (T*)sk_realloc_throw(fArray, (size_t)fReserve * sizeof(T));
378 }
379};
380
381template <typename T> static inline void swap(SkTDArray<T>& a, SkTDArray<T>& b) {
382 a.swap(b);
383}
384
385#endif
386