src/third_party/skia/include/core/SkTDArray.h

   1
   2 /*
   3  * Copyright 2006 The Android Open Source Project
   4  *
   5  * Use of this source code is governed by a BSD-style license that can be
   6  * found in the LICENSE file.
   7  */
   8
   9
  10 #ifndef SkTDArray_DEFINED
  11 #define SkTDArray_DEFINED
  12
  13 #include "SkTypes.h"
  14
  15 template <typename T> class SK_API SkTDArray {
  16 public:
  17     SkTDArray() {
  18         fReserve = fCount = 0;
  19         fArray = NULL;
  20 #ifdef SK_DEBUG
  21         fData = NULL;
  22 #endif
  23     }
  24     SkTDArray(const T src[], int count) {
  25         SkASSERT(src || count == 0);
  26
  27         fReserve = fCount = 0;
  28         fArray = NULL;
  29 #ifdef SK_DEBUG
  30         fData = NULL;
  31 #endif
  32         if (count) {
  33             fArray = (T*)sk_malloc_throw(count * sizeof(T));
  34 #ifdef SK_DEBUG
  35             fData = (ArrayT*)fArray;
  36 #endif
  37             memcpy(fArray, src, sizeof(T) * count);
  38             fReserve = fCount = count;
  39         }
  40     }
  41     SkTDArray(const SkTDArray<T>& src) {
  42         fReserve = fCount = 0;
  43         fArray = NULL;
  44 #ifdef SK_DEBUG
  45         fData = NULL;
  46 #endif
  47         SkTDArray<T> tmp(src.fArray, src.fCount);
  48         this->swap(tmp);
  49     }
  50     ~SkTDArray() {
  51         sk_free(fArray);
  52     }
  53
  54     SkTDArray<T>& operator=(const SkTDArray<T>& src) {
  55         if (this != &src) {
  56             if (src.fCount > fReserve) {
  57                 SkTDArray<T> tmp(src.fArray, src.fCount);
  58                 this->swap(tmp);
  59             } else {
  60                 memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
  61                 fCount = src.fCount;
  62             }
  63         }
  64         return *this;
  65     }
  66
  67     friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
  68         return  a.fCount == b.fCount &&
  69                 (a.fCount == 0 ||
  70                  !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
  71     }
  72     friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) {
  73         return !(a == b);
  74     }
  75
  76     void swap(SkTDArray<T>& other) {
  77         SkTSwap(fArray, other.fArray);
  78 #ifdef SK_DEBUG
  79         SkTSwap(fData, other.fData);
  80 #endif
  81         SkTSwap(fReserve, other.fReserve);
  82         SkTSwap(fCount, other.fCount);
  83     }
  84
  85     /** Return a ptr to the array of data, to be freed with sk_free. This also
  86         resets the SkTDArray to be empty.
  87      */
  88     T* detach() {
  89         T* array = fArray;
  90         fArray = NULL;
  91         fReserve = fCount = 0;
  92         SkDEBUGCODE(fData = NULL;)
  93         return array;
  94     }
  95
  96     bool isEmpty() const { return fCount == 0; }
  97
  98     /**
  99      *  Return the number of elements in the array
 100      */
 101     int count() const { return fCount; }
 102
 103     /**
 104      *  return the number of bytes in the array: count * sizeof(T)
 105      */
 106     size_t bytes() const { return fCount * sizeof(T); }
 107
 108     T*  begin() { return fArray; }
 109     const T*  begin() const { return fArray; }
 110     T*  end() { return fArray ? fArray + fCount : NULL; }
 111     const T*  end() const { return fArray ? fArray + fCount : NULL; }
 112
 113     T&  operator[](int index) {
 114         SkASSERT(index < fCount);
 115         return fArray[index];
 116     }
 117     const T&  operator[](int index) const {
 118         SkASSERT(index < fCount);
 119         return fArray[index];
 120     }
 121
 122     T&  getAt(int index)  {
 123         return (*this)[index];
 124     }
 125     const T&  getAt(int index) const {
 126         return (*this)[index];
 127     }
 128
 129     void reset() {
 130         if (fArray) {
 131             sk_free(fArray);
 132             fArray = NULL;
 133 #ifdef SK_DEBUG
 134             fData = NULL;
 135 #endif
 136             fReserve = fCount = 0;
 137         } else {
 138             SkASSERT(fReserve == 0 && fCount == 0);
 139         }
 140     }
 141
 142     void rewind() {
 143         // same as setCount(0)
 144         fCount = 0;
 145     }
 146
 147     void setCount(int count) {
 148         if (count > fReserve) {
 149             this->growBy(count - fCount);
 150         } else {
 151             fCount = count;
 152         }
 153     }
 154
 155     void setReserve(int reserve) {
 156         if (reserve > fReserve) {
 157             SkASSERT(reserve > fCount);
 158             int count = fCount;
 159             this->growBy(reserve - fCount);
 160             fCount = count;
 161         }
 162     }
 163
 164     T* prepend() {
 165         this->growBy(1);
 166         memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
 167         return fArray;
 168     }
 169
 170     T* append() {
 171         return this->append(1, NULL);
 172     }
 173     T* append(int count, const T* src = NULL) {
 174         int oldCount = fCount;
 175         if (count)  {
 176             SkASSERT(src == NULL || fArray == NULL ||
 177                     src + count <= fArray || fArray + oldCount <= src);
 178
 179             this->growBy(count);
 180             if (src) {
 181                 memcpy(fArray + oldCount, src, sizeof(T) * count);
 182             }
 183         }
 184         return fArray + oldCount;
 185     }
 186
 187     T* appendClear() {
 188         T* result = this->append();
 189         *result = 0;
 190         return result;
 191     }
 192
 193     T* insert(int index) {
 194         return this->insert(index, 1, NULL);
 195     }
 196     T* insert(int index, int count, const T* src = NULL) {
 197         SkASSERT(count);
 198         SkASSERT(index <= fCount);
 199         size_t oldCount = fCount;
 200         this->growBy(count);
 201         T* dst = fArray + index;
 202         memmove(dst + count, dst, sizeof(T) * (oldCount - index));
 203         if (src) {
 204             memcpy(dst, src, sizeof(T) * count);
 205         }
 206         return dst;
 207     }
 208
 209     void remove(int index, int count = 1) {
 210         SkASSERT(index + count <= fCount);
 211         fCount = fCount - count;
 212         memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
 213     }
 214
 215     void removeShuffle(int index) {
 216         SkASSERT(index < fCount);
 217         int newCount = fCount - 1;
 218         fCount = newCount;
 219         if (index != newCount) {
 220             memcpy(fArray + index, fArray + newCount, sizeof(T));
 221         }
 222     }
 223
 224     int find(const T& elem) const {
 225         const T* iter = fArray;
 226         const T* stop = fArray + fCount;
 227
 228         for (; iter < stop; iter++) {
 229             if (*iter == elem) {
 230                 return (int) (iter - fArray);
 231             }
 232         }
 233         return -1;
 234     }
 235
 236     int rfind(const T& elem) const {
 237         const T* iter = fArray + fCount;
 238         const T* stop = fArray;
 239
 240         while (iter > stop) {
 241             if (*--iter == elem) {
 242                 return iter - stop;
 243             }
 244         }
 245         return -1;
 246     }
 247
 248     /**
 249      * Returns true iff the array contains this element.
 250      */
 251     bool contains(const T& elem) const {
 252         return (this->find(elem) >= 0);
 253     }
 254
 255     /**
 256      * Copies up to max elements into dst. The number of items copied is
 257      * capped by count - index. The actual number copied is returned.
 258      */
 259     int copyRange(T* dst, int index, int max) const {
 260         SkASSERT(max >= 0);
 261         SkASSERT(!max || dst);
 262         if (index >= fCount) {
 263             return 0;
 264         }
 265         int count = SkMin32(max, fCount - index);
 266         memcpy(dst, fArray + index, sizeof(T) * count);
 267         return count;
 268     }
 269
 270     void copy(T* dst) const {
 271         this->copyRange(dst, 0, fCount);
 272     }
 273
 274     // routines to treat the array like a stack
 275     T*          push() { return this->append(); }
 276     void        push(const T& elem) { *this->append() = elem; }
 277     const T&    top() const { return (*this)[fCount - 1]; }
 278     T&          top() { return (*this)[fCount - 1]; }
 279     void        pop(T* elem) { if (elem) *elem = (*this)[fCount - 1]; --fCount; }
 280     void        pop() { --fCount; }
 281
 282     void deleteAll() {
 283         T*  iter = fArray;
 284         T*  stop = fArray + fCount;
 285         while (iter < stop) {
 286             SkDELETE (*iter);
 287             iter += 1;
 288         }
 289         this->reset();
 290     }
 291
 292     void freeAll() {
 293         T*  iter = fArray;
 294         T*  stop = fArray + fCount;
 295         while (iter < stop) {
 296             sk_free(*iter);
 297             iter += 1;
 298         }
 299         this->reset();
 300     }
 301
 302     void unrefAll() {
 303         T*  iter = fArray;
 304         T*  stop = fArray + fCount;
 305         while (iter < stop) {
 306             (*iter)->unref();
 307             iter += 1;
 308         }
 309         this->reset();
 310     }
 311
 312     void safeUnrefAll() {
 313         T*  iter = fArray;
 314         T*  stop = fArray + fCount;
 315         while (iter < stop) {
 316             SkSafeUnref(*iter);
 317             iter += 1;
 318         }
 319         this->reset();
 320     }
 321
 322     void visitAll(void visitor(T&)) {
 323         T* stop = this->end();
 324         for (T* curr = this->begin(); curr < stop; curr++) {
 325             if (*curr) {
 326                 visitor(*curr);
 327             }
 328         }
 329     }
 330
 331 #ifdef SK_DEBUG
 332     void validate() const {
 333         SkASSERT((fReserve == 0 && fArray == NULL) ||
 334                  (fReserve > 0 && fArray != NULL));
 335         SkASSERT(fCount <= fReserve);
 336         SkASSERT(fData == (ArrayT*)fArray);
 337     }
 338 #endif
 339
 340 private:
 341 #ifdef SK_DEBUG
 342     enum {
 343         kDebugArraySize = 16
 344     };
 345     typedef T ArrayT[kDebugArraySize];
 346     ArrayT* fData;
 347 #endif
 348     T*      fArray;
 349     int     fReserve;
 350     int     fCount;
 351
 352     void growBy(int extra) {
 353         SkASSERT(extra);
 354
 355         if (fCount + extra > fReserve) {
 356             int size = fCount + extra + 4;
 357             size += size >> 2;
 358
 359             fArray = (T*)sk_realloc_throw(fArray, size * sizeof(T));
 360 #ifdef SK_DEBUG
 361             fData = (ArrayT*)fArray;
 362 #endif
 363             fReserve = size;
 364         }
 365         fCount += extra;
 366     }
 367 };
 368
 369 #endif