| 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 26 matching lines...) Expand all Loading... |
| 37 SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren < | 37 SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren < |
| 38 static_cast<int>(SK_MaxU16)); | 38 static_cast<int>(SK_MaxU16)); |
| 39 SkASSERT((maxChildren + 1) / 2 >= minChildren); | 39 SkASSERT((maxChildren + 1) / 2 >= minChildren); |
| 40 this->validate(); | 40 this->validate(); |
| 41 } | 41 } |
| 42 | 42 |
| 43 SkRTree::~SkRTree() { | 43 SkRTree::~SkRTree() { |
| 44 this->clear(); | 44 this->clear(); |
| 45 } | 45 } |
| 46 | 46 |
| 47 void SkRTree::insert(void* data, const SkRect& fbounds, bool defer) { | 47 void SkRTree::insert(void* data, const SkIRect& bounds, bool defer) { |
| 48 SkIRect bounds; | |
| 49 if (fbounds.isLargest()) { | |
| 50 bounds.setLargest(); | |
| 51 } else { | |
| 52 fbounds.roundOut(&bounds); | |
| 53 } | |
| 54 | |
| 55 this->validate(); | 48 this->validate(); |
| 56 if (bounds.isEmpty()) { | 49 if (bounds.isEmpty()) { |
| 57 SkASSERT(false); | 50 SkASSERT(false); |
| 58 return; | 51 return; |
| 59 } | 52 } |
| 60 Branch newBranch; | 53 Branch newBranch; |
| 61 newBranch.fBounds = bounds; | 54 newBranch.fBounds = bounds; |
| 62 newBranch.fChild.data = data; | 55 newBranch.fChild.data = data; |
| 63 if (this->isEmpty()) { | 56 if (this->isEmpty()) { |
| 64 // since a bulk-load into an existing tree is as of yet unimplemented (a
nd arguably not | 57 // since a bulk-load into an existing tree is as of yet unimplemented (a
nd arguably not |
| (...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 102 fRoot = this->bulkLoad(&fDeferredInserts); | 95 fRoot = this->bulkLoad(&fDeferredInserts); |
| 103 } | 96 } |
| 104 } else { | 97 } else { |
| 105 // TODO: some algorithm for bulk loading into an already populated tree | 98 // TODO: some algorithm for bulk loading into an already populated tree |
| 106 SkASSERT(0 == fDeferredInserts.count()); | 99 SkASSERT(0 == fDeferredInserts.count()); |
| 107 } | 100 } |
| 108 fDeferredInserts.rewind(); | 101 fDeferredInserts.rewind(); |
| 109 this->validate(); | 102 this->validate(); |
| 110 } | 103 } |
| 111 | 104 |
| 112 void SkRTree::search(const SkRect& fquery, SkTDArray<void*>* results) const { | 105 void SkRTree::search(const SkIRect& query, SkTDArray<void*>* results) const { |
| 113 SkIRect query; | |
| 114 fquery.roundOut(&query); | |
| 115 this->validate(); | 106 this->validate(); |
| 116 SkASSERT(0 == fDeferredInserts.count()); // If this fails, you should have
flushed. | 107 SkASSERT(0 == fDeferredInserts.count()); // If this fails, you should have
flushed. |
| 117 if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query
)) { | 108 if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query
)) { |
| 118 this->search(fRoot.fChild.subtree, query, results); | 109 this->search(fRoot.fChild.subtree, query, results); |
| 119 } | 110 } |
| 120 this->validate(); | 111 this->validate(); |
| 121 } | 112 } |
| 122 | 113 |
| 123 void SkRTree::clear() { | 114 void SkRTree::clear() { |
| 124 this->validate(); | 115 this->validate(); |
| (...skipping 355 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 480 | 471 |
| 481 // Expand 'out' to include 'joinWith' | 472 // Expand 'out' to include 'joinWith' |
| 482 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) { | 473 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 | 474 // 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 | 475 // and we can save the empty check that SkIRect::join requires |
| 485 if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; } | 476 if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; } |
| 486 if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; } | 477 if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; } |
| 487 if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; } | 478 if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; } |
| 488 if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; } | 479 if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; } |
| 489 } | 480 } |
| OLD | NEW |