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
11static inline uint32_t get_area(const SkIRect& rect);
12static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2);
13static inline uint32_t get_margin(const SkIRect& rect);
14static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2);
15static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out);
16
17///////////////////////////////////////////////////////////////////////////////////////////////////
18
19SkRTree* 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
28SkRTree::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
43SkRTree::~SkRTree() {
44    this->clear();
45}
46
47void 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
85void 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
105void 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
116void SkRTree::clear() {
117    this->validate();
118    fNodes.reset();
119    fDeferredInserts.rewind();
120    fCount = 0;
121    this->validate();
122}
123
124SkRTree::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
131SkRTree::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
176int 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
229SkIRect 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
237int 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
305void 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
317SkRTree::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 = SkScalarCeil(SkScalarSqrt(SkIntToScalar(numBranches) *
349                                     SkScalarInvert(fAspectRatio)));
350        int numTiles = SkScalarCeil(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
402void 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
411int 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
444void 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
454static inline uint32_t get_area(const SkIRect& rect) {
455    return rect.width() * rect.height();
456}
457
458static 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)
465static inline uint32_t get_margin(const SkIRect& rect) {
466    return 2 * (rect.width() + rect.height());
467}
468
469static 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'
475static 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}
483