gfx/skia/trunk/src/core/SkQuadTree.cpp@129ffea94266
gfx/skia/trunk/src/core/SkQuadTree.cpp
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 2014 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 #include "SkQuadTree.h"
9 #include "SkTSort.h"
10 #include <stdio.h>
11 #include <vector>
13 static const int kSplitThreshold = 8;
14 static const int kMinDimensions = 128;
16 SkQuadTree::SkQuadTree(const SkIRect& bounds)
17 : fEntryCount(0)
18 , fRoot(NULL) {
19 SkASSERT((bounds.width() * bounds.height()) > 0);
20 fRoot = fNodePool.acquire();
21 fRoot->fBounds = bounds;
22 }
24 SkQuadTree::~SkQuadTree() {
25 }
27 SkQuadTree::Node* SkQuadTree::pickChild(Node* node,
28 const SkIRect& bounds) const {
29 // is it entirely to the left?
30 int index = 0;
31 if (bounds.fRight < node->fSplitPoint.fX) {
32 // Inside the left side
33 } else if(bounds.fLeft >= node->fSplitPoint.fX) {
34 // Inside the right side
35 index |= 1;
36 } else {
37 // Not inside any children
38 return NULL;
39 }
40 if (bounds.fBottom < node->fSplitPoint.fY) {
41 // Inside the top side
42 } else if(bounds.fTop >= node->fSplitPoint.fY) {
43 // Inside the bottom side
44 index |= 2;
45 } else {
46 // Not inside any children
47 return NULL;
48 }
49 return node->fChildren[index];
50 }
52 void SkQuadTree::insert(Node* node, Entry* entry) {
53 // does it belong in a child?
54 if (NULL != node->fChildren[0]) {
55 Node* child = pickChild(node, entry->fBounds);
56 if (NULL != child) {
57 insert(child, entry);
58 } else {
59 node->fEntries.push(entry);
60 }
61 return;
62 }
63 // No children yet, add to this node
64 node->fEntries.push(entry);
65 // should I split?
66 if (node->fEntries.getCount() < kSplitThreshold) {
67 return;
68 }
70 if ((node->fBounds.width() < kMinDimensions) ||
71 (node->fBounds.height() < kMinDimensions)) {
72 return;
73 }
75 // Build all the children
76 node->fSplitPoint = SkIPoint::Make(node->fBounds.centerX(),
77 node->fBounds.centerY());
78 for(int index=0; index<kChildCount; ++index) {
79 node->fChildren[index] = fNodePool.acquire();
80 }
81 node->fChildren[0]->fBounds = SkIRect::MakeLTRB(
82 node->fBounds.fLeft, node->fBounds.fTop,
83 node->fSplitPoint.fX, node->fSplitPoint.fY);
84 node->fChildren[1]->fBounds = SkIRect::MakeLTRB(
85 node->fSplitPoint.fX, node->fBounds.fTop,
86 node->fBounds.fRight, node->fSplitPoint.fY);
87 node->fChildren[2]->fBounds = SkIRect::MakeLTRB(
88 node->fBounds.fLeft, node->fSplitPoint.fY,
89 node->fSplitPoint.fX, node->fBounds.fBottom);
90 node->fChildren[3]->fBounds = SkIRect::MakeLTRB(
91 node->fSplitPoint.fX, node->fSplitPoint.fY,
92 node->fBounds.fRight, node->fBounds.fBottom);
93 // reinsert all the entries of this node to allow child trickle
94 SkTInternalSList<Entry> entries;
95 entries.pushAll(&node->fEntries);
96 while(!entries.isEmpty()) {
97 insert(node, entries.pop());
98 }
99 }
101 void SkQuadTree::search(Node* node, const SkIRect& query,
102 SkTDArray<void*>* results) const {
103 for (Entry* entry = node->fEntries.head(); NULL != entry;
104 entry = entry->getSListNext()) {
105 if (SkIRect::IntersectsNoEmptyCheck(entry->fBounds, query)) {
106 results->push(entry->fData);
107 }
108 }
109 if (NULL == node->fChildren[0]) {
110 return;
111 }
112 // fast quadrant test
113 bool left = true;
114 bool right = true;
115 if (query.fRight < node->fSplitPoint.fX) {
116 right = false;
117 } else if(query.fLeft >= node->fSplitPoint.fX) {
118 left = false;
119 }
120 bool top = true;
121 bool bottom = true;
122 if (query.fBottom < node->fSplitPoint.fY) {
123 bottom = false;
124 } else if(query.fTop >= node->fSplitPoint.fY) {
125 top = false;
126 }
127 // search all the active quadrants
128 if (top && left) {
129 search(node->fChildren[0], query, results);
130 }
131 if (top && right) {
132 search(node->fChildren[1], query, results);
133 }
134 if (bottom && left) {
135 search(node->fChildren[2], query, results);
136 }
137 if (bottom && right) {
138 search(node->fChildren[3], query, results);
139 }
140 }
142 void SkQuadTree::clear(Node* node) {
143 // first clear the entries of this node
144 fEntryPool.releaseAll(&node->fEntries);
145 // recurse into and clear all child nodes
146 for(int index=0; index<kChildCount; ++index) {
147 Node* child = node->fChildren[index];
148 node->fChildren[index] = NULL;
149 if (NULL != child) {
150 clear(child);
151 fNodePool.release(child);
152 }
153 }
154 }
156 int SkQuadTree::getDepth(Node* node) const {
157 int maxDepth = 0;
158 if (NULL != node->fChildren[0]) {
159 for(int index=0; index<kChildCount; ++index) {
160 maxDepth = SkMax32(maxDepth, getDepth(node->fChildren[index]));
161 }
162 }
163 return maxDepth + 1;
164 }
166 void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
167 if (bounds.isEmpty()) {
168 SkASSERT(false);
169 return;
170 }
171 Entry* entry = fEntryPool.acquire();
172 entry->fData = data;
173 entry->fBounds = bounds;
174 ++fEntryCount;
175 if (fRoot->fEntries.isEmpty() && (NULL == fRoot->fChildren[0])) {
176 fDeferred.push(entry);
177 } else {
178 insert(fRoot, entry);
179 }
180 }
182 void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
183 SkASSERT(fDeferred.isEmpty());
184 SkASSERT(NULL != results);
185 if (SkIRect::Intersects(fRoot->fBounds, query)) {
186 search(fRoot, query, results);
187 }
188 }
190 void SkQuadTree::clear() {
191 fEntryCount = 0;
192 clear(fRoot);
193 }
195 int SkQuadTree::getDepth() const {
196 return getDepth(fRoot);
197 }
199 void SkQuadTree::rewindInserts() {
200 SkASSERT(fClient);
201 // Currently only supports deferred inserts
202 SkASSERT(fRoot->fEntries.isEmpty() && fRoot->fChildren[0] == NULL);
203 SkTInternalSList<Entry> entries;
204 entries.pushAll(&fDeferred);
205 while(!entries.isEmpty()) {
206 Entry* entry = entries.pop();
207 if (fClient->shouldRewind(entry->fData)) {
208 entry->fData = NULL;
209 fEntryPool.release(entry);
210 --fEntryCount;
211 } else {
212 fDeferred.push(entry);
213 }
214 }
215 }
217 void SkQuadTree::flushDeferredInserts() {
218 while(!fDeferred.isEmpty()) {
219 insert(fRoot, fDeferred.pop());
220 }
221 }
