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 total number of elements allocated.
 105      *  reserved() - count() gives you the number of elements you can add
 106      *  without causing an allocation.
 107      */
 108     int reserved() const { return fReserve; }
 109
 110     /**
 111      *  return the number of bytes in the array: count * sizeof(T)
 112      */
 113     size_t bytes() const { return fCount * sizeof(T); }
 114
 115     T*  begin() { return fArray; }
 116     const T*  begin() const { return fArray; }
 117     T*  end() { return fArray ? fArray + fCount : NULL; }
 118     const T*  end() const { return fArray ? fArray + fCount : NULL; }
 119
 120     T&  operator[](int index) {
 121         SkASSERT(index < fCount);
 122         return fArray[index];
 123     }
 124     const T&  operator[](int index) const {
 125         SkASSERT(index < fCount);
 126         return fArray[index];
 127     }
 128
 129     T&  getAt(int index)  {
 130         return (*this)[index];
 131     }
 132     const T&  getAt(int index) const {
 133         return (*this)[index];
 134     }
 135
 136     void reset() {
 137         if (fArray) {
 138             sk_free(fArray);
 139             fArray = NULL;
 140 #ifdef SK_DEBUG
 141             fData = NULL;
 142 #endif
 143             fReserve = fCount = 0;
 144         } else {
 145             SkASSERT(fReserve == 0 && fCount == 0);
 146         }
 147     }
 148
 149     void rewind() {
 150         // same as setCount(0)
 151         fCount = 0;
 152     }
 153
 154     /**
 155      *  Sets the number of elements in the array.
 156      *  If the array does not have space for count elements, it will increase
 157      *  the storage allocated to some amount greater than that required.
 158      *  It will never shrink the shrink the storage.
 159      */
 160     void setCount(int count) {
 161         SkASSERT(count >= 0);
 162         if (count > fReserve) {
 163             this->resizeStorageToAtLeast(count);
 164         }
 165         fCount = count;
 166     }
 167
 168     void setReserve(int reserve) {
 169         if (reserve > fReserve) {
 170             this->resizeStorageToAtLeast(reserve);
 171         }
 172     }
 173
 174     T* prepend() {
 175         this->adjustCount(1);
 176         memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
 177         return fArray;
 178     }
 179
 180     T* append() {
 181         return this->append(1, NULL);
 182     }
 183     T* append(int count, const T* src = NULL) {
 184         int oldCount = fCount;
 185         if (count)  {
 186             SkASSERT(src == NULL || fArray == NULL ||
 187                     src + count <= fArray || fArray + oldCount <= src);
 188
 189             this->adjustCount(count);
 190             if (src) {
 191                 memcpy(fArray + oldCount, src, sizeof(T) * count);
 192             }
 193         }
 194         return fArray + oldCount;
 195     }
 196
 197     T* appendClear() {
 198         T* result = this->append();
 199         *result = 0;
 200         return result;
 201     }
 202
 203     T* insert(int index) {
 204         return this->insert(index, 1, NULL);
 205     }
 206     T* insert(int index, int count, const T* src = NULL) {
 207         SkASSERT(count);
 208         SkASSERT(index <= fCount);
 209         size_t oldCount = fCount;
 210         this->adjustCount(count);
 211         T* dst = fArray + index;
 212         memmove(dst + count, dst, sizeof(T) * (oldCount - index));
 213         if (src) {
 214             memcpy(dst, src, sizeof(T) * count);
 215         }
 216         return dst;
 217     }
 218
 219     void remove(int index, int count = 1) {
 220         SkASSERT(index + count <= fCount);
 221         fCount = fCount - count;
 222         memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
 223     }
 224
 225     void removeShuffle(int index) {
 226         SkASSERT(index < fCount);
 227         int newCount = fCount - 1;
 228         fCount = newCount;
 229         if (index != newCount) {
 230             memcpy(fArray + index, fArray + newCount, sizeof(T));
 231         }
 232     }
 233
 234     int find(const T& elem) const {
 235         const T* iter = fArray;
 236         const T* stop = fArray + fCount;
 237
 238         for (; iter < stop; iter++) {
 239             if (*iter == elem) {
 240                 return (int) (iter - fArray);
 241             }
 242         }
 243         return -1;
 244     }
 245
 246     int rfind(const T& elem) const {
 247         const T* iter = fArray + fCount;
 248         const T* stop = fArray;
 249
 250         while (iter > stop) {
 251             if (*--iter == elem) {
 252                 return SkToInt(iter - stop);
 253             }
 254         }
 255         return -1;
 256     }
 257
 258     /**
 259      * Returns true iff the array contains this element.
 260      */
 261     bool contains(const T& elem) const {
 262         return (this->find(elem) >= 0);
 263     }
 264
 265     /**
 266      * Copies up to max elements into dst. The number of items copied is
 267      * capped by count - index. The actual number copied is returned.
 268      */
 269     int copyRange(T* dst, int index, int max) const {
 270         SkASSERT(max >= 0);
 271         SkASSERT(!max || dst);
 272         if (index >= fCount) {
 273             return 0;
 274         }
 275         int count = SkMin32(max, fCount - index);
 276         memcpy(dst, fArray + index, sizeof(T) * count);
 277         return count;
 278     }
 279
 280     void copy(T* dst) const {
 281         this->copyRange(dst, 0, fCount);
 282     }
 283
 284     // routines to treat the array like a stack
 285     T*          push() { return this->append(); }
 286     void        push(const T& elem) { *this->append() = elem; }
 287     const T&    top() const { return (*this)[fCount - 1]; }
 288     T&          top() { return (*this)[fCount - 1]; }
 289     void        pop(T* elem) { if (elem) *elem = (*this)[fCount - 1]; --fCount; }
 290     void        pop() { --fCount; }
 291
 292     void deleteAll() {
 293         T*  iter = fArray;
 294         T*  stop = fArray + fCount;
 295         while (iter < stop) {
 296             SkDELETE (*iter);
 297             iter += 1;
 298         }
 299         this->reset();
 300     }
 301
 302     void freeAll() {
 303         T*  iter = fArray;
 304         T*  stop = fArray + fCount;
 305         while (iter < stop) {
 306             sk_free(*iter);
 307             iter += 1;
 308         }
 309         this->reset();
 310     }
 311
 312     void unrefAll() {
 313         T*  iter = fArray;
 314         T*  stop = fArray + fCount;
 315         while (iter < stop) {
 316             (*iter)->unref();
 317             iter += 1;
 318         }
 319         this->reset();
 320     }
 321
 322     void safeUnrefAll() {
 323         T*  iter = fArray;
 324         T*  stop = fArray + fCount;
 325         while (iter < stop) {
 326             SkSafeUnref(*iter);
 327             iter += 1;
 328         }
 329         this->reset();
 330     }
 331
 332     void visitAll(void visitor(T&)) {
 333         T* stop = this->end();
 334         for (T* curr = this->begin(); curr < stop; curr++) {
 335             if (*curr) {
 336                 visitor(*curr);
 337             }
 338         }
 339     }
 340
 341 #ifdef SK_DEBUG
 342     void validate() const {
 343         SkASSERT((fReserve == 0 && fArray == NULL) ||
 344                  (fReserve > 0 && fArray != NULL));
 345         SkASSERT(fCount <= fReserve);
 346         SkASSERT(fData == (ArrayT*)fArray);
 347     }
 348 #endif
 349
 350 private:
 351 #ifdef SK_DEBUG
 352     enum {
 353         kDebugArraySize = 16
 354     };
 355     typedef T ArrayT[kDebugArraySize];
 356     ArrayT* fData;
 357 #endif
 358     T*      fArray;
 359     int     fReserve;
 360     int     fCount;
 361
 362     /**
 363      *  Adjusts the number of elements in the array.
 364      *  This is the same as calling setCount(count() + delta).
 365      */
 366     void adjustCount(int delta) {
 367         this->setCount(fCount + delta);
 368     }
 369
 370     /**
 371      *  Increase the storage allocation such that it can hold (fCount + extra)
 372      *  elements.
 373      *  It never shrinks the allocation, and it may increase the allocation by
 374      *  more than is strictly required, based on a private growth heuristic.
 375      *
 376      *  note: does NOT modify fCount
 377      */
 378     void resizeStorageToAtLeast(int count) {
 379         SkASSERT(count > fReserve);
 380         fReserve = count + 4;
 381         fReserve += fReserve / 4;
 382         fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
 383 #ifdef SK_DEBUG
 384         fData = (ArrayT*)fArray;
 385 #endif
 386     }
 387 };
 388
 389 #endif