gfx/skia/trunk/src/pdf/SkTSet.h@129ffea94266
gfx/skia/trunk/src/pdf/SkTSet.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 2012 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 SkTSet_DEFINED
9 #define SkTSet_DEFINED
11 #include "SkTSort.h"
12 #include "SkTDArray.h"
13 #include "SkTypes.h"
15 /** \class SkTSet<T>
17 The SkTSet template class defines a set. Elements are additionally
18 guaranteed to be sorted by their insertion order.
19 Main operations supported now are: add, merge, find and contains.
21 TSet<T> is mutable.
22 */
24 // TODO: Add remove, intersect and difference operations.
25 // TODO: Add bench tests.
26 template <typename T> class SkTSet {
27 public:
28 SkTSet() {
29 fSetArray = SkNEW(SkTDArray<T>);
30 fOrderedArray = SkNEW(SkTDArray<T>);
31 }
33 ~SkTSet() {
34 SkASSERT(fSetArray);
35 SkDELETE(fSetArray);
36 SkASSERT(fOrderedArray);
37 SkDELETE(fOrderedArray);
38 }
40 SkTSet(const SkTSet<T>& src) {
41 this->fSetArray = SkNEW_ARGS(SkTDArray<T>, (*src.fSetArray));
42 this->fOrderedArray = SkNEW_ARGS(SkTDArray<T>, (*src.fOrderedArray));
43 #ifdef SK_DEBUG
44 validate();
45 #endif
46 }
48 SkTSet<T>& operator=(const SkTSet<T>& src) {
49 *this->fSetArray = *src.fSetArray;
50 *this->fOrderedArray = *src.fOrderedArray;
51 #ifdef SK_DEBUG
52 validate();
53 #endif
54 return *this;
55 }
57 /** Merges src elements into this, and returns the number of duplicates
58 * found. Elements from src will retain their ordering and will be ordered
59 * after the elements currently in this set.
60 *
61 * Implementation note: this uses a 2-stage merge to obtain O(n log n) time.
62 * The first stage goes through src.fOrderedArray, checking if
63 * this->contains() is false before adding to this.fOrderedArray.
64 * The second stage does a standard sorted list merge on the fSetArrays.
65 */
66 int mergeInto(const SkTSet<T>& src) {
67 SkASSERT(fSetArray);
68 SkASSERT(fOrderedArray);
70 // Do fOrderedArray merge.
71 for (int i = 0; i < src.count(); ++i) {
72 if (!contains((*src.fOrderedArray)[i])) {
73 fOrderedArray->push((*src.fOrderedArray)[i]);
74 }
75 }
77 // Do fSetArray merge.
78 int duplicates = 0;
80 SkTDArray<T>* fArrayNew = new SkTDArray<T>();
81 fArrayNew->setReserve(fOrderedArray->count());
82 int i = 0;
83 int j = 0;
85 while (i < fSetArray->count() && j < src.count()) {
86 if ((*fSetArray)[i] < (*src.fSetArray)[j]) {
87 fArrayNew->push((*fSetArray)[i]);
88 i++;
89 } else if ((*fSetArray)[i] > (*src.fSetArray)[j]) {
90 fArrayNew->push((*src.fSetArray)[j]);
91 j++;
92 } else {
93 duplicates++;
94 j++; // Skip one of the duplicates.
95 }
96 }
98 while (i < fSetArray->count()) {
99 fArrayNew->push((*fSetArray)[i]);
100 i++;
101 }
103 while (j < src.count()) {
104 fArrayNew->push((*src.fSetArray)[j]);
105 j++;
106 }
107 SkDELETE(fSetArray);
108 fSetArray = fArrayNew;
109 fArrayNew = NULL;
111 #ifdef SK_DEBUG
112 validate();
113 #endif
114 return duplicates;
115 }
117 /** Adds a new element into set and returns false if the element is already
118 * in this set.
119 */
120 bool add(const T& elem) {
121 SkASSERT(fSetArray);
122 SkASSERT(fOrderedArray);
124 int pos = 0;
125 int i = find(elem, &pos);
126 if (i >= 0) {
127 return false;
128 }
129 *fSetArray->insert(pos) = elem;
130 fOrderedArray->push(elem);
131 #ifdef SK_DEBUG
132 validate();
133 #endif
134 return true;
135 }
137 /** Returns true if this set is empty.
138 */
139 bool isEmpty() const {
140 SkASSERT(fOrderedArray);
141 SkASSERT(fSetArray);
142 SkASSERT(fSetArray->isEmpty() == fOrderedArray->isEmpty());
143 return fOrderedArray->isEmpty();
144 }
146 /** Return the number of elements in the set.
147 */
148 int count() const {
149 SkASSERT(fOrderedArray);
150 SkASSERT(fSetArray);
151 SkASSERT(fSetArray->count() == fOrderedArray->count());
152 return fOrderedArray->count();
153 }
155 /** Return the number of bytes in the set: count * sizeof(T).
156 */
157 size_t bytes() const {
158 SkASSERT(fOrderedArray);
159 return fOrderedArray->bytes();
160 }
162 /** Return the beginning of a set iterator.
163 * Elements in the iterator will be sorted ascending.
164 */
165 const T* begin() const {
166 SkASSERT(fOrderedArray);
167 return fOrderedArray->begin();
168 }
170 /** Return the end of a set iterator.
171 */
172 const T* end() const {
173 SkASSERT(fOrderedArray);
174 return fOrderedArray->end();
175 }
177 const T& operator[](int index) const {
178 SkASSERT(fOrderedArray);
179 return (*fOrderedArray)[index];
180 }
182 /** Resets the set (deletes memory and initiates an empty set).
183 */
184 void reset() {
185 SkASSERT(fSetArray);
186 SkASSERT(fOrderedArray);
187 fSetArray->reset();
188 fOrderedArray->reset();
189 }
191 /** Rewinds the set (preserves memory and initiates an empty set).
192 */
193 void rewind() {
194 SkASSERT(fSetArray);
195 SkASSERT(fOrderedArray);
196 fSetArray->rewind();
197 fOrderedArray->rewind();
198 }
200 /** Reserves memory for the set.
201 */
202 void setReserve(int reserve) {
203 SkASSERT(fSetArray);
204 SkASSERT(fOrderedArray);
205 fSetArray->setReserve(reserve);
206 fOrderedArray->setReserve(reserve);
207 }
209 /** Returns true if the array contains this element.
210 */
211 bool contains(const T& elem) const {
212 SkASSERT(fSetArray);
213 return (this->find(elem) >= 0);
214 }
216 /** Copies internal array to destination.
217 */
218 void copy(T* dst) const {
219 SkASSERT(fOrderedArray);
220 fOrderedArray->copyRange(dst, 0, fOrderedArray->count());
221 }
223 /** Returns a const reference to the internal vector.
224 */
225 const SkTDArray<T>& toArray() {
226 SkASSERT(fOrderedArray);
227 return *fOrderedArray;
228 }
230 /** Unref all elements in the set.
231 */
232 void unrefAll() {
233 SkASSERT(fSetArray);
234 SkASSERT(fOrderedArray);
235 fOrderedArray->unrefAll();
236 // Also reset the other array, as SkTDArray::unrefAll does an
237 // implcit reset
238 fSetArray->reset();
239 }
241 /** safeUnref all elements in the set.
242 */
243 void safeUnrefAll() {
244 SkASSERT(fSetArray);
245 SkASSERT(fOrderedArray);
246 fOrderedArray->safeUnrefAll();
247 // Also reset the other array, as SkTDArray::safeUnrefAll does an
248 // implcit reset
249 fSetArray->reset();
250 }
252 #ifdef SK_DEBUG
253 void validate() const {
254 SkASSERT(fSetArray);
255 SkASSERT(fOrderedArray);
256 fSetArray->validate();
257 fOrderedArray->validate();
258 SkASSERT(isSorted() && !hasDuplicates() && arraysConsistent());
259 }
261 bool hasDuplicates() const {
262 for (int i = 0; i < fSetArray->count() - 1; ++i) {
263 if ((*fSetArray)[i] == (*fSetArray)[i + 1]) {
264 return true;
265 }
266 }
267 return false;
268 }
270 bool isSorted() const {
271 for (int i = 0; i < fSetArray->count() - 1; ++i) {
272 // Use only < operator
273 if (!((*fSetArray)[i] < (*fSetArray)[i + 1])) {
274 return false;
275 }
276 }
277 return true;
278 }
280 /** Checks if fSetArray is consistent with fOrderedArray
281 */
282 bool arraysConsistent() const {
283 if (fSetArray->count() != fOrderedArray->count()) {
284 return false;
285 }
286 if (fOrderedArray->count() == 0) {
287 return true;
288 }
290 // Copy and sort fOrderedArray, then compare to fSetArray.
291 // A O(n log n) algorithm is necessary as O(n^2) will choke some GMs.
292 SkAutoMalloc sortedArray(fOrderedArray->bytes());
293 T* sortedBase = reinterpret_cast<T*>(sortedArray.get());
294 int count = fOrderedArray->count();
295 fOrderedArray->copyRange(sortedBase, 0, count);
297 SkTQSort<T>(sortedBase, sortedBase + count - 1);
299 for (int i = 0; i < count; ++i) {
300 if (sortedBase[i] != (*fSetArray)[i]) {
301 return false;
302 }
303 }
305 return true;
306 }
307 #endif
309 private:
310 SkTDArray<T>* fSetArray; // Sorted by pointer address for fast
311 // lookup.
312 SkTDArray<T>* fOrderedArray; // Sorted by insertion order for
313 // deterministic output.
315 /** Returns the index in fSetArray where an element was found.
316 * Returns -1 if the element was not found, and it fills *posToInsertSorted
317 * with the index of the place where elem should be inserted to preserve the
318 * internal array sorted.
319 * If element was found, *posToInsertSorted is undefined.
320 */
321 int find(const T& elem, int* posToInsertSorted = NULL) const {
322 SkASSERT(fSetArray);
324 if (fSetArray->count() == 0) {
325 if (posToInsertSorted) {
326 *posToInsertSorted = 0;
327 }
328 return -1;
329 }
330 int iMin = 0;
331 int iMax = fSetArray->count();
333 while (iMin < iMax - 1) {
334 int iMid = (iMin + iMax) / 2;
335 if (elem < (*fSetArray)[iMid]) {
336 iMax = iMid;
337 } else {
338 iMin = iMid;
339 }
340 }
341 if (elem == (*fSetArray)[iMin]) {
342 return iMin;
343 }
344 if (posToInsertSorted) {
345 if (elem < (*fSetArray)[iMin]) {
346 *posToInsertSorted = iMin;
347 } else {
348 *posToInsertSorted = iMin + 1;
349 }
350 }
352 return -1;
353 }
354 };
356 #endif
