SkTArray.h revision d51041469a9a45562d88e9ff137c6726562e8c40
1/* 2 * Copyright 2011 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8#ifndef SkTArray_DEFINED 9#define SkTArray_DEFINED 10 11#include <new> 12#include "SkTypes.h" 13#include "SkTemplates.h" 14 15template <typename T, bool MEM_COPY = false> class SkTArray; 16 17namespace SkTArrayExt { 18 19template<typename T> 20inline void copy(SkTArray<T, true>* self, const T* array) { 21 memcpy(self->fMemArray, array, self->fCount * sizeof(T)); 22} 23template<typename T> 24inline void copyAndDelete(SkTArray<T, true>* self, char* newMemArray) { 25 memcpy(newMemArray, self->fMemArray, self->fCount * sizeof(T)); 26} 27 28template<typename T> 29inline void copy(SkTArray<T, false>* self, const T* array) { 30 for (int i = 0; i < self->fCount; ++i) { 31 SkNEW_PLACEMENT_ARGS(self->fItemArray + i, T, (array[i])); 32 } 33} 34template<typename T> 35inline void copyAndDelete(SkTArray<T, false>* self, char* newMemArray) { 36 for (int i = 0; i < self->fCount; ++i) { 37 SkNEW_PLACEMENT_ARGS(newMemArray + sizeof(T) * i, T, (self->fItemArray[i])); 38 self->fItemArray[i].~T(); 39 } 40} 41 42} 43 44template <typename T, bool MEM_COPY> void* operator new(size_t, SkTArray<T, MEM_COPY>*, int); 45 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*/ 51template <typename T, bool MEM_COPY> class SkTArray { 52public: 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 /** 65 * Creates an empty array that will preallocate space for reserveCount 66 * elements. 67 */ 68 explicit SkTArray(int reserveCount) { 69 this->init(NULL, 0, NULL, reserveCount); 70 } 71 72 /** 73 * Copies one array to another. The new array will be heap allocated. 74 */ 75 explicit SkTArray(const SkTArray& array) { 76 this->init(array.fItemArray, array.fCount, NULL, 0); 77 } 78 79 /** 80 * Creates a SkTArray by copying contents of a standard C array. The new 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) { 85 this->init(array, count, NULL, 0); 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; 96 this->checkRealloc((int)array.count()); 97 fCount = array.count(); 98 SkTArrayExt::copy(this, static_cast<const T*>(array.fMemArray)); 99 return *this; 100 } 101 102 virtual ~SkTArray() { 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 /** 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 /** 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 /** 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() { 164 T* newT = reinterpret_cast<T*>(this->push_back_raw(1)); 165 SkNEW_PLACEMENT(newT, T); 166 return *newT; 167 } 168 169 /** 170 * Version of above that uses a copy constructor to initialize the new item 171 */ 172 T& push_back(const T& t) { 173 T* newT = reinterpret_cast<T*>(this->push_back_raw(1)); 174 SkNEW_PLACEMENT_ARGS(newT, T, (t)); 175 return *newT; 176 } 177 178 /** 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); 185 T* newTs = reinterpret_cast<T*>(this->push_back_raw(n)); 186 for (int i = 0; i < n; ++i) { 187 SkNEW_PLACEMENT(newTs + i, T); 188 } 189 return newTs; 190 } 191 192 /** 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); 198 T* newTs = reinterpret_cast<T*>(this->push_back_raw(n)); 199 for (int i = 0; i < n; ++i) { 200 SkNEW_PLACEMENT_ARGS(newTs[i], T, (t)); 201 } 202 return newTs; 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); 211 this->checkRealloc(n); 212 for (int i = 0; i < n; ++i) { 213 SkNEW_PLACEMENT_ARGS(fItemArray + fCount + i, T, (t[i])); 214 } 215 fCount += n; 216 return fItemArray + fCount - n; 217 } 218 219 /** 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(); 226 this->checkRealloc(0); 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) { 237 fItemArray[fCount + i].~T(); 238 } 239 this->checkRealloc(0); 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) { 250 this->push_back_n(newCount - fCount); 251 } else if (newCount < fCount) { 252 this->pop_back_n(fCount - newCount); 253 } 254 } 255 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 /** 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 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 330protected: 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) { 362 SkASSERT(count >= 0); 363 SkASSERT(preAllocOrReserveCount >= 0); 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 { 374 fAllocCount = SkMax32(fCount, fReserveCount); 375 fMemArray = sk_malloc_throw(fAllocCount * sizeof(T)); 376 } 377 378 SkTArrayExt::copy(this, array); 379 } 380 381private: 382 383 static const int gMIN_ALLOC_COUNT = 8; 384 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 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; 401 int newAllocCount = fAllocCount; 402 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); 407 } 408 if (newAllocCount != fAllocCount) { 409 410 fAllocCount = newAllocCount; 411 char* newMemArray; 412 413 if (fAllocCount == fReserveCount && NULL != fPreAllocMemArray) { 414 newMemArray = (char*) fPreAllocMemArray; 415 } else { 416 newMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T)); 417 } 418 419 SkTArrayExt::copyAndDelete<T>(this, newMemArray); 420 421 if (fMemArray != fPreAllocMemArray) { 422 sk_free(fMemArray); 423 } 424 fMemArray = newMemArray; 425 } 426 } 427 428 friend void* operator new<T>(size_t, SkTArray*, int); 429 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*); 432 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*); 435 436 int fReserveCount; 437 int fCount; 438 int fAllocCount; 439 void* fPreAllocMemArray; 440 union { 441 T* fItemArray; 442 void* fMemArray; 443 }; 444}; 445 446// Use the below macro (SkNEW_APPEND_TO_TARRAY) rather than calling this directly 447template <typename T, bool MEM_COPY> 448void* 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 461/** 462 * Subclass of SkTArray that contains a preallocated memory block for the array. 463 */ 464template <int N, typename T, bool MEM_COPY = false> 465class SkSTArray : public SkTArray<T, MEM_COPY> { 466private: 467 typedef SkTArray<T, MEM_COPY> INHERITED; 468 469public: 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 494private: 495 SkAlignedSTStorage<N,T> fStorage; 496}; 497 498#endif 499