Home | History | Annotate | Download | only in core
      1 /*
      2  * Copyright (C) 2006 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #ifndef SkTDArray_DEFINED
     18 #define SkTDArray_DEFINED
     19 
     20 #include "SkTypes.h"
     21 
     22 template <typename T> class SkTDArray {
     23 public:
     24     SkTDArray() {
     25         fReserve = fCount = 0;
     26         fArray = NULL;
     27 #ifdef SK_DEBUG
     28         fData = NULL;
     29 #endif
     30     }
     31     SkTDArray(const T src[], size_t count) {
     32         SkASSERT(src || count == 0);
     33 
     34         fReserve = fCount = 0;
     35         fArray = NULL;
     36 #ifdef SK_DEBUG
     37         fData = NULL;
     38 #endif
     39         if (count) {
     40             fArray = (T*)sk_malloc_throw(count * sizeof(T));
     41 #ifdef SK_DEBUG
     42             fData = (ArrayT*)fArray;
     43 #endif
     44             memcpy(fArray, src, sizeof(T) * count);
     45             fReserve = fCount = count;
     46         }
     47     }
     48     SkTDArray(const SkTDArray<T>& src) {
     49         fReserve = fCount = 0;
     50         fArray = NULL;
     51 #ifdef SK_DEBUG
     52         fData = NULL;
     53 #endif
     54         SkTDArray<T> tmp(src.fArray, src.fCount);
     55         this->swap(tmp);
     56     }
     57     ~SkTDArray() {
     58         sk_free(fArray);
     59     }
     60 
     61     SkTDArray<T>& operator=(const SkTDArray<T>& src) {
     62         if (this != &src) {
     63             if (src.fCount > fReserve) {
     64                 SkTDArray<T> tmp(src.fArray, src.fCount);
     65                 this->swap(tmp);
     66             } else {
     67                 memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
     68                 fCount = src.fCount;
     69             }
     70         }
     71         return *this;
     72     }
     73 
     74     friend int operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
     75         return  a.fCount == b.fCount &&
     76                 (a.fCount == 0 ||
     77                  !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
     78     }
     79 
     80     void swap(SkTDArray<T>& other) {
     81         SkTSwap(fArray, other.fArray);
     82 #ifdef SK_DEBUG
     83         SkTSwap(fData, other.fData);
     84 #endif
     85         SkTSwap(fReserve, other.fReserve);
     86         SkTSwap(fCount, other.fCount);
     87     }
     88 
     89     /** Return a ptr to the array of data, to be freed with sk_free. This also
     90         resets the SkTDArray to be empty.
     91      */
     92     T* detach() {
     93         T* array = fArray;
     94         fArray = NULL;
     95         fReserve = fCount = 0;
     96         SkDEBUGCODE(fData = NULL;)
     97         return array;
     98     }
     99 
    100     bool isEmpty() const { return fCount == 0; }
    101     int count() const { return fCount; }
    102     T*  begin() const { return fArray; }
    103     T*  end() const { return fArray ? fArray + fCount : NULL; }
    104     T&  operator[](int index) const {
    105         SkASSERT((unsigned)index < fCount);
    106         return fArray[index];
    107     }
    108 
    109     void reset() {
    110         if (fArray) {
    111             sk_free(fArray);
    112             fArray = NULL;
    113 #ifdef SK_DEBUG
    114             fData = NULL;
    115 #endif
    116             fReserve = fCount = 0;
    117         } else {
    118             SkASSERT(fReserve == 0 && fCount == 0);
    119         }
    120     }
    121 
    122     void rewind() {
    123         // same as setCount(0)
    124         fCount = 0;
    125     }
    126 
    127     void setCount(size_t count) {
    128         if (count > fReserve) {
    129             this->growBy(count - fCount);
    130         } else {
    131             fCount = count;
    132         }
    133     }
    134 
    135     void setReserve(size_t reserve) {
    136         if (reserve > fReserve) {
    137             SkASSERT(reserve > fCount);
    138             size_t count = fCount;
    139             this->growBy(reserve - fCount);
    140             fCount = count;
    141         }
    142     }
    143 
    144     T* prepend() {
    145         this->growBy(1);
    146         memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
    147         return fArray;
    148     }
    149 
    150     T* append() {
    151         return this->append(1, NULL);
    152     }
    153     T* append(size_t count, const T* src = NULL) {
    154         unsigned oldCount = fCount;
    155         if (count)  {
    156             SkASSERT(src == NULL || fArray == NULL ||
    157                     src + count <= fArray || fArray + oldCount <= src);
    158 
    159             this->growBy(count);
    160             if (src) {
    161                 memcpy(fArray + oldCount, src, sizeof(T) * count);
    162             }
    163         }
    164         return fArray + oldCount;
    165     }
    166 
    167     T* appendClear() {
    168         T* result = this->append();
    169         *result = 0;
    170         return result;
    171     }
    172 
    173     T* insert(size_t index) {
    174         return this->insert(index, 1, NULL);
    175     }
    176     T* insert(size_t index, size_t count, const T* src = NULL) {
    177         SkASSERT(count);
    178         SkASSERT(index <= fCount);
    179         int oldCount = fCount;
    180         this->growBy(count);
    181         T* dst = fArray + index;
    182         memmove(dst + count, dst, sizeof(T) * (oldCount - index));
    183         if (src) {
    184             memcpy(dst, src, sizeof(T) * count);
    185         }
    186         return dst;
    187     }
    188 
    189     void remove(size_t index, size_t count = 1) {
    190         SkASSERT(index + count <= fCount);
    191         fCount = fCount - count;
    192         memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
    193     }
    194 
    195     void removeShuffle(size_t index) {
    196         SkASSERT(index < fCount);
    197         unsigned newCount = fCount - 1;
    198         fCount = newCount;
    199         if (index != newCount) {
    200             memcpy(fArray + index, fArray + newCount, sizeof(T));
    201         }
    202     }
    203 
    204     int find(const T& elem) const {
    205         const T* iter = fArray;
    206         const T* stop = fArray + fCount;
    207 
    208         for (; iter < stop; iter++) {
    209             if (*iter == elem) {
    210                 return (int) (iter - fArray);
    211             }
    212         }
    213         return -1;
    214     }
    215 
    216     int rfind(const T& elem) const {
    217         const T* iter = fArray + fCount;
    218         const T* stop = fArray;
    219 
    220         while (iter > stop) {
    221             if (*--iter == elem) {
    222                 return iter - stop;
    223             }
    224         }
    225         return -1;
    226     }
    227 
    228     // routines to treat the array like a stack
    229     T*          push() { return this->append(); }
    230     void        push(const T& elem) { *this->append() = elem; }
    231     const T&    top() const { return (*this)[fCount - 1]; }
    232     T&          top() { return (*this)[fCount - 1]; }
    233     void        pop(T* elem) { if (elem) *elem = (*this)[fCount - 1]; --fCount; }
    234     void        pop() { --fCount; }
    235 
    236     void deleteAll() {
    237         T*  iter = fArray;
    238         T*  stop = fArray + fCount;
    239         while (iter < stop) {
    240             delete (*iter);
    241             iter += 1;
    242         }
    243         this->reset();
    244     }
    245 
    246     void freeAll() {
    247         T*  iter = fArray;
    248         T*  stop = fArray + fCount;
    249         while (iter < stop) {
    250             sk_free(*iter);
    251             iter += 1;
    252         }
    253         this->reset();
    254     }
    255 
    256     void unrefAll() {
    257         T*  iter = fArray;
    258         T*  stop = fArray + fCount;
    259         while (iter < stop) {
    260             (*iter)->unref();
    261             iter += 1;
    262         }
    263         this->reset();
    264     }
    265 
    266     void safeUnrefAll() {
    267         T*  iter = fArray;
    268         T*  stop = fArray + fCount;
    269         while (iter < stop) {
    270             SkSafeUnref(*iter);
    271             iter += 1;
    272         }
    273         this->reset();
    274     }
    275 
    276 #ifdef SK_DEBUG
    277     void validate() const {
    278         SkASSERT((fReserve == 0 && fArray == NULL) ||
    279                  (fReserve > 0 && fArray != NULL));
    280         SkASSERT(fCount <= fReserve);
    281         SkASSERT(fData == (ArrayT*)fArray);
    282     }
    283 #endif
    284 
    285 private:
    286 #ifdef SK_DEBUG
    287     enum {
    288         kDebugArraySize = 16
    289     };
    290     typedef T ArrayT[kDebugArraySize];
    291     ArrayT* fData;
    292 #endif
    293     T*      fArray;
    294     size_t  fReserve, fCount;
    295 
    296     void growBy(size_t extra) {
    297         SkASSERT(extra);
    298 
    299         if (fCount + extra > fReserve) {
    300             size_t size = fCount + extra + 4;
    301             size += size >> 2;
    302 
    303             fArray = (T*)sk_realloc_throw(fArray, size * sizeof(T));
    304 #ifdef SK_DEBUG
    305             fData = (ArrayT*)fArray;
    306 #endif
    307             fReserve = size;
    308         }
    309         fCount += extra;
    310     }
    311 };
    312 
    313 #endif
    314 
    315