The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/core/SkRTree.cpp

gfx/skia/trunk/src/core/SkRTree.cpp

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:4fe1cb840884
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 */
7
8 #include "SkRTree.h"
9 #include "SkTSort.h"
10
11 static inline uint32_t get_area(const SkIRect& rect);
12 static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2);
13 static inline uint32_t get_margin(const SkIRect& rect);
14 static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2);
15 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out);
16
17 ///////////////////////////////////////////////////////////////////////////////////////////////////
18
19 SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio,
20 bool sortWhenBulkLoading) {
21 if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren &&
22 minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) {
23 return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLoading);
24 }
25 return NULL;
26 }
27
28 SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio,
29 bool sortWhenBulkLoading)
30 : fMinChildren(minChildren)
31 , fMaxChildren(maxChildren)
32 , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren)
33 , fCount(0)
34 , fNodes(fNodeSize * 256)
35 , fAspectRatio(aspectRatio)
36 , fSortWhenBulkLoading(sortWhenBulkLoading) {
37 SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
38 static_cast<int>(SK_MaxU16));
39 SkASSERT((maxChildren + 1) / 2 >= minChildren);
40 this->validate();
41 }
42
43 SkRTree::~SkRTree() {
44 this->clear();
45 }
46
47 void SkRTree::insert(void* data, const SkIRect& bounds, bool defer) {
48 this->validate();
49 if (bounds.isEmpty()) {
50 SkASSERT(false);
51 return;
52 }
53 Branch newBranch;
54 newBranch.fBounds = bounds;
55 newBranch.fChild.data = data;
56 if (this->isEmpty()) {
57 // since a bulk-load into an existing tree is as of yet unimplemented (and arguably not
58 // of vital importance right now), we only batch up inserts if the tree is empty.
59 if (defer) {
60 fDeferredInserts.push(newBranch);
61 return;
62 } else {
63 fRoot.fChild.subtree = allocateNode(0);
64 fRoot.fChild.subtree->fNumChildren = 0;
65 }
66 }
67
68 Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch);
69 fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
70
71 if (NULL != newSibling) {
72 Node* oldRoot = fRoot.fChild.subtree;
73 Node* newRoot = this->allocateNode(oldRoot->fLevel + 1);
74 newRoot->fNumChildren = 2;
75 *newRoot->child(0) = fRoot;
76 *newRoot->child(1) = *newSibling;
77 fRoot.fChild.subtree = newRoot;
78 fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
79 }
80
81 ++fCount;
82 this->validate();
83 }
84
85 void SkRTree::flushDeferredInserts() {
86 this->validate();
87 if (this->isEmpty() && fDeferredInserts.count() > 0) {
88 fCount = fDeferredInserts.count();
89 if (1 == fCount) {
90 fRoot.fChild.subtree = allocateNode(0);
91 fRoot.fChild.subtree->fNumChildren = 0;
92 this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]);
93 fRoot.fBounds = fDeferredInserts[0].fBounds;
94 } else {
95 fRoot = this->bulkLoad(&fDeferredInserts);
96 }
97 } else {
98 // TODO: some algorithm for bulk loading into an already populated tree
99 SkASSERT(0 == fDeferredInserts.count());
100 }
101 fDeferredInserts.rewind();
102 this->validate();
103 }
104
105 void SkRTree::search(const SkIRect& query, SkTDArray<void*>* results) {
106 this->validate();
107 if (0 != fDeferredInserts.count()) {
108 this->flushDeferredInserts();
109 }
110 if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) {
111 this->search(fRoot.fChild.subtree, query, results);
112 }
113 this->validate();
114 }
115
116 void SkRTree::clear() {
117 this->validate();
118 fNodes.reset();
119 fDeferredInserts.rewind();
120 fCount = 0;
121 this->validate();
122 }
123
124 SkRTree::Node* SkRTree::allocateNode(uint16_t level) {
125 Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize));
126 out->fNumChildren = 0;
127 out->fLevel = level;
128 return out;
129 }
130
131 SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) {
132 Branch* toInsert = branch;
133 if (root->fLevel != level) {
134 int childIndex = this->chooseSubtree(root, branch);
135 toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level);
136 root->child(childIndex)->fBounds = this->computeBounds(
137 root->child(childIndex)->fChild.subtree);
138 }
139 if (NULL != toInsert) {
140 if (root->fNumChildren == fMaxChildren) {
141 // handle overflow by splitting. TODO: opportunistic reinsertion
142
143 // decide on a distribution to divide with
144 Node* newSibling = this->allocateNode(root->fLevel);
145 Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1);
146 for (int i = 0; i < fMaxChildren; ++i) {
147 toDivide[i] = *root->child(i);
148 }
149 toDivide[fMaxChildren] = *toInsert;
150 int splitIndex = this->distributeChildren(toDivide);
151
152 // divide up the branches
153 root->fNumChildren = splitIndex;
154 newSibling->fNumChildren = fMaxChildren + 1 - splitIndex;
155 for (int i = 0; i < splitIndex; ++i) {
156 *root->child(i) = toDivide[i];
157 }
158 for (int i = splitIndex; i < fMaxChildren + 1; ++i) {
159 *newSibling->child(i - splitIndex) = toDivide[i];
160 }
161 SkDELETE_ARRAY(toDivide);
162
163 // pass the new sibling branch up to the parent
164 branch->fChild.subtree = newSibling;
165 branch->fBounds = this->computeBounds(newSibling);
166 return branch;
167 } else {
168 *root->child(root->fNumChildren) = *toInsert;
169 ++root->fNumChildren;
170 return NULL;
171 }
172 }
173 return NULL;
174 }
175
176 int SkRTree::chooseSubtree(Node* root, Branch* branch) {
177 SkASSERT(!root->isLeaf());
178 if (1 < root->fLevel) {
179 // root's child pointers do not point to leaves, so minimize area increase
180 int32_t minAreaIncrease = SK_MaxS32;
181 int32_t minArea = SK_MaxS32;
182 int32_t bestSubtree = -1;
183 for (int i = 0; i < root->fNumChildren; ++i) {
184 const SkIRect& subtreeBounds = root->child(i)->fBounds;
185 int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBounds);
186 // break ties in favor of subtree with smallest area
187 if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrease &&
188 static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) {
189 minAreaIncrease = areaIncrease;
190 minArea = get_area(subtreeBounds);
191 bestSubtree = i;
192 }
193 }
194 SkASSERT(-1 != bestSubtree);
195 return bestSubtree;
196 } else if (1 == root->fLevel) {
197 // root's child pointers do point to leaves, so minimize overlap increase
198 int32_t minOverlapIncrease = SK_MaxS32;
199 int32_t minAreaIncrease = SK_MaxS32;
200 int32_t bestSubtree = -1;
201 for (int32_t i = 0; i < root->fNumChildren; ++i) {
202 const SkIRect& subtreeBounds = root->child(i)->fBounds;
203 SkIRect expandedBounds = subtreeBounds;
204 join_no_empty_check(branch->fBounds, &expandedBounds);
205 int32_t overlap = 0;
206 for (int32_t j = 0; j < root->fNumChildren; ++j) {
207 if (j == i) continue;
208 // Note: this would be more correct if we subtracted the original pre-expanded
209 // overlap, but computing overlaps is expensive and omitting it doesn't seem to
210 // hurt query performance. See get_overlap_increase()
211 overlap += get_overlap(expandedBounds, root->child(j)->fBounds);
212 }
213 // break ties with lowest area increase
214 if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease &&
215 static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) <
216 minAreaIncrease)) {
217 minOverlapIncrease = overlap;
218 minAreaIncrease = get_area_increase(branch->fBounds, subtreeBounds);
219 bestSubtree = i;
220 }
221 }
222 return bestSubtree;
223 } else {
224 SkASSERT(false);
225 return 0;
226 }
227 }
228
229 SkIRect SkRTree::computeBounds(Node* n) {
230 SkIRect r = n->child(0)->fBounds;
231 for (int i = 1; i < n->fNumChildren; ++i) {
232 join_no_empty_check(n->child(i)->fBounds, &r);
233 }
234 return r;
235 }
236
237 int SkRTree::distributeChildren(Branch* children) {
238 // We have two sides to sort by on each of two axes:
239 const static SortSide sorts[2][2] = {
240 {&SkIRect::fLeft, &SkIRect::fRight},
241 {&SkIRect::fTop, &SkIRect::fBottom}
242 };
243
244 // We want to choose an axis to split on, then a distribution along that axis; we'll need
245 // three pieces of info: the split axis, the side to sort by on that axis, and the index
246 // to split the sorted array on.
247 int32_t sortSide = -1;
248 int32_t k = -1;
249 int32_t axis = -1;
250 int32_t bestS = SK_MaxS32;
251
252 // Evaluate each axis, we want the min summed margin-value (s) over all distributions
253 for (int i = 0; i < 2; ++i) {
254 int32_t minOverlap = SK_MaxS32;
255 int32_t minArea = SK_MaxS32;
256 int32_t axisBestK = 0;
257 int32_t axisBestSide = 0;
258 int32_t s = 0;
259
260 // Evaluate each sort
261 for (int j = 0; j < 2; ++j) {
262 SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j]));
263
264 // Evaluate each split index
265 for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) {
266 SkIRect r1 = children[0].fBounds;
267 SkIRect r2 = children[fMinChildren + k - 1].fBounds;
268 for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) {
269 join_no_empty_check(children[l].fBounds, &r1);
270 }
271 for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) {
272 join_no_empty_check(children[l].fBounds, &r2);
273 }
274
275 int32_t area = get_area(r1) + get_area(r2);
276 int32_t overlap = get_overlap(r1, r2);
277 s += get_margin(r1) + get_margin(r2);
278
279 if (overlap < minOverlap || (overlap == minOverlap && area < minArea)) {
280 minOverlap = overlap;
281 minArea = area;
282 axisBestSide = j;
283 axisBestK = k;
284 }
285 }
286 }
287
288 if (s < bestS) {
289 bestS = s;
290 axis = i;
291 sortSide = axisBestSide;
292 k = axisBestK;
293 }
294 }
295
296 // replicate the sort of the winning distribution, (we can skip this if the last
297 // sort ended up being best)
298 if (!(axis == 1 && sortSide == 1)) {
299 SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide]));
300 }
301
302 return fMinChildren - 1 + k;
303 }
304
305 void SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* results) const {
306 for (int i = 0; i < root->fNumChildren; ++i) {
307 if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) {
308 if (root->isLeaf()) {
309 results->push(root->child(i)->fChild.data);
310 } else {
311 this->search(root->child(i)->fChild.subtree, query, results);
312 }
313 }
314 }
315 }
316
317 SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
318 if (branches->count() == 1) {
319 // Only one branch: it will be the root
320 Branch out = (*branches)[0];
321 branches->rewind();
322 return out;
323 } else {
324 // We sort the whole list by y coordinates, if we are told to do so.
325 //
326 // We expect Webkit / Blink to give us a reasonable x,y order.
327 // Avoiding this call resulted in a 17% win for recording with
328 // negligible difference in playback speed.
329 if (fSortWhenBulkLoading) {
330 SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
331 }
332
333 int numBranches = branches->count() / fMaxChildren;
334 int remainder = branches->count() % fMaxChildren;
335 int newBranches = 0;
336
337 if (0 != remainder) {
338 ++numBranches;
339 // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to
340 // some other branches to make up for it
341 if (remainder >= fMinChildren) {
342 remainder = 0;
343 } else {
344 remainder = fMinChildren - remainder;
345 }
346 }
347
348 int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) *
349 SkScalarInvert(fAspectRatio)));
350 int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) /
351 SkIntToScalar(numStrips));
352 int currentBranch = 0;
353
354 for (int i = 0; i < numStrips; ++i) {
355 // Once again, if we are told to do so, we sort by x.
356 if (fSortWhenBulkLoading) {
357 int begin = currentBranch;
358 int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder,
359 (fMaxChildren - fMinChildren) * numTiles);
360 if (end > branches->count()) {
361 end = branches->count();
362 }
363
364 // Now we sort horizontal strips of rectangles by their x coords
365 SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX());
366 }
367
368 for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
369 int incrementBy = fMaxChildren;
370 if (remainder != 0) {
371 // if need be, omit some nodes to make up for remainder
372 if (remainder <= fMaxChildren - fMinChildren) {
373 incrementBy -= remainder;
374 remainder = 0;
375 } else {
376 incrementBy = fMinChildren;
377 remainder -= fMaxChildren - fMinChildren;
378 }
379 }
380 Node* n = allocateNode(level);
381 n->fNumChildren = 1;
382 *n->child(0) = (*branches)[currentBranch];
383 Branch b;
384 b.fBounds = (*branches)[currentBranch].fBounds;
385 b.fChild.subtree = n;
386 ++currentBranch;
387 for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
388 b.fBounds.join((*branches)[currentBranch].fBounds);
389 *n->child(k) = (*branches)[currentBranch];
390 ++n->fNumChildren;
391 ++currentBranch;
392 }
393 (*branches)[newBranches] = b;
394 ++newBranches;
395 }
396 }
397 branches->setCount(newBranches);
398 return this->bulkLoad(branches, level + 1);
399 }
400 }
401
402 void SkRTree::validate() {
403 #ifdef SK_DEBUG
404 if (this->isEmpty()) {
405 return;
406 }
407 SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true));
408 #endif
409 }
410
411 int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) {
412 // make sure the pointer is pointing to a valid place
413 SkASSERT(fNodes.contains(static_cast<void*>(root)));
414
415 if (isRoot) {
416 // If the root of this subtree is the overall root, we have looser standards:
417 if (root->isLeaf()) {
418 SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildren);
419 } else {
420 SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren);
421 }
422 } else {
423 SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren);
424 }
425
426 for (int i = 0; i < root->fNumChildren; ++i) {
427 SkASSERT(bounds.contains(root->child(i)->fBounds));
428 }
429
430 if (root->isLeaf()) {
431 SkASSERT(0 == root->fLevel);
432 return root->fNumChildren;
433 } else {
434 int childCount = 0;
435 for (int i = 0; i < root->fNumChildren; ++i) {
436 SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1);
437 childCount += this->validateSubtree(root->child(i)->fChild.subtree,
438 root->child(i)->fBounds);
439 }
440 return childCount;
441 }
442 }
443
444 void SkRTree::rewindInserts() {
445 SkASSERT(this->isEmpty()); // Currently only supports deferred inserts
446 while (!fDeferredInserts.isEmpty() &&
447 fClient->shouldRewind(fDeferredInserts.top().fChild.data)) {
448 fDeferredInserts.pop();
449 }
450 }
451
452 ///////////////////////////////////////////////////////////////////////////////////////////////////
453
454 static inline uint32_t get_area(const SkIRect& rect) {
455 return rect.width() * rect.height();
456 }
457
458 static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) {
459 // I suspect there's a more efficient way of computing this...
460 return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) *
461 SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop, rect2.fTop));
462 }
463
464 // Get the margin (aka perimeter)
465 static inline uint32_t get_margin(const SkIRect& rect) {
466 return 2 * (rect.width() + rect.height());
467 }
468
469 static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) {
470 join_no_empty_check(rect1, &rect2);
471 return get_area(rect2) - get_area(rect1);
472 }
473
474 // Expand 'out' to include 'joinWith'
475 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) {
476 // since we check for empty bounds on insert, we know we'll never have empty rects
477 // and we can save the empty check that SkIRect::join requires
478 if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; }
479 if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; }
480 if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; }
481 if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; }
482 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial