blob: 16f8474bd4441ee65ceadad8be398f3ddee7ef0a [file] [log] [blame]
epoger@google.comec3ed6a2011-07-28 14:26:00 +00001
reed@android.com8a1c16f2008-12-17 15:59:43 +00002/*
epoger@google.comec3ed6a2011-07-28 14:26:00 +00003 * Copyright 2006 The Android Open Source Project
reed@android.com8a1c16f2008-12-17 15:59:43 +00004 *
epoger@google.comec3ed6a2011-07-28 14:26:00 +00005 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
reed@android.com8a1c16f2008-12-17 15:59:43 +00007 */
8
epoger@google.comec3ed6a2011-07-28 14:26:00 +00009
reed@android.com8a1c16f2008-12-17 15:59:43 +000010#ifndef SkTDArray_DEFINED
11#define SkTDArray_DEFINED
12
13#include "SkTypes.h"
14
ehsan.akhgaridb5f7bf2014-07-09 11:13:55 -070015template <typename T> class SkTDArray {
reed@android.com8a1c16f2008-12-17 15:59:43 +000016public:
halcanary9be37202016-08-08 07:21:42 -070017 SkTDArray() : fArray(nullptr), fReserve(0), fCount(0) {}
robertphillips@google.come9cd27d2013-10-16 17:48:11 +000018 SkTDArray(const T src[], int count) {
reed@android.com8a1c16f2008-12-17 15:59:43 +000019 SkASSERT(src || count == 0);
20
21 fReserve = fCount = 0;
22 fArray = NULL;
reed@android.com8a1c16f2008-12-17 15:59:43 +000023 if (count) {
24 fArray = (T*)sk_malloc_throw(count * sizeof(T));
reed@android.com8a1c16f2008-12-17 15:59:43 +000025 memcpy(fArray, src, sizeof(T) * count);
26 fReserve = fCount = count;
27 }
28 }
halcanary9be37202016-08-08 07:21:42 -070029 SkTDArray(const SkTDArray<T>& src) : fArray(nullptr), fReserve(0), fCount(0) {
reed@android.com8a1c16f2008-12-17 15:59:43 +000030 SkTDArray<T> tmp(src.fArray, src.fCount);
31 this->swap(tmp);
32 }
halcanary9be37202016-08-08 07:21:42 -070033 SkTDArray(SkTDArray<T>&& src) : fArray(nullptr), fReserve(0), fCount(0) {
34 this->swap(src);
35 }
reed@android.com8a1c16f2008-12-17 15:59:43 +000036 ~SkTDArray() {
37 sk_free(fArray);
38 }
39
40 SkTDArray<T>& operator=(const SkTDArray<T>& src) {
41 if (this != &src) {
42 if (src.fCount > fReserve) {
43 SkTDArray<T> tmp(src.fArray, src.fCount);
44 this->swap(tmp);
45 } else {
mtkleincc881da2015-12-08 11:55:17 -080046 sk_careful_memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
reed@android.com8a1c16f2008-12-17 15:59:43 +000047 fCount = src.fCount;
48 }
49 }
50 return *this;
51 }
halcanary9be37202016-08-08 07:21:42 -070052 SkTDArray<T>& operator=(SkTDArray<T>&& src) {
53 if (this != &src) {
54 this->swap(src);
55 src.reset();
56 }
57 return *this;
58 }
reed@android.com8a1c16f2008-12-17 15:59:43 +000059
reed@google.comb530ef52011-07-20 19:55:42 +000060 friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
reed@android.com8a1c16f2008-12-17 15:59:43 +000061 return a.fCount == b.fCount &&
62 (a.fCount == 0 ||
63 !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
64 }
reed@google.com3467ee02013-05-29 18:05:52 +000065 friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) {
66 return !(a == b);
67 }
reed@android.com8a1c16f2008-12-17 15:59:43 +000068
69 void swap(SkTDArray<T>& other) {
70 SkTSwap(fArray, other.fArray);
reed@android.com8a1c16f2008-12-17 15:59:43 +000071 SkTSwap(fReserve, other.fReserve);
72 SkTSwap(fCount, other.fCount);
73 }
74
Brian Salomon958fbc42017-01-30 17:01:28 -050075 // The deleter that ought to be used for a std:: smart pointer that takes ownership from
76 // release().
77 struct Deleter {
78 void operator()(const void* p) { sk_free((void*)p); }
79 };
80
reed@android.com0da41db2009-08-25 16:03:59 +000081 /** Return a ptr to the array of data, to be freed with sk_free. This also
82 resets the SkTDArray to be empty.
83 */
mtklein18300a32016-03-16 13:53:35 -070084 T* release() {
reed@android.com0da41db2009-08-25 16:03:59 +000085 T* array = fArray;
86 fArray = NULL;
87 fReserve = fCount = 0;
reed@android.com0da41db2009-08-25 16:03:59 +000088 return array;
89 }
90
reed@android.com8a1c16f2008-12-17 15:59:43 +000091 bool isEmpty() const { return fCount == 0; }
reed@google.com1271d782011-11-28 19:54:12 +000092
93 /**
94 * Return the number of elements in the array
95 */
robertphillips@google.come9cd27d2013-10-16 17:48:11 +000096 int count() const { return fCount; }
reed@google.com1271d782011-11-28 19:54:12 +000097
98 /**
commit-bot@chromium.org046f1f62014-02-11 10:17:02 +000099 * 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 /**
reed@google.com1271d782011-11-28 19:54:12 +0000106 * return the number of bytes in the array: count * sizeof(T)
107 */
108 size_t bytes() const { return fCount * sizeof(T); }
109
commit-bot@chromium.orgaa537d42013-02-28 19:03:13 +0000110 T* begin() { return fArray; }
111 const T* begin() const { return fArray; }
112 T* end() { return fArray ? fArray + fCount : NULL; }
113 const T* end() const { return fArray ? fArray + fCount : NULL; }
114
115 T& operator[](int index) {
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000116 SkASSERT(index < fCount);
commit-bot@chromium.orgaa537d42013-02-28 19:03:13 +0000117 return fArray[index];
118 }
119 const T& operator[](int index) const {
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000120 SkASSERT(index < fCount);
reed@android.com8a1c16f2008-12-17 15:59:43 +0000121 return fArray[index];
122 }
skia.committer@gmail.com7fc0e0a2013-01-15 02:01:40 +0000123
commit-bot@chromium.orgaa537d42013-02-28 19:03:13 +0000124 T& getAt(int index) {
125 return (*this)[index];
126 }
127 const T& getAt(int index) const {
humper@google.com7af56be2013-01-14 18:49:19 +0000128 return (*this)[index];
129 }
reed@android.com8a1c16f2008-12-17 15:59:43 +0000130
131 void reset() {
132 if (fArray) {
133 sk_free(fArray);
134 fArray = NULL;
reed@android.com8a1c16f2008-12-17 15:59:43 +0000135 fReserve = fCount = 0;
136 } else {
137 SkASSERT(fReserve == 0 && fCount == 0);
138 }
139 }
rmistry@google.comfbfcd562012-08-23 18:09:54 +0000140
reed@android.com8a1c16f2008-12-17 15:59:43 +0000141 void rewind() {
142 // same as setCount(0)
143 fCount = 0;
144 }
145
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000146 /**
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.
robertphillips91df6c22015-04-24 11:10:51 -0700150 * It will never shrink the storage.
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000151 */
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000152 void setCount(int count) {
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000153 SkASSERT(count >= 0);
reed@android.com8a1c16f2008-12-17 15:59:43 +0000154 if (count > fReserve) {
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000155 this->resizeStorageToAtLeast(count);
reed@android.com8a1c16f2008-12-17 15:59:43 +0000156 }
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000157 fCount = count;
158 }
159
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000160 void setReserve(int reserve) {
reed@android.com8a1c16f2008-12-17 15:59:43 +0000161 if (reserve > fReserve) {
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000162 this->resizeStorageToAtLeast(reserve);
reed@android.com8a1c16f2008-12-17 15:59:43 +0000163 }
164 }
165
166 T* prepend() {
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000167 this->adjustCount(1);
reed@android.com8a1c16f2008-12-17 15:59:43 +0000168 memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
169 return fArray;
170 }
171
172 T* append() {
173 return this->append(1, NULL);
174 }
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000175 T* append(int count, const T* src = NULL) {
176 int oldCount = fCount;
reed@android.com8a1c16f2008-12-17 15:59:43 +0000177 if (count) {
178 SkASSERT(src == NULL || fArray == NULL ||
179 src + count <= fArray || fArray + oldCount <= src);
180
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000181 this->adjustCount(count);
reed@android.com8a1c16f2008-12-17 15:59:43 +0000182 if (src) {
183 memcpy(fArray + oldCount, src, sizeof(T) * count);
184 }
185 }
186 return fArray + oldCount;
187 }
rmistry@google.comfbfcd562012-08-23 18:09:54 +0000188
reed@android.com8a1c16f2008-12-17 15:59:43 +0000189 T* appendClear() {
rmistry@google.comfbfcd562012-08-23 18:09:54 +0000190 T* result = this->append();
reed@android.com8a1c16f2008-12-17 15:59:43 +0000191 *result = 0;
192 return result;
193 }
194
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000195 T* insert(int index) {
reed@android.com8a1c16f2008-12-17 15:59:43 +0000196 return this->insert(index, 1, NULL);
197 }
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000198 T* insert(int index, int count, const T* src = NULL) {
reed@android.com8a1c16f2008-12-17 15:59:43 +0000199 SkASSERT(count);
200 SkASSERT(index <= fCount);
tomhudson@google.comffe39bd2012-05-17 15:38:00 +0000201 size_t oldCount = fCount;
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000202 this->adjustCount(count);
reed@android.com8a1c16f2008-12-17 15:59:43 +0000203 T* dst = fArray + index;
204 memmove(dst + count, dst, sizeof(T) * (oldCount - index));
205 if (src) {
206 memcpy(dst, src, sizeof(T) * count);
207 }
208 return dst;
209 }
210
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000211 void remove(int index, int count = 1) {
reed@android.com8a1c16f2008-12-17 15:59:43 +0000212 SkASSERT(index + count <= fCount);
213 fCount = fCount - count;
214 memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
215 }
216
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000217 void removeShuffle(int index) {
reed@android.com8a1c16f2008-12-17 15:59:43 +0000218 SkASSERT(index < fCount);
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000219 int newCount = fCount - 1;
reed@android.com8a1c16f2008-12-17 15:59:43 +0000220 fCount = newCount;
221 if (index != newCount) {
222 memcpy(fArray + index, fArray + newCount, sizeof(T));
223 }
224 }
225
reed22b2af12016-08-29 07:52:13 -0700226 template <typename S> int select(S&& selector) const {
227 const T* iter = fArray;
228 const T* stop = fArray + fCount;
229
230 for (; iter < stop; iter++) {
231 if (selector(*iter)) {
232 return SkToInt(iter - fArray);
233 }
234 }
235 return -1;
236 }
237
reed@android.com8a1c16f2008-12-17 15:59:43 +0000238 int find(const T& elem) const {
239 const T* iter = fArray;
240 const T* stop = fArray + fCount;
241
242 for (; iter < stop; iter++) {
243 if (*iter == elem) {
fmalitaf89f60f2015-02-13 08:55:24 -0800244 return SkToInt(iter - fArray);
reed@android.com8a1c16f2008-12-17 15:59:43 +0000245 }
246 }
247 return -1;
248 }
249
250 int rfind(const T& elem) const {
251 const T* iter = fArray + fCount;
252 const T* stop = fArray;
253
254 while (iter > stop) {
255 if (*--iter == elem) {
reed@google.com6fcd28b2014-02-04 16:03:51 +0000256 return SkToInt(iter - stop);
reed@android.com8a1c16f2008-12-17 15:59:43 +0000257 }
258 }
259 return -1;
260 }
261
bsalomon@google.comdf9d6562012-06-07 21:43:15 +0000262 /**
epoger@google.comaf07d062012-07-13 14:53:18 +0000263 * Returns true iff the array contains this element.
264 */
265 bool contains(const T& elem) const {
266 return (this->find(elem) >= 0);
267 }
268
269 /**
bsalomon@google.comdf9d6562012-06-07 21:43:15 +0000270 * Copies up to max elements into dst. The number of items copied is
271 * capped by count - index. The actual number copied is returned.
272 */
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000273 int copyRange(T* dst, int index, int max) const {
bsalomon@google.comdf9d6562012-06-07 21:43:15 +0000274 SkASSERT(max >= 0);
275 SkASSERT(!max || dst);
276 if (index >= fCount) {
277 return 0;
278 }
279 int count = SkMin32(max, fCount - index);
280 memcpy(dst, fArray + index, sizeof(T) * count);
281 return count;
282 }
283
284 void copy(T* dst) const {
zachr@google.comc6081ab2013-07-01 17:04:32 +0000285 this->copyRange(dst, 0, fCount);
bsalomon@google.comdf9d6562012-06-07 21:43:15 +0000286 }
287
reed@android.com8a1c16f2008-12-17 15:59:43 +0000288 // routines to treat the array like a stack
mtkleinaa90d002014-09-11 06:36:11 -0700289 T* push() { return this->append(); }
290 void push(const T& elem) { *this->append() = elem; }
291 const T& top() const { return (*this)[fCount - 1]; }
292 T& top() { return (*this)[fCount - 1]; }
293 void pop(T* elem) { SkASSERT(fCount > 0); if (elem) *elem = (*this)[fCount - 1]; --fCount; }
294 void pop() { SkASSERT(fCount > 0); --fCount; }
reed@android.com8a1c16f2008-12-17 15:59:43 +0000295
296 void deleteAll() {
297 T* iter = fArray;
298 T* stop = fArray + fCount;
299 while (iter < stop) {
halcanary385fe4d2015-08-26 13:07:48 -0700300 delete *iter;
reed@android.com8a1c16f2008-12-17 15:59:43 +0000301 iter += 1;
302 }
303 this->reset();
304 }
305
306 void freeAll() {
307 T* iter = fArray;
308 T* stop = fArray + fCount;
309 while (iter < stop) {
310 sk_free(*iter);
311 iter += 1;
312 }
313 this->reset();
314 }
315
316 void unrefAll() {
317 T* iter = fArray;
318 T* stop = fArray + fCount;
319 while (iter < stop) {
320 (*iter)->unref();
321 iter += 1;
322 }
323 this->reset();
324 }
reed@android.com8433b5d2009-07-03 02:52:27 +0000325
326 void safeUnrefAll() {
327 T* iter = fArray;
328 T* stop = fArray + fCount;
329 while (iter < stop) {
330 SkSafeUnref(*iter);
331 iter += 1;
332 }
333 this->reset();
334 }
335
commit-bot@chromium.orgaa537d42013-02-28 19:03:13 +0000336 void visitAll(void visitor(T&)) {
bsalomon@google.com21cbec42013-01-07 17:23:00 +0000337 T* stop = this->end();
338 for (T* curr = this->begin(); curr < stop; curr++) {
339 if (*curr) {
340 visitor(*curr);
341 }
342 }
343 }
344
reed@android.com8a1c16f2008-12-17 15:59:43 +0000345#ifdef SK_DEBUG
346 void validate() const {
347 SkASSERT((fReserve == 0 && fArray == NULL) ||
348 (fReserve > 0 && fArray != NULL));
349 SkASSERT(fCount <= fReserve);
reed@android.com8a1c16f2008-12-17 15:59:43 +0000350 }
351#endif
352
mtklein092dab92014-10-09 18:22:41 -0700353 void shrinkToFit() {
354 fReserve = fCount;
355 fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
356 }
357
reed@android.com8a1c16f2008-12-17 15:59:43 +0000358private:
reed@android.com8a1c16f2008-12-17 15:59:43 +0000359 T* fArray;
robertphillips@google.come9cd27d2013-10-16 17:48:11 +0000360 int fReserve;
361 int fCount;
reed@android.com8a1c16f2008-12-17 15:59:43 +0000362
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000363 /**
364 * Adjusts the number of elements in the array.
365 * This is the same as calling setCount(count() + delta).
366 */
367 void adjustCount(int delta) {
368 this->setCount(fCount + delta);
369 }
reed@android.com8a1c16f2008-12-17 15:59:43 +0000370
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000371 /**
commit-bot@chromium.orga87b21c2014-02-11 18:22:04 +0000372 * Increase the storage allocation such that it can hold (fCount + extra)
373 * elements.
374 * It never shrinks the allocation, and it may increase the allocation by
375 * more than is strictly required, based on a private growth heuristic.
376 *
377 * note: does NOT modify fCount
378 */
379 void resizeStorageToAtLeast(int count) {
380 SkASSERT(count > fReserve);
commit-bot@chromium.orgca21a002014-02-13 18:35:54 +0000381 fReserve = count + 4;
382 fReserve += fReserve / 4;
383 fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
reed@android.com8a1c16f2008-12-17 15:59:43 +0000384 }
385};
386
387#endif