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