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