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 "src/core/SkRTree.h"
9
10SkRTree::SkRTree() : fCount(0) {}
11
12void SkRTree::insert(const SkRect boundsArray[], int N) {
13 SkASSERT(0 == fCount);
14
15 std::vector<Branch> branches;
16 branches.reserve(N);
17
18 for (int i = 0; i < N; i++) {
19 const SkRect& bounds = boundsArray[i];
20 if (bounds.isEmpty()) {
21 continue;
22 }
23
24 Branch b;
25 b.fBounds = bounds;
26 b.fOpIndex = i;
27 branches.push_back(b);
28 }
29
30 fCount = (int)branches.size();
31 if (fCount) {
32 if (1 == fCount) {
33 fNodes.reserve(1);
34 Node* n = this->allocateNodeAtLevel(0);
35 n->fNumChildren = 1;
36 n->fChildren[0] = branches[0];
37 fRoot.fSubtree = n;
38 fRoot.fBounds = branches[0].fBounds;
39 } else {
40 fNodes.reserve(CountNodes(fCount));
41 fRoot = this->bulkLoad(&branches);
42 }
43 }
44}
45
46SkRTree::Node* SkRTree::allocateNodeAtLevel(uint16_t level) {
47 SkDEBUGCODE(Node* p = fNodes.data());
48 fNodes.push_back(Node{});
49 Node& out = fNodes.back();
50 SkASSERT(fNodes.data() == p); // If this fails, we didn't reserve() enough.
51 out.fNumChildren = 0;
52 out.fLevel = level;
53 return &out;
54}
55
56// This function parallels bulkLoad, but just counts how many nodes bulkLoad would allocate.
57int SkRTree::CountNodes(int branches) {
58 if (branches == 1) {
59 return 1;
60 }
61 int numBranches = branches / kMaxChildren;
62 int remainder = branches % kMaxChildren;
63 if (remainder > 0) {
64 numBranches++;
65 if (remainder >= kMinChildren) {
66 remainder = 0;
67 } else {
68 remainder = kMinChildren - remainder;
69 }
70 }
71 int currentBranch = 0;
72 int nodes = 0;
73 while (currentBranch < branches) {
74 int incrementBy = kMaxChildren;
75 if (remainder != 0) {
76 if (remainder <= kMaxChildren - kMinChildren) {
77 incrementBy -= remainder;
78 remainder = 0;
79 } else {
80 incrementBy = kMinChildren;
81 remainder -= kMaxChildren - kMinChildren;
82 }
83 }
84 nodes++;
85 currentBranch++;
86 for (int k = 1; k < incrementBy && currentBranch < branches; ++k) {
87 currentBranch++;
88 }
89 }
90 return nodes + CountNodes(nodes);
91}
92
93SkRTree::Branch SkRTree::bulkLoad(std::vector<Branch>* branches, int level) {
94 if (branches->size() == 1) { // Only one branch. It will be the root.
95 return (*branches)[0];
96 }
97
98 // We might sort our branches here, but we expect Blink gives us a reasonable x,y order.
99 // Skipping a call to sort (in Y) here resulted in a 17% win for recording with negligible
100 // difference in playback speed.
101 int numBranches = (int)branches->size() / kMaxChildren;
102 int remainder = (int)branches->size() % kMaxChildren;
103 int newBranches = 0;
104
105 if (remainder > 0) {
106 ++numBranches;
107 // If the remainder isn't enough to fill a node, we'll add fewer nodes to other branches.
108 if (remainder >= kMinChildren) {
109 remainder = 0;
110 } else {
111 remainder = kMinChildren - remainder;
112 }
113 }
114
115 int currentBranch = 0;
116 while (currentBranch < (int)branches->size()) {
117 int incrementBy = kMaxChildren;
118 if (remainder != 0) {
119 // if need be, omit some nodes to make up for remainder
120 if (remainder <= kMaxChildren - kMinChildren) {
121 incrementBy -= remainder;
122 remainder = 0;
123 } else {
124 incrementBy = kMinChildren;
125 remainder -= kMaxChildren - kMinChildren;
126 }
127 }
128 Node* n = allocateNodeAtLevel(level);
129 n->fNumChildren = 1;
130 n->fChildren[0] = (*branches)[currentBranch];
131 Branch b;
132 b.fBounds = (*branches)[currentBranch].fBounds;
133 b.fSubtree = n;
134 ++currentBranch;
135 for (int k = 1; k < incrementBy && currentBranch < (int)branches->size(); ++k) {
136 b.fBounds.join((*branches)[currentBranch].fBounds);
137 n->fChildren[k] = (*branches)[currentBranch];
138 ++n->fNumChildren;
139 ++currentBranch;
140 }
141 (*branches)[newBranches] = b;
142 ++newBranches;
143 }
144 branches->resize(newBranches);
145 return this->bulkLoad(branches, level + 1);
146}
147
148void SkRTree::search(const SkRect& query, std::vector<int>* results) const {
149 if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) {
150 this->search(fRoot.fSubtree, query, results);
151 }
152}
153
154void SkRTree::search(Node* node, const SkRect& query, std::vector<int>* results) const {
155 for (int i = 0; i < node->fNumChildren; ++i) {
156 if (SkRect::Intersects(node->fChildren[i].fBounds, query)) {
157 if (0 == node->fLevel) {
158 results->push_back(node->fChildren[i].fOpIndex);
159 } else {
160 this->search(node->fChildren[i].fSubtree, query, results);
161 }
162 }
163 }
164}
165
166size_t SkRTree::bytesUsed() const {
167 size_t byteCount = sizeof(SkRTree);
168
169 byteCount += fNodes.capacity() * sizeof(Node);
170
171 return byteCount;
172}
173