1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/include/core/SkTArray.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,510 @@
1.4 +/*
1.5 + * Copyright 2011 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#ifndef SkTArray_DEFINED
1.12 +#define SkTArray_DEFINED
1.13 +
1.14 +#include <new>
1.15 +#include "SkTypes.h"
1.16 +#include "SkTemplates.h"
1.17 +
1.18 +template <typename T, bool MEM_COPY = false> class SkTArray;
1.19 +
1.20 +namespace SkTArrayExt {
1.21 +
1.22 +template<typename T>
1.23 +inline void copy(SkTArray<T, true>* self, const T* array) {
1.24 + memcpy(self->fMemArray, array, self->fCount * sizeof(T));
1.25 +}
1.26 +template<typename T>
1.27 +inline void copyAndDelete(SkTArray<T, true>* self, char* newMemArray) {
1.28 + memcpy(newMemArray, self->fMemArray, self->fCount * sizeof(T));
1.29 +}
1.30 +
1.31 +template<typename T>
1.32 +inline void copy(SkTArray<T, false>* self, const T* array) {
1.33 + for (int i = 0; i < self->fCount; ++i) {
1.34 + SkNEW_PLACEMENT_ARGS(self->fItemArray + i, T, (array[i]));
1.35 + }
1.36 +}
1.37 +template<typename T>
1.38 +inline void copyAndDelete(SkTArray<T, false>* self, char* newMemArray) {
1.39 + for (int i = 0; i < self->fCount; ++i) {
1.40 + SkNEW_PLACEMENT_ARGS(newMemArray + sizeof(T) * i, T, (self->fItemArray[i]));
1.41 + self->fItemArray[i].~T();
1.42 + }
1.43 +}
1.44 +
1.45 +}
1.46 +
1.47 +template <typename T, bool MEM_COPY> void* operator new(size_t, SkTArray<T, MEM_COPY>*, int);
1.48 +
1.49 +/** When MEM_COPY is true T will be bit copied when moved.
1.50 + When MEM_COPY is false, T will be copy constructed / destructed.
1.51 + In all cases T's constructor will be called on allocation,
1.52 + and its destructor will be called from this object's destructor.
1.53 +*/
1.54 +template <typename T, bool MEM_COPY> class SkTArray {
1.55 +public:
1.56 + /**
1.57 + * Creates an empty array with no initial storage
1.58 + */
1.59 + SkTArray() {
1.60 + fCount = 0;
1.61 + fReserveCount = gMIN_ALLOC_COUNT;
1.62 + fAllocCount = 0;
1.63 + fMemArray = NULL;
1.64 + fPreAllocMemArray = NULL;
1.65 + }
1.66 +
1.67 + /**
1.68 + * Creates an empty array that will preallocate space for reserveCount
1.69 + * elements.
1.70 + */
1.71 + explicit SkTArray(int reserveCount) {
1.72 + this->init(NULL, 0, NULL, reserveCount);
1.73 + }
1.74 +
1.75 + /**
1.76 + * Copies one array to another. The new array will be heap allocated.
1.77 + */
1.78 + explicit SkTArray(const SkTArray& array) {
1.79 + this->init(array.fItemArray, array.fCount, NULL, 0);
1.80 + }
1.81 +
1.82 + /**
1.83 + * Creates a SkTArray by copying contents of a standard C array. The new
1.84 + * array will be heap allocated. Be careful not to use this constructor
1.85 + * when you really want the (void*, int) version.
1.86 + */
1.87 + SkTArray(const T* array, int count) {
1.88 + this->init(array, count, NULL, 0);
1.89 + }
1.90 +
1.91 + /**
1.92 + * assign copy of array to this
1.93 + */
1.94 + SkTArray& operator =(const SkTArray& array) {
1.95 + for (int i = 0; i < fCount; ++i) {
1.96 + fItemArray[i].~T();
1.97 + }
1.98 + fCount = 0;
1.99 + this->checkRealloc((int)array.count());
1.100 + fCount = array.count();
1.101 + SkTArrayExt::copy(this, static_cast<const T*>(array.fMemArray));
1.102 + return *this;
1.103 + }
1.104 +
1.105 + virtual ~SkTArray() {
1.106 + for (int i = 0; i < fCount; ++i) {
1.107 + fItemArray[i].~T();
1.108 + }
1.109 + if (fMemArray != fPreAllocMemArray) {
1.110 + sk_free(fMemArray);
1.111 + }
1.112 + }
1.113 +
1.114 + /**
1.115 + * Resets to count() == 0
1.116 + */
1.117 + void reset() { this->pop_back_n(fCount); }
1.118 +
1.119 + /**
1.120 + * Resets to count() = n newly constructed T objects.
1.121 + */
1.122 + void reset(int n) {
1.123 + SkASSERT(n >= 0);
1.124 + for (int i = 0; i < fCount; ++i) {
1.125 + fItemArray[i].~T();
1.126 + }
1.127 + // set fCount to 0 before calling checkRealloc so that no copy cons. are called.
1.128 + fCount = 0;
1.129 + this->checkRealloc(n);
1.130 + fCount = n;
1.131 + for (int i = 0; i < fCount; ++i) {
1.132 + SkNEW_PLACEMENT(fItemArray + i, T);
1.133 + }
1.134 + }
1.135 +
1.136 + /**
1.137 + * Resets to a copy of a C array.
1.138 + */
1.139 + void reset(const T* array, int count) {
1.140 + for (int i = 0; i < fCount; ++i) {
1.141 + fItemArray[i].~T();
1.142 + }
1.143 + int delta = count - fCount;
1.144 + this->checkRealloc(delta);
1.145 + fCount = count;
1.146 + for (int i = 0; i < count; ++i) {
1.147 + SkTArrayExt::copy(this, array);
1.148 + }
1.149 + }
1.150 +
1.151 + /**
1.152 + * Number of elements in the array.
1.153 + */
1.154 + int count() const { return fCount; }
1.155 +
1.156 + /**
1.157 + * Is the array empty.
1.158 + */
1.159 + bool empty() const { return !fCount; }
1.160 +
1.161 + /**
1.162 + * Adds 1 new default-constructed T value and returns in by reference. Note
1.163 + * the reference only remains valid until the next call that adds or removes
1.164 + * elements.
1.165 + */
1.166 + T& push_back() {
1.167 + T* newT = reinterpret_cast<T*>(this->push_back_raw(1));
1.168 + SkNEW_PLACEMENT(newT, T);
1.169 + return *newT;
1.170 + }
1.171 +
1.172 + /**
1.173 + * Version of above that uses a copy constructor to initialize the new item
1.174 + */
1.175 + T& push_back(const T& t) {
1.176 + T* newT = reinterpret_cast<T*>(this->push_back_raw(1));
1.177 + SkNEW_PLACEMENT_ARGS(newT, T, (t));
1.178 + return *newT;
1.179 + }
1.180 +
1.181 + /**
1.182 + * Allocates n more default T values, and returns the address of the start
1.183 + * of that new range. Note: this address is only valid until the next API
1.184 + * call made on the array that might add or remove elements.
1.185 + */
1.186 + T* push_back_n(int n) {
1.187 + SkASSERT(n >= 0);
1.188 + T* newTs = reinterpret_cast<T*>(this->push_back_raw(n));
1.189 + for (int i = 0; i < n; ++i) {
1.190 + SkNEW_PLACEMENT(newTs + i, T);
1.191 + }
1.192 + return newTs;
1.193 + }
1.194 +
1.195 + /**
1.196 + * Version of above that uses a copy constructor to initialize all n items
1.197 + * to the same T.
1.198 + */
1.199 + T* push_back_n(int n, const T& t) {
1.200 + SkASSERT(n >= 0);
1.201 + T* newTs = reinterpret_cast<T*>(this->push_back_raw(n));
1.202 + for (int i = 0; i < n; ++i) {
1.203 + SkNEW_PLACEMENT_ARGS(newTs[i], T, (t));
1.204 + }
1.205 + return newTs;
1.206 + }
1.207 +
1.208 + /**
1.209 + * Version of above that uses a copy constructor to initialize the n items
1.210 + * to separate T values.
1.211 + */
1.212 + T* push_back_n(int n, const T t[]) {
1.213 + SkASSERT(n >= 0);
1.214 + this->checkRealloc(n);
1.215 + for (int i = 0; i < n; ++i) {
1.216 + SkNEW_PLACEMENT_ARGS(fItemArray + fCount + i, T, (t[i]));
1.217 + }
1.218 + fCount += n;
1.219 + return fItemArray + fCount - n;
1.220 + }
1.221 +
1.222 + /**
1.223 + * Removes the last element. Not safe to call when count() == 0.
1.224 + */
1.225 + void pop_back() {
1.226 + SkASSERT(fCount > 0);
1.227 + --fCount;
1.228 + fItemArray[fCount].~T();
1.229 + this->checkRealloc(0);
1.230 + }
1.231 +
1.232 + /**
1.233 + * Removes the last n elements. Not safe to call when count() < n.
1.234 + */
1.235 + void pop_back_n(int n) {
1.236 + SkASSERT(n >= 0);
1.237 + SkASSERT(fCount >= n);
1.238 + fCount -= n;
1.239 + for (int i = 0; i < n; ++i) {
1.240 + fItemArray[fCount + i].~T();
1.241 + }
1.242 + this->checkRealloc(0);
1.243 + }
1.244 +
1.245 + /**
1.246 + * Pushes or pops from the back to resize. Pushes will be default
1.247 + * initialized.
1.248 + */
1.249 + void resize_back(int newCount) {
1.250 + SkASSERT(newCount >= 0);
1.251 +
1.252 + if (newCount > fCount) {
1.253 + this->push_back_n(newCount - fCount);
1.254 + } else if (newCount < fCount) {
1.255 + this->pop_back_n(fCount - newCount);
1.256 + }
1.257 + }
1.258 +
1.259 + T* begin() {
1.260 + return fItemArray;
1.261 + }
1.262 + const T* begin() const {
1.263 + return fItemArray;
1.264 + }
1.265 + T* end() {
1.266 + return fItemArray ? fItemArray + fCount : NULL;
1.267 + }
1.268 + const T* end() const {
1.269 + return fItemArray ? fItemArray + fCount : NULL;;
1.270 + }
1.271 +
1.272 + /**
1.273 + * Get the i^th element.
1.274 + */
1.275 + T& operator[] (int i) {
1.276 + SkASSERT(i < fCount);
1.277 + SkASSERT(i >= 0);
1.278 + return fItemArray[i];
1.279 + }
1.280 +
1.281 + const T& operator[] (int i) const {
1.282 + SkASSERT(i < fCount);
1.283 + SkASSERT(i >= 0);
1.284 + return fItemArray[i];
1.285 + }
1.286 +
1.287 + /**
1.288 + * equivalent to operator[](0)
1.289 + */
1.290 + T& front() { SkASSERT(fCount > 0); return fItemArray[0];}
1.291 +
1.292 + const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];}
1.293 +
1.294 + /**
1.295 + * equivalent to operator[](count() - 1)
1.296 + */
1.297 + T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];}
1.298 +
1.299 + const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];}
1.300 +
1.301 + /**
1.302 + * equivalent to operator[](count()-1-i)
1.303 + */
1.304 + T& fromBack(int i) {
1.305 + SkASSERT(i >= 0);
1.306 + SkASSERT(i < fCount);
1.307 + return fItemArray[fCount - i - 1];
1.308 + }
1.309 +
1.310 + const T& fromBack(int i) const {
1.311 + SkASSERT(i >= 0);
1.312 + SkASSERT(i < fCount);
1.313 + return fItemArray[fCount - i - 1];
1.314 + }
1.315 +
1.316 + bool operator==(const SkTArray<T, MEM_COPY>& right) const {
1.317 + int leftCount = this->count();
1.318 + if (leftCount != right.count()) {
1.319 + return false;
1.320 + }
1.321 + for (int index = 0; index < leftCount; ++index) {
1.322 + if (fItemArray[index] != right.fItemArray[index]) {
1.323 + return false;
1.324 + }
1.325 + }
1.326 + return true;
1.327 + }
1.328 +
1.329 + bool operator!=(const SkTArray<T, MEM_COPY>& right) const {
1.330 + return !(*this == right);
1.331 + }
1.332 +
1.333 +protected:
1.334 + /**
1.335 + * Creates an empty array that will use the passed storage block until it
1.336 + * is insufficiently large to hold the entire array.
1.337 + */
1.338 + template <int N>
1.339 + SkTArray(SkAlignedSTStorage<N,T>* storage) {
1.340 + this->init(NULL, 0, storage->get(), N);
1.341 + }
1.342 +
1.343 + /**
1.344 + * Copy another array, using preallocated storage if preAllocCount >=
1.345 + * array.count(). Otherwise storage will only be used when array shrinks
1.346 + * to fit.
1.347 + */
1.348 + template <int N>
1.349 + SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) {
1.350 + this->init(array.fItemArray, array.fCount, storage->get(), N);
1.351 + }
1.352 +
1.353 + /**
1.354 + * Copy a C array, using preallocated storage if preAllocCount >=
1.355 + * count. Otherwise storage will only be used when array shrinks
1.356 + * to fit.
1.357 + */
1.358 + template <int N>
1.359 + SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) {
1.360 + this->init(array, count, storage->get(), N);
1.361 + }
1.362 +
1.363 + void init(const T* array, int count,
1.364 + void* preAllocStorage, int preAllocOrReserveCount) {
1.365 + SkASSERT(count >= 0);
1.366 + SkASSERT(preAllocOrReserveCount >= 0);
1.367 + fCount = count;
1.368 + fReserveCount = (preAllocOrReserveCount > 0) ?
1.369 + preAllocOrReserveCount :
1.370 + gMIN_ALLOC_COUNT;
1.371 + fPreAllocMemArray = preAllocStorage;
1.372 + if (fReserveCount >= fCount &&
1.373 + NULL != preAllocStorage) {
1.374 + fAllocCount = fReserveCount;
1.375 + fMemArray = preAllocStorage;
1.376 + } else {
1.377 + fAllocCount = SkMax32(fCount, fReserveCount);
1.378 + fMemArray = sk_malloc_throw(fAllocCount * sizeof(T));
1.379 + }
1.380 +
1.381 + SkTArrayExt::copy(this, array);
1.382 + }
1.383 +
1.384 +private:
1.385 +
1.386 + static const int gMIN_ALLOC_COUNT = 8;
1.387 +
1.388 + // Helper function that makes space for n objects, adjusts the count, but does not initialize
1.389 + // the new objects.
1.390 + void* push_back_raw(int n) {
1.391 + this->checkRealloc(n);
1.392 + void* ptr = fItemArray + fCount;
1.393 + fCount += n;
1.394 + return ptr;
1.395 + }
1.396 +
1.397 + inline void checkRealloc(int delta) {
1.398 + SkASSERT(fCount >= 0);
1.399 + SkASSERT(fAllocCount >= 0);
1.400 +
1.401 + SkASSERT(-delta <= fCount);
1.402 +
1.403 + int newCount = fCount + delta;
1.404 + int newAllocCount = fAllocCount;
1.405 +
1.406 + if (newCount > fAllocCount || newCount < (fAllocCount / 3)) {
1.407 + // whether we're growing or shrinking, we leave at least 50% extra space for future
1.408 + // growth (clamped to the reserve count).
1.409 + newAllocCount = SkMax32(newCount + ((newCount + 1) >> 1), fReserveCount);
1.410 + }
1.411 + if (newAllocCount != fAllocCount) {
1.412 +
1.413 + fAllocCount = newAllocCount;
1.414 + char* newMemArray;
1.415 +
1.416 + if (fAllocCount == fReserveCount && NULL != fPreAllocMemArray) {
1.417 + newMemArray = (char*) fPreAllocMemArray;
1.418 + } else {
1.419 + newMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T));
1.420 + }
1.421 +
1.422 + SkTArrayExt::copyAndDelete<T>(this, newMemArray);
1.423 +
1.424 + if (fMemArray != fPreAllocMemArray) {
1.425 + sk_free(fMemArray);
1.426 + }
1.427 + fMemArray = newMemArray;
1.428 + }
1.429 + }
1.430 +
1.431 + friend void* operator new<T>(size_t, SkTArray*, int);
1.432 +
1.433 + template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, const X*);
1.434 + template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, true>* that, char*);
1.435 +
1.436 + template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, const X*);
1.437 + template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, false>* that, char*);
1.438 +
1.439 + int fReserveCount;
1.440 + int fCount;
1.441 + int fAllocCount;
1.442 + void* fPreAllocMemArray;
1.443 + union {
1.444 + T* fItemArray;
1.445 + void* fMemArray;
1.446 + };
1.447 +};
1.448 +
1.449 +// Use the below macro (SkNEW_APPEND_TO_TARRAY) rather than calling this directly
1.450 +template <typename T, bool MEM_COPY>
1.451 +void* operator new(size_t, SkTArray<T, MEM_COPY>* array, int atIndex) {
1.452 + // Currently, we only support adding to the end of the array. When the array class itself
1.453 + // supports random insertion then this should be updated.
1.454 + // SkASSERT(atIndex >= 0 && atIndex <= array->count());
1.455 + SkASSERT(atIndex == array->count());
1.456 + return array->push_back_raw(1);
1.457 +}
1.458 +
1.459 +// Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete
1.460 +// to match the op new silences warnings about missing op delete when a constructor throws an
1.461 +// exception.
1.462 +template <typename T, bool MEM_COPY>
1.463 +void operator delete(void*, SkTArray<T, MEM_COPY>* array, int atIndex) {
1.464 + SK_CRASH();
1.465 +}
1.466 +
1.467 +// Constructs a new object as the last element of an SkTArray.
1.468 +#define SkNEW_APPEND_TO_TARRAY(array_ptr, type_name, args) \
1.469 + (new ((array_ptr), (array_ptr)->count()) type_name args)
1.470 +
1.471 +
1.472 +/**
1.473 + * Subclass of SkTArray that contains a preallocated memory block for the array.
1.474 + */
1.475 +template <int N, typename T, bool MEM_COPY = false>
1.476 +class SkSTArray : public SkTArray<T, MEM_COPY> {
1.477 +private:
1.478 + typedef SkTArray<T, MEM_COPY> INHERITED;
1.479 +
1.480 +public:
1.481 + SkSTArray() : INHERITED(&fStorage) {
1.482 + }
1.483 +
1.484 + SkSTArray(const SkSTArray& array)
1.485 + : INHERITED(array, &fStorage) {
1.486 + }
1.487 +
1.488 + explicit SkSTArray(const INHERITED& array)
1.489 + : INHERITED(array, &fStorage) {
1.490 + }
1.491 +
1.492 + explicit SkSTArray(int reserveCount)
1.493 + : INHERITED(reserveCount) {
1.494 + }
1.495 +
1.496 + SkSTArray(const T* array, int count)
1.497 + : INHERITED(array, count, &fStorage) {
1.498 + }
1.499 +
1.500 + SkSTArray& operator= (const SkSTArray& array) {
1.501 + return *this = *(const INHERITED*)&array;
1.502 + }
1.503 +
1.504 + SkSTArray& operator= (const INHERITED& array) {
1.505 + INHERITED::operator=(array);
1.506 + return *this;
1.507 + }
1.508 +
1.509 +private:
1.510 + SkAlignedSTStorage<N,T> fStorage;
1.511 +};
1.512 +
1.513 +#endif
