| 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 |