1/*
2 * Copyright 2014 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 "SkQuadTree.h"
9#include "SkTSort.h"
10#include <stdio.h>
11
12static const int kSplitThreshold = 8;
13
14enum {
15    kTopLeft,
16    kTopRight,
17    kBottomLeft,
18    kBottomRight,
19};
20enum {
21    kTopLeft_Bit = 1 << kTopLeft,
22    kTopRight_Bit = 1 << kTopRight,
23    kBottomLeft_Bit = 1 << kBottomLeft,
24    kBottomRight_Bit = 1 << kBottomRight,
25};
26enum {
27    kMaskLeft = kTopLeft_Bit | kBottomLeft_Bit,
28    kMaskRight = kTopRight_Bit | kBottomRight_Bit,
29    kMaskTop = kTopLeft_Bit | kTopRight_Bit,
30    kMaskBottom = kBottomLeft_Bit | kBottomRight_Bit,
31};
32
33static U8CPU child_intersect(const SkIRect& query, const SkIPoint& split) {
34    // fast quadrant test
35    U8CPU intersect = 0xf;
36    if (query.fRight <  split.fX) {
37        intersect &= ~kMaskRight;
38    } else if(query.fLeft >= split.fX) {
39        intersect &= ~kMaskLeft;
40    }
41    if (query.fBottom < split.fY) {
42        intersect &= ~kMaskBottom;
43    } else if(query.fTop >= split.fY) {
44        intersect &= ~kMaskTop;
45    }
46    return intersect;
47}
48
49SkQuadTree::SkQuadTree(const SkIRect& bounds) : fRoot(NULL) {
50    SkASSERT((bounds.width() * bounds.height()) > 0);
51    fRootBounds = bounds;
52}
53
54SkQuadTree::~SkQuadTree() {
55}
56
57void SkQuadTree::insert(Node* node, Entry* entry) {
58    // does it belong in a child?
59    if (NULL != node->fChildren[0]) {
60        switch(child_intersect(entry->fBounds, node->fSplitPoint)) {
61            case kTopLeft_Bit:
62                this->insert(node->fChildren[kTopLeft], entry);
63                return;
64            case kTopRight_Bit:
65                this->insert(node->fChildren[kTopRight], entry);
66                return;
67            case kBottomLeft_Bit:
68                this->insert(node->fChildren[kBottomLeft], entry);
69                return;
70            case kBottomRight_Bit:
71                this->insert(node->fChildren[kBottomRight], entry);
72                return;
73            default:
74                node->fEntries.push(entry);
75                return;
76        }
77    }
78    // No children yet, add to this node
79    node->fEntries.push(entry);
80    // should I split?
81    if (node->fEntries.getCount() > kSplitThreshold) {
82        this->split(node);
83    }
84}
85
86void SkQuadTree::split(Node* node) {
87    // Build all the children
88    node->fSplitPoint = SkIPoint::Make(node->fBounds.centerX(),
89                                       node->fBounds.centerY());
90    for(int index=0; index<kChildCount; ++index) {
91        node->fChildren[index] = fNodePool.acquire();
92    }
93    node->fChildren[0]->fBounds = SkIRect::MakeLTRB(
94        node->fBounds.fLeft,    node->fBounds.fTop,
95        node->fSplitPoint.fX,   node->fSplitPoint.fY);
96    node->fChildren[1]->fBounds = SkIRect::MakeLTRB(
97        node->fSplitPoint.fX,   node->fBounds.fTop,
98        node->fBounds.fRight,   node->fSplitPoint.fY);
99    node->fChildren[2]->fBounds = SkIRect::MakeLTRB(
100        node->fBounds.fLeft,    node->fSplitPoint.fY,
101        node->fSplitPoint.fX,   node->fBounds.fBottom);
102    node->fChildren[3]->fBounds = SkIRect::MakeLTRB(
103        node->fSplitPoint.fX,   node->fSplitPoint.fY,
104        node->fBounds.fRight,   node->fBounds.fBottom);
105    // reinsert all the entries of this node to allow child trickle
106    SkTInternalSList<Entry> entries;
107    entries.pushAll(&node->fEntries);
108    while(!entries.isEmpty()) {
109        this->insert(node, entries.pop());
110    }
111}
112
113void SkQuadTree::search(Node* node, const SkIRect& query,
114                        SkTDArray<void*>* results) const {
115    for (Entry* entry = node->fEntries.head(); NULL != entry;
116        entry = entry->getSListNext()) {
117        if (SkIRect::IntersectsNoEmptyCheck(entry->fBounds, query)) {
118            results->push(entry->fData);
119        }
120    }
121    if (NULL == node->fChildren[0]) {
122        return;
123    }
124    U8CPU intersect = child_intersect(query, node->fSplitPoint);
125    for(int index=0; index<kChildCount; ++index) {
126        if (intersect & (1 << index)) {
127            this->search(node->fChildren[index], query, results);
128        }
129    }
130}
131
132void SkQuadTree::clear(Node* node) {
133    // first clear the entries of this node
134    fEntryPool.releaseAll(&node->fEntries);
135    // recurse into and clear all child nodes
136    for(int index=0; index<kChildCount; ++index) {
137        Node* child = node->fChildren[index];
138        node->fChildren[index] = NULL;
139        if (NULL != child) {
140            this->clear(child);
141            fNodePool.release(child);
142        }
143    }
144}
145
146int SkQuadTree::getDepth(Node* node) const {
147    int maxDepth = 0;
148    if (NULL != node) {
149        for(int index=0; index<kChildCount; ++index) {
150            maxDepth = SkMax32(maxDepth, getDepth(node->fChildren[index]));
151        }
152    }
153    return maxDepth + 1;
154}
155
156void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
157    if (bounds.isEmpty()) {
158        SkASSERT(false);
159        return;
160    }
161    Entry* entry = fEntryPool.acquire();
162    entry->fData = data;
163    entry->fBounds = bounds;
164    if (NULL == fRoot) {
165        fDeferred.push(entry);
166    } else {
167        this->insert(fRoot, entry);
168    }
169}
170
171void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
172    SkASSERT(NULL != fRoot);
173    SkASSERT(NULL != results);
174    if (SkIRect::Intersects(fRootBounds, query)) {
175        this->search(fRoot, query, results);
176    }
177}
178
179void SkQuadTree::clear() {
180    this->flushDeferredInserts();
181    if (NULL != fRoot) {
182        this->clear(fRoot);
183        fNodePool.release(fRoot);
184        fRoot = NULL;
185    }
186    SkASSERT(fEntryPool.allocated() == fEntryPool.available());
187    SkASSERT(fNodePool.allocated() == fNodePool.available());
188}
189
190int SkQuadTree::getDepth() const {
191    return this->getDepth(fRoot);
192}
193
194void SkQuadTree::rewindInserts() {
195    SkASSERT(fClient);
196     // Currently only supports deferred inserts
197    SkASSERT(NULL == fRoot);
198    SkTInternalSList<Entry> entries;
199    entries.pushAll(&fDeferred);
200    while(!entries.isEmpty()) {
201        Entry* entry = entries.pop();
202        if (fClient->shouldRewind(entry->fData)) {
203            entry->fData = NULL;
204            fEntryPool.release(entry);
205        } else {
206            fDeferred.push(entry);
207        }
208    }
209}
210
211void SkQuadTree::flushDeferredInserts() {
212    if (NULL == fRoot) {
213        fRoot = fNodePool.acquire();
214        fRoot->fBounds = fRootBounds;
215    }
216    while(!fDeferred.isEmpty()) {
217        this->insert(fRoot, fDeferred.pop());
218    }
219}
220