11f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com/* 21f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Copyright 2012 Google Inc. 31f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * 41f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * Use of this source code is governed by a BSD-style license that can be 51f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com * found in the LICENSE file. 61f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com */ 71f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 81f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#include "SkRTree.h" 91f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#include "SkTSort.h" 101f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 111f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comstatic inline uint32_t get_area(const SkIRect& rect); 121f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comstatic inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2); 131f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comstatic inline uint32_t get_margin(const SkIRect& rect); 141f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comstatic inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2); 151f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comstatic inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out); 161f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 171f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com/////////////////////////////////////////////////////////////////////////////////////////////////// 181f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 198c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.comSkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio, 208c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com bool sortWhenBulkLoading) { 211f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren && 221f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) { 238c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLoading); 241f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 251f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return NULL; 261f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 271f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 288c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.comSkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, 298c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com bool sortWhenBulkLoading) 301f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com : fMinChildren(minChildren) 311f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com , fMaxChildren(maxChildren) 321f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren) 331f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com , fCount(0) 34b839f0f6a92db9bcdbf8aa8004f20b0c0000111crileya@google.com , fNodes(fNodeSize * 256) 358c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com , fAspectRatio(aspectRatio) 368c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com , fSortWhenBulkLoading(sortWhenBulkLoading) { 376c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren < 381f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com static_cast<int>(SK_MaxU16)); 391f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT((maxChildren + 1) / 2 >= minChildren); 401f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->validate(); 411f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 421f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 431f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comSkRTree::~SkRTree() { 441f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->clear(); 451f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 461f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 47533eb782edaa0b6fece6166d3001edf72ec39f11mtkleinvoid SkRTree::insert(void* data, const SkRect& fbounds, bool defer) { 48533eb782edaa0b6fece6166d3001edf72ec39f11mtklein SkIRect bounds; 49533eb782edaa0b6fece6166d3001edf72ec39f11mtklein if (fbounds.isLargest()) { 50533eb782edaa0b6fece6166d3001edf72ec39f11mtklein bounds.setLargest(); 51533eb782edaa0b6fece6166d3001edf72ec39f11mtklein } else { 52533eb782edaa0b6fece6166d3001edf72ec39f11mtklein fbounds.roundOut(&bounds); 53533eb782edaa0b6fece6166d3001edf72ec39f11mtklein } 54533eb782edaa0b6fece6166d3001edf72ec39f11mtklein 551f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->validate(); 566c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com if (bounds.isEmpty()) { 571f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(false); 581f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return; 591f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 601f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Branch newBranch; 611f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com newBranch.fBounds = bounds; 621f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com newBranch.fChild.data = data; 631f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (this->isEmpty()) { 641f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // since a bulk-load into an existing tree is as of yet unimplemented (and arguably not 651f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // of vital importance right now), we only batch up inserts if the tree is empty. 661f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (defer) { 671f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fDeferredInserts.push(newBranch); 681f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return; 691f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 701f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fRoot.fChild.subtree = allocateNode(0); 711f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fRoot.fChild.subtree->fNumChildren = 0; 721f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 731f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 741f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 751f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch); 761f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree); 771f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 7849f085dddff10473b6ebf832a974288300224e60bsalomon if (newSibling) { 791f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Node* oldRoot = fRoot.fChild.subtree; 801f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Node* newRoot = this->allocateNode(oldRoot->fLevel + 1); 811f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com newRoot->fNumChildren = 2; 821f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com *newRoot->child(0) = fRoot; 831f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com *newRoot->child(1) = *newSibling; 841f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fRoot.fChild.subtree = newRoot; 851f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree); 861f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 871f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 881f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com ++fCount; 891f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->validate(); 901f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 911f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 921f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comvoid SkRTree::flushDeferredInserts() { 931f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->validate(); 941f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (this->isEmpty() && fDeferredInserts.count() > 0) { 951f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fCount = fDeferredInserts.count(); 961f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (1 == fCount) { 971f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fRoot.fChild.subtree = allocateNode(0); 981f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fRoot.fChild.subtree->fNumChildren = 0; 991f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]); 1001f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fRoot.fBounds = fDeferredInserts[0].fBounds; 1011f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 1021f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fRoot = this->bulkLoad(&fDeferredInserts); 1031f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 1041f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 1051f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // TODO: some algorithm for bulk loading into an already populated tree 1061f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(0 == fDeferredInserts.count()); 1071f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 1081f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fDeferredInserts.rewind(); 1091f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->validate(); 1101f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 1111f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 112533eb782edaa0b6fece6166d3001edf72ec39f11mtkleinvoid SkRTree::search(const SkRect& fquery, SkTDArray<void*>* results) const { 113533eb782edaa0b6fece6166d3001edf72ec39f11mtklein SkIRect query; 114533eb782edaa0b6fece6166d3001edf72ec39f11mtklein fquery.roundOut(&query); 1151f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->validate(); 1168875a0413686eb3dc9f7d7d18a2cee9076aade54mtklein SkASSERT(0 == fDeferredInserts.count()); // If this fails, you should have flushed. 1171f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) { 1181f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->search(fRoot.fChild.subtree, query, results); 1191f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 1201f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->validate(); 1211f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 1221f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1231f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comvoid SkRTree::clear() { 1241f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->validate(); 1251f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fNodes.reset(); 1261f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fDeferredInserts.rewind(); 1271f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com fCount = 0; 1281f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->validate(); 1291f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 1301f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1311f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comSkRTree::Node* SkRTree::allocateNode(uint16_t level) { 1321f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize)); 1331f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com out->fNumChildren = 0; 1341f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com out->fLevel = level; 1351f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return out; 1361f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 1371f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1381f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comSkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) { 1391f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Branch* toInsert = branch; 1401f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (root->fLevel != level) { 1411f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int childIndex = this->chooseSubtree(root, branch); 1421f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level); 1431f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com root->child(childIndex)->fBounds = this->computeBounds( 1441f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com root->child(childIndex)->fChild.subtree); 1451f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 14649f085dddff10473b6ebf832a974288300224e60bsalomon if (toInsert) { 1471f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (root->fNumChildren == fMaxChildren) { 1481f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // handle overflow by splitting. TODO: opportunistic reinsertion 1491f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1501f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // decide on a distribution to divide with 1511f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Node* newSibling = this->allocateNode(root->fLevel); 1521f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1); 1531f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int i = 0; i < fMaxChildren; ++i) { 1541f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com toDivide[i] = *root->child(i); 1551f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 1561f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com toDivide[fMaxChildren] = *toInsert; 1571f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int splitIndex = this->distributeChildren(toDivide); 1581f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1591f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // divide up the branches 1601f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com root->fNumChildren = splitIndex; 1611f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com newSibling->fNumChildren = fMaxChildren + 1 - splitIndex; 1621f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int i = 0; i < splitIndex; ++i) { 1631f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com *root->child(i) = toDivide[i]; 1641f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 1651f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int i = splitIndex; i < fMaxChildren + 1; ++i) { 1661f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com *newSibling->child(i - splitIndex) = toDivide[i]; 1671f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 1681f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkDELETE_ARRAY(toDivide); 1691f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1701f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // pass the new sibling branch up to the parent 1711f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com branch->fChild.subtree = newSibling; 1721f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com branch->fBounds = this->computeBounds(newSibling); 1731f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return branch; 1741f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 1751f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com *root->child(root->fNumChildren) = *toInsert; 1761f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com ++root->fNumChildren; 1771f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return NULL; 1781f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 1791f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 1801f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return NULL; 1811f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 1821f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 1831f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comint SkRTree::chooseSubtree(Node* root, Branch* branch) { 1841f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(!root->isLeaf()); 1851f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (1 < root->fLevel) { 1861f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // root's child pointers do not point to leaves, so minimize area increase 1871f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t minAreaIncrease = SK_MaxS32; 1881f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t minArea = SK_MaxS32; 1891f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t bestSubtree = -1; 1901f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int i = 0; i < root->fNumChildren; ++i) { 1911f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com const SkIRect& subtreeBounds = root->child(i)->fBounds; 1921f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBounds); 1931f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // break ties in favor of subtree with smallest area 1941f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrease && 1951f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) { 1961f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com minAreaIncrease = areaIncrease; 1971f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com minArea = get_area(subtreeBounds); 1981f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com bestSubtree = i; 1991f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 2001f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 2011f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(-1 != bestSubtree); 2021f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return bestSubtree; 2031f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else if (1 == root->fLevel) { 2041f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // root's child pointers do point to leaves, so minimize overlap increase 2051f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t minOverlapIncrease = SK_MaxS32; 2061f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t minAreaIncrease = SK_MaxS32; 2071f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t bestSubtree = -1; 2081f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int32_t i = 0; i < root->fNumChildren; ++i) { 2091f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com const SkIRect& subtreeBounds = root->child(i)->fBounds; 2101f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkIRect expandedBounds = subtreeBounds; 2111f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com join_no_empty_check(branch->fBounds, &expandedBounds); 2121f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t overlap = 0; 2131f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int32_t j = 0; j < root->fNumChildren; ++j) { 2141f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (j == i) continue; 2151f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // Note: this would be more correct if we subtracted the original pre-expanded 2161f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // overlap, but computing overlaps is expensive and omitting it doesn't seem to 2171f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // hurt query performance. See get_overlap_increase() 2181f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com overlap += get_overlap(expandedBounds, root->child(j)->fBounds); 2191f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 2201f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // break ties with lowest area increase 2211f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease && 2226c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) < 2231f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com minAreaIncrease)) { 2241f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com minOverlapIncrease = overlap; 2251f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com minAreaIncrease = get_area_increase(branch->fBounds, subtreeBounds); 2261f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com bestSubtree = i; 2271f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 2281f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 2291f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return bestSubtree; 2301f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 2311f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(false); 2321f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return 0; 2331f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 2341f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 2351f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 2361f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comSkIRect SkRTree::computeBounds(Node* n) { 2371f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkIRect r = n->child(0)->fBounds; 2381f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int i = 1; i < n->fNumChildren; ++i) { 2391f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com join_no_empty_check(n->child(i)->fBounds, &r); 2401f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 2411f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return r; 2421f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 2431f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 2441f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comint SkRTree::distributeChildren(Branch* children) { 2451f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // We have two sides to sort by on each of two axes: 2461f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com const static SortSide sorts[2][2] = { 2471f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com {&SkIRect::fLeft, &SkIRect::fRight}, 2481f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com {&SkIRect::fTop, &SkIRect::fBottom} 2491f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com }; 2501f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 2511f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // We want to choose an axis to split on, then a distribution along that axis; we'll need 2521f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // three pieces of info: the split axis, the side to sort by on that axis, and the index 2531f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // to split the sorted array on. 2541f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t sortSide = -1; 2551f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t k = -1; 2561f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t axis = -1; 2571f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t bestS = SK_MaxS32; 2581f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 2591f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // Evaluate each axis, we want the min summed margin-value (s) over all distributions 2601f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int i = 0; i < 2; ++i) { 2611f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t minOverlap = SK_MaxS32; 2621f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t minArea = SK_MaxS32; 2631f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t axisBestK = 0; 2641f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t axisBestSide = 0; 2651f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t s = 0; 2661f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 2671f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // Evaluate each sort 2681f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int j = 0; j < 2; ++j) { 269e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j])); 2701f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 2711f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // Evaluate each split index 2721f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) { 2731f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkIRect r1 = children[0].fBounds; 2741f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkIRect r2 = children[fMinChildren + k - 1].fBounds; 2751f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) { 2761f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com join_no_empty_check(children[l].fBounds, &r1); 2776c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com } 2781f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) { 2791f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com join_no_empty_check(children[l].fBounds, &r2); 2801f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 2811f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 2821f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t area = get_area(r1) + get_area(r2); 2831f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int32_t overlap = get_overlap(r1, r2); 2841f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com s += get_margin(r1) + get_margin(r2); 2851f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 2861f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (overlap < minOverlap || (overlap == minOverlap && area < minArea)) { 2871f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com minOverlap = overlap; 2881f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com minArea = area; 2891f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com axisBestSide = j; 2901f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com axisBestK = k; 2911f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 2921f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 2931f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 2941f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 2951f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (s < bestS) { 2961f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com bestS = s; 2971f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com axis = i; 2981f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com sortSide = axisBestSide; 2991f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com k = axisBestK; 3001f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 3011f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 3021f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 3031f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // replicate the sort of the winning distribution, (we can skip this if the last 3041f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // sort ended up being best) 3051f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (!(axis == 1 && sortSide == 1)) { 306e83e994da4add978d1b7f0bc9d6df6099098a55bbungeman@google.com SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide])); 3071f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 3086c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com 3091f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return fMinChildren - 1 + k; 3101f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 3111f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 3121f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comvoid SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* results) const { 3131f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int i = 0; i < root->fNumChildren; ++i) { 3141f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) { 3151f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (root->isLeaf()) { 3161f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com results->push(root->child(i)->fChild.data); 3171f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 3181f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com this->search(root->child(i)->fChild.subtree, query, results); 3191f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 3201f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 3211f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 3221f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 3231f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 3241f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comSkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) { 3251f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (branches->count() == 1) { 3261f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // Only one branch: it will be the root 3271f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Branch out = (*branches)[0]; 3281f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com branches->rewind(); 3291f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return out; 3301f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 3318c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com // We sort the whole list by y coordinates, if we are told to do so. 3328c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com // 3338c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com // We expect Webkit / Blink to give us a reasonable x,y order. 3348c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com // Avoiding this call resulted in a 17% win for recording with 3358c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com // negligible difference in playback speed. 3368c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com if (fSortWhenBulkLoading) { 3378c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkTQSort(branches->begin(), branches->end() - 1, RectLessY()); 3388c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com } 3396c778164a743f8760dca251524d51848548b436fskia.committer@gmail.com 3401f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int numBranches = branches->count() / fMaxChildren; 3411f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int remainder = branches->count() % fMaxChildren; 3421f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int newBranches = 0; 3431f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 3441f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (0 != remainder) { 3451f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com ++numBranches; 3461f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to 3471f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // some other branches to make up for it 3481f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (remainder >= fMinChildren) { 3491f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com remainder = 0; 3501f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 3511f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com remainder = fMinChildren - remainder; 3521f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 3531f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 3541f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 355e1ca705cac4b946993f6cbf798e2a0ba27e739f3reed@google.com int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) * 356b839f0f6a92db9bcdbf8aa8004f20b0c0000111crileya@google.com SkScalarInvert(fAspectRatio))); 357e1ca705cac4b946993f6cbf798e2a0ba27e739f3reed@google.com int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / 3580ab786515fea21a3427095948a372f185400c7d3rileya@google.com SkIntToScalar(numStrips)); 3591f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int currentBranch = 0; 3601f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 3611f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int i = 0; i < numStrips; ++i) { 3628c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com // Once again, if we are told to do so, we sort by x. 3638c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com if (fSortWhenBulkLoading) { 3648c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com int begin = currentBranch; 3658c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder, 3668c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com (fMaxChildren - fMinChildren) * numTiles); 3678c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com if (end > branches->count()) { 3688c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com end = branches->count(); 3698c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com } 3701f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 3718c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com // Now we sort horizontal strips of rectangles by their x coords 3728c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX()); 3738c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com } 3741f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 375b839f0f6a92db9bcdbf8aa8004f20b0c0000111crileya@google.com for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) { 3761f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int incrementBy = fMaxChildren; 3771f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (remainder != 0) { 3781f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // if need be, omit some nodes to make up for remainder 3791f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (remainder <= fMaxChildren - fMinChildren) { 3801f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com incrementBy -= remainder; 3811f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com remainder = 0; 3821f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 3831f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com incrementBy = fMinChildren; 3841f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com remainder -= fMaxChildren - fMinChildren; 3851f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 3861f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 3871f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Node* n = allocateNode(level); 3881f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com n->fNumChildren = 1; 3891f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com *n->child(0) = (*branches)[currentBranch]; 3901f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com Branch b; 3911f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com b.fBounds = (*branches)[currentBranch].fBounds; 3921f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com b.fChild.subtree = n; 3931f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com ++currentBranch; 3941f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) { 3951f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com b.fBounds.join((*branches)[currentBranch].fBounds); 3961f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com *n->child(k) = (*branches)[currentBranch]; 3971f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com ++n->fNumChildren; 3981f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com ++currentBranch; 3991f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 4001f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com (*branches)[newBranches] = b; 4011f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com ++newBranches; 4021f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 4031f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 4041f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com branches->setCount(newBranches); 4051f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return this->bulkLoad(branches, level + 1); 4061f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 4071f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 4081f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 4098875a0413686eb3dc9f7d7d18a2cee9076aade54mtkleinvoid SkRTree::validate() const { 4101f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#ifdef SK_DEBUG 4111f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (this->isEmpty()) { 4121f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return; 4131f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 414adacc7067ad617cdc7bbef39192ca80f4b4d27f9robertphillips@google.com SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true)); 4151f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com#endif 4161f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 4171f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 4188875a0413686eb3dc9f7d7d18a2cee9076aade54mtkleinint SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) const { 4191f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // make sure the pointer is pointing to a valid place 4201f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(fNodes.contains(static_cast<void*>(root))); 4211f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 4221f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (isRoot) { 4231f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // If the root of this subtree is the overall root, we have looser standards: 4241f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (root->isLeaf()) { 4251f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildren); 4261f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 4271f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren); 4281f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 4291f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 4301f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren); 4311f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 4321f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 4331f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int i = 0; i < root->fNumChildren; ++i) { 4341f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(bounds.contains(root->child(i)->fBounds)); 4351f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 4361f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 4371f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (root->isLeaf()) { 4381f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(0 == root->fLevel); 4391f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return root->fNumChildren; 4401f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } else { 4411f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com int childCount = 0; 4421f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com for (int i = 0; i < root->fNumChildren; ++i) { 4431f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1); 4441f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com childCount += this->validateSubtree(root->child(i)->fChild.subtree, 4451f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com root->child(i)->fBounds); 4461f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 4471f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return childCount; 4481f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com } 4491f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 4501f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 4514b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.orgvoid SkRTree::rewindInserts() { 4524b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org SkASSERT(this->isEmpty()); // Currently only supports deferred inserts 4534b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org while (!fDeferredInserts.isEmpty() && 4544b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org fClient->shouldRewind(fDeferredInserts.top().fChild.data)) { 4554b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org fDeferredInserts.pop(); 4564b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org } 4574b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org} 4584b32bd53c63b245707822ae83e3215863303bf43commit-bot@chromium.org 4591f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com/////////////////////////////////////////////////////////////////////////////////////////////////// 4601f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 4611f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comstatic inline uint32_t get_area(const SkIRect& rect) { 4621f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return rect.width() * rect.height(); 4631f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 4641f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 4651f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comstatic inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) { 4661f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // I suspect there's a more efficient way of computing this... 4671f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) * 4681f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop, rect2.fTop)); 4691f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 4701f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 4711f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com// Get the margin (aka perimeter) 4721f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comstatic inline uint32_t get_margin(const SkIRect& rect) { 4731f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return 2 * (rect.width() + rect.height()); 4741f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 4751f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 4761f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comstatic inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) { 4771f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com join_no_empty_check(rect1, &rect2); 4781f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com return get_area(rect2) - get_area(rect1); 4791f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 4801f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com 4811f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com// Expand 'out' to include 'joinWith' 4821f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.comstatic inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) { 4831f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // since we check for empty bounds on insert, we know we'll never have empty rects 4841f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com // and we can save the empty check that SkIRect::join requires 4851f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; } 4861f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; } 4871f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; } 4881f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; } 4891f45e934b68a5985b2127ec871ff593c3bfc7c2erileya@google.com} 490