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, int dst, int src) {
21    memcpy(&self->fItemArray[dst], &self->fItemArray[src], sizeof(T));
22}
23template<typename T>
24inline void copy(SkTArray<T, true>* self, const T* array) {
25    memcpy(self->fMemArray, array, self->fCount * sizeof(T));
26}
27template<typename T>
28inline void copyAndDelete(SkTArray<T, true>* self, char* newMemArray) {
29    memcpy(newMemArray, self->fMemArray, self->fCount * sizeof(T));
30}
31
32template<typename T>
33inline void copy(SkTArray<T, false>* self, int dst, int src) {
34    SkNEW_PLACEMENT_ARGS(&self->fItemArray[dst], T, (self->fItemArray[src]));
35}
36template<typename T>
37inline void copy(SkTArray<T, false>* self, const T* array) {
38    for (int i = 0; i < self->fCount; ++i) {
39        SkNEW_PLACEMENT_ARGS(self->fItemArray + i, T, (array[i]));
40    }
41}
42template<typename T>
43inline void copyAndDelete(SkTArray<T, false>* self, char* newMemArray) {
44    for (int i = 0; i < self->fCount; ++i) {
45        SkNEW_PLACEMENT_ARGS(newMemArray + sizeof(T) * i, T, (self->fItemArray[i]));
46        self->fItemArray[i].~T();
47    }
48}
49
50}
51
52template <typename T, bool MEM_COPY> void* operator new(size_t, SkTArray<T, MEM_COPY>*, int);
53
54/** When MEM_COPY is true T will be bit copied when moved.
55    When MEM_COPY is false, T will be copy constructed / destructed.
56    In all cases T will be default-initialized on allocation,
57    and its destructor will be called from this object's destructor.
58*/
59template <typename T, bool MEM_COPY> class SkTArray {
60public:
61    /**
62     * Creates an empty array with no initial storage
63     */
64    SkTArray() {
65        fCount = 0;
66        fReserveCount = gMIN_ALLOC_COUNT;
67        fAllocCount = 0;
68        fMemArray = NULL;
69        fPreAllocMemArray = NULL;
70    }
71
72    /**
73     * Creates an empty array that will preallocate space for reserveCount
74     * elements.
75     */
76    explicit SkTArray(int reserveCount) {
77        this->init(NULL, 0, NULL, reserveCount);
78    }
79
80    /**
81     * Copies one array to another. The new array will be heap allocated.
82     */
83    explicit SkTArray(const SkTArray& array) {
84        this->init(array.fItemArray, array.fCount, NULL, 0);
85    }
86
87    /**
88     * Creates a SkTArray by copying contents of a standard C array. The new
89     * array will be heap allocated. Be careful not to use this constructor
90     * when you really want the (void*, int) version.
91     */
92    SkTArray(const T* array, int count) {
93        this->init(array, count, NULL, 0);
94    }
95
96    /**
97     * assign copy of array to this
98     */
99    SkTArray& operator =(const SkTArray& array) {
100        for (int i = 0; i < fCount; ++i) {
101            fItemArray[i].~T();
102        }
103        fCount = 0;
104        this->checkRealloc((int)array.count());
105        fCount = array.count();
106        SkTArrayExt::copy(this, static_cast<const T*>(array.fMemArray));
107        return *this;
108    }
109
110    virtual ~SkTArray() {
111        for (int i = 0; i < fCount; ++i) {
112            fItemArray[i].~T();
113        }
114        if (fMemArray != fPreAllocMemArray) {
115            sk_free(fMemArray);
116        }
117    }
118
119    /**
120     * Resets to count() == 0
121     */
122    void reset() { this->pop_back_n(fCount); }
123
124    /**
125     * Resets to count() = n newly constructed T objects.
126     */
127    void reset(int n) {
128        SkASSERT(n >= 0);
129        for (int i = 0; i < fCount; ++i) {
130            fItemArray[i].~T();
131        }
132        // set fCount to 0 before calling checkRealloc so that no copy cons. are called.
133        fCount = 0;
134        this->checkRealloc(n);
135        fCount = n;
136        for (int i = 0; i < fCount; ++i) {
137            SkNEW_PLACEMENT(fItemArray + i, T);
138        }
139    }
140
141    /**
142     * Resets to a copy of a C array.
143     */
144    void reset(const T* array, int count) {
145        for (int i = 0; i < fCount; ++i) {
146            fItemArray[i].~T();
147        }
148        int delta = count - fCount;
149        this->checkRealloc(delta);
150        fCount = count;
151        SkTArrayExt::copy(this, array);
152    }
153
154    void removeShuffle(int n) {
155        SkASSERT(n < fCount);
156        int newCount = fCount - 1;
157        fCount = newCount;
158        fItemArray[n].~T();
159        if (n != newCount) {
160            SkTArrayExt::copy(this, n, newCount);
161            fItemArray[newCount].~T();
162        }
163    }
164
165    /**
166     * Number of elements in the array.
167     */
168    int count() const { return fCount; }
169
170    /**
171     * Is the array empty.
172     */
173    bool empty() const { return !fCount; }
174
175    /**
176     * Adds 1 new default-initialized T value and returns it by reference. Note
177     * the reference only remains valid until the next call that adds or removes
178     * elements.
179     */
180    T& push_back() {
181        T* newT = reinterpret_cast<T*>(this->push_back_raw(1));
182        SkNEW_PLACEMENT(newT, T);
183        return *newT;
184    }
185
186    /**
187     * Version of above that uses a copy constructor to initialize the new item
188     */
189    T& push_back(const T& t) {
190        T* newT = reinterpret_cast<T*>(this->push_back_raw(1));
191        SkNEW_PLACEMENT_ARGS(newT, T, (t));
192        return *newT;
193    }
194
195    /**
196     * Allocates n more default-initialized T values, and returns the address of
197     * the start of that new range. Note: this address is only valid until the
198     * next API call made on the array that might add or remove elements.
199     */
200    T* push_back_n(int n) {
201        SkASSERT(n >= 0);
202        T* newTs = reinterpret_cast<T*>(this->push_back_raw(n));
203        for (int i = 0; i < n; ++i) {
204            SkNEW_PLACEMENT(newTs + i, T);
205        }
206        return newTs;
207    }
208
209    /**
210     * Version of above that uses a copy constructor to initialize all n items
211     * to the same T.
212     */
213    T* push_back_n(int n, const T& t) {
214        SkASSERT(n >= 0);
215        T* newTs = reinterpret_cast<T*>(this->push_back_raw(n));
216        for (int i = 0; i < n; ++i) {
217            SkNEW_PLACEMENT_ARGS(newTs[i], T, (t));
218        }
219        return newTs;
220    }
221
222    /**
223     * Version of above that uses a copy constructor to initialize the n items
224     * to separate T values.
225     */
226    T* push_back_n(int n, const T t[]) {
227        SkASSERT(n >= 0);
228        this->checkRealloc(n);
229        for (int i = 0; i < n; ++i) {
230            SkNEW_PLACEMENT_ARGS(fItemArray + fCount + i, T, (t[i]));
231        }
232        fCount += n;
233        return fItemArray + fCount - n;
234    }
235
236    /**
237     * Removes the last element. Not safe to call when count() == 0.
238     */
239    void pop_back() {
240        SkASSERT(fCount > 0);
241        --fCount;
242        fItemArray[fCount].~T();
243        this->checkRealloc(0);
244    }
245
246    /**
247     * Removes the last n elements. Not safe to call when count() < n.
248     */
249    void pop_back_n(int n) {
250        SkASSERT(n >= 0);
251        SkASSERT(fCount >= n);
252        fCount -= n;
253        for (int i = 0; i < n; ++i) {
254            fItemArray[fCount + i].~T();
255        }
256        this->checkRealloc(0);
257    }
258
259    /**
260     * Pushes or pops from the back to resize. Pushes will be default
261     * initialized.
262     */
263    void resize_back(int newCount) {
264        SkASSERT(newCount >= 0);
265
266        if (newCount > fCount) {
267            this->push_back_n(newCount - fCount);
268        } else if (newCount < fCount) {
269            this->pop_back_n(fCount - newCount);
270        }
271    }
272
273    /** Swaps the contents of this array with that array. Does a pointer swap if possible,
274        otherwise copies the T values. */
275    void swap(SkTArray* that) {
276        if (this == that) {
277            return;
278        }
279        if (this->fPreAllocMemArray != this->fItemArray &&
280            that->fPreAllocMemArray != that->fItemArray) {
281            // If neither is using a preallocated array then just swap.
282            SkTSwap(fItemArray, that->fItemArray);
283            SkTSwap(fCount, that->fCount);
284            SkTSwap(fAllocCount, that->fAllocCount);
285        } else {
286            // This could be more optimal...
287            SkTArray copy(*that);
288            *that = *this;
289            *this = copy;
290        }
291    }
292
293    T* begin() {
294        return fItemArray;
295    }
296    const T* begin() const {
297        return fItemArray;
298    }
299    T* end() {
300        return fItemArray ? fItemArray + fCount : NULL;
301    }
302    const T* end() const {
303        return fItemArray ? fItemArray + fCount : NULL;
304    }
305
306   /**
307     * Get the i^th element.
308     */
309    T& operator[] (int i) {
310        SkASSERT(i < fCount);
311        SkASSERT(i >= 0);
312        return fItemArray[i];
313    }
314
315    const T& operator[] (int i) const {
316        SkASSERT(i < fCount);
317        SkASSERT(i >= 0);
318        return fItemArray[i];
319    }
320
321    /**
322     * equivalent to operator[](0)
323     */
324    T& front() { SkASSERT(fCount > 0); return fItemArray[0];}
325
326    const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];}
327
328    /**
329     * equivalent to operator[](count() - 1)
330     */
331    T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];}
332
333    const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];}
334
335    /**
336     * equivalent to operator[](count()-1-i)
337     */
338    T& fromBack(int i) {
339        SkASSERT(i >= 0);
340        SkASSERT(i < fCount);
341        return fItemArray[fCount - i - 1];
342    }
343
344    const T& fromBack(int i) const {
345        SkASSERT(i >= 0);
346        SkASSERT(i < fCount);
347        return fItemArray[fCount - i - 1];
348    }
349
350    bool operator==(const SkTArray<T, MEM_COPY>& right) const {
351        int leftCount = this->count();
352        if (leftCount != right.count()) {
353            return false;
354        }
355        for (int index = 0; index < leftCount; ++index) {
356            if (fItemArray[index] != right.fItemArray[index]) {
357                return false;
358            }
359        }
360        return true;
361    }
362
363    bool operator!=(const SkTArray<T, MEM_COPY>& right) const {
364        return !(*this == right);
365    }
366
367protected:
368    /**
369     * Creates an empty array that will use the passed storage block until it
370     * is insufficiently large to hold the entire array.
371     */
372    template <int N>
373    SkTArray(SkAlignedSTStorage<N,T>* storage) {
374        this->init(NULL, 0, storage->get(), N);
375    }
376
377    /**
378     * Copy another array, using preallocated storage if preAllocCount >=
379     * array.count(). Otherwise storage will only be used when array shrinks
380     * to fit.
381     */
382    template <int N>
383    SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) {
384        this->init(array.fItemArray, array.fCount, storage->get(), N);
385    }
386
387    /**
388     * Copy a C array, using preallocated storage if preAllocCount >=
389     * count. Otherwise storage will only be used when array shrinks
390     * to fit.
391     */
392    template <int N>
393    SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) {
394        this->init(array, count, storage->get(), N);
395    }
396
397    void init(const T* array, int count,
398              void* preAllocStorage, int preAllocOrReserveCount) {
399        SkASSERT(count >= 0);
400        SkASSERT(preAllocOrReserveCount >= 0);
401        fCount              = count;
402        fReserveCount       = (preAllocOrReserveCount > 0) ?
403                                    preAllocOrReserveCount :
404                                    gMIN_ALLOC_COUNT;
405        fPreAllocMemArray   = preAllocStorage;
406        if (fReserveCount >= fCount &&
407            preAllocStorage) {
408            fAllocCount = fReserveCount;
409            fMemArray = preAllocStorage;
410        } else {
411            fAllocCount = SkMax32(fCount, fReserveCount);
412            fMemArray = sk_malloc_throw(fAllocCount * sizeof(T));
413        }
414
415        SkTArrayExt::copy(this, array);
416    }
417
418private:
419
420    static const int gMIN_ALLOC_COUNT = 8;
421
422    // Helper function that makes space for n objects, adjusts the count, but does not initialize
423    // the new objects.
424    void* push_back_raw(int n) {
425        this->checkRealloc(n);
426        void* ptr = fItemArray + fCount;
427        fCount += n;
428        return ptr;
429    }
430
431    inline void checkRealloc(int delta) {
432        SkASSERT(fCount >= 0);
433        SkASSERT(fAllocCount >= 0);
434
435        SkASSERT(-delta <= fCount);
436
437        int newCount = fCount + delta;
438        int newAllocCount = fAllocCount;
439
440        if (newCount > fAllocCount || newCount < (fAllocCount / 3)) {
441            // whether we're growing or shrinking, we leave at least 50% extra space for future
442            // growth (clamped to the reserve count).
443            newAllocCount = SkMax32(newCount + ((newCount + 1) >> 1), fReserveCount);
444        }
445        if (newAllocCount != fAllocCount) {
446
447            fAllocCount = newAllocCount;
448            char* newMemArray;
449
450            if (fAllocCount == fReserveCount && fPreAllocMemArray) {
451                newMemArray = (char*) fPreAllocMemArray;
452            } else {
453                newMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T));
454            }
455
456            SkTArrayExt::copyAndDelete<T>(this, newMemArray);
457
458            if (fMemArray != fPreAllocMemArray) {
459                sk_free(fMemArray);
460            }
461            fMemArray = newMemArray;
462        }
463    }
464
465    friend void* operator new<T>(size_t, SkTArray*, int);
466
467    template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, int dst, int src);
468    template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, const X*);
469    template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, true>* that, char*);
470
471    template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, int dst, int src);
472    template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, const X*);
473    template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, false>* that, char*);
474
475    int     fReserveCount;
476    int     fCount;
477    int     fAllocCount;
478    void*   fPreAllocMemArray;
479    union {
480        T*       fItemArray;
481        void*    fMemArray;
482    };
483};
484
485// Use the below macro (SkNEW_APPEND_TO_TARRAY) rather than calling this directly
486template <typename T, bool MEM_COPY>
487void* operator new(size_t, SkTArray<T, MEM_COPY>* array, int SkDEBUGCODE(atIndex)) {
488    // Currently, we only support adding to the end of the array. When the array class itself
489    // supports random insertion then this should be updated.
490    // SkASSERT(atIndex >= 0 && atIndex <= array->count());
491    SkASSERT(atIndex == array->count());
492    return array->push_back_raw(1);
493}
494
495// Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete
496// to match the op new silences warnings about missing op delete when a constructor throws an
497// exception.
498template <typename T, bool MEM_COPY>
499void operator delete(void*, SkTArray<T, MEM_COPY>* /*array*/, int /*atIndex*/) {
500    SK_CRASH();
501}
502
503// Constructs a new object as the last element of an SkTArray.
504#define SkNEW_APPEND_TO_TARRAY(array_ptr, type_name, args)  \
505    (new ((array_ptr), (array_ptr)->count()) type_name args)
506
507
508/**
509 * Subclass of SkTArray that contains a preallocated memory block for the array.
510 */
511template <int N, typename T, bool MEM_COPY = false>
512class SkSTArray : public SkTArray<T, MEM_COPY> {
513private:
514    typedef SkTArray<T, MEM_COPY> INHERITED;
515
516public:
517    SkSTArray() : INHERITED(&fStorage) {
518    }
519
520    SkSTArray(const SkSTArray& array)
521        : INHERITED(array, &fStorage) {
522    }
523
524    explicit SkSTArray(const INHERITED& array)
525        : INHERITED(array, &fStorage) {
526    }
527
528    explicit SkSTArray(int reserveCount)
529        : INHERITED(reserveCount) {
530    }
531
532    SkSTArray(const T* array, int count)
533        : INHERITED(array, count, &fStorage) {
534    }
535
536    SkSTArray& operator= (const SkSTArray& array) {
537        return *this = *(const INHERITED*)&array;
538    }
539
540    SkSTArray& operator= (const INHERITED& array) {
541        INHERITED::operator=(array);
542        return *this;
543    }
544
545private:
546    SkAlignedSTStorage<N,T> fStorage;
547};
548
549#endif
550