00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef SkTDArray_DEFINED
00018 #define SkTDArray_DEFINED
00019
00020 #include "SkTypes.h"
00021
00022 template <typename T> class SkTDArray {
00023 public:
00024 SkTDArray() {
00025 fReserve = fCount = 0;
00026 fArray = NULL;
00027 #ifdef SK_DEBUG
00028 fData = NULL;
00029 #endif
00030 }
00031 SkTDArray(const T src[], size_t count) {
00032 SkASSERT(src || count == 0);
00033
00034 fReserve = fCount = 0;
00035 fArray = NULL;
00036 #ifdef SK_DEBUG
00037 fData = NULL;
00038 #endif
00039 if (count) {
00040 fArray = (T*)sk_malloc_throw(count * sizeof(T));
00041 #ifdef SK_DEBUG
00042 fData = (ArrayT*)fArray;
00043 #endif
00044 memcpy(fArray, src, sizeof(T) * count);
00045 fReserve = fCount = count;
00046 }
00047 }
00048 SkTDArray(const SkTDArray<T>& src) {
00049 fReserve = fCount = 0;
00050 fArray = NULL;
00051 #ifdef SK_DEBUG
00052 fData = NULL;
00053 #endif
00054 SkTDArray<T> tmp(src.fArray, src.fCount);
00055 this->swap(tmp);
00056 }
00057 ~SkTDArray() {
00058 sk_free(fArray);
00059 }
00060
00061 SkTDArray<T>& operator=(const SkTDArray<T>& src) {
00062 if (this != &src) {
00063 if (src.fCount > fReserve) {
00064 SkTDArray<T> tmp(src.fArray, src.fCount);
00065 this->swap(tmp);
00066 } else {
00067 memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
00068 fCount = src.fCount;
00069 }
00070 }
00071 return *this;
00072 }
00073
00074 friend int operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
00075 return a.fCount == b.fCount &&
00076 (a.fCount == 0 ||
00077 !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
00078 }
00079
00080 void swap(SkTDArray<T>& other) {
00081 SkTSwap(fArray, other.fArray);
00082 #ifdef SK_DEBUG
00083 SkTSwap(fData, other.fData);
00084 #endif
00085 SkTSwap(fReserve, other.fReserve);
00086 SkTSwap(fCount, other.fCount);
00087 }
00088
00092 T* detach() {
00093 T* array = fArray;
00094 fArray = NULL;
00095 fReserve = fCount = 0;
00096 SkDEBUGCODE(fData = NULL;)
00097 return array;
00098 }
00099
00100 bool isEmpty() const { return fCount == 0; }
00101 int count() const { return fCount; }
00102 T* begin() const { return fArray; }
00103 T* end() const { return fArray ? fArray + fCount : NULL; }
00104 T& operator[](int index) const {
00105 SkASSERT((unsigned)index < fCount);
00106 return fArray[index];
00107 }
00108
00109 void reset() {
00110 if (fArray) {
00111 sk_free(fArray);
00112 fArray = NULL;
00113 #ifdef SK_DEBUG
00114 fData = NULL;
00115 #endif
00116 fReserve = fCount = 0;
00117 } else {
00118 SkASSERT(fReserve == 0 && fCount == 0);
00119 }
00120 }
00121
00122 void rewind() {
00123
00124 fCount = 0;
00125 }
00126
00127 void setCount(size_t count) {
00128 if (count > fReserve) {
00129 this->growBy(count - fCount);
00130 } else {
00131 fCount = count;
00132 }
00133 }
00134
00135 void setReserve(size_t reserve) {
00136 if (reserve > fReserve) {
00137 SkASSERT(reserve > fCount);
00138 size_t count = fCount;
00139 this->growBy(reserve - fCount);
00140 fCount = count;
00141 }
00142 }
00143
00144 T* prepend() {
00145 this->growBy(1);
00146 memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
00147 return fArray;
00148 }
00149
00150 T* append() {
00151 return this->append(1, NULL);
00152 }
00153 T* append(size_t count, const T* src = NULL) {
00154 unsigned oldCount = fCount;
00155 if (count) {
00156 SkASSERT(src == NULL || fArray == NULL ||
00157 src + count <= fArray || fArray + oldCount <= src);
00158
00159 this->growBy(count);
00160 if (src) {
00161 memcpy(fArray + oldCount, src, sizeof(T) * count);
00162 }
00163 }
00164 return fArray + oldCount;
00165 }
00166
00167 T* appendClear() {
00168 T* result = this->append();
00169 *result = 0;
00170 return result;
00171 }
00172
00173 T* insert(size_t index) {
00174 return this->insert(index, 1, NULL);
00175 }
00176 T* insert(size_t index, size_t count, const T* src = NULL) {
00177 SkASSERT(count);
00178 SkASSERT(index <= fCount);
00179 int oldCount = fCount;
00180 this->growBy(count);
00181 T* dst = fArray + index;
00182 memmove(dst + count, dst, sizeof(T) * (oldCount - index));
00183 if (src) {
00184 memcpy(dst, src, sizeof(T) * count);
00185 }
00186 return dst;
00187 }
00188
00189 void remove(size_t index, size_t count = 1) {
00190 SkASSERT(index + count <= fCount);
00191 fCount = fCount - count;
00192 memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
00193 }
00194
00195 void removeShuffle(size_t index) {
00196 SkASSERT(index < fCount);
00197 unsigned newCount = fCount - 1;
00198 fCount = newCount;
00199 if (index != newCount) {
00200 memcpy(fArray + index, fArray + newCount, sizeof(T));
00201 }
00202 }
00203
00204 int find(const T& elem) const {
00205 const T* iter = fArray;
00206 const T* stop = fArray + fCount;
00207
00208 for (; iter < stop; iter++) {
00209 if (*iter == elem) {
00210 return (int) (iter - fArray);
00211 }
00212 }
00213 return -1;
00214 }
00215
00216 int rfind(const T& elem) const {
00217 const T* iter = fArray + fCount;
00218 const T* stop = fArray;
00219
00220 while (iter > stop) {
00221 if (*--iter == elem) {
00222 return iter - stop;
00223 }
00224 }
00225 return -1;
00226 }
00227
00228
00229 T* push() { return this->append(); }
00230 void push(const T& elem) { *this->append() = elem; }
00231 const T& top() const { return (*this)[fCount - 1]; }
00232 T& top() { return (*this)[fCount - 1]; }
00233 void pop(T* elem) { if (elem) *elem = (*this)[fCount - 1]; --fCount; }
00234 void pop() { --fCount; }
00235
00236 void deleteAll() {
00237 T* iter = fArray;
00238 T* stop = fArray + fCount;
00239 while (iter < stop) {
00240 delete (*iter);
00241 iter += 1;
00242 }
00243 this->reset();
00244 }
00245
00246 void freeAll() {
00247 T* iter = fArray;
00248 T* stop = fArray + fCount;
00249 while (iter < stop) {
00250 sk_free(*iter);
00251 iter += 1;
00252 }
00253 this->reset();
00254 }
00255
00256 void unrefAll() {
00257 T* iter = fArray;
00258 T* stop = fArray + fCount;
00259 while (iter < stop) {
00260 (*iter)->unref();
00261 iter += 1;
00262 }
00263 this->reset();
00264 }
00265
00266 void safeUnrefAll() {
00267 T* iter = fArray;
00268 T* stop = fArray + fCount;
00269 while (iter < stop) {
00270 SkSafeUnref(*iter);
00271 iter += 1;
00272 }
00273 this->reset();
00274 }
00275
00276 #ifdef SK_DEBUG
00277 void validate() const {
00278 SkASSERT((fReserve == 0 && fArray == NULL) ||
00279 (fReserve > 0 && fArray != NULL));
00280 SkASSERT(fCount <= fReserve);
00281 SkASSERT(fData == (ArrayT*)fArray);
00282 }
00283 #endif
00284
00285 private:
00286 #ifdef SK_DEBUG
00287 enum {
00288 kDebugArraySize = 16
00289 };
00290 typedef T ArrayT[kDebugArraySize];
00291 ArrayT* fData;
00292 #endif
00293 T* fArray;
00294 size_t fReserve, fCount;
00295
00296 void growBy(size_t extra) {
00297 SkASSERT(extra);
00298
00299 if (fCount + extra > fReserve) {
00300 size_t size = fCount + extra + 4;
00301 size += size >> 2;
00302
00303 fArray = (T*)sk_realloc_throw(fArray, size * sizeof(T));
00304 #ifdef SK_DEBUG
00305 fData = (ArrayT*)fArray;
00306 #endif
00307 fReserve = size;
00308 }
00309 fCount += extra;
00310 }
00311 };
00312
00313 #endif
00314