gfx/skia/trunk/include/core/SkTArray.h@129ffea94266
gfx/skia/trunk/include/core/SkTArray.h
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rw-r--r--
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
1 /*
2 * Copyright 2011 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
8 #ifndef SkTArray_DEFINED
9 #define SkTArray_DEFINED
11 #include <new>
12 #include "SkTypes.h"
13 #include "SkTemplates.h"
15 template <typename T, bool MEM_COPY = false> class SkTArray;
17 namespace SkTArrayExt {
19 template<typename T>
20 inline void copy(SkTArray<T, true>* self, const T* array) {
21 memcpy(self->fMemArray, array, self->fCount * sizeof(T));
22 }
23 template<typename T>
24 inline void copyAndDelete(SkTArray<T, true>* self, char* newMemArray) {
25 memcpy(newMemArray, self->fMemArray, self->fCount * sizeof(T));
26 }
28 template<typename T>
29 inline void copy(SkTArray<T, false>* self, const T* array) {
30 for (int i = 0; i < self->fCount; ++i) {
31 SkNEW_PLACEMENT_ARGS(self->fItemArray + i, T, (array[i]));
32 }
33 }
34 template<typename T>
35 inline void copyAndDelete(SkTArray<T, false>* self, char* newMemArray) {
36 for (int i = 0; i < self->fCount; ++i) {
37 SkNEW_PLACEMENT_ARGS(newMemArray + sizeof(T) * i, T, (self->fItemArray[i]));
38 self->fItemArray[i].~T();
39 }
40 }
42 }
44 template <typename T, bool MEM_COPY> void* operator new(size_t, SkTArray<T, MEM_COPY>*, int);
46 /** When MEM_COPY is true T will be bit copied when moved.
47 When MEM_COPY is false, T will be copy constructed / destructed.
48 In all cases T's constructor will be called on allocation,
49 and its destructor will be called from this object's destructor.
50 */
51 template <typename T, bool MEM_COPY> class SkTArray {
52 public:
53 /**
54 * Creates an empty array with no initial storage
55 */
56 SkTArray() {
57 fCount = 0;
58 fReserveCount = gMIN_ALLOC_COUNT;
59 fAllocCount = 0;
60 fMemArray = NULL;
61 fPreAllocMemArray = NULL;
62 }
64 /**
65 * Creates an empty array that will preallocate space for reserveCount
66 * elements.
67 */
68 explicit SkTArray(int reserveCount) {
69 this->init(NULL, 0, NULL, reserveCount);
70 }
72 /**
73 * Copies one array to another. The new array will be heap allocated.
74 */
75 explicit SkTArray(const SkTArray& array) {
76 this->init(array.fItemArray, array.fCount, NULL, 0);
77 }
79 /**
80 * Creates a SkTArray by copying contents of a standard C array. The new
81 * array will be heap allocated. Be careful not to use this constructor
82 * when you really want the (void*, int) version.
83 */
84 SkTArray(const T* array, int count) {
85 this->init(array, count, NULL, 0);
86 }
88 /**
89 * assign copy of array to this
90 */
91 SkTArray& operator =(const SkTArray& array) {
92 for (int i = 0; i < fCount; ++i) {
93 fItemArray[i].~T();
94 }
95 fCount = 0;
96 this->checkRealloc((int)array.count());
97 fCount = array.count();
98 SkTArrayExt::copy(this, static_cast<const T*>(array.fMemArray));
99 return *this;
100 }
102 virtual ~SkTArray() {
103 for (int i = 0; i < fCount; ++i) {
104 fItemArray[i].~T();
105 }
106 if (fMemArray != fPreAllocMemArray) {
107 sk_free(fMemArray);
108 }
109 }
111 /**
112 * Resets to count() == 0
113 */
114 void reset() { this->pop_back_n(fCount); }
116 /**
117 * Resets to count() = n newly constructed T objects.
118 */
119 void reset(int n) {
120 SkASSERT(n >= 0);
121 for (int i = 0; i < fCount; ++i) {
122 fItemArray[i].~T();
123 }
124 // set fCount to 0 before calling checkRealloc so that no copy cons. are called.
125 fCount = 0;
126 this->checkRealloc(n);
127 fCount = n;
128 for (int i = 0; i < fCount; ++i) {
129 SkNEW_PLACEMENT(fItemArray + i, T);
130 }
131 }
133 /**
134 * Resets to a copy of a C array.
135 */
136 void reset(const T* array, int count) {
137 for (int i = 0; i < fCount; ++i) {
138 fItemArray[i].~T();
139 }
140 int delta = count - fCount;
141 this->checkRealloc(delta);
142 fCount = count;
143 for (int i = 0; i < count; ++i) {
144 SkTArrayExt::copy(this, array);
145 }
146 }
148 /**
149 * Number of elements in the array.
150 */
151 int count() const { return fCount; }
153 /**
154 * Is the array empty.
155 */
156 bool empty() const { return !fCount; }
158 /**
159 * Adds 1 new default-constructed T value and returns in by reference. Note
160 * the reference only remains valid until the next call that adds or removes
161 * elements.
162 */
163 T& push_back() {
164 T* newT = reinterpret_cast<T*>(this->push_back_raw(1));
165 SkNEW_PLACEMENT(newT, T);
166 return *newT;
167 }
169 /**
170 * Version of above that uses a copy constructor to initialize the new item
171 */
172 T& push_back(const T& t) {
173 T* newT = reinterpret_cast<T*>(this->push_back_raw(1));
174 SkNEW_PLACEMENT_ARGS(newT, T, (t));
175 return *newT;
176 }
178 /**
179 * Allocates n more default T values, and returns the address of the start
180 * of that new range. Note: this address is only valid until the next API
181 * call made on the array that might add or remove elements.
182 */
183 T* push_back_n(int n) {
184 SkASSERT(n >= 0);
185 T* newTs = reinterpret_cast<T*>(this->push_back_raw(n));
186 for (int i = 0; i < n; ++i) {
187 SkNEW_PLACEMENT(newTs + i, T);
188 }
189 return newTs;
190 }
192 /**
193 * Version of above that uses a copy constructor to initialize all n items
194 * to the same T.
195 */
196 T* push_back_n(int n, const T& t) {
197 SkASSERT(n >= 0);
198 T* newTs = reinterpret_cast<T*>(this->push_back_raw(n));
199 for (int i = 0; i < n; ++i) {
200 SkNEW_PLACEMENT_ARGS(newTs[i], T, (t));
201 }
202 return newTs;
203 }
205 /**
206 * Version of above that uses a copy constructor to initialize the n items
207 * to separate T values.
208 */
209 T* push_back_n(int n, const T t[]) {
210 SkASSERT(n >= 0);
211 this->checkRealloc(n);
212 for (int i = 0; i < n; ++i) {
213 SkNEW_PLACEMENT_ARGS(fItemArray + fCount + i, T, (t[i]));
214 }
215 fCount += n;
216 return fItemArray + fCount - n;
217 }
219 /**
220 * Removes the last element. Not safe to call when count() == 0.
221 */
222 void pop_back() {
223 SkASSERT(fCount > 0);
224 --fCount;
225 fItemArray[fCount].~T();
226 this->checkRealloc(0);
227 }
229 /**
230 * Removes the last n elements. Not safe to call when count() < n.
231 */
232 void pop_back_n(int n) {
233 SkASSERT(n >= 0);
234 SkASSERT(fCount >= n);
235 fCount -= n;
236 for (int i = 0; i < n; ++i) {
237 fItemArray[fCount + i].~T();
238 }
239 this->checkRealloc(0);
240 }
242 /**
243 * Pushes or pops from the back to resize. Pushes will be default
244 * initialized.
245 */
246 void resize_back(int newCount) {
247 SkASSERT(newCount >= 0);
249 if (newCount > fCount) {
250 this->push_back_n(newCount - fCount);
251 } else if (newCount < fCount) {
252 this->pop_back_n(fCount - newCount);
253 }
254 }
256 T* begin() {
257 return fItemArray;
258 }
259 const T* begin() const {
260 return fItemArray;
261 }
262 T* end() {
263 return fItemArray ? fItemArray + fCount : NULL;
264 }
265 const T* end() const {
266 return fItemArray ? fItemArray + fCount : NULL;;
267 }
269 /**
270 * Get the i^th element.
271 */
272 T& operator[] (int i) {
273 SkASSERT(i < fCount);
274 SkASSERT(i >= 0);
275 return fItemArray[i];
276 }
278 const T& operator[] (int i) const {
279 SkASSERT(i < fCount);
280 SkASSERT(i >= 0);
281 return fItemArray[i];
282 }
284 /**
285 * equivalent to operator[](0)
286 */
287 T& front() { SkASSERT(fCount > 0); return fItemArray[0];}
289 const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];}
291 /**
292 * equivalent to operator[](count() - 1)
293 */
294 T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];}
296 const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];}
298 /**
299 * equivalent to operator[](count()-1-i)
300 */
301 T& fromBack(int i) {
302 SkASSERT(i >= 0);
303 SkASSERT(i < fCount);
304 return fItemArray[fCount - i - 1];
305 }
307 const T& fromBack(int i) const {
308 SkASSERT(i >= 0);
309 SkASSERT(i < fCount);
310 return fItemArray[fCount - i - 1];
311 }
313 bool operator==(const SkTArray<T, MEM_COPY>& right) const {
314 int leftCount = this->count();
315 if (leftCount != right.count()) {
316 return false;
317 }
318 for (int index = 0; index < leftCount; ++index) {
319 if (fItemArray[index] != right.fItemArray[index]) {
320 return false;
321 }
322 }
323 return true;
324 }
326 bool operator!=(const SkTArray<T, MEM_COPY>& right) const {
327 return !(*this == right);
328 }
330 protected:
331 /**
332 * Creates an empty array that will use the passed storage block until it
333 * is insufficiently large to hold the entire array.
334 */
335 template <int N>
336 SkTArray(SkAlignedSTStorage<N,T>* storage) {
337 this->init(NULL, 0, storage->get(), N);
338 }
340 /**
341 * Copy another array, using preallocated storage if preAllocCount >=
342 * array.count(). Otherwise storage will only be used when array shrinks
343 * to fit.
344 */
345 template <int N>
346 SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) {
347 this->init(array.fItemArray, array.fCount, storage->get(), N);
348 }
350 /**
351 * Copy a C array, using preallocated storage if preAllocCount >=
352 * count. Otherwise storage will only be used when array shrinks
353 * to fit.
354 */
355 template <int N>
356 SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) {
357 this->init(array, count, storage->get(), N);
358 }
360 void init(const T* array, int count,
361 void* preAllocStorage, int preAllocOrReserveCount) {
362 SkASSERT(count >= 0);
363 SkASSERT(preAllocOrReserveCount >= 0);
364 fCount = count;
365 fReserveCount = (preAllocOrReserveCount > 0) ?
366 preAllocOrReserveCount :
367 gMIN_ALLOC_COUNT;
368 fPreAllocMemArray = preAllocStorage;
369 if (fReserveCount >= fCount &&
370 NULL != preAllocStorage) {
371 fAllocCount = fReserveCount;
372 fMemArray = preAllocStorage;
373 } else {
374 fAllocCount = SkMax32(fCount, fReserveCount);
375 fMemArray = sk_malloc_throw(fAllocCount * sizeof(T));
376 }
378 SkTArrayExt::copy(this, array);
379 }
381 private:
383 static const int gMIN_ALLOC_COUNT = 8;
385 // Helper function that makes space for n objects, adjusts the count, but does not initialize
386 // the new objects.
387 void* push_back_raw(int n) {
388 this->checkRealloc(n);
389 void* ptr = fItemArray + fCount;
390 fCount += n;
391 return ptr;
392 }
394 inline void checkRealloc(int delta) {
395 SkASSERT(fCount >= 0);
396 SkASSERT(fAllocCount >= 0);
398 SkASSERT(-delta <= fCount);
400 int newCount = fCount + delta;
401 int newAllocCount = fAllocCount;
403 if (newCount > fAllocCount || newCount < (fAllocCount / 3)) {
404 // whether we're growing or shrinking, we leave at least 50% extra space for future
405 // growth (clamped to the reserve count).
406 newAllocCount = SkMax32(newCount + ((newCount + 1) >> 1), fReserveCount);
407 }
408 if (newAllocCount != fAllocCount) {
410 fAllocCount = newAllocCount;
411 char* newMemArray;
413 if (fAllocCount == fReserveCount && NULL != fPreAllocMemArray) {
414 newMemArray = (char*) fPreAllocMemArray;
415 } else {
416 newMemArray = (char*) sk_malloc_throw(fAllocCount*sizeof(T));
417 }
419 SkTArrayExt::copyAndDelete<T>(this, newMemArray);
421 if (fMemArray != fPreAllocMemArray) {
422 sk_free(fMemArray);
423 }
424 fMemArray = newMemArray;
425 }
426 }
428 friend void* operator new<T>(size_t, SkTArray*, int);
430 template<typename X> friend void SkTArrayExt::copy(SkTArray<X, true>* that, const X*);
431 template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, true>* that, char*);
433 template<typename X> friend void SkTArrayExt::copy(SkTArray<X, false>* that, const X*);
434 template<typename X> friend void SkTArrayExt::copyAndDelete(SkTArray<X, false>* that, char*);
436 int fReserveCount;
437 int fCount;
438 int fAllocCount;
439 void* fPreAllocMemArray;
440 union {
441 T* fItemArray;
442 void* fMemArray;
443 };
444 };
446 // Use the below macro (SkNEW_APPEND_TO_TARRAY) rather than calling this directly
447 template <typename T, bool MEM_COPY>
448 void* operator new(size_t, SkTArray<T, MEM_COPY>* array, int atIndex) {
449 // Currently, we only support adding to the end of the array. When the array class itself
450 // supports random insertion then this should be updated.
451 // SkASSERT(atIndex >= 0 && atIndex <= array->count());
452 SkASSERT(atIndex == array->count());
453 return array->push_back_raw(1);
454 }
456 // Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete
457 // to match the op new silences warnings about missing op delete when a constructor throws an
458 // exception.
459 template <typename T, bool MEM_COPY>
460 void operator delete(void*, SkTArray<T, MEM_COPY>* array, int atIndex) {
461 SK_CRASH();
462 }
464 // Constructs a new object as the last element of an SkTArray.
465 #define SkNEW_APPEND_TO_TARRAY(array_ptr, type_name, args) \
466 (new ((array_ptr), (array_ptr)->count()) type_name args)
469 /**
470 * Subclass of SkTArray that contains a preallocated memory block for the array.
471 */
472 template <int N, typename T, bool MEM_COPY = false>
473 class SkSTArray : public SkTArray<T, MEM_COPY> {
474 private:
475 typedef SkTArray<T, MEM_COPY> INHERITED;
477 public:
478 SkSTArray() : INHERITED(&fStorage) {
479 }
481 SkSTArray(const SkSTArray& array)
482 : INHERITED(array, &fStorage) {
483 }
485 explicit SkSTArray(const INHERITED& array)
486 : INHERITED(array, &fStorage) {
487 }
489 explicit SkSTArray(int reserveCount)
490 : INHERITED(reserveCount) {
491 }
493 SkSTArray(const T* array, int count)
494 : INHERITED(array, count, &fStorage) {
495 }
497 SkSTArray& operator= (const SkSTArray& array) {
498 return *this = *(const INHERITED*)&array;
499 }
501 SkSTArray& operator= (const INHERITED& array) {
502 INHERITED::operator=(array);
503 return *this;
504 }
506 private:
507 SkAlignedSTStorage<N,T> fStorage;
508 };
510 #endif
