• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
15 template <typename T> class SK_API SkTDArray {
16 public:
SkTDArray()17     SkTDArray() {
18         fReserve = fCount = 0;
19         fArray = NULL;
20 #ifdef SK_DEBUG
21         fData = NULL;
22 #endif
23     }
SkTDArray(const T src[],size_t count)24     SkTDArray(const T src[], size_t count) {
25         SkASSERT(src || count == 0);
26 
27         fReserve = fCount = 0;
28         fArray = NULL;
29 #ifdef SK_DEBUG
30         fData = NULL;
31 #endif
32         if (count) {
33             fArray = (T*)sk_malloc_throw(count * sizeof(T));
34 #ifdef SK_DEBUG
35             fData = (ArrayT*)fArray;
36 #endif
37             memcpy(fArray, src, sizeof(T) * count);
38             fReserve = fCount = count;
39         }
40     }
SkTDArray(const SkTDArray<T> & src)41     SkTDArray(const SkTDArray<T>& src) {
42         fReserve = fCount = 0;
43         fArray = NULL;
44 #ifdef SK_DEBUG
45         fData = NULL;
46 #endif
47         SkTDArray<T> tmp(src.fArray, src.fCount);
48         this->swap(tmp);
49     }
~SkTDArray()50     ~SkTDArray() {
51         sk_free(fArray);
52     }
53 
54     SkTDArray<T>& operator=(const SkTDArray<T>& src) {
55         if (this != &src) {
56             if (src.fCount > fReserve) {
57                 SkTDArray<T> tmp(src.fArray, src.fCount);
58                 this->swap(tmp);
59             } else {
60                 memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
61                 fCount = src.fCount;
62             }
63         }
64         return *this;
65     }
66 
67     friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
68         return  a.fCount == b.fCount &&
69                 (a.fCount == 0 ||
70                  !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
71     }
72 
swap(SkTDArray<T> & other)73     void swap(SkTDArray<T>& other) {
74         SkTSwap(fArray, other.fArray);
75 #ifdef SK_DEBUG
76         SkTSwap(fData, other.fData);
77 #endif
78         SkTSwap(fReserve, other.fReserve);
79         SkTSwap(fCount, other.fCount);
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      */
detach()85     T* detach() {
86         T* array = fArray;
87         fArray = NULL;
88         fReserve = fCount = 0;
89         SkDEBUGCODE(fData = NULL;)
90         return array;
91     }
92 
isEmpty()93     bool isEmpty() const { return fCount == 0; }
94 
95     /**
96      *  Return the number of elements in the array
97      */
count()98     int count() const { return fCount; }
99 
100     /**
101      *  return the number of bytes in the array: count * sizeof(T)
102      */
bytes()103     size_t bytes() const { return fCount * sizeof(T); }
104 
begin()105     T*  begin() const { return fArray; }
end()106     T*  end() const { return fArray ? fArray + fCount : NULL; }
107     T&  operator[](int index) const {
108         SkASSERT((unsigned)index < fCount);
109         return fArray[index];
110     }
111 
reset()112     void reset() {
113         if (fArray) {
114             sk_free(fArray);
115             fArray = NULL;
116 #ifdef SK_DEBUG
117             fData = NULL;
118 #endif
119             fReserve = fCount = 0;
120         } else {
121             SkASSERT(fReserve == 0 && fCount == 0);
122         }
123     }
124 
rewind()125     void rewind() {
126         // same as setCount(0)
127         fCount = 0;
128     }
129 
setCount(size_t count)130     void setCount(size_t count) {
131         if (count > fReserve) {
132             this->growBy(count - fCount);
133         } else {
134             fCount = count;
135         }
136     }
137 
setReserve(size_t reserve)138     void setReserve(size_t reserve) {
139         if (reserve > fReserve) {
140             SkASSERT(reserve > fCount);
141             size_t count = fCount;
142             this->growBy(reserve - fCount);
143             fCount = count;
144         }
145     }
146 
prepend()147     T* prepend() {
148         this->growBy(1);
149         memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
150         return fArray;
151     }
152 
append()153     T* append() {
154         return this->append(1, NULL);
155     }
156     T* append(size_t count, const T* src = NULL) {
157         unsigned oldCount = fCount;
158         if (count)  {
159             SkASSERT(src == NULL || fArray == NULL ||
160                     src + count <= fArray || fArray + oldCount <= src);
161 
162             this->growBy(count);
163             if (src) {
164                 memcpy(fArray + oldCount, src, sizeof(T) * count);
165             }
166         }
167         return fArray + oldCount;
168     }
169 
appendClear()170     T* appendClear() {
171         T* result = this->append();
172         *result = 0;
173         return result;
174     }
175 
insert(size_t index)176     T* insert(size_t index) {
177         return this->insert(index, 1, NULL);
178     }
179     T* insert(size_t index, size_t count, const T* src = NULL) {
180         SkASSERT(count);
181         SkASSERT(index <= fCount);
182         int oldCount = fCount;
183         this->growBy(count);
184         T* dst = fArray + index;
185         memmove(dst + count, dst, sizeof(T) * (oldCount - index));
186         if (src) {
187             memcpy(dst, src, sizeof(T) * count);
188         }
189         return dst;
190     }
191 
192     void remove(size_t index, size_t count = 1) {
193         SkASSERT(index + count <= fCount);
194         fCount = fCount - count;
195         memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
196     }
197 
removeShuffle(size_t index)198     void removeShuffle(size_t index) {
199         SkASSERT(index < fCount);
200         unsigned newCount = fCount - 1;
201         fCount = newCount;
202         if (index != newCount) {
203             memcpy(fArray + index, fArray + newCount, sizeof(T));
204         }
205     }
206 
find(const T & elem)207     int find(const T& elem) const {
208         const T* iter = fArray;
209         const T* stop = fArray + fCount;
210 
211         for (; iter < stop; iter++) {
212             if (*iter == elem) {
213                 return (int) (iter - fArray);
214             }
215         }
216         return -1;
217     }
218 
rfind(const T & elem)219     int rfind(const T& elem) const {
220         const T* iter = fArray + fCount;
221         const T* stop = fArray;
222 
223         while (iter > stop) {
224             if (*--iter == elem) {
225                 return iter - stop;
226             }
227         }
228         return -1;
229     }
230 
231     // routines to treat the array like a stack
push()232     T*          push() { return this->append(); }
push(const T & elem)233     void        push(const T& elem) { *this->append() = elem; }
top()234     const T&    top() const { return (*this)[fCount - 1]; }
top()235     T&          top() { return (*this)[fCount - 1]; }
pop(T * elem)236     void        pop(T* elem) { if (elem) *elem = (*this)[fCount - 1]; --fCount; }
pop()237     void        pop() { --fCount; }
238 
deleteAll()239     void deleteAll() {
240         T*  iter = fArray;
241         T*  stop = fArray + fCount;
242         while (iter < stop) {
243             delete (*iter);
244             iter += 1;
245         }
246         this->reset();
247     }
248 
freeAll()249     void freeAll() {
250         T*  iter = fArray;
251         T*  stop = fArray + fCount;
252         while (iter < stop) {
253             sk_free(*iter);
254             iter += 1;
255         }
256         this->reset();
257     }
258 
unrefAll()259     void unrefAll() {
260         T*  iter = fArray;
261         T*  stop = fArray + fCount;
262         while (iter < stop) {
263             (*iter)->unref();
264             iter += 1;
265         }
266         this->reset();
267     }
268 
safeUnrefAll()269     void safeUnrefAll() {
270         T*  iter = fArray;
271         T*  stop = fArray + fCount;
272         while (iter < stop) {
273             SkSafeUnref(*iter);
274             iter += 1;
275         }
276         this->reset();
277     }
278 
279 #ifdef SK_DEBUG
validate()280     void validate() const {
281         SkASSERT((fReserve == 0 && fArray == NULL) ||
282                  (fReserve > 0 && fArray != NULL));
283         SkASSERT(fCount <= fReserve);
284         SkASSERT(fData == (ArrayT*)fArray);
285     }
286 #endif
287 
288 private:
289 #ifdef SK_DEBUG
290     enum {
291         kDebugArraySize = 16
292     };
293     typedef T ArrayT[kDebugArraySize];
294     ArrayT* fData;
295 #endif
296     T*      fArray;
297     size_t  fReserve, fCount;
298 
growBy(size_t extra)299     void growBy(size_t extra) {
300         SkASSERT(extra);
301 
302         if (fCount + extra > fReserve) {
303             size_t size = fCount + extra + 4;
304             size += size >> 2;
305 
306             fArray = (T*)sk_realloc_throw(fArray, size * sizeof(T));
307 #ifdef SK_DEBUG
308             fData = (ArrayT*)fArray;
309 #endif
310             fReserve = size;
311         }
312         fCount += extra;
313     }
314 };
315 
316 #endif
317 
318