OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2006 The Android Open Source Project | 3 * Copyright 2006 The Android Open Source Project |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 | 9 |
10 #ifndef SkTDArray_DEFINED | 10 #ifndef SkTDArray_DEFINED |
(...skipping 133 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
144 } else { | 144 } else { |
145 SkASSERT(fReserve == 0 && fCount == 0); | 145 SkASSERT(fReserve == 0 && fCount == 0); |
146 } | 146 } |
147 } | 147 } |
148 | 148 |
149 void rewind() { | 149 void rewind() { |
150 // same as setCount(0) | 150 // same as setCount(0) |
151 fCount = 0; | 151 fCount = 0; |
152 } | 152 } |
153 | 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 */ |
154 void setCount(int count) { | 160 void setCount(int count) { |
| 161 // TODO(mtklein): eliminate this method, setCountExact -> setCount |
| 162 SkASSERT(count >= 0); |
155 if (count > fReserve) { | 163 if (count > fReserve) { |
156 this->growBy(count - fCount); | 164 resizeStorageToAtLeast(count); |
157 } else { | |
158 fCount = count; | |
159 } | 165 } |
| 166 fCount = count; |
| 167 } |
| 168 |
| 169 /** |
| 170 * Sets the number of elements in the array. |
| 171 * If the array does not have space for count elements, it will increase |
| 172 * the storage allocated to exactly the amount required, with no remaining |
| 173 * reserved space. |
| 174 * It will never shrink the shrink the storage. |
| 175 */ |
| 176 void setCountExact(int count) { |
| 177 if (count > fReserve) { |
| 178 this->resizeStorageToExact(count); |
| 179 } |
| 180 fCount = count; |
160 } | 181 } |
161 | 182 |
162 void setReserve(int reserve) { | 183 void setReserve(int reserve) { |
163 if (reserve > fReserve) { | 184 if (reserve > fReserve) { |
164 SkASSERT(reserve > fCount); | 185 resizeStorageToAtLeast(reserve); |
165 int count = fCount; | |
166 this->growBy(reserve - fCount); | |
167 fCount = count; | |
168 } | 186 } |
169 } | 187 } |
170 | 188 |
171 T* prepend() { | 189 T* prepend() { |
172 this->growBy(1); | 190 this->adjustCount(1); |
173 memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T)); | 191 memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T)); |
174 return fArray; | 192 return fArray; |
175 } | 193 } |
176 | 194 |
177 T* append() { | 195 T* append() { |
178 return this->append(1, NULL); | 196 return this->append(1, NULL); |
179 } | 197 } |
180 T* append(int count, const T* src = NULL) { | 198 T* append(int count, const T* src = NULL) { |
181 int oldCount = fCount; | 199 int oldCount = fCount; |
182 if (count) { | 200 if (count) { |
183 SkASSERT(src == NULL || fArray == NULL || | 201 SkASSERT(src == NULL || fArray == NULL || |
184 src + count <= fArray || fArray + oldCount <= src); | 202 src + count <= fArray || fArray + oldCount <= src); |
185 | 203 |
186 this->growBy(count); | 204 this->adjustCount(count); |
187 if (src) { | 205 if (src) { |
188 memcpy(fArray + oldCount, src, sizeof(T) * count); | 206 memcpy(fArray + oldCount, src, sizeof(T) * count); |
189 } | 207 } |
190 } | 208 } |
191 return fArray + oldCount; | 209 return fArray + oldCount; |
192 } | 210 } |
193 | 211 |
194 T* appendClear() { | 212 T* appendClear() { |
195 T* result = this->append(); | 213 T* result = this->append(); |
196 *result = 0; | 214 *result = 0; |
197 return result; | 215 return result; |
198 } | 216 } |
199 | 217 |
200 T* insert(int index) { | 218 T* insert(int index) { |
201 return this->insert(index, 1, NULL); | 219 return this->insert(index, 1, NULL); |
202 } | 220 } |
203 T* insert(int index, int count, const T* src = NULL) { | 221 T* insert(int index, int count, const T* src = NULL) { |
204 SkASSERT(count); | 222 SkASSERT(count); |
205 SkASSERT(index <= fCount); | 223 SkASSERT(index <= fCount); |
206 size_t oldCount = fCount; | 224 size_t oldCount = fCount; |
207 this->growBy(count); | 225 this->adjustCount(count); |
208 T* dst = fArray + index; | 226 T* dst = fArray + index; |
209 memmove(dst + count, dst, sizeof(T) * (oldCount - index)); | 227 memmove(dst + count, dst, sizeof(T) * (oldCount - index)); |
210 if (src) { | 228 if (src) { |
211 memcpy(dst, src, sizeof(T) * count); | 229 memcpy(dst, src, sizeof(T) * count); |
212 } | 230 } |
213 return dst; | 231 return dst; |
214 } | 232 } |
215 | 233 |
216 void remove(int index, int count = 1) { | 234 void remove(int index, int count = 1) { |
217 SkASSERT(index + count <= fCount); | 235 SkASSERT(index + count <= fCount); |
(...skipping 131 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
349 enum { | 367 enum { |
350 kDebugArraySize = 16 | 368 kDebugArraySize = 16 |
351 }; | 369 }; |
352 typedef T ArrayT[kDebugArraySize]; | 370 typedef T ArrayT[kDebugArraySize]; |
353 ArrayT* fData; | 371 ArrayT* fData; |
354 #endif | 372 #endif |
355 T* fArray; | 373 T* fArray; |
356 int fReserve; | 374 int fReserve; |
357 int fCount; | 375 int fCount; |
358 | 376 |
359 void growBy(int extra) { | 377 /** |
360 SkASSERT(extra); | 378 * Adjusts the number of elements in the array. |
| 379 * This is the same as calling setCount(count() + delta). |
| 380 */ |
| 381 void adjustCount(int delta) { |
| 382 setCount(fCount + delta); |
| 383 } |
361 | 384 |
362 if (fCount + extra > fReserve) { | 385 /** |
363 int size = fCount + extra + 4; | 386 * This resizes the storage to *exactly* count elements, growing or |
364 size += size >> 2; | 387 * shrinking the allocation as needed. It does not ASSERT anything about |
| 388 * the previous allocation size, or about fCount. |
| 389 * |
| 390 * note: does NOT modify fCount |
| 391 */ |
| 392 void resizeStorageToExact(int count) { |
| 393 SkASSERT(count >= 0); |
| 394 fArray = (T*)sk_realloc_throw(fArray, count * sizeof(T)); |
| 395 #ifdef SK_DEBUG |
| 396 fData = (ArrayT*)fArray; |
| 397 #endif |
| 398 fReserve = count; |
| 399 } |
365 | 400 |
366 fArray = (T*)sk_realloc_throw(fArray, size * sizeof(T)); | 401 /** |
367 #ifdef SK_DEBUG | 402 * Increase the storage allocation such that it can hold (fCount + extra) |
368 fData = (ArrayT*)fArray; | 403 * elements. |
369 #endif | 404 * It never shrinks the allocation, and it may increase the allocation by |
370 fReserve = size; | 405 * more than is strictly required, based on a private growth heuristic. |
371 } | 406 * |
372 fCount += extra; | 407 * note: does NOT modify fCount |
| 408 */ |
| 409 void resizeStorageToAtLeast(int count) { |
| 410 SkASSERT(count > fReserve); |
| 411 int space = count + 4; |
| 412 space += space>>2; |
| 413 resizeStorageToExact(space); |
373 } | 414 } |
374 }; | 415 }; |
375 | 416 |
376 #endif | 417 #endif |
OLD | NEW |