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