1/*
2 * Copyright 2011 Google Inc.
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#ifndef SkTArray_DEFINED
9#define SkTArray_DEFINED
10
11#include <new>
12#include "SkTypes.h"
13#include "SkTemplates.h"
14
15template <typename T, bool MEM_COPY = false> class SkTArray;
16
17namespace SkTArrayExt {
18
19template<typename T>
20inline void copy(SkTArray<T, true>* self, const T* array) {
21    memcpy(self->fMemArray, array, self->fCount * sizeof(T));
22}
23template<typename T>
24inline void copyAndDelete(SkTArray<T, true>* self, char* newMemArray) {
25    memcpy(newMemArray, self->fMemArray, self->fCount * sizeof(T));
26}
27
28template<typename T>
29inline void copy(SkTArray<T, false>* self, const T* array) {
30    for (int i = 0; i < self->fCount; ++i) {
31        new (self->fItemArray + i) T(array[i]);
32    }
33}
34template<typename T>
35inline void copyAndDelete(SkTArray<T, false>* self, char* newMemArray) {
36    for (int i = 0; i < self->fCount; ++i) {
37        new (newMemArray + sizeof(T) * i) T(self->fItemArray[i]);
38        self->fItemArray[i].~T();
39    }
40}
41
42}
43
44/** When MEM_COPY is true T will be bit copied when moved.
45    When MEM_COPY is false, T will be copy constructed / destructed.
46    In all cases T's constructor will be called on allocation,
47    and its destructor will be called from this object's destructor.
48*/
49template <typename T, bool MEM_COPY> class SkTArray {
50public:
51    /**
52     * Creates an empty array with no initial storage
53     */
54    SkTArray() {
55        fCount = 0;
56        fReserveCount = gMIN_ALLOC_COUNT;
57        fAllocCount = 0;
58        fMemArray = NULL;
59        fPreAllocMemArray = NULL;
60    }
61
62    /**
63     * Creates an empty array that will preallocate space for reserveCount
64     * elements.
65     */
66    explicit SkTArray(int reserveCount) {
67        this->init(NULL, 0, NULL, reserveCount);
68    }
69
70    /**
71     * Copies one array to another. The new array will be heap allocated.
72     */
73    explicit SkTArray(const SkTArray& array) {
74        this->init(array.fItemArray, array.fCount, NULL, 0);
75    }
76
77    /**
78     * Creates a SkTArray by copying contents of a standard C array. The new
79     * array will be heap allocated. Be careful not to use this constructor
80     * when you really want the (void*, int) version.
81     */
82    SkTArray(const T* array, int count) {
83        this->init(array, count, NULL, 0);
84    }
85
86    /**
87     * assign copy of array to this
88     */
89    SkTArray& operator =(const SkTArray& array) {
90        for (int i = 0; i < fCount; ++i) {
91            fItemArray[i].~T();
92        }
93        fCount = 0;
94        checkRealloc((int)array.count());
95        fCount = array.count();
96        SkTArrayExt::copy(this, static_cast<const T*>(array.fMemArray));
97        return *this;
98    }
99
100    virtual ~SkTArray() {
101        for (int i = 0; i < fCount; ++i) {
102            fItemArray[i].~T();
103        }
104        if (fMemArray != fPreAllocMemArray) {
105            sk_free(fMemArray);
106        }
107    }
108
109    /**
110     * Resets to count() == 0
111     */
112    void reset() { this->pop_back_n(fCount); }
113
114    /**
115     * Number of elements in the array.
116     */
117    int count() const { return fCount; }
118
119    /**
120     * Is the array empty.
121     */
122    bool empty() const { return !fCount; }
123
124    /**
125     * Adds 1 new default-constructed T value and returns in by reference. Note
126     * the reference only remains valid until the next call that adds or removes
127     * elements.
128     */
129    T& push_back() {
130        checkRealloc(1);
131        new ((char*)fMemArray+sizeof(T)*fCount) T;
132        ++fCount;
133        return fItemArray[fCount-1];
134    }
135
136    /**
137     * Version of above that uses a copy constructor to initialize the new item
138     */
139    T& push_back(const T& t) {
140        checkRealloc(1);
141        new ((char*)fMemArray+sizeof(T)*fCount) T(t);
142        ++fCount;
143        return fItemArray[fCount-1];
144    }
145
146    /**
147     * Allocates n more default T values, and returns the address of the start
148     * of that new range. Note: this address is only valid until the next API
149     * call made on the array that might add or remove elements.
150     */
151    T* push_back_n(int n) {
152        SkASSERT(n >= 0);
153        checkRealloc(n);
154        for (int i = 0; i < n; ++i) {
155            new (fItemArray + fCount + i) T;
156        }
157        fCount += n;
158        return fItemArray + fCount - n;
159    }
160
161    /**
162     * Version of above that uses a copy constructor to initialize all n items
163     * to the same T.
164     */
165    T* push_back_n(int n, const T& t) {
166        SkASSERT(n >= 0);
167        checkRealloc(n);
168        for (int i = 0; i < n; ++i) {
169            new (fItemArray + fCount + i) T(t);
170        }
171        fCount += n;
172        return fItemArray + fCount - n;
173    }
174
175    /**
176     * Version of above that uses a copy constructor to initialize the n items
177     * to separate T values.
178     */
179    T* push_back_n(int n, const T t[]) {
180        SkASSERT(n >= 0);
181        checkRealloc(n);
182        for (int i = 0; i < n; ++i) {
183            new (fItemArray + fCount + i) T(t[i]);
184        }
185        fCount += n;
186        return fItemArray + fCount - n;
187    }
188
189    /**
190     * Removes the last element. Not safe to call when count() == 0.
191     */
192    void pop_back() {
193        SkASSERT(fCount > 0);
194        --fCount;
195        fItemArray[fCount].~T();
196        checkRealloc(0);
197    }
198
199    /**
200     * Removes the last n elements. Not safe to call when count() < n.
201     */
202    void pop_back_n(int n) {
203        SkASSERT(n >= 0);
204        SkASSERT(fCount >= n);
205        fCount -= n;
206        for (int i = 0; i < n; ++i) {
207            fItemArray[i].~T();
208        }
209        checkRealloc(0);
210    }
211
212    /**
213     * Pushes or pops from the back to resize. Pushes will be default
214     * initialized.
215     */
216    void resize_back(int newCount) {
217        SkASSERT(newCount >= 0);
218
219        if (newCount > fCount) {
220            push_back_n(newCount - fCount);
221        } else if (newCount < fCount) {
222            pop_back_n(fCount - newCount);
223        }
224    }
225
226    /**
227     * Get the i^th element.
228     */
229    T& operator[] (int i) {
230        SkASSERT(i < fCount);
231        SkASSERT(i >= 0);
232        return fItemArray[i];
233    }
234
235    const T& operator[] (int i) const {
236        SkASSERT(i < fCount);
237        SkASSERT(i >= 0);
238        return fItemArray[i];
239    }
240
241    /**
242     * equivalent to operator[](0)
243     */
244    T& front() { SkASSERT(fCount > 0); return fItemArray[0];}
245
246    const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];}
247
248    /**
249     * equivalent to operator[](count() - 1)
250     */
251    T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];}
252
253    const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];}
254
255    /**
256     * equivalent to operator[](count()-1-i)
257     */
258    T& fromBack(int i) {
259        SkASSERT(i >= 0);
260        SkASSERT(i < fCount);
261        return fItemArray[fCount - i - 1];
262    }
263
264    const T& fromBack(int i) const {
265        SkASSERT(i >= 0);
266        SkASSERT(i < fCount);
267        return fItemArray[fCount - i - 1];
268    }
269
270protected:
271    /**
272     * Creates an empty array that will use the passed storage block until it
273     * is insufficiently large to hold the entire array.
274     */
275    template <int N>
276    SkTArray(SkAlignedSTStorage<N,T>* storage) {
277        this->init(NULL, 0, storage->get(), N);
278    }
279
280    /**
281     * Copy another array, using preallocated storage if preAllocCount >=
282     * array.count(). Otherwise storage will only be used when array shrinks
283     * to fit.
284     */
285    template <int N>
286    SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) {
287        this->init(array.fItemArray, array.fCount, storage->get(), N);
288    }
289
290    /**
291     * Copy a C array, using preallocated storage if preAllocCount >=
292     * count. Otherwise storage will only be used when array shrinks
293     * to fit.
294     */
295    template <int N>
296    SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) {
297        this->init(array, count, storage->get(), N);
298    }
299
300    void init(const T* array, int count,
301               void* preAllocStorage, int preAllocOrReserveCount) {
302        SkASSERT(count >= 0);
303        SkASSERT(preAllocOrReserveCount >= 0);
304        fCount              = count;
305        fReserveCount       = (preAllocOrReserveCount > 0) ?
306                                    preAllocOrReserveCount :
307                                    gMIN_ALLOC_COUNT;
308        fPreAllocMemArray   = preAllocStorage;
309        if (fReserveCount >= fCount &&
310            NULL != preAllocStorage) {
311            fAllocCount = fReserveCount;
312            fMemArray = preAllocStorage;
313        } else {
314            fAllocCount = SkMax32(fCount, fReserveCount);
315            fMemArray = sk_malloc_throw(fAllocCount * sizeof(T));
316        }
317
318        SkTArrayExt::copy(this, array);
319    }
320
321private:
322
323    static const int gMIN_ALLOC_COUNT = 8;
324
325    inline void checkRealloc(int delta) {
326        SkASSERT(fCount >= 0);
327        SkASSERT(fAllocCount >= 0);
328
329        SkASSERT(-delta <= fCount);
330
331        int newCount = fCount + delta;
332        int newAllocCount = fAllocCount;
333
334        if (newCount > fAllocCount) {
335            newAllocCount = SkMax32(newCount + ((newCount + 1) >> 1),
336                                   fReserveCount);
337        } else if (newCount < fAllocCount / 3) {
338            newAllocCount = SkMax32(fAllocCount / 2, fReserveCount);
339        }
340
341        if (newAllocCount != fAllocCount) {
342
343            fAllocCount = newAllocCount;
344            char* newMemArray;
345
346            if (fAllocCount == fReserveCount && NULL != fPreAllocMemArray) {
347                newMemArray = (char*) fPreAllocMemArray;
348            } else {
349                newMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T));
350            }
351
352            SkTArrayExt::copyAndDelete<T>(this, newMemArray);
353
354            if (fMemArray != fPreAllocMemArray) {
355                sk_free(fMemArray);
356            }
357            fMemArray = newMemArray;
358        }
359    }
360
361    template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, const X*);
362    template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, true>* that, char*);
363
364    template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, const X*);
365    template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, false>* that, char*);
366
367    int fReserveCount;
368    int fCount;
369    int fAllocCount;
370    void*    fPreAllocMemArray;
371    union {
372        T*       fItemArray;
373        void*    fMemArray;
374    };
375};
376
377/**
378 * Subclass of SkTArray that contains a preallocated memory block for the array.
379 */
380template <int N, typename T, bool DATA_TYPE = false>
381class SkSTArray : public SkTArray<T, DATA_TYPE> {
382private:
383    typedef SkTArray<T, DATA_TYPE> INHERITED;
384
385public:
386    SkSTArray() : INHERITED(&fStorage) {
387    }
388
389    SkSTArray(const SkSTArray& array)
390        : INHERITED(array, &fStorage) {
391    }
392
393    explicit SkSTArray(const INHERITED& array)
394        : INHERITED(array, &fStorage) {
395    }
396
397    SkSTArray(const T* array, int count)
398        : INHERITED(array, count, &fStorage) {
399    }
400
401    SkSTArray& operator= (const SkSTArray& array) {
402        return *this = *(const INHERITED*)&array;
403    }
404
405    SkSTArray& operator= (const INHERITED& array) {
406        INHERITED::operator=(array);
407        return *this;
408    }
409
410private:
411    SkAlignedSTStorage<N,T> fStorage;
412};
413
414#endif
415
416