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 15db5f7bf0a439b744facda6b6b1590b4554d64fd8ehsan.akhgaritemplate <typename T> class 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 } 24e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com SkTDArray(const T src[], int 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 } 723467ee06d31798b2673364ef4f7abd83619b21ddreed@google.com friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) { 733467ee06d31798b2673364ef4f7abd83619b21ddreed@google.com return !(a == b); 743467ee06d31798b2673364ef4f7abd83619b21ddreed@google.com } 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void swap(SkTDArray<T>& other) { 778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap(fArray, other.fArray); 788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap(fData, other.fData); 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap(fReserve, other.fReserve); 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTSwap(fCount, other.fCount); 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 850da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com /** Return a ptr to the array of data, to be freed with sk_free. This also 860da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com resets the SkTDArray to be empty. 870da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com */ 880da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com T* detach() { 890da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com T* array = fArray; 900da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com fArray = NULL; 910da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com fReserve = fCount = 0; 920da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com SkDEBUGCODE(fData = NULL;) 930da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com return array; 940da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com } 950da41dbf5bdf9614a3d2f1d3ebd959221bbac44breed@android.com 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool isEmpty() const { return fCount == 0; } 971271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com 981271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com /** 991271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com * Return the number of elements in the array 1001271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com */ 101e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com int count() const { return fCount; } 1021271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com 1031271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com /** 104046f1f6ff4b2b3f4571a9562e74f41e82419a4a1commit-bot@chromium.org * Return the total number of elements allocated. 105046f1f6ff4b2b3f4571a9562e74f41e82419a4a1commit-bot@chromium.org * reserved() - count() gives you the number of elements you can add 106046f1f6ff4b2b3f4571a9562e74f41e82419a4a1commit-bot@chromium.org * without causing an allocation. 107046f1f6ff4b2b3f4571a9562e74f41e82419a4a1commit-bot@chromium.org */ 108046f1f6ff4b2b3f4571a9562e74f41e82419a4a1commit-bot@chromium.org int reserved() const { return fReserve; } 109046f1f6ff4b2b3f4571a9562e74f41e82419a4a1commit-bot@chromium.org 110046f1f6ff4b2b3f4571a9562e74f41e82419a4a1commit-bot@chromium.org /** 1111271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com * return the number of bytes in the array: count * sizeof(T) 1121271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com */ 1131271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com size_t bytes() const { return fCount * sizeof(T); } 1141271d78e8ff4cda0622a24dcec6063b50f6be051reed@google.com 115aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org T* begin() { return fArray; } 116aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org const T* begin() const { return fArray; } 117aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org T* end() { return fArray ? fArray + fCount : NULL; } 118aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org const T* end() const { return fArray ? fArray + fCount : NULL; } 119aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org 120aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org T& operator[](int index) { 121e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com SkASSERT(index < fCount); 122aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org return fArray[index]; 123aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org } 124aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org const T& operator[](int index) const { 125e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com SkASSERT(index < fCount); 1268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fArray[index]; 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1287fc0e0a75a99ac5ea2e5d03ab3a00cacabacfa09skia.committer@gmail.com 129aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org T& getAt(int index) { 130aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org return (*this)[index]; 131aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org } 132aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org const T& getAt(int index) const { 1337af56bee17764a0c118c8856a035bb3d27766969humper@google.com return (*this)[index]; 1347af56bee17764a0c118c8856a035bb3d27766969humper@google.com } 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void reset() { 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fArray) { 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_free(fArray); 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fArray = NULL; 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 1418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fData = NULL; 1428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fReserve = fCount = 0; 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fReserve == 0 && fCount == 0); 1468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 148fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void rewind() { 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // same as setCount(0) 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount = 0; 1528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 154a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org /** 155a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * Sets the number of elements in the array. 156a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * If the array does not have space for count elements, it will increase 157a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * the storage allocated to some amount greater than that required. 158a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * It will never shrink the shrink the storage. 159a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org */ 160e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com void setCount(int count) { 161a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org SkASSERT(count >= 0); 1628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count > fReserve) { 163a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org this->resizeStorageToAtLeast(count); 16493d5ffda58391fe819199bf5afddc622e067af7ecommit-bot@chromium.org } 165a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org fCount = count; 166a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org } 167a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org 168e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com void setReserve(int reserve) { 1698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (reserve > fReserve) { 170a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org this->resizeStorageToAtLeast(reserve); 1718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* prepend() { 175a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org this->adjustCount(1); 1768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T)); 1778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fArray; 1788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* append() { 1818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->append(1, NULL); 1828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 183e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com T* append(int count, const T* src = NULL) { 184e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com int oldCount = fCount; 1858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count) { 1868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(src == NULL || fArray == NULL || 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com src + count <= fArray || fArray + oldCount <= src); 1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 189a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org this->adjustCount(count); 1908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (src) { 1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(fArray + oldCount, src, sizeof(T) * count); 1928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return fArray + oldCount; 1958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 196fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* appendClear() { 198fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com T* result = this->append(); 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *result = 0; 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return result; 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 203e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com T* insert(int index) { 2048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->insert(index, 1, NULL); 2058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 206e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com T* insert(int index, int count, const T* src = NULL) { 2078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(count); 2088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(index <= fCount); 209ffe39bd3b66eb5090684959e7f2409346ab72d93tomhudson@google.com size_t oldCount = fCount; 210a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org this->adjustCount(count); 2118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* dst = fArray + index; 2128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memmove(dst + count, dst, sizeof(T) * (oldCount - index)); 2138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (src) { 2148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(dst, src, sizeof(T) * count); 2158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return dst; 2178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 219e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com void remove(int index, int count = 1) { 2208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(index + count <= fCount); 2218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount = fCount - count; 2228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index)); 2238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 225e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com void removeShuffle(int index) { 2268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(index < fCount); 227e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com int newCount = fCount - 1; 2288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCount = newCount; 2298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (index != newCount) { 2308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(fArray + index, fArray + newCount, sizeof(T)); 2318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int find(const T& elem) const { 2358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const T* iter = fArray; 2368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const T* stop = fArray + fCount; 2378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (; iter < stop; iter++) { 2398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (*iter == elem) { 2408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (int) (iter - fArray); 2418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return -1; 2448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int rfind(const T& elem) const { 2478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const T* iter = fArray + fCount; 2488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const T* stop = fArray; 2498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (iter > stop) { 2518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (*--iter == elem) { 2526fcd28ba1de83b72f4c8343ccec27d26c127de32reed@google.com return SkToInt(iter - stop); 2538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return -1; 2568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 258df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com /** 259af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com * Returns true iff the array contains this element. 260af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com */ 261af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com bool contains(const T& elem) const { 262af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com return (this->find(elem) >= 0); 263af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com } 264af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com 265af07d065d19ec387b783b6dfdc3deafd7c614b69epoger@google.com /** 266df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com * Copies up to max elements into dst. The number of items copied is 267df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com * capped by count - index. The actual number copied is returned. 268df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com */ 269e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com int copyRange(T* dst, int index, int max) const { 270df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com SkASSERT(max >= 0); 271df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com SkASSERT(!max || dst); 272df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com if (index >= fCount) { 273df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com return 0; 274df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com } 275df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com int count = SkMin32(max, fCount - index); 276df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com memcpy(dst, fArray + index, sizeof(T) * count); 277df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com return count; 278df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com } 279df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com 280df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com void copy(T* dst) const { 281c6081abd2f28d2179ad8e3bef557cb0d00fffe01zachr@google.com this->copyRange(dst, 0, fCount); 282df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com } 283df9d656c352928f995abce0a62c4ec3255232a45bsalomon@google.com 2848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // routines to treat the array like a stack 285aa90d00f14414db39b3d990d8d5fd594d6eadc6emtklein T* push() { return this->append(); } 286aa90d00f14414db39b3d990d8d5fd594d6eadc6emtklein void push(const T& elem) { *this->append() = elem; } 287aa90d00f14414db39b3d990d8d5fd594d6eadc6emtklein const T& top() const { return (*this)[fCount - 1]; } 288aa90d00f14414db39b3d990d8d5fd594d6eadc6emtklein T& top() { return (*this)[fCount - 1]; } 289aa90d00f14414db39b3d990d8d5fd594d6eadc6emtklein void pop(T* elem) { SkASSERT(fCount > 0); if (elem) *elem = (*this)[fCount - 1]; --fCount; } 290aa90d00f14414db39b3d990d8d5fd594d6eadc6emtklein void pop() { SkASSERT(fCount > 0); --fCount; } 2918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void deleteAll() { 2938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* iter = fArray; 2948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* stop = fArray + fCount; 2958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (iter < stop) { 296c51db02181982fbcb8888e2a89132363a7d9371cscroggo SkDELETE (*iter); 2978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com iter += 1; 2988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->reset(); 3008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void freeAll() { 3038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* iter = fArray; 3048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* stop = fArray + fCount; 3058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (iter < stop) { 3068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_free(*iter); 3078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com iter += 1; 3088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->reset(); 3108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void unrefAll() { 3138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* iter = fArray; 3148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* stop = fArray + fCount; 3158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (iter < stop) { 3168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (*iter)->unref(); 3178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com iter += 1; 3188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->reset(); 3208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3218433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com 3228433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com void safeUnrefAll() { 3238433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com T* iter = fArray; 3248433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com T* stop = fArray + fCount; 3258433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com while (iter < stop) { 3268433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com SkSafeUnref(*iter); 3278433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com iter += 1; 3288433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com } 3298433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com this->reset(); 3308433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com } 3318433b5db1a0f94cd92d2606817d5374ab899b87areed@android.com 332aa537d4bdb2384cdcd0644a02a2ab7fb0ecdd3b3commit-bot@chromium.org void visitAll(void visitor(T&)) { 33321cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com T* stop = this->end(); 33421cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com for (T* curr = this->begin(); curr < stop; curr++) { 33521cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com if (*curr) { 33621cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com visitor(*curr); 33721cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com } 33821cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com } 33921cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com } 34021cbec4870660f776f470e3a5e327599b6433dd2bsalomon@google.com 3418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 3428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void validate() const { 3438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((fReserve == 0 && fArray == NULL) || 3448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com (fReserve > 0 && fArray != NULL)); 3458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCount <= fReserve); 3468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fData == (ArrayT*)fArray); 3478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 3498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comprivate: 3518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 3528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com enum { 3538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kDebugArraySize = 16 3548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 3558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com typedef T ArrayT[kDebugArraySize]; 3568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ArrayT* fData; 3578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 3588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com T* fArray; 359e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com int fReserve; 360e9cd27d4a3c92393cc6c79d4d6f93d266411d95erobertphillips@google.com int fCount; 3618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 362a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org /** 363a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * Adjusts the number of elements in the array. 364a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * This is the same as calling setCount(count() + delta). 365a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org */ 366a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org void adjustCount(int delta) { 367a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org this->setCount(fCount + delta); 368a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org } 36909f0ba7eb3c1933c7be878a043de5c287edd00abcommit-bot@chromium.org 370a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org /** 371a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * Increase the storage allocation such that it can hold (fCount + extra) 372a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * elements. 373a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * It never shrinks the allocation, and it may increase the allocation by 374a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * more than is strictly required, based on a private growth heuristic. 375a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * 376a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org * note: does NOT modify fCount 377a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org */ 378a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org void resizeStorageToAtLeast(int count) { 379a87b21cd0041bac0d96b6836ac6e71a2dbcd4e10commit-bot@chromium.org SkASSERT(count > fReserve); 380ca21a00c736d05686c84ab874ce6a49008da6a76commit-bot@chromium.org fReserve = count + 4; 381ca21a00c736d05686c84ab874ce6a49008da6a76commit-bot@chromium.org fReserve += fReserve / 4; 382ca21a00c736d05686c84ab874ce6a49008da6a76commit-bot@chromium.org fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T)); 383ca21a00c736d05686c84ab874ce6a49008da6a76commit-bot@chromium.org#ifdef SK_DEBUG 384ca21a00c736d05686c84ab874ce6a49008da6a76commit-bot@chromium.org fData = (ArrayT*)fArray; 385ca21a00c736d05686c84ab874ce6a49008da6a76commit-bot@chromium.org#endif 3868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 3888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 390