Cut down SkBBH API more.

src/core/SkRTree.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkRTree.h"
 #include "SkTSort.h"
 
@@ skipping 26 matching lines @@
     SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
              static_cast<int>(SK_MaxU16));
     SkASSERT((maxChildren + 1) / 2 >= minChildren);
     this->validate();
 }
 
 SkRTree::~SkRTree() {
     this->clear();
 }
 
-void SkRTree::insert(unsigned opIndex, const SkRect& fbounds, bool defer) {
-    SkIRect bounds;
-    if (fbounds.isLargest()) {
-        bounds.setLargest();
-    } else {
-        fbounds.roundOut(&bounds);
-    }
+void SkRTree::insert(SkAutoTMalloc<SkRect>* boundsArray, int N) {
+    this->validate();
 
-    this->validate();
-    if (bounds.isEmpty()) {
-        SkASSERT(false);
-        return;
-    }
-    Branch newBranch;
-    newBranch.fBounds = bounds;
-    newBranch.fChild.opIndex = opIndex;
-    if (this->isEmpty()) {
-        // since a bulk-load into an existing tree is as of yet unimplemented (and arguably not
-        // of vital importance right now), we only batch up inserts if the tree is empty.
-        if (defer) {
-            fDeferredInserts.push(newBranch);
-            return;
-        } else {
-            fRoot.fChild.subtree = allocateNode(0);
-            fRoot.fChild.subtree->fNumChildren = 0;
+    // Since a bulk-load into an existing tree is as of yet unimplemented (and arguably not
+    // of vital importance right now), we only batch up inserts if the tree is empty.
+    const bool bulkLoad = this->isEmpty();
+    SkTDArray<Branch> deferred;
+    deferred.setReserve(bulkLoad ? N : 0);
+
+    for (int i = 0; i < N; i++) {
+        SkIRect bounds;
+        (*boundsArray)[i].roundOut(&bounds);
+        if (bounds.isEmpty()) {
+            continue;
+        }
+        fCount++;
+
+        Branch newBranch;
+        newBranch.fBounds = bounds;
+        newBranch.fChild.opIndex = i;
+
+        if (bulkLoad) {
+            deferred.push(newBranch);
+            continue;
+        }
+

[robertphillips, 2014/10/24 18:52:45]

In this case the tree isn't empty. So I think this allocateNode will do bad
things.

[mtklein, 2014/10/24 19:05:48]

I've just asserted this->isEmpty() and deleted the non-empty path.

+        fRoot.fChild.subtree = allocateNode(0);
+        fRoot.fChild.subtree->fNumChildren = 0;
+

[robertphillips, 2014/10/24 18:52:45]

this-> ?

+        Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch);
+        fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
+        if (newSibling) {
+            Node* oldRoot = fRoot.fChild.subtree;
+            Node* newRoot = this->allocateNode(oldRoot->fLevel + 1);
+            newRoot->fNumChildren = 2;
+            *newRoot->child(0) = fRoot;
+            *newRoot->child(1) = *newSibling;
+            fRoot.fChild.subtree = newRoot;
+            fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
         }
     }
 
-    Branch* newSibling = insert(fRoot.fChild.subtree, &newBranch);
-    fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
-
-    if (newSibling) {
-        Node* oldRoot = fRoot.fChild.subtree;
-        Node* newRoot = this->allocateNode(oldRoot->fLevel + 1);
-        newRoot->fNumChildren = 2;
-        *newRoot->child(0) = fRoot;
-        *newRoot->child(1) = *newSibling;
-        fRoot.fChild.subtree = newRoot;
-        fRoot.fBounds = this->computeBounds(fRoot.fChild.subtree);
+    if (bulkLoad && fCount > 0) {
+        SkASSERT(fCount == deferred.count());
+        if (1 == fCount) {

[robertphillips, 2014/10/24 18:52:45]

this-> ?

[mtklein, 2014/10/24 19:05:48]

Done.

+            fRoot.fChild.subtree = allocateNode(0);
+            fRoot.fChild.subtree->fNumChildren = 0;
+            this->insert(fRoot.fChild.subtree, &deferred[0]);
+            fRoot.fBounds = deferred[0].fBounds;
+        } else {
+            fRoot = this->bulkLoad(&deferred);
+        }
     }
-
-    ++fCount;
     this->validate();
 }
 
-void SkRTree::flushDeferredInserts() {
-    this->validate();
-    if (this->isEmpty() && fDeferredInserts.count() > 0) {
-        fCount = fDeferredInserts.count();
-        if (1 == fCount) {
-            fRoot.fChild.subtree = allocateNode(0);
-            fRoot.fChild.subtree->fNumChildren = 0;
-            this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]);
-            fRoot.fBounds = fDeferredInserts[0].fBounds;
-        } else {
-            fRoot = this->bulkLoad(&fDeferredInserts);
-        }
-    } else {
-        // TODO: some algorithm for bulk loading into an already populated tree
-        SkASSERT(0 == fDeferredInserts.count());
-    }
-    fDeferredInserts.rewind();
-    this->validate();
-}
-
 void SkRTree::search(const SkRect& fquery, SkTDArray<unsigned>* results) const {
     SkIRect query;
     fquery.roundOut(&query);
     this->validate();
-    SkASSERT(0 == fDeferredInserts.count());  // If this fails, you should have flushed.
     if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) {
         this->search(fRoot.fChild.subtree, query, results);
     }
     this->validate();
 }
 
 void SkRTree::clear() {
     this->validate();
     fNodes.reset();
-    fDeferredInserts.rewind();
     fCount = 0;
     this->validate();
 }
 
 SkRTree::Node* SkRTree::allocateNode(uint16_t level) {
     Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize));
     out->fNumChildren = 0;
     out->fLevel = level;
     return out;
 }
@@ skipping 335 matching lines @@
 
 // Expand 'out' to include 'joinWith'
 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) {
     // since we check for empty bounds on insert, we know we'll never have empty rects
     // and we can save the empty check that SkIRect::join requires
     if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; }
     if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; }
     if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; }
     if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; }
 }