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