SkTDArray.h revision 7af56bee17764a0c118c8856a035bb3d27766969
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 28a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 48a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.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. 78a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifndef SkTDArray_DEFINED 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define SkTDArray_DEFINED 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkTypes.h" 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 157ffb1b21abcc7bbed5a0fc711f6dd7b9dbb4f577ctguil@chromium.orgtemplate <typename T> class SK_API SkTDArray { 168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.compublic: 178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTDArray() { 188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fReserve = fCount = 0; 198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fArray = NULL; 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fData = NULL; 228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTDArray(const T src[], size_t count) { 258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src || count == 0); 268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fReserve = fCount = 0; 288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fArray = NULL; 298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fData = NULL; 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count) { 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fArray = (T*)sk_malloc_throw(count * sizeof(T)); 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fData = (ArrayT*)fArray; 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(fArray, src, sizeof(T) * count); 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fReserve = fCount = count; 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTDArray(const SkTDArray<T>& src) { 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fReserve = fCount = 0; 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fArray = NULL; 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fData = NULL; 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTDArray<T> tmp(src.fArray, src.fCount); 488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->swap(tmp); 498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ~SkTDArray() { 518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_free(fArray); 528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTDArray<T>& operator=(const SkTDArray<T>& src) { 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (this != &src) { 568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (src.fCount > fReserve) { 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTDArray<T> tmp(src.fArray, src.fCount); 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->swap(tmp); 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(fArray, src.fArray, sizeof(T) * src.fCount); 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount = src.fCount; 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return *this; 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 67b530ef5869c5c64af8f3b3c62ed7711fe4325c9creed@google.com friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) { 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return a.fCount == b.fCount && 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (a.fCount == 0 || 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T))); 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void swap(SkTDArray<T>& other) { 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap(fArray, other.fArray); 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap(fData, other.fData); 778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap(fReserve, other.fReserve); 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap(fCount, other.fCount); 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 820da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com /** Return a ptr to the array of data, to be freed with sk_free. This also 830da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com resets the SkTDArray to be empty. 840da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com */ 850da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com T* detach() { 860da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com T* array = fArray; 870da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com fArray = NULL; 880da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com fReserve = fCount = 0; 890da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com SkDEBUGCODE(fData = NULL;) 900da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com return array; 910da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com } 920da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool isEmpty() const { return fCount == 0; } 941271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com 951271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com /** 961271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com * Return the number of elements in the array 971271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com */ 98b158a82bc18b5535224e3ca315ee6d80c7ad899breed@google.com int count() const { return (int)fCount; } 991271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com 1001271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com /** 1011271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com * return the number of bytes in the array: count * sizeof(T) 1021271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com */ 1031271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com size_t bytes() const { return fCount * sizeof(T); } 1041271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* begin() const { return fArray; } 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* end() const { return fArray ? fArray + fCount : NULL; } 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T& operator[](int index) const { 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((unsigned)index < fCount); 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fArray[index]; 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1117af56bee17764a0c118c8856a035bb3d27766969humper@google.com 1127af56bee17764a0c118c8856a035bb3d27766969humper@google.com T& getAt(int index) const { 1137af56bee17764a0c118c8856a035bb3d27766969humper@google.com return (*this)[index]; 1147af56bee17764a0c118c8856a035bb3d27766969humper@google.com } 1158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void reset() { 1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fArray) { 1188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_free(fArray); 1198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fArray = NULL; 1208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 1218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fData = NULL; 1228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fReserve = fCount = 0; 1248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fReserve == 0 && fCount == 0); 1268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 128fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 1298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void rewind() { 1308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // same as setCount(0) 1318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount = 0; 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void setCount(size_t count) { 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count > fReserve) { 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->growBy(count - fCount); 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount = count; 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void setReserve(size_t reserve) { 1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (reserve > fReserve) { 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(reserve > fCount); 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t count = fCount; 1468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->growBy(reserve - fCount); 1478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount = count; 1488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* prepend() { 1528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->growBy(1); 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T)); 1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fArray; 1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* append() { 1588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->append(1, NULL); 1598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* append(size_t count, const T* src = NULL) { 161ffe39bd3b66eb5090684959e7f2409346ab72d93tomhudson@google.com size_t oldCount = fCount; 1628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count) { 1638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src == NULL || fArray == NULL || 1648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com src + count <= fArray || fArray + oldCount <= src); 1658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->growBy(count); 1678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (src) { 1688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(fArray + oldCount, src, sizeof(T) * count); 1698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fArray + oldCount; 1728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 173fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 1748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* appendClear() { 175fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com T* result = this->append(); 1768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *result = 0; 1778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return result; 1788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* insert(size_t index) { 1818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->insert(index, 1, NULL); 1828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* insert(size_t index, size_t count, const T* src = NULL) { 1848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(count); 1858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(index <= fCount); 186ffe39bd3b66eb5090684959e7f2409346ab72d93tomhudson@google.com size_t oldCount = fCount; 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->growBy(count); 1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* dst = fArray + index; 1898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memmove(dst + count, dst, sizeof(T) * (oldCount - index)); 1908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (src) { 1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, sizeof(T) * count); 1928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return dst; 1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void remove(size_t index, size_t count = 1) { 1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(index + count <= fCount); 1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount = fCount - count; 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index)); 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void removeShuffle(size_t index) { 2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(index < fCount); 204ffe39bd3b66eb5090684959e7f2409346ab72d93tomhudson@google.com size_t newCount = fCount - 1; 2058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount = newCount; 2068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (index != newCount) { 2078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(fArray + index, fArray + newCount, sizeof(T)); 2088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int find(const T& elem) const { 2128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const T* iter = fArray; 2138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const T* stop = fArray + fCount; 2148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (; iter < stop; iter++) { 2168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (*iter == elem) { 2178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (int) (iter - fArray); 2188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return -1; 2218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int rfind(const T& elem) const { 2248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const T* iter = fArray + fCount; 2258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const T* stop = fArray; 2268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (iter > stop) { 2288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (*--iter == elem) { 2298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return iter - stop; 2308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return -1; 2338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 235df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com /** 236af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com * Returns true iff the array contains this element. 237af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com */ 238af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com bool contains(const T& elem) const { 239af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com return (this->find(elem) >= 0); 240af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com } 241af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com 242af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com /** 243df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com * Copies up to max elements into dst. The number of items copied is 244df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com * capped by count - index. The actual number copied is returned. 245df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com */ 246df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com int copyRange(T* dst, size_t index, int max) const { 247df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com SkASSERT(max >= 0); 248df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com SkASSERT(!max || dst); 249df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com if (index >= fCount) { 250df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com return 0; 251df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com } 252df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com int count = SkMin32(max, fCount - index); 253df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com memcpy(dst, fArray + index, sizeof(T) * count); 254df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com return count; 255df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com } 256df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com 257df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com void copy(T* dst) const { 258df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com this->copyRange(0, fCount, dst); 259df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com } 260df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com 2618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // routines to treat the array like a stack 2628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* push() { return this->append(); } 2638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void push(const T& elem) { *this->append() = elem; } 2648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const T& top() const { return (*this)[fCount - 1]; } 2658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T& top() { return (*this)[fCount - 1]; } 2668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void pop(T* elem) { if (elem) *elem = (*this)[fCount - 1]; --fCount; } 2678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void pop() { --fCount; } 2688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void deleteAll() { 2708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* iter = fArray; 2718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* stop = fArray + fCount; 2728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (iter < stop) { 273c51db02181982fbcb8888e2a89132363a7d9371cscroggo SkDELETE (*iter); 2748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com iter += 1; 2758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->reset(); 2778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void freeAll() { 2808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* iter = fArray; 2818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* stop = fArray + fCount; 2828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (iter < stop) { 2838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_free(*iter); 2848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com iter += 1; 2858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->reset(); 2878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void unrefAll() { 2908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* iter = fArray; 2918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* stop = fArray + fCount; 2928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (iter < stop) { 2938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (*iter)->unref(); 2948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com iter += 1; 2958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->reset(); 2978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2988433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com 2998433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com void safeUnrefAll() { 3008433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com T* iter = fArray; 3018433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com T* stop = fArray + fCount; 3028433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com while (iter < stop) { 3038433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com SkSafeUnref(*iter); 3048433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com iter += 1; 3058433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com } 3068433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com this->reset(); 3078433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com } 3088433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com 30921cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com void visitAll(void visitor(T&)) const { 31021cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com T* stop = this->end(); 31121cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com for (T* curr = this->begin(); curr < stop; curr++) { 31221cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com if (*curr) { 31321cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com visitor(*curr); 31421cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com } 31521cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com } 31621cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com } 31721cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com 3188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 3198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void validate() const { 3208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((fReserve == 0 && fArray == NULL) || 3218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (fReserve > 0 && fArray != NULL)); 3228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCount <= fReserve); 3238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fData == (ArrayT*)fArray); 3248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 3268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comprivate: 3288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 3298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com enum { 3308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kDebugArraySize = 16 3318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 3328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com typedef T ArrayT[kDebugArraySize]; 3338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ArrayT* fData; 3348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 3358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* fArray; 3368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t fReserve, fCount; 3378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void growBy(size_t extra) { 3398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(extra); 3408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fCount + extra > fReserve) { 3428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t size = fCount + extra + 4; 3438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size += size >> 2; 3448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fArray = (T*)sk_realloc_throw(fArray, size * sizeof(T)); 3468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 3478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fData = (ArrayT*)fArray; 3488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 3498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fReserve = size; 3508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount += extra; 3528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 3548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 356