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