1
2/*
3 * Copyright 2010 Google Inc.
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
11#ifndef GrTDArray_DEFINED
12#define GrTDArray_DEFINED
13
14#include "GrTypes.h"
15#include "GrRefCnt.h"
16
17static int GrInitialArrayAllocationCount() {
18    return 4;
19}
20
21static int GrNextArrayAllocationCount(int count) {
22    return count + ((count + 1) >> 1);
23}
24
25template <typename T> class GrTDArray {
26public:
27    GrTDArray() : fArray(NULL), fAllocated(0), fCount(0) {}
28    GrTDArray(const GrTDArray& src) {
29        fCount = fAllocated = src.fCount;
30        fArray = (T*)GrMalloc(fAllocated * sizeof(T));
31        memcpy(fArray, src.fArray, fCount * sizeof(T));
32    }
33    ~GrTDArray() {
34        if (fArray) {
35            GrFree(fArray);
36        }
37    }
38
39    bool isEmpty() const { return 0 == fCount; }
40    int count() const { return fCount; }
41
42    const T& at(int index) const {
43        GrAssert((unsigned)index < (unsigned)fCount);
44        return fArray[index];
45    }
46    T& at(int index) {
47        GrAssert((unsigned)index < (unsigned)fCount);
48        return fArray[index];
49    }
50
51    const T& operator[](int index) const { return this->at(index); }
52    T& operator[](int index) { return this->at(index); }
53
54    GrTDArray& operator=(const GrTDArray& src) {
55        if (fAllocated < src.fCount) {
56            fAllocated = src.fCount;
57            GrFree(fArray);
58            fArray = (T*)GrMalloc(fAllocated * sizeof(T));
59        }
60        fCount = src.fCount;
61        memcpy(fArray, src.fArray, fCount * sizeof(T));
62        return *this;
63    }
64
65    void reset() {
66        if (fArray) {
67            GrFree(fArray);
68            fArray = NULL;
69        }
70        fAllocated = fCount = 0;
71    }
72
73    T* begin() const { return fArray; }
74    T* end() const { return fArray + fCount; }
75    T* back() const { GrAssert(fCount); return fArray + (fCount - 1); }
76
77    T* prepend() {
78        this->growAt(0);
79        return fArray;
80    }
81
82    T* append() {
83        this->growAt(fCount);
84        return fArray + fCount - 1;
85    }
86
87    /**
88     *  index may be [0..count], so that you can insert at the end (like append)
89     */
90    T* insert(int index) {
91        GrAssert((unsigned)index <= (unsigned)fCount);
92        this->growAt(index);
93        return fArray + index;
94    }
95
96    void remove(int index) {
97        GrAssert((unsigned)index < (unsigned)fCount);
98        fCount -= 1;
99        if (index < fCount) {
100            int remaining = fCount - index;
101            memmove(fArray + index, fArray + index + 1, remaining * sizeof(T));
102        }
103    }
104
105    void removeShuffle(int index) {
106        GrAssert((unsigned)index < (unsigned)fCount);
107        fCount -= 1;
108        if (index < fCount) {
109            memmove(fArray + index, fArray + fCount, sizeof(T));
110        }
111    }
112
113    // Utility iterators
114
115    /**
116     *  Calls GrFree() on each element. Assumes each is NULL or was allocated
117     *  with GrMalloc().
118     */
119    void freeAll() {
120        T* stop = this->end();
121        for (T* curr = this->begin(); curr < stop; curr++) {
122            GrFree(*curr);
123        }
124        this->reset();
125    }
126
127    /**
128     *  Calls delete on each element. Assumes each is NULL or was allocated
129     *  with new.
130     */
131    void deleteAll() {
132        T* stop = this->end();
133        for (T* curr = this->begin(); curr < stop; curr++) {
134            delete *curr;
135        }
136        this->reset();
137    }
138
139    /**
140     *  Calls GrSafeUnref() on each element. Assumes each is NULL or is a
141     *  subclass of GrRefCnt.
142     */
143    void unrefAll() {
144        T* stop = this->end();
145        for (T* curr = this->begin(); curr < stop; curr++) {
146            GrSafeUnref(*curr);
147        }
148        this->reset();
149    }
150
151    void visit(void visitor(T&)) const {
152        T* stop = this->end();
153        for (T* curr = this->begin(); curr < stop; curr++) {
154            if (*curr) {
155                visitor(*curr);
156            }
157        }
158    }
159
160    int find(const T& elem) const {
161        int count = this->count();
162        T* curr = this->begin();
163        for (int i = 0; i < count; i++) {
164            if (elem == curr[i]) {
165                return i;
166            }
167        }
168        return -1;
169    }
170
171    friend bool operator==(const GrTDArray<T>& a, const GrTDArray<T>& b) {
172        return a.count() == b.count() &&
173               (0 == a.count() ||
174                0 == memcmp(a.begin(), b.begin(), a.count() * sizeof(T)));
175    }
176    friend bool operator!=(const GrTDArray<T>& a, const GrTDArray<T>& b) {
177        return !(a == b);
178    }
179
180private:
181    T*  fArray;
182    int fAllocated, fCount;
183
184    // growAt will increment fCount, reallocate fArray (as needed), and slide
185    // the contents of fArray to make a hole for new data at index.
186    void growAt(int index) {
187        GrAssert(fCount <= fAllocated);
188        if (0 == fAllocated) {
189            fAllocated = GrInitialArrayAllocationCount();
190            fArray = (T*)GrMalloc(fAllocated * sizeof(T));
191        } else if (fCount == fAllocated) {
192            fAllocated = GrNextArrayAllocationCount(fAllocated);
193            T* newArray = (T*)GrMalloc(fAllocated * sizeof(T));
194            memcpy(newArray, fArray, index * sizeof(T));
195            memcpy(newArray + index + 1, fArray + index,
196                   (fCount - index) * sizeof(T));
197            GrFree(fArray);
198            fArray = newArray;
199        } else {
200            // check that we're not just appending
201            if (index < fCount) {
202                memmove(fArray + index + 1, fArray + index,
203                        (fCount - index) * sizeof(T));
204            }
205        }
206        GrAssert(fCount < fAllocated);
207        fCount += 1;
208    }
209};
210
211extern void* GrTDArray_growAt(void*, int* allocated, int& count, int index,
212                              size_t);
213
214
215#endif
216
217