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