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 
SkRTree()10 SkRTree::SkRTree() : fCount(0) {}
11 
insert(const SkRect boundsArray[],int N)12 void 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 
allocateNodeAtLevel(uint16_t level)46 SkRTree::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.
CountNodes(int branches)57 int 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 
bulkLoad(std::vector<Branch> * branches,int level)93 SkRTree::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 
search(const SkRect & query,std::vector<int> * results) const148 void 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 
search(Node * node,const SkRect & query,std::vector<int> * results) const154 void 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 
bytesUsed() const166 size_t SkRTree::bytesUsed() const {
167     size_t byteCount = sizeof(SkRTree);
168 
169     byteCount += fNodes.capacity() * sizeof(Node);
170 
171     return byteCount;
172 }
173