SkTArray.h revision f47dd74da3c7454af46aa0abe052d3fc6f02b9b2
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Copyright 2011 Google Inc. 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com */ 7ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#ifndef SkTArray_DEFINED 949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#define SkTArray_DEFINED 10ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 11ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com#include <new> 1249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#include "SkTypes.h" 1349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com#include "SkTemplates.h" 14ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 15a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate <typename T, bool MEM_COPY = false> class SkTArray; 16a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com 17a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comnamespace SkTArrayExt { 18a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com 19a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate<typename T> 20a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.cominline void copy(SkTArray<T, true>* self, const T* array) { 21a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com memcpy(self->fMemArray, array, self->fCount * sizeof(T)); 22a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com} 23a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate<typename T> 24a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.cominline void copyAndDelete(SkTArray<T, true>* self, char* newMemArray) { 25a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com memcpy(newMemArray, self->fMemArray, self->fCount * sizeof(T)); 26a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com} 27a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com 28a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate<typename T> 29a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.cominline void copy(SkTArray<T, false>* self, const T* array) { 30a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com for (int i = 0; i < self->fCount; ++i) { 31a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com new (self->fItemArray + i) T(array[i]); 32a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com } 33a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com} 34a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate<typename T> 35a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.cominline void copyAndDelete(SkTArray<T, false>* self, char* newMemArray) { 36a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com for (int i = 0; i < self->fCount; ++i) { 37a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com new (newMemArray + sizeof(T) * i) T(self->fItemArray[i]); 38a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com self->fItemArray[i].~T(); 39a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com } 40a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com} 41a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com 42a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com} 43a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com 44a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com/** When MEM_COPY is true T will be bit copied when moved. 45a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com When MEM_COPY is false, T will be copy constructed / destructed. 46a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com In all cases T's constructor will be called on allocation, 47a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com and its destructor will be called from this object's destructor. 48a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com*/ 49a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.comtemplate <typename T, bool MEM_COPY> class SkTArray { 50ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.compublic: 5149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 5249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Creates an empty array with no initial storage 5349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 5449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkTArray() { 55ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = 0; 5649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com fReserveCount = gMIN_ALLOC_COUNT; 57ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fAllocCount = 0; 58ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fMemArray = NULL; 59ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fPreAllocMemArray = NULL; 60ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 61ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 6249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 63fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * Creates an empty array that will preallocate space for reserveCount 6449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * elements. 6549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 6649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com explicit SkTArray(int reserveCount) { 6792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com this->init(NULL, 0, NULL, reserveCount); 68ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 69fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 7049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 7149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Copies one array to another. The new array will be heap allocated. 7249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 7349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com explicit SkTArray(const SkTArray& array) { 7492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com this->init(array.fItemArray, array.fCount, NULL, 0); 75ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 76ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 7749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 78fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com * Creates a SkTArray by copying contents of a standard C array. The new 7949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * array will be heap allocated. Be careful not to use this constructor 8049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * when you really want the (void*, int) version. 8149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 8249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkTArray(const T* array, int count) { 8392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com this->init(array, count, NULL, 0); 84ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 85ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 8649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 8749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * assign copy of array to this 8849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 8949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkTArray& operator =(const SkTArray& array) { 901c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < fCount; ++i) { 91ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fItemArray[i].~T(); 92ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 93ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = 0; 94ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com checkRealloc((int)array.count()); 95ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount = array.count(); 96a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com SkTArrayExt::copy(this, static_cast<const T*>(array.fMemArray)); 97ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return *this; 98ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 99ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 10092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com virtual ~SkTArray() { 1011c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < fCount; ++i) { 102ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fItemArray[i].~T(); 103ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 104ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (fMemArray != fPreAllocMemArray) { 10549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com sk_free(fMemArray); 106ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 107ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 108ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 10949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 11049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Resets to count() == 0 11149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 112d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com void reset() { this->pop_back_n(fCount); } 113d302f1401b3c9aea094804bad4e76de98782cfe8bsalomon@google.com 11449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 11549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Number of elements in the array. 11649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 1171c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com int count() const { return fCount; } 118ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 11949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 12049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Is the array empty. 12149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 122ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com bool empty() const { return !fCount; } 123ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 124a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com /** 125a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * Adds 1 new default-constructed T value and returns in by reference. Note 126a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * the reference only remains valid until the next call that adds or removes 127a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * elements. 128a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com */ 129ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com T& push_back() { 130ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com checkRealloc(1); 131ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com new ((char*)fMemArray+sizeof(T)*fCount) T; 132ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com ++fCount; 133ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return fItemArray[fCount-1]; 134ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 135ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 136a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com /** 1374fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com * Version of above that uses a copy constructor to initialize the new item 1384fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com */ 1394fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com T& push_back(const T& t) { 1404fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com checkRealloc(1); 1414fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com new ((char*)fMemArray+sizeof(T)*fCount) T(t); 1424fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com ++fCount; 1434fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com return fItemArray[fCount-1]; 1444fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com } 1454fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com 1464fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com /** 147a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * Allocates n more default T values, and returns the address of the start 148a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * of that new range. Note: this address is only valid until the next API 149a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com * call made on the array that might add or remove elements. 150a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com */ 151a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com T* push_back_n(int n) { 15249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(n >= 0); 153ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com checkRealloc(n); 1541c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < n; ++i) { 155ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com new (fItemArray + fCount + i) T; 156ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 157ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount += n; 158a996fec40444e8b914cd84c17037f0c84301f717bsalomon@google.com return fItemArray + fCount - n; 159ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 160ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 16149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 1624fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com * Version of above that uses a copy constructor to initialize all n items 1634fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com * to the same T. 1644fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com */ 1654fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com T* push_back_n(int n, const T& t) { 1664fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com SkASSERT(n >= 0); 1674fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com checkRealloc(n); 1684fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com for (int i = 0; i < n; ++i) { 1694fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com new (fItemArray + fCount + i) T(t); 1704fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com } 1714fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com fCount += n; 1724fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com return fItemArray + fCount - n; 1734fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com } 1744fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com 1754fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com /** 1764fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com * Version of above that uses a copy constructor to initialize the n items 1774fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com * to separate T values. 1784fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com */ 1794fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com T* push_back_n(int n, const T t[]) { 1804fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com SkASSERT(n >= 0); 1814fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com checkRealloc(n); 1824fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com for (int i = 0; i < n; ++i) { 1834fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com new (fItemArray + fCount + i) T(t[i]); 1844fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com } 1854fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com fCount += n; 1864fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com return fItemArray + fCount - n; 1874fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com } 1884fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com 1894fa6694c587b3830932429766c99d08c8dd9b723bsalomon@google.com /** 19049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Removes the last element. Not safe to call when count() == 0. 19149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 192ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com void pop_back() { 19349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(fCount > 0); 194ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com --fCount; 195ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fItemArray[fCount].~T(); 196ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com checkRealloc(0); 197ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 198ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 19949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 20049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Removes the last n elements. Not safe to call when count() < n. 20149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 2021c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com void pop_back_n(int n) { 20349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(n >= 0); 20449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(fCount >= n); 205ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fCount -= n; 2061c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com for (int i = 0; i < n; ++i) { 207ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com fItemArray[i].~T(); 208ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 209ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com checkRealloc(0); 210ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 211ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 21249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 21349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Pushes or pops from the back to resize. Pushes will be default 21449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * initialized. 21549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 2161c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com void resize_back(int newCount) { 21749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(newCount >= 0); 2181c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com 219ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (newCount > fCount) { 220ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com push_back_n(newCount - fCount); 221ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else if (newCount < fCount) { 222ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com pop_back_n(fCount - newCount); 223ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 224ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 225ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 22649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 22749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * Get the i^th element. 22849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 2291c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com T& operator[] (int i) { 23049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i < fCount); 23149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i >= 0); 232ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return fItemArray[i]; 233ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 234ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 2351c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com const T& operator[] (int i) const { 23649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i < fCount); 23749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i >= 0); 238ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return fItemArray[i]; 239ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 240ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 24149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 24249313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * equivalent to operator[](0) 24349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 24449313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com T& front() { SkASSERT(fCount > 0); return fItemArray[0];} 245ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 24649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];} 247ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 24849313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 24949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * equivalent to operator[](count() - 1) 25049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 25149313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];} 252ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 25349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];} 254ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 25549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com /** 25649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com * equivalent to operator[](count()-1-i) 25749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com */ 2581c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com T& fromBack(int i) { 25949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i >= 0); 26049313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i < fCount); 261ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return fItemArray[fCount - i - 1]; 262ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 263ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 2641c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com const T& fromBack(int i) const { 26549313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i >= 0); 26649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(i < fCount); 267ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com return fItemArray[fCount - i - 1]; 268ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 269ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 27092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.comprotected: 27192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com /** 27292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com * Creates an empty array that will use the passed storage block until it 27392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com * is insufficiently large to hold the entire array. 27492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com */ 27592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com template <int N> 27692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com SkTArray(SkAlignedSTStorage<N,T>* storage) { 27792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com this->init(NULL, 0, storage->get(), N); 27892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } 27992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 28092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com /** 28192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com * Copy another array, using preallocated storage if preAllocCount >= 28292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com * array.count(). Otherwise storage will only be used when array shrinks 28392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com * to fit. 28492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com */ 28592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com template <int N> 28692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) { 28792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com this->init(array.fItemArray, array.fCount, storage->get(), N); 28892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } 28992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 29092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com /** 29192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com * Copy a C array, using preallocated storage if preAllocCount >= 29292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com * count. Otherwise storage will only be used when array shrinks 29392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com * to fit. 29492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com */ 29592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com template <int N> 29692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) { 29792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com this->init(array, count, storage->get(), N); 29892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } 29992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 30092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com void init(const T* array, int count, 30192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com void* preAllocStorage, int preAllocOrReserveCount) { 302d80a509eb773cdca6c7a9d3af4ac44a6dd24c567junov@chromium.org SkASSERT(count >= 0); 303d80a509eb773cdca6c7a9d3af4ac44a6dd24c567junov@chromium.org SkASSERT(preAllocOrReserveCount >= 0); 30492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com fCount = count; 30592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com fReserveCount = (preAllocOrReserveCount > 0) ? 30692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com preAllocOrReserveCount : 30792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com gMIN_ALLOC_COUNT; 30892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com fPreAllocMemArray = preAllocStorage; 30992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com if (fReserveCount >= fCount && 31092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com NULL != preAllocStorage) { 31192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com fAllocCount = fReserveCount; 31292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com fMemArray = preAllocStorage; 31392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } else { 314d80a509eb773cdca6c7a9d3af4ac44a6dd24c567junov@chromium.org fAllocCount = SkMax32(fCount, fReserveCount); 315d80a509eb773cdca6c7a9d3af4ac44a6dd24c567junov@chromium.org fMemArray = sk_malloc_throw(fAllocCount * sizeof(T)); 31692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } 31792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 318a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com SkTArrayExt::copy(this, array); 31992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } 32092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 321ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.comprivate: 322ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 32349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com static const int gMIN_ALLOC_COUNT = 8; 3241c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com 3251c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com inline void checkRealloc(int delta) { 32649313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(fCount >= 0); 32749313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(fAllocCount >= 0); 3281c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com 32949313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com SkASSERT(-delta <= fCount); 330ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 3311c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com int newCount = fCount + delta; 332a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com int newAllocCount = fAllocCount; 333ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 334137209f9f4b6ee08ca59a135909185cb0caf6d91bsalomon@google.com if (newCount > fAllocCount || newCount < (fAllocCount / 3)) { 335137209f9f4b6ee08ca59a135909185cb0caf6d91bsalomon@google.com // whether we're growing or shrinking, we leave at least 50% extra space for future 336137209f9f4b6ee08ca59a135909185cb0caf6d91bsalomon@google.com // growth (clamped to the reserve count). 337137209f9f4b6ee08ca59a135909185cb0caf6d91bsalomon@google.com newAllocCount = SkMax32(newCount + ((newCount + 1) >> 1), fReserveCount); 338ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 339a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com if (newAllocCount != fAllocCount) { 340ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 341a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com fAllocCount = newAllocCount; 342a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com char* newMemArray; 343ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 344ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (fAllocCount == fReserveCount && NULL != fPreAllocMemArray) { 345a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com newMemArray = (char*) fPreAllocMemArray; 346ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } else { 347a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com newMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T)); 348ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 349ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 350a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com SkTArrayExt::copyAndDelete<T>(this, newMemArray); 351ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 352ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com if (fMemArray != fPreAllocMemArray) { 35349313f6b4391d0f74ab1964c295634e8830680f6bsalomon@google.com sk_free(fMemArray); 354ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 355a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com fMemArray = newMemArray; 356ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 357ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com } 358ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 359cf385232c45b7692eaf31260fe650457f400521abungeman@google.com template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, const X*); 360cf385232c45b7692eaf31260fe650457f400521abungeman@google.com template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, true>* that, char*); 361a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com 362cf385232c45b7692eaf31260fe650457f400521abungeman@google.com template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, const X*); 363cf385232c45b7692eaf31260fe650457f400521abungeman@google.com template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, false>* that, char*); 364a12cc7fda00236549961d7b8e2d708cfe3cfa4e6bungeman@google.com 3651c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com int fReserveCount; 3661c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com int fCount; 3671c13c9668a889e56a0c85b51b9f28139c25b76ffbsalomon@google.com int fAllocCount; 368ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com void* fPreAllocMemArray; 369ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com union { 370ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com T* fItemArray; 371ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com void* fMemArray; 372ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com }; 373ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com}; 374ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com 37592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com/** 37692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com * Subclass of SkTArray that contains a preallocated memory block for the array. 37792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com */ 378f47dd74da3c7454af46aa0abe052d3fc6f02b9b2bsalomon@google.comtemplate <int N, typename T, bool MEM_COPY = false> 379f47dd74da3c7454af46aa0abe052d3fc6f02b9b2bsalomon@google.comclass SkSTArray : public SkTArray<T, MEM_COPY> { 38092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.comprivate: 381f47dd74da3c7454af46aa0abe052d3fc6f02b9b2bsalomon@google.com typedef SkTArray<T, MEM_COPY> INHERITED; 38292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 38392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.compublic: 38492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com SkSTArray() : INHERITED(&fStorage) { 38592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } 38692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 38792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com SkSTArray(const SkSTArray& array) 38892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com : INHERITED(array, &fStorage) { 38992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } 39092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 39192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com explicit SkSTArray(const INHERITED& array) 39292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com : INHERITED(array, &fStorage) { 39392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } 39492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 39592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com SkSTArray(const T* array, int count) 39692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com : INHERITED(array, count, &fStorage) { 39792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } 39892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 39992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com SkSTArray& operator= (const SkSTArray& array) { 40092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com return *this = *(const INHERITED*)&array; 40192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } 40292669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 40392669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com SkSTArray& operator= (const INHERITED& array) { 40492669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com INHERITED::operator=(array); 40592669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com return *this; 40692669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com } 40792669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 40892669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.comprivate: 40992669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com SkAlignedSTStorage<N,T> fStorage; 41092669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com}; 41192669014aa7ab821cdc09cc9ad610316eb16b490bsalomon@google.com 412ac10a2d039c5d52eed66e27cbbc503ab523c1cd5reed@google.com#endif 413