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