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