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
15template <typename T> class SK_API SkTDArray {
16public:
17    SkTDArray() {
18        fReserve = fCount = 0;
19        fArray = NULL;
20#ifdef SK_DEBUG
21        fData = NULL;
22#endif
23    }
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    }
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    }
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
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     */
85    T* detach() {
86        T* array = fArray;
87        fArray = NULL;
88        fReserve = fCount = 0;
89        SkDEBUGCODE(fData = NULL;)
90        return array;
91    }
92
93    bool isEmpty() const { return fCount == 0; }
94
95    /**
96     *  Return the number of elements in the array
97     */
98    int count() const { return fCount; }
99
100    /**
101     *  return the number of bytes in the array: count * sizeof(T)
102     */
103    size_t bytes() const { return fCount * sizeof(T); }
104
105    T*  begin() const { return fArray; }
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
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
125    void rewind() {
126        // same as setCount(0)
127        fCount = 0;
128    }
129
130    void setCount(size_t count) {
131        if (count > fReserve) {
132            this->growBy(count - fCount);
133        } else {
134            fCount = count;
135        }
136    }
137
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
147    T* prepend() {
148        this->growBy(1);
149        memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
150        return fArray;
151    }
152
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
170    T* appendClear() {
171        T* result = this->append();
172        *result = 0;
173        return result;
174    }
175
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
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
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
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
232    T*          push() { return this->append(); }
233    void        push(const T& elem) { *this->append() = elem; }
234    const T&    top() const { return (*this)[fCount - 1]; }
235    T&          top() { return (*this)[fCount - 1]; }
236    void        pop(T* elem) { if (elem) *elem = (*this)[fCount - 1]; --fCount; }
237    void        pop() { --fCount; }
238
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
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
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
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
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
288private:
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
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