SkTArray.h revision 4fa6694c587b3830932429766c99d08c8dd9b723
1ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Copyright 2011 Google Inc. 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 7ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com */ 8ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 9ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 10ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 1149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#ifndef SkTArray_DEFINED 1249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#define SkTArray_DEFINED 13ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 14ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com#include <new> 1549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#include "SkTypes.h" 1649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#include "SkTemplates.h" 17ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 18ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com// DATA_TYPE indicates that T has a trivial cons, destructor 19ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com// and can be shallow-copied 2049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.comtemplate <typename T, bool DATA_TYPE = false> class SkTArray { 21ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.compublic: 2249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 2349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Creates an empty array with no initial storage 2449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 2549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkTArray() { 26ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = 0; 2749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fReserveCount = gMIN_ALLOC_COUNT; 28ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fAllocCount = 0; 29ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fMemArray = NULL; 30ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fPreAllocMemArray = NULL; 31ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 32ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 3349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 3449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Creates an empty array that will preallocate space for reserveCount 3549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * elements. 3649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 3749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com explicit SkTArray(int reserveCount) { 3849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(reserveCount >= 0); 39ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = 0; 4049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fReserveCount = reserveCount > gMIN_ALLOC_COUNT ? reserveCount : 4149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com gMIN_ALLOC_COUNT; 42ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fAllocCount = fReserveCount; 4349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fMemArray = sk_malloc_throw(sizeof(T) * fReserveCount); 44ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fPreAllocMemArray = NULL; 45ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 46ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 4749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 4849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Creates an empty array that will use the passed storage block until it 4949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * is insufficiently large to hold the entire array. 5049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 51a55847ba22ae4a673af022e7d88404e080195464bsalomon@google.com template <int N> 5249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkTArray(SkAlignedSTStorage<N,T>* storage) { 5349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(N > 0); 54a55847ba22ae4a673af022e7d88404e080195464bsalomon@google.com fCount = 0; 55a55847ba22ae4a673af022e7d88404e080195464bsalomon@google.com fReserveCount = N; 56a55847ba22ae4a673af022e7d88404e080195464bsalomon@google.com fAllocCount = N; 57a55847ba22ae4a673af022e7d88404e080195464bsalomon@google.com fMemArray = storage->get(); 58a55847ba22ae4a673af022e7d88404e080195464bsalomon@google.com fPreAllocMemArray = storage->get(); 59a55847ba22ae4a673af022e7d88404e080195464bsalomon@google.com } 60a55847ba22ae4a673af022e7d88404e080195464bsalomon@google.com 6149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 6249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Creates an empty array that will use the passed memory block until the 6349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * count exceeds preAllocCount. Be careful not to use this constructor 6449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * when you really want the (T*, int) version. 6549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 6649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkTArray(void* preAllocStorage, int preAllocCount) { 6749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(preAllocCount >= 0); 68ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com // we allow NULL,0 args and revert to the default cons. behavior 69ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com // this makes it possible for a owner-object to use same constructor 70ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com // to get either prealloc or nonprealloc behavior based using same line 7149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT((NULL == preAllocStorage) == !preAllocCount); 72ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 73ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = 0; 74ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fReserveCount = preAllocCount > 0 ? preAllocCount : 7549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com gMIN_ALLOC_COUNT; 76ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fAllocCount = preAllocCount; 77ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fMemArray = preAllocStorage; 78ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fPreAllocMemArray = preAllocStorage; 79ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 80ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 8149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 8249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Copies one array to another. The new array will be heap allocated. 8349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 8449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com explicit SkTArray(const SkTArray& array) { 85ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = array.count(); 8649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fReserveCount = gMIN_ALLOC_COUNT; 8749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fAllocCount = SkMax32(fReserveCount, fCount); 885c6ae60a713a2befec9c26c4058640320ac0d85ebsalomon@google.com fMemArray = sk_malloc_throw(sizeof(T) * fAllocCount); 89ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fPreAllocMemArray = NULL; 90a55847ba22ae4a673af022e7d88404e080195464bsalomon@google.com 91ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (DATA_TYPE) { 92ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com memcpy(fMemArray, array.fMemArray, sizeof(T) * fCount); 93ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else { 941c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < fCount; ++i) { 95ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com new (fItemArray + i) T(array[i]); 96ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 97ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 98ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 99ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 10049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 10149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Creates a SkTArray by copying contents of a standard C array. The new 10249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * array will be heap allocated. Be careful not to use this constructor 10349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * when you really want the (void*, int) version. 10449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 10549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkTArray(const T* array, int count) { 10649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(count >= 0); 107ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = count; 10849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fReserveCount = gMIN_ALLOC_COUNT; 10949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fAllocCount = SkMax32(fReserveCount, fCount); 1105c6ae60a713a2befec9c26c4058640320ac0d85ebsalomon@google.com fMemArray = sk_malloc_throw(sizeof(T) * fAllocCount); 111ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fPreAllocMemArray = NULL; 112ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (DATA_TYPE) { 113ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com memcpy(fMemArray, array, sizeof(T) * fCount); 114ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else { 1151c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < fCount; ++i) { 116ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com new (fItemArray + i) T(array[i]); 117ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 118ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 119ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 120ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 12149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 12249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Copy another array, using preallocated storage if preAllocCount >= 12349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * array.count(). Otherwise preAllocStorage is only used if the array 12449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * shrinks to fit. 12549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 12649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkTArray(const SkTArray& array, 1271c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com void* preAllocStorage, int preAllocCount) { 1281c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com 12949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(preAllocCount >= 0); 130ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 131ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com // for same reason as non-copying cons we allow NULL, 0 for prealloc 13249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT((NULL == preAllocStorage) == !preAllocCount); 133ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 134ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = array.count(); 135ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fReserveCount = preAllocCount > 0 ? preAllocCount : 13649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com gMIN_ALLOC_COUNT; 137ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fPreAllocMemArray = preAllocStorage; 138ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 139ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (fReserveCount >= fCount && preAllocCount) { 140ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fAllocCount = fReserveCount; 141ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fMemArray = preAllocStorage; 142ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else { 14349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fAllocCount = SkMax32(fCount, fReserveCount); 14449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fMemArray = sk_malloc_throw(fAllocCount * sizeof(T)); 145ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 146ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 147ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (DATA_TYPE) { 148ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com memcpy(fMemArray, array.fMemArray, sizeof(T) * fCount); 149ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else { 1501c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < fCount; ++i) { 151ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com new (fItemArray + i) T(array[i]); 152ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 153ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 154ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 155ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 15649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 15749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Copy C array to SkTArray, using preallocated storage if preAllocCount >= 15849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * preAllocCount. Otherwise preAllocStorage is only used if the array 15949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * shrinks to fit. 16049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 16149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkTArray(const T* array, int count, 1621c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com void* preAllocStorage, int preAllocCount) { 1631c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com 16449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(count >= 0); 16549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(preAllocCount >= 0); 166ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 167ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com // for same reason as non-copying cons we allow NULL, 0 for prealloc 16849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT((NULL == preAllocStorage) == !preAllocCount); 169ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 170ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = count; 171ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fReserveCount = (preAllocCount > 0) ? preAllocCount : 17249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com gMIN_ALLOC_COUNT; 173ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fPreAllocMemArray = preAllocStorage; 174ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 175ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (fReserveCount >= fCount && preAllocCount) { 176ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fAllocCount = fReserveCount; 177ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fMemArray = preAllocStorage; 178ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else { 17949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fAllocCount = SkMax32(fCount, fReserveCount); 18049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fMemArray = sk_malloc_throw(fAllocCount * sizeof(T)); 181ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 182ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 183ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (DATA_TYPE) { 184ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com memcpy(fMemArray, array, sizeof(T) * fCount); 185ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else { 1861c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < fCount; ++i) { 187ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com new (fItemArray + i) T(array[i]); 188ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 189ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 190ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 191ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 19249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 19349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * assign copy of array to this 19449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 19549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkTArray& operator =(const SkTArray& array) { 1961c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < fCount; ++i) { 197ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fItemArray[i].~T(); 198ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 199ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = 0; 200ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com checkRealloc((int)array.count()); 201ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = array.count(); 202ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (DATA_TYPE) { 203ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com memcpy(fMemArray, array.fMemArray, sizeof(T) * fCount); 204ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else { 2051c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < fCount; ++i) { 206ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com new (fItemArray + i) T(array[i]); 207ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 208ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 209ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return *this; 210ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 211ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 21249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com ~SkTArray() { 2131c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < fCount; ++i) { 214ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fItemArray[i].~T(); 215ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 216ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (fMemArray != fPreAllocMemArray) { 21749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com sk_free(fMemArray); 218ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 219ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 220ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 22149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 22249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Resets to count() == 0 22349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 224d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com void reset() { this->pop_back_n(fCount); } 225d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com 22649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 22749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Number of elements in the array. 22849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 2291c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com int count() const { return fCount; } 230ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 23149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 23249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Is the array empty. 23349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 234ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com bool empty() const { return !fCount; } 235ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 236a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com /** 237a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * Adds 1 new default-constructed T value and returns in by reference. Note 238a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * the reference only remains valid until the next call that adds or removes 239a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * elements. 240a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com */ 241ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com T& push_back() { 242ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com checkRealloc(1); 243ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com new ((char*)fMemArray+sizeof(T)*fCount) T; 244ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com ++fCount; 245ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return fItemArray[fCount-1]; 246ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 247ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 248a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com /** 2494fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com * Version of above that uses a copy constructor to initialize the new item 2504fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com */ 2514fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com T& push_back(const T& t) { 2524fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com checkRealloc(1); 2534fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com new ((char*)fMemArray+sizeof(T)*fCount) T(t); 2544fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com ++fCount; 2554fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com return fItemArray[fCount-1]; 2564fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com } 2574fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com 2584fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com /** 259a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * Allocates n more default T values, and returns the address of the start 260a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * of that new range. Note: this address is only valid until the next API 261a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * call made on the array that might add or remove elements. 262a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com */ 263a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com T* push_back_n(int n) { 26449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(n >= 0); 265ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com checkRealloc(n); 2661c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < n; ++i) { 267ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com new (fItemArray + fCount + i) T; 268ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 269ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount += n; 270a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com return fItemArray + fCount - n; 271ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 272ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 27349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 2744fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com * Version of above that uses a copy constructor to initialize all n items 2754fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com * to the same T. 2764fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com */ 2774fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com T* push_back_n(int n, const T& t) { 2784fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com SkASSERT(n >= 0); 2794fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com checkRealloc(n); 2804fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com for (int i = 0; i < n; ++i) { 2814fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com new (fItemArray + fCount + i) T(t); 2824fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com } 2834fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com fCount += n; 2844fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com return fItemArray + fCount - n; 2854fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com } 2864fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com 2874fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com /** 2884fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com * Version of above that uses a copy constructor to initialize the n items 2894fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com * to separate T values. 2904fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com */ 2914fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com T* push_back_n(int n, const T t[]) { 2924fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com SkASSERT(n >= 0); 2934fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com checkRealloc(n); 2944fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com for (int i = 0; i < n; ++i) { 2954fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com new (fItemArray + fCount + i) T(t[i]); 2964fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com } 2974fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com fCount += n; 2984fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com return fItemArray + fCount - n; 2994fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com } 3004fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com 3014fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com /** 30249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Removes the last element. Not safe to call when count() == 0. 30349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 304ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com void pop_back() { 30549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(fCount > 0); 306ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com --fCount; 307ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fItemArray[fCount].~T(); 308ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com checkRealloc(0); 309ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 310ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 31149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 31249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Removes the last n elements. Not safe to call when count() < n. 31349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 3141c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com void pop_back_n(int n) { 31549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(n >= 0); 31649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(fCount >= n); 317ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount -= n; 3181c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < n; ++i) { 319ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fItemArray[i].~T(); 320ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 321ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com checkRealloc(0); 322ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 323ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 32449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 32549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Pushes or pops from the back to resize. Pushes will be default 32649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * initialized. 32749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 3281c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com void resize_back(int newCount) { 32949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(newCount >= 0); 3301c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com 331ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (newCount > fCount) { 332ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com push_back_n(newCount - fCount); 333ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else if (newCount < fCount) { 334ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com pop_back_n(fCount - newCount); 335ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 336ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 337ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 33849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 33949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Get the i^th element. 34049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 3411c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com T& operator[] (int i) { 34249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i < fCount); 34349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i >= 0); 344ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return fItemArray[i]; 345ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 346ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 3471c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com const T& operator[] (int i) const { 34849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i < fCount); 34949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i >= 0); 350ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return fItemArray[i]; 351ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 352ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 35349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 35449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * equivalent to operator[](0) 35549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 35649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com T& front() { SkASSERT(fCount > 0); return fItemArray[0];} 357ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 35849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];} 359ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 36049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 36149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * equivalent to operator[](count() - 1) 36249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 36349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];} 364ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 36549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];} 366ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 36749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 36849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * equivalent to operator[](count()-1-i) 36949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 3701c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com T& fromBack(int i) { 37149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i >= 0); 37249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i < fCount); 373ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return fItemArray[fCount - i - 1]; 374ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 375ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 3761c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com const T& fromBack(int i) const { 37749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i >= 0); 37849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i < fCount); 379ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return fItemArray[fCount - i - 1]; 380ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 381ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 382ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.comprivate: 383ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 38449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com static const int gMIN_ALLOC_COUNT = 8; 3851c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com 3861c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com inline void checkRealloc(int delta) { 38749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(fCount >= 0); 38849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(fAllocCount >= 0); 3891c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com 39049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(-delta <= fCount); 391ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 3921c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com int newCount = fCount + delta; 3931c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com int fNewAllocCount = fAllocCount; 394ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 395ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (newCount > fAllocCount) { 39649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fNewAllocCount = SkMax32(newCount + ((newCount + 1) >> 1), 397ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fReserveCount); 398ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else if (newCount < fAllocCount / 3) { 39949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fNewAllocCount = SkMax32(fAllocCount / 2, fReserveCount); 400ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 401ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 402ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (fNewAllocCount != fAllocCount) { 403ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 404ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fAllocCount = fNewAllocCount; 405ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com char* fNewMemArray; 406ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 407ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (fAllocCount == fReserveCount && NULL != fPreAllocMemArray) { 408ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fNewMemArray = (char*) fPreAllocMemArray; 409ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else { 41049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fNewMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T)); 411ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 412ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 413ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (DATA_TYPE) { 414ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com memcpy(fNewMemArray, fMemArray, fCount * sizeof(T)); 415ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else { 4161c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < fCount; ++i) { 417ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com new (fNewMemArray + sizeof(T) * i) T(fItemArray[i]); 418ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fItemArray[i].~T(); 419ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 420ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 421ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 422ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (fMemArray != fPreAllocMemArray) { 42349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com sk_free(fMemArray); 424ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 425ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fMemArray = fNewMemArray; 426ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 427ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 428ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 4291c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com int fReserveCount; 4301c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com int fCount; 4311c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com int fAllocCount; 432ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com void* fPreAllocMemArray; 433ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com union { 434ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com T* fItemArray; 435ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com void* fMemArray; 436ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com }; 437ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com}; 438ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 439ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com#endif 440ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 441