SkTArray.h revision 49313f6b4391d0f74ab1964c295634e8830680f6
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copyright 2011 Google Inc. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Use of this source code is governed by a BSD-style license that can be 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * found in the LICENSE file. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef SkTArray_DEFINED 12cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)#define SkTArray_DEFINED 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <new> 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "SkTypes.h" 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "SkTemplates.h" 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA_TYPE indicates that T has a trivial cons, destructor 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// and can be shallow-copied 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename T, bool DATA_TYPE = false> class SkTArray { 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 22cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 23cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * Creates an empty array with no initial storage 24cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 25cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkTArray() { 26cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fCount = 0; 27cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fReserveCount = gMIN_ALLOC_COUNT; 28cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fAllocCount = 0; 29cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fMemArray = NULL; 30cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fPreAllocMemArray = NULL; 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /** 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Creates an empty array that will preallocate space for reserveCount 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * elements. 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 37cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) explicit SkTArray(int reserveCount) { 38cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(reserveCount >= 0); 39cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fCount = 0; 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fReserveCount = reserveCount > gMIN_ALLOC_COUNT ? reserveCount : 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) gMIN_ALLOC_COUNT; 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fAllocCount = fReserveCount; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fMemArray = sk_malloc_throw(sizeof(T) * fReserveCount); 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fPreAllocMemArray = NULL; 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 46cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 47cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 48cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * Creates an empty array that will use the passed storage block until it 49cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * is insufficiently large to hold the entire array. 50cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 51cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) template <int N> 52cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkTArray(SkAlignedSTStorage<N,T>* storage) { 53cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(N > 0); 54cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fCount = 0; 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fReserveCount = N; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fAllocCount = N; 57cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fMemArray = storage->get(); 58cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fPreAllocMemArray = storage->get(); 59cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /** 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Creates an empty array that will use the passed memory block until the 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * count exceeds preAllocCount. Be careful not to use this constructor 64cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * when you really want the (T*, int) version. 65cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 66cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkTArray(void* preAllocStorage, int preAllocCount) { 67cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(preAllocCount >= 0); 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // we allow NULL,0 args and revert to the default cons. behavior 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this makes it possible for a owner-object to use same constructor 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to get either prealloc or nonprealloc behavior based using same line 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkASSERT((NULL == preAllocStorage) == !preAllocCount); 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fCount = 0; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fReserveCount = preAllocCount > 0 ? preAllocCount : 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) gMIN_ALLOC_COUNT; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fAllocCount = preAllocCount; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fMemArray = preAllocStorage; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fPreAllocMemArray = preAllocStorage; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /** 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copies one array to another. The new array will be heap allocated. 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit SkTArray(const SkTArray& array) { 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fCount = array.count(); 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fReserveCount = gMIN_ALLOC_COUNT; 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fAllocCount = SkMax32(fReserveCount, fCount); 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fMemArray = sk_malloc(sizeof(T) * fAllocCount); 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fPreAllocMemArray = NULL; 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (DATA_TYPE) { 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(fMemArray, array.fMemArray, sizeof(T) * fCount); 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < fCount; ++i) { 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new (fItemArray + i) T(array[i]); 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /** 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Creates a SkTArray by copying contents of a standard C array. The new 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * array will be heap allocated. Be careful not to use this constructor 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * when you really want the (void*, int) version. 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkTArray(const T* array, int count) { 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkASSERT(count >= 0); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fCount = count; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fReserveCount = gMIN_ALLOC_COUNT; 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fAllocCount = SkMax32(fReserveCount, fCount); 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fMemArray = sk_malloc(sizeof(T) * fAllocCount); 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fPreAllocMemArray = NULL; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (DATA_TYPE) { 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(fMemArray, array, sizeof(T) * fCount); 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < fCount; ++i) { 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new (fItemArray + i) T(array[i]); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /** 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copy another array, using preallocated storage if preAllocCount >= 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * array.count(). Otherwise preAllocStorage is only used if the array 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * shrinks to fit. 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkTArray(const SkTArray& array, 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* preAllocStorage, int preAllocCount) { 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkASSERT(preAllocCount >= 0); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for same reason as non-copying cons we allow NULL, 0 for prealloc 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkASSERT((NULL == preAllocStorage) == !preAllocCount); 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fCount = array.count(); 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fReserveCount = preAllocCount > 0 ? preAllocCount : 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) gMIN_ALLOC_COUNT; 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fPreAllocMemArray = preAllocStorage; 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (fReserveCount >= fCount && preAllocCount) { 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fAllocCount = fReserveCount; 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fMemArray = preAllocStorage; 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fAllocCount = SkMax32(fCount, fReserveCount); 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fMemArray = sk_malloc_throw(fAllocCount * sizeof(T)); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (DATA_TYPE) { 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(fMemArray, array.fMemArray, sizeof(T) * fCount); 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < fCount; ++i) { 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new (fItemArray + i) T(array[i]); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /** 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copy C array to SkTArray, using preallocated storage if preAllocCount >= 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * preAllocCount. Otherwise preAllocStorage is only used if the array 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * shrinks to fit. 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkTArray(const T* array, int count, 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* preAllocStorage, int preAllocCount) { 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkASSERT(count >= 0); 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkASSERT(preAllocCount >= 0); 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for same reason as non-copying cons we allow NULL, 0 for prealloc 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkASSERT((NULL == preAllocStorage) == !preAllocCount); 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fCount = count; 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fReserveCount = (preAllocCount > 0) ? preAllocCount : 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) gMIN_ALLOC_COUNT; 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fPreAllocMemArray = preAllocStorage; 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (fReserveCount >= fCount && preAllocCount) { 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fAllocCount = fReserveCount; 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fMemArray = preAllocStorage; 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fAllocCount = SkMax32(fCount, fReserveCount); 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fMemArray = sk_malloc_throw(fAllocCount * sizeof(T)); 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (DATA_TYPE) { 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(fMemArray, array, sizeof(T) * fCount); 185cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } else { 186cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) for (int i = 0; i < fCount; ++i) { 187cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) new (fItemArray + i) T(array[i]); 188cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 189cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 190cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 191cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 192cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 193cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * assign copy of array to this 194cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 195cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkTArray& operator =(const SkTArray& array) { 196cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) for (int i = 0; i < fCount; ++i) { 197cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fItemArray[i].~T(); 198cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 199cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fCount = 0; 200cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) checkRealloc((int)array.count()); 201cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fCount = array.count(); 202cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) if (DATA_TYPE) { 203cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) memcpy(fMemArray, array.fMemArray, sizeof(T) * fCount); 204cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } else { 205cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) for (int i = 0; i < fCount; ++i) { 206cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) new (fItemArray + i) T(array[i]); 207cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 208cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 209cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return *this; 210cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 211cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 212cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) ~SkTArray() { 213cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) for (int i = 0; i < fCount; ++i) { 214cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fItemArray[i].~T(); 215cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 216cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) if (fMemArray != fPreAllocMemArray) { 217cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) sk_free(fMemArray); 218cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 219cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 220cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 221cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 222cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * Resets to count() == 0 223cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 224cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void reset() { this->pop_back_n(fCount); } 225cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 226cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 227cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * Number of elements in the array. 228cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 229cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) int count() const { return fCount; } 230cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 231cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 232cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * Is the array empty. 233cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 234cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) bool empty() const { return !fCount; } 235cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 236cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 237cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * Adds 1 new default-constructed T value and returns in by reference. Note 238cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * the reference only remains valid until the next call that adds or removes 239cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * elements. 240cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 241cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) T& push_back() { 242cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) checkRealloc(1); 243cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) new ((char*)fMemArray+sizeof(T)*fCount) T; 244cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) ++fCount; 245cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return fItemArray[fCount-1]; 246cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 247cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 248cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 249cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * Allocates n more default T values, and returns the address of the start 250cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * of that new range. Note: this address is only valid until the next API 251cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * call made on the array that might add or remove elements. 252cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 253cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) T* push_back_n(int n) { 254cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(n >= 0); 255cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) checkRealloc(n); 256cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) for (int i = 0; i < n; ++i) { 257cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) new (fItemArray + fCount + i) T; 258cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 259cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fCount += n; 260cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return fItemArray + fCount - n; 261cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 262cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 263cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 264cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * Removes the last element. Not safe to call when count() == 0. 265cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 266cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void pop_back() { 267cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(fCount > 0); 268cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) --fCount; 269cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fItemArray[fCount].~T(); 270cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) checkRealloc(0); 271cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 272cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 273cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 274cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * Removes the last n elements. Not safe to call when count() < n. 275cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 276cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) void pop_back_n(int n) { 277cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(n >= 0); 278cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(fCount >= n); 279cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) fCount -= n; 280f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) for (int i = 0; i < n; ++i) { 281f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) fItemArray[i].~T(); 282f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 283f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) checkRealloc(0); 284f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 285f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 286f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) /** 287f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) * Pushes or pops from the back to resize. Pushes will be default 288f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) * initialized. 289f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) */ 290f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) void resize_back(int newCount) { 291f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) SkASSERT(newCount >= 0); 292f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 293f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) if (newCount > fCount) { 294f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) push_back_n(newCount - fCount); 295f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } else if (newCount < fCount) { 296f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) pop_back_n(fCount - newCount); 297f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 298cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 299cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 300cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 301cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * Get the i^th element. 302cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 303cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) T& operator[] (int i) { 304cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(i < fCount); 305cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(i >= 0); 306cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return fItemArray[i]; 307cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 308cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 309cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) const T& operator[] (int i) const { 310cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(i < fCount); 311cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(i >= 0); 312cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return fItemArray[i]; 313cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 314cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 315cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 316cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * equivalent to operator[](0) 317cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 318cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) T& front() { SkASSERT(fCount > 0); return fItemArray[0];} 319cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 320cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];} 321cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 322cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 323cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * equivalent to operator[](count() - 1) 324cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 325cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];} 326cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 327cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];} 328cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 329cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) /** 330cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) * equivalent to operator[](count()-1-i) 331cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) */ 332cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) T& fromBack(int i) { 333cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(i >= 0); 334cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(i < fCount); 335cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return fItemArray[fCount - i - 1]; 336cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 337cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 338cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) const T& fromBack(int i) const { 339cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(i >= 0); 340cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(i < fCount); 341cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) return fItemArray[fCount - i - 1]; 342cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) } 343cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 344cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles)private: 345cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 346cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) static const int gMIN_ALLOC_COUNT = 8; 347cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 348cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) inline void checkRealloc(int delta) { 349cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(fCount >= 0); 350cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) SkASSERT(fAllocCount >= 0); 351cedac228d2dd51db4b79ea1e72c7f249408ee061Torne (Richard Coles) 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkASSERT(-delta <= fCount); 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int newCount = fCount + delta; 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int fNewAllocCount = fAllocCount; 356 357 if (newCount > fAllocCount) { 358 fNewAllocCount = SkMax32(newCount + ((newCount + 1) >> 1), 359 fReserveCount); 360 } else if (newCount < fAllocCount / 3) { 361 fNewAllocCount = SkMax32(fAllocCount / 2, fReserveCount); 362 } 363 364 if (fNewAllocCount != fAllocCount) { 365 366 fAllocCount = fNewAllocCount; 367 char* fNewMemArray; 368 369 if (fAllocCount == fReserveCount && NULL != fPreAllocMemArray) { 370 fNewMemArray = (char*) fPreAllocMemArray; 371 } else { 372 fNewMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T)); 373 } 374 375 if (DATA_TYPE) { 376 memcpy(fNewMemArray, fMemArray, fCount * sizeof(T)); 377 } else { 378 for (int i = 0; i < fCount; ++i) { 379 new (fNewMemArray + sizeof(T) * i) T(fItemArray[i]); 380 fItemArray[i].~T(); 381 } 382 } 383 384 if (fMemArray != fPreAllocMemArray) { 385 sk_free(fMemArray); 386 } 387 fMemArray = fNewMemArray; 388 } 389 } 390 391 int fReserveCount; 392 int fCount; 393 int fAllocCount; 394 void* fPreAllocMemArray; 395 union { 396 T* fItemArray; 397 void* fMemArray; 398 }; 399}; 400 401#endif 402 403