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