Cut down SkBBH API more.

  - The expected case is now a single bulk-load insert() call instead of N;
  - reserve() and flushDeferredInserts() can fold into insert() now;
  - SkBBH subclasses may take ownership of the bounds

This appears to be a performance no-op on both my Mac and N5.  I guess
even the simplest indirect branch predictor ("same as last time") can predict
the repeated virtual calls to SkBBH::insert() perfectly.

BUG=skia:

Review URL: https://codereview.chromium.org/670213002

6 files changed, 66 insertions, 143 deletions

diff --git a/src/core/SkBBoxHierarchy.h b/src/core/SkBBoxHierarchy.h
index 7246787de8..de8ea0b98a 100644
--- a/src/core/SkBBoxHierarchy.h
+++ b/src/core/SkBBoxHierarchy.h
@@ -1,4 +1,3 @@
-
 /*
  * Copyright 2012 Google Inc.
  *
@@ -10,45 +9,31 @@
 #define SkBBoxHierarchy_DEFINED
 
 #include "SkRect.h"
-#include "SkTDArray.h"
 #include "SkRefCnt.h"
+#include "SkTDArray.h"
+#include "SkTemplates.h"
 
 /**
- * Interface for a spatial data structure that associates user data with axis-aligned
- * bounding boxes, and allows efficient retrieval of intersections with query rectangles.
+ * Interface for a spatial data structure that stores axis-aligned bounding
+ * boxes and allows efficient retrieval of intersections with query rectangles.
  */
 class SkBBoxHierarchy : public SkRefCnt {
 public:
-    SK_DECLARE_INST_COUNT(SkBBoxHierarchy)
-
     SkBBoxHierarchy() {}
+    virtual ~SkBBoxHierarchy() {}
 
     /**
-     * Hint that <= opCount calls to insert() will be made.
-     */
-    virtual void reserve(unsigned opCount) {}
-
-    /**
-     * Insert opIndex and corresponding bounding box.
-     * @param opIndex Any value, will be returned in order.
-     * @param bounds The bounding box, should not be empty.
-     * @param defer Whether or not it is acceptable to delay insertion of this element (building up
-     *        an entire spatial data structure at once is often faster and produces better
-     *        structures than repeated inserts) until flushDeferredInserts is called or the first
-     *        search.
-     */
-    virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer = false) = 0;
-
-    /**
-     * If any insertions have been deferred, force them to be inserted.
+     * Insert N bounding boxes into the hierarchy.
+     * The SkBBoxHierarchy may take ownership of boundsArray by calling detach().
      */
-    virtual void flushDeferredInserts() {}
+    virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) = 0;
 
     /**
-     * Populate results with sorted opIndex corresponding to bounding boxes that intersect query.
+     * Populate results with the indices of bounding boxes interesecting that query.
      */
     virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const = 0;
 
+    SK_DECLARE_INST_COUNT(SkBBoxHierarchy)
 private:
     typedef SkRefCnt INHERITED;
 };
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index 4a081db26d..93f914276f 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -44,68 +44,39 @@ 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) {
+    SkASSERT(this->isEmpty());
     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;
+
+    SkTDArray<Branch> deferred;
+    deferred.setReserve(N);
+
+    for (int i = 0; i < N; i++) {
+        SkIRect bounds;
+        (*boundsArray)[i].roundOut(&bounds);
+        if (bounds.isEmpty()) {
+            continue;
         }
-    }
 
-    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 newBranch;
+        newBranch.fBounds = bounds;
+        newBranch.fChild.opIndex = i;
 
-    ++fCount;
-    this->validate();
-}
+        deferred.push(newBranch);
+    }
 
-void SkRTree::flushDeferredInserts() {
-    this->validate();
-    if (this->isEmpty() && fDeferredInserts.count() > 0) {
-        fCount = fDeferredInserts.count();
+    fCount = deferred.count();
+    if (fCount) {
         if (1 == fCount) {
-            fRoot.fChild.subtree = allocateNode(0);
+            fRoot.fChild.subtree = this->allocateNode(0);
             fRoot.fChild.subtree->fNumChildren = 0;
-            this->insert(fRoot.fChild.subtree, &fDeferredInserts[0]);
-            fRoot.fBounds = fDeferredInserts[0].fBounds;
+            this->insert(fRoot.fChild.subtree, &deferred[0]);
+            fRoot.fBounds = deferred[0].fBounds;
         } else {
-            fRoot = this->bulkLoad(&fDeferredInserts);
+            fRoot = this->bulkLoad(&deferred);
         }
-    } else {
-        // TODO: some algorithm for bulk loading into an already populated tree
-        SkASSERT(0 == fDeferredInserts.count());
     }
-    fDeferredInserts.rewind();
+
     this->validate();
 }
 
@@ -113,7 +84,6 @@ 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);
     }
@@ -123,7 +93,6 @@ void SkRTree::search(const SkRect& fquery, SkTDArray<unsigned>* results) const {
 void SkRTree::clear() {
     this->validate();
     fNodes.reset();
-    fDeferredInserts.rewind();
     fCount = 0;
     this->validate();
 }
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 0d88804c30..00c6c8941d 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -59,24 +59,7 @@ public:
             bool orderWhenBulkLoading = true);
     virtual ~SkRTree();
 
-    /**
-     * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
-     * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
-     * a large batch of nodes at once, which tends to be faster and produce a better tree).
-     *  @param opIndex The data value
-     *  @param bounds The corresponding bounding box
-     *  @param defer Can this insert be deferred? (this may be ignored)
-     */
-    virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer = false) SK_OVERRIDE;
-
-    /**
-     * If any inserts have been deferred, this will add them into the tree
-     */
-    virtual void flushDeferredInserts() SK_OVERRIDE;
-
-    /**
-     * Given a query rectangle, populates the passed-in array with the elements it intersects
-     */
+    virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) SK_OVERRIDE;
     virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
 
     void clear();
@@ -179,7 +162,6 @@ private:
 
     Branch fRoot;
     SkChunkAlloc fNodes;
-    SkTDArray<Branch> fDeferredInserts;
     SkScalar fAspectRatio;
     bool fSortWhenBulkLoading;
 
diff --git a/src/core/SkRecordDraw.cpp b/src/core/SkRecordDraw.cpp
index 12579e9b65..5981245c01 100644
--- a/src/core/SkRecordDraw.cpp
+++ b/src/core/SkRecordDraw.cpp
@@ -164,13 +164,7 @@ public:
 
         // Finally feed all stored bounds into the BBH.  They'll be returned in this order.
         SkASSERT(bbh);
-        bbh->reserve(record.count());
-        for (unsigned i = 0; i < record.count(); i++) {
-            if (!fBounds[i].isEmpty()) {
-                bbh->insert(i, fBounds[i], true/*ok to defer*/);
-            }
-        }
-        bbh->flushDeferredInserts();
+        bbh->insert(&fBounds, record.count());
     }
 
     template <typename T> void operator()(const T& op) {
diff --git a/src/core/SkTileGrid.cpp b/src/core/SkTileGrid.cpp
index 10782c4d6d..e285cccd0b 100644
--- a/src/core/SkTileGrid.cpp
+++ b/src/core/SkTileGrid.cpp
@@ -23,7 +23,7 @@ SkTileGrid::~SkTileGrid() {
     SkDELETE_ARRAY(fTiles);
 }
 
-void SkTileGrid::reserve(unsigned opCount) {
+void SkTileGrid::reserve(int opCount) {
     if (fXTiles * fYTiles == 0) {
         return;  // A tileless tile grid is nonsensical, but happens in at least cc_unittests.
     }
@@ -44,7 +44,7 @@ void SkTileGrid::reserve(unsigned opCount) {
     // than if we made no setReserve() calls, but time spent in insert() drops by about 50%.
 }
 
-void SkTileGrid::flushDeferredInserts() {
+void SkTileGrid::shrinkToFit() {
     for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles); tile++) {
         tile->shrinkToFit();
     }
@@ -70,30 +70,35 @@ void SkTileGrid::userToGrid(const SkRect& user, SkIRect* grid) const {
     grid->fBottom = SkPin32(user.bottom() * fInvHeight, 0, fYTiles - 1);
 }
 
-void SkTileGrid::insert(unsigned opIndex, const SkRect& originalBounds, bool) {
-    SkRect bounds = originalBounds;
-    bounds.outset(fMarginWidth, fMarginHeight);
-    this->commonAdjust(&bounds);
+void SkTileGrid::insert(SkAutoTMalloc<SkRect>* boundsArray, int N) {
+    this->reserve(N);
 
-    // TODO(mtklein): can we assert this instead to save an intersection in Release mode,
-    // or just allow out-of-bound insertions to insert anyway (clamped to nearest tile)?
-    if (!SkRect::Intersects(bounds, fGridBounds)) {
-        return;
-    }
+    for (int i = 0; i < N; i++) {
+        SkRect bounds = (*boundsArray)[i];
+        bounds.outset(fMarginWidth, fMarginHeight);
+        this->commonAdjust(&bounds);
 
-    SkIRect grid;
-    this->userToGrid(bounds, &grid);
-
-    // This is just a loop over y then x.  This compiles to a slightly faster and
-    // more compact loop than if we just did fTiles[y * fXTiles + x].push(opIndex).
-    SkTDArray<unsigned>* row = &fTiles[grid.fTop * fXTiles + grid.fLeft];
-    for (int y = 0; y <= grid.fBottom - grid.fTop; y++) {
-        SkTDArray<unsigned>* tile = row;
-        for (int x = 0; x <= grid.fRight - grid.fLeft; x++) {
-            (tile++)->push(opIndex);
+        // TODO(mtklein): can we assert this instead to save an intersection in Release mode,
+        // or just allow out-of-bound insertions to insert anyway (clamped to nearest tile)?
+        if (!SkRect::Intersects(bounds, fGridBounds)) {
+            continue;
+        }
+
+        SkIRect grid;
+        this->userToGrid(bounds, &grid);
+
+        // This is just a loop over y then x.  This compiles to a slightly faster and
+        // more compact loop than if we just did fTiles[y * fXTiles + x].push(i).
+        SkTDArray<unsigned>* row = &fTiles[grid.fTop * fXTiles + grid.fLeft];
+        for (int y = 0; y <= grid.fBottom - grid.fTop; y++) {
+            SkTDArray<unsigned>* tile = row;
+            for (int x = 0; x <= grid.fRight - grid.fLeft; x++) {
+                (tile++)->push(i);
+            }
+            row += fXTiles;
         }
-        row += fXTiles;
     }
+    this->shrinkToFit();
 }
 
 // Number of tiles for which data is allocated on the stack in
diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h
index fd7584fd9c..99218c77be 100644
--- a/src/core/SkTileGrid.h
+++ b/src/core/SkTileGrid.h
@@ -19,30 +19,18 @@
 class SkTileGrid : public SkBBoxHierarchy {
 public:
     SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGridInfo& info);
-
     virtual ~SkTileGrid();
 
-    /**
-     * Insert a opIndex value and corresponding bounding box
-     * @param opIndex
-     * @param bounds The bounding box, should not be empty.
-     * @param defer  Ignored; SkTileGrid does not defer insertions.
-     */
-    virtual void insert(unsigned opIndex, const SkRect& bounds, bool) SK_OVERRIDE;
-
-    /**
-     * Populate 'results' with opIndexes corresponding to bounding boxes that intersect 'query'.
-     * This will be fastest if the query is an exact match to a single grid tile.
-     */
+    virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) SK_OVERRIDE;
     virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
 
     // For testing.
     int tileCount(int x, int y) { return fTiles[y * fXTiles + x].count(); }
 
-    virtual void reserve(unsigned opCount) SK_OVERRIDE;
-    virtual void flushDeferredInserts() SK_OVERRIDE;
-
 private:
+    void reserve(int);
+    void shrinkToFit();
+
     void commonAdjust(SkRect*) const;
     void userToGrid(const SkRect&, SkIRect* grid) const;