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