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