1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/*
249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Copyright 2011 Google Inc.
3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com *
4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be
5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file.
6ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com */
7ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#ifndef SkTArray_DEFINED
949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#define SkTArray_DEFINED
10ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
11ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com#include <new>
1249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#include "SkTypes.h"
1349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#include "SkTemplates.h"
14ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
15a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate <typename T, bool MEM_COPY = false> class SkTArray;
16a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com
17a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comnamespace SkTArrayExt {
18a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com
19a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate<typename T>
2095ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.cominline void copy(SkTArray<T, true>* self, int dst, int src) {
2195ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com    memcpy(&self->fItemArray[dst], &self->fItemArray[src], sizeof(T));
2295ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com}
2395ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.comtemplate<typename T>
24a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.cominline void copy(SkTArray<T, true>* self, const T* array) {
25a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com    memcpy(self->fMemArray, array, self->fCount * sizeof(T));
26a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com}
27a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate<typename T>
28a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.cominline void copyAndDelete(SkTArray<T, true>* self, char* newMemArray) {
29a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com    memcpy(newMemArray, self->fMemArray, self->fCount * sizeof(T));
30a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com}
31a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com
32a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate<typename T>
3395ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.cominline void copy(SkTArray<T, false>* self, int dst, int src) {
3495ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com    SkNEW_PLACEMENT_ARGS(&self->fItemArray[dst], T, (self->fItemArray[src]));
3595ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com}
3695ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.comtemplate<typename T>
37a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.cominline void copy(SkTArray<T, false>* self, const T* array) {
38a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com    for (int i = 0; i < self->fCount; ++i) {
39b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        SkNEW_PLACEMENT_ARGS(self->fItemArray + i, T, (array[i]));
40a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com    }
41a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com}
42a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate<typename T>
43a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.cominline void copyAndDelete(SkTArray<T, false>* self, char* newMemArray) {
44a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com    for (int i = 0; i < self->fCount; ++i) {
45b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        SkNEW_PLACEMENT_ARGS(newMemArray + sizeof(T) * i, T, (self->fItemArray[i]));
46a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com        self->fItemArray[i].~T();
47a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com    }
48a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com}
49a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com
50a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com}
51a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com
52d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.comtemplate <typename T, bool MEM_COPY> void* operator new(size_t, SkTArray<T, MEM_COPY>*, int);
53d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com
54a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com/** When MEM_COPY is true T will be bit copied when moved.
55a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com    When MEM_COPY is false, T will be copy constructed / destructed.
56d58a856418ba3b3ecdc5e94629c911ec0034dfb1bungeman@google.com    In all cases T will be default-initialized on allocation,
57a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com    and its destructor will be called from this object's destructor.
58a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com*/
59a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate <typename T, bool MEM_COPY> class SkTArray {
60ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.compublic:
6149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
6249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * Creates an empty array with no initial storage
6349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
6449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    SkTArray() {
65ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        fCount = 0;
6649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        fReserveCount = gMIN_ALLOC_COUNT;
67ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        fAllocCount = 0;
68ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        fMemArray = NULL;
69ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        fPreAllocMemArray = NULL;
70ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
71ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
7249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
73fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com     * Creates an empty array that will preallocate space for reserveCount
7449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * elements.
7549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
7649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    explicit SkTArray(int reserveCount) {
7792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        this->init(NULL, 0, NULL, reserveCount);
78ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
79fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com
8049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
8149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * Copies one array to another. The new array will be heap allocated.
8249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
8349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    explicit SkTArray(const SkTArray& array) {
8492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        this->init(array.fItemArray, array.fCount, NULL, 0);
85ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
86ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
8749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
88fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com     * Creates a SkTArray by copying contents of a standard C array. The new
8949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * array will be heap allocated. Be careful not to use this constructor
9049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * when you really want the (void*, int) version.
9149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
9249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    SkTArray(const T* array, int count) {
9392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        this->init(array, count, NULL, 0);
94ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
95ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
9649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
9749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * assign copy of array to this
9849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
9949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    SkTArray& operator =(const SkTArray& array) {
1001c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com        for (int i = 0; i < fCount; ++i) {
101ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com            fItemArray[i].~T();
102ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        }
103ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        fCount = 0;
104d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        this->checkRealloc((int)array.count());
105ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        fCount = array.count();
106a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com        SkTArrayExt::copy(this, static_cast<const T*>(array.fMemArray));
107ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        return *this;
108ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
109ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
11092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    virtual ~SkTArray() {
1111c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com        for (int i = 0; i < fCount; ++i) {
112ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com            fItemArray[i].~T();
113ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        }
114ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        if (fMemArray != fPreAllocMemArray) {
11549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com            sk_free(fMemArray);
116ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        }
117ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
118ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
11949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
12049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * Resets to count() == 0
12149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
122d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com    void reset() { this->pop_back_n(fCount); }
123d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com
12449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
125b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org     * Resets to count() = n newly constructed T objects.
126b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org     */
127b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org    void reset(int n) {
128b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        SkASSERT(n >= 0);
129b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        for (int i = 0; i < fCount; ++i) {
130b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org            fItemArray[i].~T();
131b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        }
132b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        // set fCount to 0 before calling checkRealloc so that no copy cons. are called.
133b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        fCount = 0;
134b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        this->checkRealloc(n);
135b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        fCount = n;
136b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        for (int i = 0; i < fCount; ++i) {
137b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org            SkNEW_PLACEMENT(fItemArray + i, T);
138b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        }
139b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org    }
140b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org
141b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org    /**
142054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com     * Resets to a copy of a C array.
143054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com     */
144054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com    void reset(const T* array, int count) {
145054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com        for (int i = 0; i < fCount; ++i) {
146054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com            fItemArray[i].~T();
147054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com        }
148054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com        int delta = count - fCount;
149054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com        this->checkRealloc(delta);
150054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com        fCount = count;
15195ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com        SkTArrayExt::copy(this, array);
15295ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com    }
15395ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com
15495ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com    void removeShuffle(int n) {
15595ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com        SkASSERT(n < fCount);
15695ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com        int newCount = fCount - 1;
15795ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com        fCount = newCount;
15895ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com        fItemArray[n].~T();
15995ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com        if (n != newCount) {
16095ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com            SkTArrayExt::copy(this, n, newCount);
16195ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com            fItemArray[newCount].~T();
162054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com        }
163054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com    }
164054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com
165054ae99d93711c26e40682a0e3a03a47ea605c53jvanverth@google.com    /**
16649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * Number of elements in the array.
16749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
1681c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com    int count() const { return fCount; }
169ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
17049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
17149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * Is the array empty.
17249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
173ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    bool empty() const { return !fCount; }
174ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
175a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com    /**
176d58a856418ba3b3ecdc5e94629c911ec0034dfb1bungeman@google.com     * Adds 1 new default-initialized T value and returns it by reference. Note
177a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com     * the reference only remains valid until the next call that adds or removes
178a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com     * elements.
179a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com     */
180ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    T& push_back() {
181d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        T* newT = reinterpret_cast<T*>(this->push_back_raw(1));
182d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        SkNEW_PLACEMENT(newT, T);
183d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        return *newT;
184ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
185ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
186a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com    /**
1874fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com     * Version of above that uses a copy constructor to initialize the new item
1884fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com     */
1894fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com    T& push_back(const T& t) {
190d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        T* newT = reinterpret_cast<T*>(this->push_back_raw(1));
191d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        SkNEW_PLACEMENT_ARGS(newT, T, (t));
192d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        return *newT;
1934fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com    }
1944fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com
1954fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com    /**
196d58a856418ba3b3ecdc5e94629c911ec0034dfb1bungeman@google.com     * Allocates n more default-initialized T values, and returns the address of
197d58a856418ba3b3ecdc5e94629c911ec0034dfb1bungeman@google.com     * the start of that new range. Note: this address is only valid until the
198d58a856418ba3b3ecdc5e94629c911ec0034dfb1bungeman@google.com     * next API call made on the array that might add or remove elements.
199a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com     */
200a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com    T* push_back_n(int n) {
20149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(n >= 0);
202d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        T* newTs = reinterpret_cast<T*>(this->push_back_raw(n));
2031c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com        for (int i = 0; i < n; ++i) {
204d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com            SkNEW_PLACEMENT(newTs + i, T);
205ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        }
206d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        return newTs;
207ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
208ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
20949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
2104fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com     * Version of above that uses a copy constructor to initialize all n items
2114fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com     * to the same T.
2124fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com     */
2134fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com    T* push_back_n(int n, const T& t) {
2144fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com        SkASSERT(n >= 0);
215d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        T* newTs = reinterpret_cast<T*>(this->push_back_raw(n));
2164fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com        for (int i = 0; i < n; ++i) {
217d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com            SkNEW_PLACEMENT_ARGS(newTs[i], T, (t));
2184fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com        }
219d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        return newTs;
2204fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com    }
2214fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com
2224fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com    /**
2234fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com     * Version of above that uses a copy constructor to initialize the n items
2244fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com     * to separate T values.
2254fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com     */
2264fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com    T* push_back_n(int n, const T t[]) {
2274fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com        SkASSERT(n >= 0);
228b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        this->checkRealloc(n);
2294fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com        for (int i = 0; i < n; ++i) {
230b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org            SkNEW_PLACEMENT_ARGS(fItemArray + fCount + i, T, (t[i]));
2314fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com        }
2324fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com        fCount += n;
2334fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com        return fItemArray + fCount - n;
2344fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com    }
2354fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com
2364fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com    /**
23749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * Removes the last element. Not safe to call when count() == 0.
23849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
239ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    void pop_back() {
24049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(fCount > 0);
241ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        --fCount;
242ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        fItemArray[fCount].~T();
243b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        this->checkRealloc(0);
244ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
245ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
24649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
24749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * Removes the last n elements. Not safe to call when count() < n.
24849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
2491c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com    void pop_back_n(int n) {
25049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(n >= 0);
25149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(fCount >= n);
252ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        fCount -= n;
2531c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com        for (int i = 0; i < n; ++i) {
254d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com            fItemArray[fCount + i].~T();
255ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        }
256b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org        this->checkRealloc(0);
257ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
258ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
25949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
26049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * Pushes or pops from the back to resize. Pushes will be default
26149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * initialized.
26249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
2631c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com    void resize_back(int newCount) {
26449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(newCount >= 0);
2651c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com
266ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        if (newCount > fCount) {
267b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org            this->push_back_n(newCount - fCount);
268ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        } else if (newCount < fCount) {
269b4a8d97b4c68896da363e7f365354ab8ddbb7fc1commit-bot@chromium.org            this->pop_back_n(fCount - newCount);
270ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        }
271ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
272ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
2739b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com    T* begin() {
2749b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com        return fItemArray;
2759b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com    }
2769b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com    const T* begin() const {
2779b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com        return fItemArray;
2789b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com    }
2799b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com    T* end() {
2809b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com        return fItemArray ? fItemArray + fCount : NULL;
2819b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com    }
2829b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com    const T* end() const {
2839b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com        return fItemArray ? fItemArray + fCount : NULL;;
2849b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com    }
2859b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com
2869b855c7c95ce9fff7a447e4a6bdf8a469c1f3097jvanverth@google.com   /**
28749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * Get the i^th element.
28849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
2891c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com    T& operator[] (int i) {
29049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(i < fCount);
29149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(i >= 0);
292ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        return fItemArray[i];
293ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
294ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
2951c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com    const T& operator[] (int i) const {
29649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(i < fCount);
29749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(i >= 0);
298ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        return fItemArray[i];
299ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
300ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
30149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
30249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * equivalent to operator[](0)
30349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
30449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    T& front() { SkASSERT(fCount > 0); return fItemArray[0];}
305ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
30649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];}
307ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
30849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
30949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * equivalent to operator[](count() - 1)
31049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
31149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];}
312ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
31349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];}
314ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
31549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    /**
31649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     * equivalent to operator[](count()-1-i)
31749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com     */
3181c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com    T& fromBack(int i) {
31949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(i >= 0);
32049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(i < fCount);
321ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        return fItemArray[fCount - i - 1];
322ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
323ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
3241c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com    const T& fromBack(int i) const {
32549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(i >= 0);
32649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(i < fCount);
327ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        return fItemArray[fCount - i - 1];
328ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
329ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
330ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org    bool operator==(const SkTArray<T, MEM_COPY>& right) const {
331ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org        int leftCount = this->count();
332ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org        if (leftCount != right.count()) {
333ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org            return false;
334ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org        }
335ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org        for (int index = 0; index < leftCount; ++index) {
336ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org            if (fItemArray[index] != right.fItemArray[index]) {
337ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org                return false;
338ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org            }
339ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org        }
340ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org        return true;
341ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org    }
342ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org
343ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org    bool operator!=(const SkTArray<T, MEM_COPY>& right) const {
344ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org        return !(*this == right);
345ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org    }
346ff6ea2663f76aa85ec55ddd0f00ca7906f1bc4e3commit-bot@chromium.org
34792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.comprotected:
34892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    /**
34992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com     * Creates an empty array that will use the passed storage block until it
35092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com     * is insufficiently large to hold the entire array.
35192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com     */
35292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    template <int N>
35392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    SkTArray(SkAlignedSTStorage<N,T>* storage) {
35492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        this->init(NULL, 0, storage->get(), N);
35592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    }
35692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
35792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    /**
35892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com     * Copy another array, using preallocated storage if preAllocCount >=
35992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com     * array.count(). Otherwise storage will only be used when array shrinks
36092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com     * to fit.
36192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com     */
36292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    template <int N>
36392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) {
36492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        this->init(array.fItemArray, array.fCount, storage->get(), N);
36592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    }
36692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
36792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    /**
36892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com     * Copy a C array, using preallocated storage if preAllocCount >=
36992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com     * count. Otherwise storage will only be used when array shrinks
37092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com     * to fit.
37192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com     */
37292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    template <int N>
37392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) {
37492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        this->init(array, count, storage->get(), N);
37592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    }
37692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
37792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    void init(const T* array, int count,
37892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com               void* preAllocStorage, int preAllocOrReserveCount) {
379d80a509eb773cdca6c7a9d3af4ac44a6dd24c567junov@chromium.org        SkASSERT(count >= 0);
380d80a509eb773cdca6c7a9d3af4ac44a6dd24c567junov@chromium.org        SkASSERT(preAllocOrReserveCount >= 0);
38192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        fCount              = count;
38292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        fReserveCount       = (preAllocOrReserveCount > 0) ?
38392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com                                    preAllocOrReserveCount :
38492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com                                    gMIN_ALLOC_COUNT;
38592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        fPreAllocMemArray   = preAllocStorage;
38692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        if (fReserveCount >= fCount &&
38792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com            NULL != preAllocStorage) {
38892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com            fAllocCount = fReserveCount;
38992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com            fMemArray = preAllocStorage;
39092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        } else {
391d80a509eb773cdca6c7a9d3af4ac44a6dd24c567junov@chromium.org            fAllocCount = SkMax32(fCount, fReserveCount);
392d80a509eb773cdca6c7a9d3af4ac44a6dd24c567junov@chromium.org            fMemArray = sk_malloc_throw(fAllocCount * sizeof(T));
39392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        }
39492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
395a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com        SkTArrayExt::copy(this, array);
39692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    }
39792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
398ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.comprivate:
399ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
40049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com    static const int gMIN_ALLOC_COUNT = 8;
4011c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com
402d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com    // Helper function that makes space for n objects, adjusts the count, but does not initialize
403d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com    // the new objects.
404d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com    void* push_back_raw(int n) {
405d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        this->checkRealloc(n);
406d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        void* ptr = fItemArray + fCount;
407d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        fCount += n;
408d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com        return ptr;
409d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com    }
410d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com
4111c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com    inline void checkRealloc(int delta) {
41249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(fCount >= 0);
41349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(fAllocCount >= 0);
4141c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com
41549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com        SkASSERT(-delta <= fCount);
416ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
4171c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com        int newCount = fCount + delta;
418a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com        int newAllocCount = fAllocCount;
419ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
420137209f9f4b6ee08ca59a135909185cb0caf6d91bsalomon@google.com        if (newCount > fAllocCount || newCount < (fAllocCount / 3)) {
421137209f9f4b6ee08ca59a135909185cb0caf6d91bsalomon@google.com            // whether we're growing or shrinking, we leave at least 50% extra space for future
422137209f9f4b6ee08ca59a135909185cb0caf6d91bsalomon@google.com            // growth (clamped to the reserve count).
423137209f9f4b6ee08ca59a135909185cb0caf6d91bsalomon@google.com            newAllocCount = SkMax32(newCount + ((newCount + 1) >> 1), fReserveCount);
424ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        }
425a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com        if (newAllocCount != fAllocCount) {
426ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
427a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com            fAllocCount = newAllocCount;
428a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com            char* newMemArray;
429ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
430ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com            if (fAllocCount == fReserveCount && NULL != fPreAllocMemArray) {
431a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com                newMemArray = (char*) fPreAllocMemArray;
432ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com            } else {
433a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com                newMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T));
434ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com            }
435ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
436a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com            SkTArrayExt::copyAndDelete<T>(this, newMemArray);
437ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
438ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com            if (fMemArray != fPreAllocMemArray) {
43949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com                sk_free(fMemArray);
440ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com            }
441a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com            fMemArray = newMemArray;
442ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        }
443ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    }
444ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
445d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com    friend void* operator new<T>(size_t, SkTArray*, int);
446d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com
44795ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com    template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, int dst, int src);
448cf385232c45b7692eaf31260fe650457f400521abungeman@google.com    template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, const X*);
449cf385232c45b7692eaf31260fe650457f400521abungeman@google.com    template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, true>* that, char*);
450a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com
45195ebd17cf4f66952862289882ee5ac00da31cb8abungeman@google.com    template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, int dst, int src);
452cf385232c45b7692eaf31260fe650457f400521abungeman@google.com    template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, const X*);
453cf385232c45b7692eaf31260fe650457f400521abungeman@google.com    template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, false>* that, char*);
454a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com
4551c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com    int fReserveCount;
4561c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com    int fCount;
4571c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com    int fAllocCount;
458ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    void*    fPreAllocMemArray;
459ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    union {
460ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        T*       fItemArray;
461ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com        void*    fMemArray;
462ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com    };
463ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com};
464ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com
465d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com// Use the below macro (SkNEW_APPEND_TO_TARRAY) rather than calling this directly
466d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.comtemplate <typename T, bool MEM_COPY>
467d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.comvoid* operator new(size_t, SkTArray<T, MEM_COPY>* array, int atIndex) {
468d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com    // Currently, we only support adding to the end of the array. When the array class itself
469d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com    // supports random insertion then this should be updated.
470d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com    // SkASSERT(atIndex >= 0 && atIndex <= array->count());
471d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com    SkASSERT(atIndex == array->count());
472d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com    return array->push_back_raw(1);
473d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com}
474d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com
475a47347eb9c8de4f64c6e7a0b3242fe87d939cb21bsalomon@google.com// Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete
476a47347eb9c8de4f64c6e7a0b3242fe87d939cb21bsalomon@google.com// to match the op new silences warnings about missing op delete when a constructor throws an
477a47347eb9c8de4f64c6e7a0b3242fe87d939cb21bsalomon@google.com// exception.
478f85693d53a487b00360e77de69556b13bda0e602skia.committer@gmail.comtemplate <typename T, bool MEM_COPY>
47968b6eca42ed2bf9b4daaa2f210c9c14d7a5d0e3frobertphillips@google.comvoid operator delete(void*, SkTArray<T, MEM_COPY>* array, int atIndex) {
480a47347eb9c8de4f64c6e7a0b3242fe87d939cb21bsalomon@google.com    SK_CRASH();
481a47347eb9c8de4f64c6e7a0b3242fe87d939cb21bsalomon@google.com}
482a47347eb9c8de4f64c6e7a0b3242fe87d939cb21bsalomon@google.com
483d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com// Constructs a new object as the last element of an SkTArray.
484d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com#define SkNEW_APPEND_TO_TARRAY(array_ptr, type_name, args)  \
485d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com    (new ((array_ptr), (array_ptr)->count()) type_name args)
486d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com
487d51041469a9a45562d88e9ff137c6726562e8c40bsalomon@google.com
48892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com/**
48992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com * Subclass of SkTArray that contains a preallocated memory block for the array.
49092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com */
491f47dd74da3c7454af46aa0abe052d3fc6f02b9b2bsalomon@google.comtemplate <int N, typename T, bool MEM_COPY = false>
492f47dd74da3c7454af46aa0abe052d3fc6f02b9b2bsalomon@google.comclass SkSTArray : public SkTArray<T, MEM_COPY> {
49392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.comprivate:
494f47dd74da3c7454af46aa0abe052d3fc6f02b9b2bsalomon@google.com    typedef SkTArray<T, MEM_COPY> INHERITED;
49592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
49692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.compublic:
49792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    SkSTArray() : INHERITED(&fStorage) {
49892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    }
49992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
50092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    SkSTArray(const SkSTArray& array)
50192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        : INHERITED(array, &fStorage) {
50292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    }
50392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
50492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    explicit SkSTArray(const INHERITED& array)
50592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        : INHERITED(array, &fStorage) {
50692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    }
50792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
5083390b9ac9ad69a6e772c2b957d75d19611239025commit-bot@chromium.org    explicit SkSTArray(int reserveCount)
5093390b9ac9ad69a6e772c2b957d75d19611239025commit-bot@chromium.org        : INHERITED(reserveCount) {
5103390b9ac9ad69a6e772c2b957d75d19611239025commit-bot@chromium.org    }
5113390b9ac9ad69a6e772c2b957d75d19611239025commit-bot@chromium.org
51292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    SkSTArray(const T* array, int count)
51392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        : INHERITED(array, count, &fStorage) {
51492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    }
51592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
51692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    SkSTArray& operator= (const SkSTArray& array) {
51792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        return *this = *(const INHERITED*)&array;
51892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    }
51992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
52092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    SkSTArray& operator= (const INHERITED& array) {
52192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        INHERITED::operator=(array);
52292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com        return *this;
52392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    }
52492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
52592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.comprivate:
52692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com    SkAlignedSTStorage<N,T> fStorage;
52792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com};
52892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com
529ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com#endif
530