1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/include/core/SkTDArray.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,389 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2006 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#ifndef SkTDArray_DEFINED
1.14 +#define SkTDArray_DEFINED
1.15 +
1.16 +#include "SkTypes.h"
1.17 +
1.18 +template <typename T> class SK_API SkTDArray {
1.19 +public:
1.20 + SkTDArray() {
1.21 + fReserve = fCount = 0;
1.22 + fArray = NULL;
1.23 +#ifdef SK_DEBUG
1.24 + fData = NULL;
1.25 +#endif
1.26 + }
1.27 + SkTDArray(const T src[], int count) {
1.28 + SkASSERT(src || count == 0);
1.29 +
1.30 + fReserve = fCount = 0;
1.31 + fArray = NULL;
1.32 +#ifdef SK_DEBUG
1.33 + fData = NULL;
1.34 +#endif
1.35 + if (count) {
1.36 + fArray = (T*)sk_malloc_throw(count * sizeof(T));
1.37 +#ifdef SK_DEBUG
1.38 + fData = (ArrayT*)fArray;
1.39 +#endif
1.40 + memcpy(fArray, src, sizeof(T) * count);
1.41 + fReserve = fCount = count;
1.42 + }
1.43 + }
1.44 + SkTDArray(const SkTDArray<T>& src) {
1.45 + fReserve = fCount = 0;
1.46 + fArray = NULL;
1.47 +#ifdef SK_DEBUG
1.48 + fData = NULL;
1.49 +#endif
1.50 + SkTDArray<T> tmp(src.fArray, src.fCount);
1.51 + this->swap(tmp);
1.52 + }
1.53 + ~SkTDArray() {
1.54 + sk_free(fArray);
1.55 + }
1.56 +
1.57 + SkTDArray<T>& operator=(const SkTDArray<T>& src) {
1.58 + if (this != &src) {
1.59 + if (src.fCount > fReserve) {
1.60 + SkTDArray<T> tmp(src.fArray, src.fCount);
1.61 + this->swap(tmp);
1.62 + } else {
1.63 + memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
1.64 + fCount = src.fCount;
1.65 + }
1.66 + }
1.67 + return *this;
1.68 + }
1.69 +
1.70 + friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
1.71 + return a.fCount == b.fCount &&
1.72 + (a.fCount == 0 ||
1.73 + !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
1.74 + }
1.75 + friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) {
1.76 + return !(a == b);
1.77 + }
1.78 +
1.79 + void swap(SkTDArray<T>& other) {
1.80 + SkTSwap(fArray, other.fArray);
1.81 +#ifdef SK_DEBUG
1.82 + SkTSwap(fData, other.fData);
1.83 +#endif
1.84 + SkTSwap(fReserve, other.fReserve);
1.85 + SkTSwap(fCount, other.fCount);
1.86 + }
1.87 +
1.88 + /** Return a ptr to the array of data, to be freed with sk_free. This also
1.89 + resets the SkTDArray to be empty.
1.90 + */
1.91 + T* detach() {
1.92 + T* array = fArray;
1.93 + fArray = NULL;
1.94 + fReserve = fCount = 0;
1.95 + SkDEBUGCODE(fData = NULL;)
1.96 + return array;
1.97 + }
1.98 +
1.99 + bool isEmpty() const { return fCount == 0; }
1.100 +
1.101 + /**
1.102 + * Return the number of elements in the array
1.103 + */
1.104 + int count() const { return fCount; }
1.105 +
1.106 + /**
1.107 + * Return the total number of elements allocated.
1.108 + * reserved() - count() gives you the number of elements you can add
1.109 + * without causing an allocation.
1.110 + */
1.111 + int reserved() const { return fReserve; }
1.112 +
1.113 + /**
1.114 + * return the number of bytes in the array: count * sizeof(T)
1.115 + */
1.116 + size_t bytes() const { return fCount * sizeof(T); }
1.117 +
1.118 + T* begin() { return fArray; }
1.119 + const T* begin() const { return fArray; }
1.120 + T* end() { return fArray ? fArray + fCount : NULL; }
1.121 + const T* end() const { return fArray ? fArray + fCount : NULL; }
1.122 +
1.123 + T& operator[](int index) {
1.124 + SkASSERT(index < fCount);
1.125 + return fArray[index];
1.126 + }
1.127 + const T& operator[](int index) const {
1.128 + SkASSERT(index < fCount);
1.129 + return fArray[index];
1.130 + }
1.131 +
1.132 + T& getAt(int index) {
1.133 + return (*this)[index];
1.134 + }
1.135 + const T& getAt(int index) const {
1.136 + return (*this)[index];
1.137 + }
1.138 +
1.139 + void reset() {
1.140 + if (fArray) {
1.141 + sk_free(fArray);
1.142 + fArray = NULL;
1.143 +#ifdef SK_DEBUG
1.144 + fData = NULL;
1.145 +#endif
1.146 + fReserve = fCount = 0;
1.147 + } else {
1.148 + SkASSERT(fReserve == 0 && fCount == 0);
1.149 + }
1.150 + }
1.151 +
1.152 + void rewind() {
1.153 + // same as setCount(0)
1.154 + fCount = 0;
1.155 + }
1.156 +
1.157 + /**
1.158 + * Sets the number of elements in the array.
1.159 + * If the array does not have space for count elements, it will increase
1.160 + * the storage allocated to some amount greater than that required.
1.161 + * It will never shrink the shrink the storage.
1.162 + */
1.163 + void setCount(int count) {
1.164 + SkASSERT(count >= 0);
1.165 + if (count > fReserve) {
1.166 + this->resizeStorageToAtLeast(count);
1.167 + }
1.168 + fCount = count;
1.169 + }
1.170 +
1.171 + void setReserve(int reserve) {
1.172 + if (reserve > fReserve) {
1.173 + this->resizeStorageToAtLeast(reserve);
1.174 + }
1.175 + }
1.176 +
1.177 + T* prepend() {
1.178 + this->adjustCount(1);
1.179 + memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
1.180 + return fArray;
1.181 + }
1.182 +
1.183 + T* append() {
1.184 + return this->append(1, NULL);
1.185 + }
1.186 + T* append(int count, const T* src = NULL) {
1.187 + int oldCount = fCount;
1.188 + if (count) {
1.189 + SkASSERT(src == NULL || fArray == NULL ||
1.190 + src + count <= fArray || fArray + oldCount <= src);
1.191 +
1.192 + this->adjustCount(count);
1.193 + if (src) {
1.194 + memcpy(fArray + oldCount, src, sizeof(T) * count);
1.195 + }
1.196 + }
1.197 + return fArray + oldCount;
1.198 + }
1.199 +
1.200 + T* appendClear() {
1.201 + T* result = this->append();
1.202 + *result = 0;
1.203 + return result;
1.204 + }
1.205 +
1.206 + T* insert(int index) {
1.207 + return this->insert(index, 1, NULL);
1.208 + }
1.209 + T* insert(int index, int count, const T* src = NULL) {
1.210 + SkASSERT(count);
1.211 + SkASSERT(index <= fCount);
1.212 + size_t oldCount = fCount;
1.213 + this->adjustCount(count);
1.214 + T* dst = fArray + index;
1.215 + memmove(dst + count, dst, sizeof(T) * (oldCount - index));
1.216 + if (src) {
1.217 + memcpy(dst, src, sizeof(T) * count);
1.218 + }
1.219 + return dst;
1.220 + }
1.221 +
1.222 + void remove(int index, int count = 1) {
1.223 + SkASSERT(index + count <= fCount);
1.224 + fCount = fCount - count;
1.225 + memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
1.226 + }
1.227 +
1.228 + void removeShuffle(int index) {
1.229 + SkASSERT(index < fCount);
1.230 + int newCount = fCount - 1;
1.231 + fCount = newCount;
1.232 + if (index != newCount) {
1.233 + memcpy(fArray + index, fArray + newCount, sizeof(T));
1.234 + }
1.235 + }
1.236 +
1.237 + int find(const T& elem) const {
1.238 + const T* iter = fArray;
1.239 + const T* stop = fArray + fCount;
1.240 +
1.241 + for (; iter < stop; iter++) {
1.242 + if (*iter == elem) {
1.243 + return (int) (iter - fArray);
1.244 + }
1.245 + }
1.246 + return -1;
1.247 + }
1.248 +
1.249 + int rfind(const T& elem) const {
1.250 + const T* iter = fArray + fCount;
1.251 + const T* stop = fArray;
1.252 +
1.253 + while (iter > stop) {
1.254 + if (*--iter == elem) {
1.255 + return SkToInt(iter - stop);
1.256 + }
1.257 + }
1.258 + return -1;
1.259 + }
1.260 +
1.261 + /**
1.262 + * Returns true iff the array contains this element.
1.263 + */
1.264 + bool contains(const T& elem) const {
1.265 + return (this->find(elem) >= 0);
1.266 + }
1.267 +
1.268 + /**
1.269 + * Copies up to max elements into dst. The number of items copied is
1.270 + * capped by count - index. The actual number copied is returned.
1.271 + */
1.272 + int copyRange(T* dst, int index, int max) const {
1.273 + SkASSERT(max >= 0);
1.274 + SkASSERT(!max || dst);
1.275 + if (index >= fCount) {
1.276 + return 0;
1.277 + }
1.278 + int count = SkMin32(max, fCount - index);
1.279 + memcpy(dst, fArray + index, sizeof(T) * count);
1.280 + return count;
1.281 + }
1.282 +
1.283 + void copy(T* dst) const {
1.284 + this->copyRange(dst, 0, fCount);
1.285 + }
1.286 +
1.287 + // routines to treat the array like a stack
1.288 + T* push() { return this->append(); }
1.289 + void push(const T& elem) { *this->append() = elem; }
1.290 + const T& top() const { return (*this)[fCount - 1]; }
1.291 + T& top() { return (*this)[fCount - 1]; }
1.292 + void pop(T* elem) { if (elem) *elem = (*this)[fCount - 1]; --fCount; }
1.293 + void pop() { --fCount; }
1.294 +
1.295 + void deleteAll() {
1.296 + T* iter = fArray;
1.297 + T* stop = fArray + fCount;
1.298 + while (iter < stop) {
1.299 + SkDELETE (*iter);
1.300 + iter += 1;
1.301 + }
1.302 + this->reset();
1.303 + }
1.304 +
1.305 + void freeAll() {
1.306 + T* iter = fArray;
1.307 + T* stop = fArray + fCount;
1.308 + while (iter < stop) {
1.309 + sk_free(*iter);
1.310 + iter += 1;
1.311 + }
1.312 + this->reset();
1.313 + }
1.314 +
1.315 + void unrefAll() {
1.316 + T* iter = fArray;
1.317 + T* stop = fArray + fCount;
1.318 + while (iter < stop) {
1.319 + (*iter)->unref();
1.320 + iter += 1;
1.321 + }
1.322 + this->reset();
1.323 + }
1.324 +
1.325 + void safeUnrefAll() {
1.326 + T* iter = fArray;
1.327 + T* stop = fArray + fCount;
1.328 + while (iter < stop) {
1.329 + SkSafeUnref(*iter);
1.330 + iter += 1;
1.331 + }
1.332 + this->reset();
1.333 + }
1.334 +
1.335 + void visitAll(void visitor(T&)) {
1.336 + T* stop = this->end();
1.337 + for (T* curr = this->begin(); curr < stop; curr++) {
1.338 + if (*curr) {
1.339 + visitor(*curr);
1.340 + }
1.341 + }
1.342 + }
1.343 +
1.344 +#ifdef SK_DEBUG
1.345 + void validate() const {
1.346 + SkASSERT((fReserve == 0 && fArray == NULL) ||
1.347 + (fReserve > 0 && fArray != NULL));
1.348 + SkASSERT(fCount <= fReserve);
1.349 + SkASSERT(fData == (ArrayT*)fArray);
1.350 + }
1.351 +#endif
1.352 +
1.353 +private:
1.354 +#ifdef SK_DEBUG
1.355 + enum {
1.356 + kDebugArraySize = 16
1.357 + };
1.358 + typedef T ArrayT[kDebugArraySize];
1.359 + ArrayT* fData;
1.360 +#endif
1.361 + T* fArray;
1.362 + int fReserve;
1.363 + int fCount;
1.364 +
1.365 + /**
1.366 + * Adjusts the number of elements in the array.
1.367 + * This is the same as calling setCount(count() + delta).
1.368 + */
1.369 + void adjustCount(int delta) {
1.370 + this->setCount(fCount + delta);
1.371 + }
1.372 +
1.373 + /**
1.374 + * Increase the storage allocation such that it can hold (fCount + extra)
1.375 + * elements.
1.376 + * It never shrinks the allocation, and it may increase the allocation by
1.377 + * more than is strictly required, based on a private growth heuristic.
1.378 + *
1.379 + * note: does NOT modify fCount
1.380 + */
1.381 + void resizeStorageToAtLeast(int count) {
1.382 + SkASSERT(count > fReserve);
1.383 + fReserve = count + 4;
1.384 + fReserve += fReserve / 4;
1.385 + fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
1.386 +#ifdef SK_DEBUG
1.387 + fData = (ArrayT*)fArray;
1.388 +#endif
1.389 + }
1.390 +};
1.391 +
1.392 +#endif
