OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #include "SkRTree.h" | 8 #include "SkRTree.h" |
9 #include "SkTSort.h" | 9 #include "SkTSort.h" |
10 | 10 |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
68 return; | 68 return; |
69 } else { | 69 } else { |
70 fRoot.fChild.subtree = allocateNode(0); | 70 fRoot.fChild.subtree = allocateNode(0); |
71 fRoot.fChild.subtree->fNumChildren = 0; | 71 fRoot.fChild.subtree->fNumChildren = 0; |
72 } | 72 } |
73 } | 73 } |
74 | 74 |
75 Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch); | 75 Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch); |
76 fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree); | 76 fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree); |
77 | 77 |
78 if (NULL != newSibling) { | 78 if (newSibling) { |
79 Node* oldRoot = fRoot.fChild.subtree; | 79 Node* oldRoot = fRoot.fChild.subtree; |
80 Node* newRoot = this->allocateNode(oldRoot->fLevel + 1); | 80 Node* newRoot = this->allocateNode(oldRoot->fLevel + 1); |
81 newRoot->fNumChildren = 2; | 81 newRoot->fNumChildren = 2; |
82 *newRoot->child(0) = fRoot; | 82 *newRoot->child(0) = fRoot; |
83 *newRoot->child(1) = *newSibling; | 83 *newRoot->child(1) = *newSibling; |
84 fRoot.fChild.subtree = newRoot; | 84 fRoot.fChild.subtree = newRoot; |
85 fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree); | 85 fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree); |
86 } | 86 } |
87 | 87 |
88 ++fCount; | 88 ++fCount; |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
136 } | 136 } |
137 | 137 |
138 SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) { | 138 SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) { |
139 Branch* toInsert = branch; | 139 Branch* toInsert = branch; |
140 if (root->fLevel != level) { | 140 if (root->fLevel != level) { |
141 int childIndex = this->chooseSubtree(root, branch); | 141 int childIndex = this->chooseSubtree(root, branch); |
142 toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch,
level); | 142 toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch,
level); |
143 root->child(childIndex)->fBounds = this->computeBounds( | 143 root->child(childIndex)->fBounds = this->computeBounds( |
144 root->child(childIndex)->fChild.subtree); | 144 root->child(childIndex)->fChild.subtree); |
145 } | 145 } |
146 if (NULL != toInsert) { | 146 if (toInsert) { |
147 if (root->fNumChildren == fMaxChildren) { | 147 if (root->fNumChildren == fMaxChildren) { |
148 // handle overflow by splitting. TODO: opportunistic reinsertion | 148 // handle overflow by splitting. TODO: opportunistic reinsertion |
149 | 149 |
150 // decide on a distribution to divide with | 150 // decide on a distribution to divide with |
151 Node* newSibling = this->allocateNode(root->fLevel); | 151 Node* newSibling = this->allocateNode(root->fLevel); |
152 Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1); | 152 Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1); |
153 for (int i = 0; i < fMaxChildren; ++i) { | 153 for (int i = 0; i < fMaxChildren; ++i) { |
154 toDivide[i] = *root->child(i); | 154 toDivide[i] = *root->child(i); |
155 } | 155 } |
156 toDivide[fMaxChildren] = *toInsert; | 156 toDivide[fMaxChildren] = *toInsert; |
(...skipping 323 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
480 | 480 |
481 // Expand 'out' to include 'joinWith' | 481 // Expand 'out' to include 'joinWith' |
482 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) { | 482 static 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 | 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 | 484 // and we can save the empty check that SkIRect::join requires |
485 if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; } | 485 if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; } |
486 if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; } | 486 if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; } |
487 if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; } | 487 if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; } |
488 if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; } | 488 if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; } |
489 } | 489 } |
OLD | NEW |