make SkBBH a public interface

I don't necessarily like this long term, but in the short term Flutter
would like to record pictures using their own type separate from
SkRTree.  This makes SkBBoxHierarchy public, and converts it to use
other public types (SkTDArray -> vector).

Change-Id: I29c5ef9da7d641d8f4ba18522b168ddf7cefe84f
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/270387
Commit-Queue: Mike Klein <mtklein@google.com>
Reviewed-by: Mike Reed <reed@google.com>
diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp
index 95fd89d..1c7f9b4 100644
--- a/bench/RTreeBench.cpp
+++ b/bench/RTreeBench.cpp
@@ -79,7 +79,7 @@
     void onDraw(int loops, SkCanvas* canvas) override {
         SkRandom rand;
         for (int i = 0; i < loops; ++i) {
-            SkTDArray<int> hits;
+            std::vector<int> hits;
             SkRect query;
             query.fLeft   = rand.nextRangeF(0, GENERATE_EXTENTS);
             query.fTop    = rand.nextRangeF(0, GENERATE_EXTENTS);
diff --git a/bench/nanobench.cpp b/bench/nanobench.cpp
index 04be13e..3647451 100644
--- a/bench/nanobench.cpp
+++ b/bench/nanobench.cpp
@@ -31,7 +31,6 @@
 #include "include/core/SkSurface.h"
 #include "include/core/SkTime.h"
 #include "src/core/SkAutoMalloc.h"
-#include "src/core/SkBBoxHierarchy.h"
 #include "src/core/SkColorSpacePriv.h"
 #include "src/core/SkLeanWindows.h"
 #include "src/core/SkOSFile.h"
diff --git a/dm/DMSrcSink.h b/dm/DMSrcSink.h
index 174f69d..d07b151 100644
--- a/dm/DMSrcSink.h
+++ b/dm/DMSrcSink.h
@@ -15,7 +15,6 @@
 #include "include/core/SkCanvas.h"
 #include "include/core/SkData.h"
 #include "include/core/SkPicture.h"
-#include "src/core/SkBBoxHierarchy.h"
 #include "src/utils/SkMultiPictureDocument.h"
 #include "tools/flags/CommonFlagsConfig.h"
 #include "tools/gpu/MemoryCache.h"
diff --git a/gn/core.gni b/gn/core.gni
index 923890e..c3a4471 100644
--- a/gn/core.gni
+++ b/gn/core.gni
@@ -112,7 +112,6 @@
   "$_src/core/SkAutoPixmapStorage.h",
   "$_src/core/SkAutoPixmapStorage.cpp",
   "$_src/core/SkBBHFactory.cpp",
-  "$_src/core/SkBBoxHierarchy.h",
   "$_src/core/SkBitmap.cpp",
   "$_src/core/SkBitmapCache.cpp",
   "$_src/core/SkBitmapController.cpp",
diff --git a/include/core/SkBBHFactory.h b/include/core/SkBBHFactory.h
index 5d0dd0a..7e88847 100644
--- a/include/core/SkBBHFactory.h
+++ b/include/core/SkBBHFactory.h
@@ -8,15 +8,30 @@
 #ifndef SkBBHFactory_DEFINED
 #define SkBBHFactory_DEFINED
 
+#include "include/core/SkRect.h"
 #include "include/core/SkRefCnt.h"
 #include "include/core/SkTypes.h"
+#include <vector>
 
 class SkBBoxHierarchy : public SkRefCnt {
 public:
     SkBBoxHierarchy() {}
     virtual ~SkBBoxHierarchy() {}
 
-    // Future public APIs may go here.
+    /**
+     * Insert N bounding boxes into the hierarchy.
+     */
+    virtual void insert(const SkRect[], int N) = 0;
+
+    /**
+     * Populate results with the indices of bounding boxes intersecting that query.
+     */
+    virtual void search(const SkRect& query, std::vector<int>* results) const = 0;
+
+    /**
+     * Return approximate size in memory of *this.
+     */
+    virtual size_t bytesUsed() const = 0;
 };
 
 class SK_API SkBBHFactory {
diff --git a/src/core/SkBBoxHierarchy.h b/src/core/SkBBoxHierarchy.h
deleted file mode 100644
index fc1cd10..0000000
--- a/src/core/SkBBoxHierarchy.h
+++ /dev/null
@@ -1,36 +0,0 @@
-/*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#ifndef SkBBoxHierarchy_DEFINED
-#define SkBBoxHierarchy_DEFINED
-
-#include "include/core/SkBBHFactory.h"
-#include "include/core/SkRect.h"
-#include "include/private/SkTDArray.h"
-
-/**
- * Interface for a spatial data structure that stores axis-aligned bounding
- * boxes and allows efficient retrieval of intersections with query rectangles.
- */
-class SkBBoxHierarchy_Base : public SkBBoxHierarchy {
-public:
-    SkBBoxHierarchy_Base() {}
-
-    /**
-     * Insert N bounding boxes into the hierarchy.
-     */
-    virtual void insert(const SkRect[], int N) = 0;
-
-    /**
-     * Populate results with the indices of bounding boxes interesecting that query.
-     */
-    virtual void search(const SkRect& query, SkTDArray<int>* results) const = 0;
-
-    virtual size_t bytesUsed() const = 0;
-};
-
-#endif
diff --git a/src/core/SkBigPicture.cpp b/src/core/SkBigPicture.cpp
index fbdd57e..a197ac1 100644
--- a/src/core/SkBigPicture.cpp
+++ b/src/core/SkBigPicture.cpp
@@ -5,7 +5,7 @@
  * found in the LICENSE file.
  */
 
-#include "src/core/SkBBoxHierarchy.h"
+#include "include/core/SkBBHFactory.h"
 #include "src/core/SkBigPicture.h"
 #include "src/core/SkPictureCommon.h"
 #include "src/core/SkRecord.h"
@@ -57,7 +57,7 @@
 int    SkBigPicture::approximateOpCount()   const { return fRecord->count(); }
 size_t SkBigPicture::approximateBytesUsed() const {
     size_t bytes = sizeof(*this) + fRecord->bytesUsed() + fApproxBytesUsedBySubPictures;
-    if (fBBH) { bytes += static_cast<const SkBBoxHierarchy_Base*>(fBBH.get())->bytesUsed(); }
+    if (fBBH) { bytes += fBBH->bytesUsed(); }
     return bytes;
 }
 
diff --git a/src/core/SkPictureRecorder.cpp b/src/core/SkPictureRecorder.cpp
index ea785e9..0022d98 100644
--- a/src/core/SkPictureRecorder.cpp
+++ b/src/core/SkPictureRecorder.cpp
@@ -61,9 +61,9 @@
 
     if (fRecord->count() == 0) {
         auto pic = fMiniRecorder->detachAsPicture(fBBH ? nullptr : &fCullRect);
-        if (auto bbh = (SkBBoxHierarchy_Base*)fBBH.get()) {
+        if (fBBH) {
             SkRect bounds = pic->cullRect();  // actually the computed bounds, not fCullRect.
-            bbh->insert(&bounds, 1);
+            fBBH->insert(&bounds, 1);
         }
         fBBH.reset(nullptr);
         return pic;
@@ -81,8 +81,7 @@
         SkAutoTMalloc<SkRect> bounds(fRecord->count());
         SkRecordFillBounds(fCullRect, *fRecord, bounds);
 
-        auto bbh = static_cast<SkBBoxHierarchy_Base*>(fBBH.get());
-        bbh->insert(bounds, fRecord->count());
+        fBBH->insert(bounds, fRecord->count());
 
         // Now that we've calculated content bounds, we can update fCullRect, often trimming it.
         SkRect bbhBound = SkRect::MakeEmpty();
@@ -137,7 +136,7 @@
     if (fBBH.get()) {
         SkAutoTMalloc<SkRect> bounds(fRecord->count());
         SkRecordFillBounds(fCullRect, *fRecord, bounds);
-        static_cast<SkBBoxHierarchy_Base*>(fBBH.get())->insert(bounds, fRecord->count());
+        fBBH->insert(bounds, fRecord->count());
     }
 
     sk_sp<SkDrawable> drawable =
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index f4a3511..783c95f 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -12,8 +12,8 @@
 void SkRTree::insert(const SkRect boundsArray[], int N) {
     SkASSERT(0 == fCount);
 
-    SkTDArray<Branch> branches;
-    branches.setReserve(N);
+    std::vector<Branch> branches;
+    branches.reserve(N);
 
     for (int i = 0; i < N; i++) {
         const SkRect& bounds = boundsArray[i];
@@ -21,34 +21,36 @@
             continue;
         }
 
-        Branch* b = branches.push();
-        b->fBounds = bounds;
-        b->fOpIndex = i;
+        Branch b;
+        b.fBounds = bounds;
+        b.fOpIndex = i;
+        branches.push_back(b);
     }
 
-    fCount = branches.count();
+    fCount = (int)branches.size();
     if (fCount) {
         if (1 == fCount) {
-            fNodes.setReserve(1);
+            fNodes.reserve(1);
             Node* n = this->allocateNodeAtLevel(0);
             n->fNumChildren = 1;
             n->fChildren[0] = branches[0];
             fRoot.fSubtree = n;
             fRoot.fBounds  = branches[0].fBounds;
         } else {
-            fNodes.setReserve(CountNodes(fCount));
+            fNodes.reserve(CountNodes(fCount));
             fRoot = this->bulkLoad(&branches);
         }
     }
 }
 
 SkRTree::Node* SkRTree::allocateNodeAtLevel(uint16_t level) {
-    SkDEBUGCODE(Node* p = fNodes.begin());
-    Node* out = fNodes.push();
-    SkASSERT(fNodes.begin() == p);  // If this fails, we didn't setReserve() enough.
-    out->fNumChildren = 0;
-    out->fLevel = level;
-    return out;
+    SkDEBUGCODE(Node* p = fNodes.data());
+    fNodes.push_back(Node{});
+    Node& out = fNodes.back();
+    SkASSERT(fNodes.data() == p);  // If this fails, we didn't reserve() enough.
+    out.fNumChildren = 0;
+    out.fLevel = level;
+    return &out;
 }
 
 // This function parallels bulkLoad, but just counts how many nodes bulkLoad would allocate.
@@ -88,16 +90,16 @@
     return nodes + CountNodes(nodes);
 }
 
-SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
-    if (branches->count() == 1) { // Only one branch.  It will be the root.
+SkRTree::Branch SkRTree::bulkLoad(std::vector<Branch>* branches, int level) {
+    if (branches->size() == 1) { // Only one branch.  It will be the root.
         return (*branches)[0];
     }
 
     // We might sort our branches here, but we expect Blink gives us a reasonable x,y order.
     // Skipping a call to sort (in Y) here resulted in a 17% win for recording with negligible
     // difference in playback speed.
-    int numBranches = branches->count() / kMaxChildren;
-    int remainder   = branches->count() % kMaxChildren;
+    int numBranches = (int)branches->size() / kMaxChildren;
+    int remainder   = (int)branches->size() % kMaxChildren;
     int newBranches = 0;
 
     if (remainder > 0) {
@@ -111,7 +113,7 @@
     }
 
     int currentBranch = 0;
-    while (currentBranch < branches->count()) {
+    while (currentBranch < (int)branches->size()) {
         int incrementBy = kMaxChildren;
         if (remainder != 0) {
             // if need be, omit some nodes to make up for remainder
@@ -130,7 +132,7 @@
         b.fBounds = (*branches)[currentBranch].fBounds;
         b.fSubtree = n;
         ++currentBranch;
-        for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
+        for (int k = 1; k < incrementBy && currentBranch < (int)branches->size(); ++k) {
             b.fBounds.join((*branches)[currentBranch].fBounds);
             n->fChildren[k] = (*branches)[currentBranch];
             ++n->fNumChildren;
@@ -139,17 +141,17 @@
         (*branches)[newBranches] = b;
         ++newBranches;
     }
-    branches->setCount(newBranches);
+    branches->resize(newBranches);
     return this->bulkLoad(branches, level + 1);
 }
 
-void SkRTree::search(const SkRect& query, SkTDArray<int>* results) const {
+void SkRTree::search(const SkRect& query, std::vector<int>* results) const {
     if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) {
         this->search(fRoot.fSubtree, query, results);
     }
 }
 
-void SkRTree::search(Node* node, const SkRect& query, SkTDArray<int>* results) const {
+void SkRTree::search(Node* node, const SkRect& query, std::vector<int>* results) const {
     for (int i = 0; i < node->fNumChildren; ++i) {
         if (SkRect::Intersects(node->fChildren[i].fBounds, query)) {
             if (0 == node->fLevel) {
@@ -164,7 +166,7 @@
 size_t SkRTree::bytesUsed() const {
     size_t byteCount = sizeof(SkRTree);
 
-    byteCount += fNodes.reserved() * sizeof(Node);
+    byteCount += fNodes.capacity() * sizeof(Node);
 
     return byteCount;
 }
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 735b945..03d55eb 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -8,9 +8,8 @@
 #ifndef SkRTree_DEFINED
 #define SkRTree_DEFINED
 
+#include "include/core/SkBBHFactory.h"
 #include "include/core/SkRect.h"
-#include "include/private/SkTDArray.h"
-#include "src/core/SkBBoxHierarchy.h"
 
 /**
  * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
@@ -28,12 +27,12 @@
  *  Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree:
  *      an efficient and robust access method for points and rectangles"
  */
-class SkRTree : public SkBBoxHierarchy_Base {
+class SkRTree : public SkBBoxHierarchy {
 public:
     SkRTree();
 
     void insert(const SkRect[], int N) override;
-    void search(const SkRect& query, SkTDArray<int>* results) const override;
+    void search(const SkRect& query, std::vector<int>* results) const override;
     size_t bytesUsed() const override;
 
     // Methods and constants below here are only public for tests.
@@ -64,10 +63,10 @@
         Branch fChildren[kMaxChildren];
     };
 
-    void search(Node* root, const SkRect& query, SkTDArray<int>* results) const;
+    void search(Node* root, const SkRect& query, std::vector<int>* results) const;
 
     // Consumes the input array.
-    Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
+    Branch bulkLoad(std::vector<Branch>* branches, int level = 0);
 
     // How many times will bulkLoad() call allocateNodeAtLevel()?
     static int CountNodes(int branches);
@@ -77,7 +76,7 @@
     // This is the count of data elements (rather than total nodes in the tree)
     int fCount;
     Branch fRoot;
-    SkTDArray<Node> fNodes;
+    std::vector<Node> fNodes;
 };
 
 #endif
diff --git a/src/core/SkRecordDraw.cpp b/src/core/SkRecordDraw.cpp
index e97729c..3d7b987 100644
--- a/src/core/SkRecordDraw.cpp
+++ b/src/core/SkRecordDraw.cpp
@@ -5,6 +5,7 @@
  * found in the LICENSE file.
  */
 
+#include "include/core/SkBBHFactory.h"
 #include "include/core/SkImage.h"
 #include "src/core/SkCanvasPriv.h"
 #include "src/core/SkRecordDraw.h"
@@ -27,11 +28,11 @@
         // lets us query the BBH.
         SkRect query = canvas->getLocalClipBounds();
 
-        SkTDArray<int> ops;
-        static_cast<const SkBBoxHierarchy_Base*>(bbh)->search(query, &ops);
+        std::vector<int> ops;
+        bbh->search(query, &ops);
 
         SkRecords::Draw draw(canvas, drawablePicts, drawables, drawableCount);
-        for (int i = 0; i < ops.count(); i++) {
+        for (int i = 0; i < (int)ops.size(); i++) {
             if (callback && callback->abort()) {
                 return;
             }
diff --git a/src/core/SkRecordDraw.h b/src/core/SkRecordDraw.h
index baffab5..4b3bc77 100644
--- a/src/core/SkRecordDraw.h
+++ b/src/core/SkRecordDraw.h
@@ -10,7 +10,6 @@
 
 #include "include/core/SkCanvas.h"
 #include "include/core/SkMatrix.h"
-#include "src/core/SkBBoxHierarchy.h"
 #include "src/core/SkBigPicture.h"
 #include "src/core/SkRecord.h"
 
diff --git a/src/core/SkRecordedDrawable.h b/src/core/SkRecordedDrawable.h
index 75502cd..2f8f6cc 100644
--- a/src/core/SkRecordedDrawable.h
+++ b/src/core/SkRecordedDrawable.h
@@ -8,7 +8,6 @@
 #define SkRecordedDrawable_DEFINED
 
 #include "include/core/SkDrawable.h"
-#include "src/core/SkBBoxHierarchy.h"
 #include "src/core/SkRecord.h"
 #include "src/core/SkRecorder.h"
 
diff --git a/src/ports/SkGlobalInitialization_default.cpp b/src/ports/SkGlobalInitialization_default.cpp
index 56e88a4..30d41da 100644
--- a/src/ports/SkGlobalInitialization_default.cpp
+++ b/src/ports/SkGlobalInitialization_default.cpp
@@ -14,6 +14,7 @@
 
 #else
 
+    #include "include/core/SkBBHFactory.h"
     #include "include/core/SkColorFilter.h"
     #include "include/core/SkPathEffect.h"
     #include "include/effects/Sk1DPathEffect.h"
diff --git a/tests/PictureBBHTest.cpp b/tests/PictureBBHTest.cpp
index 298f141..8fbeea3 100644
--- a/tests/PictureBBHTest.cpp
+++ b/tests/PictureBBHTest.cpp
@@ -10,7 +10,6 @@
 #include "include/core/SkPaint.h"
 #include "include/core/SkPicture.h"
 #include "include/core/SkPictureRecorder.h"
-#include "src/core/SkBBoxHierarchy.h"
 #include "src/core/SkRectPriv.h"
 
 #include "tests/Test.h"
diff --git a/tests/PictureTest.cpp b/tests/PictureTest.cpp
index 174c08d..6ab7e25 100644
--- a/tests/PictureTest.cpp
+++ b/tests/PictureTest.cpp
@@ -26,7 +26,6 @@
 #include "include/core/SkTypeface.h"
 #include "include/core/SkTypes.h"
 #include "include/utils/SkRandom.h"
-#include "src/core/SkBBoxHierarchy.h"
 #include "src/core/SkBigPicture.h"
 #include "src/core/SkClipOpPriv.h"
 #include "src/core/SkMiniRecorder.h"
@@ -659,12 +658,12 @@
     REPORTER_ASSERT(reporter, replayBM.getColor(55, 55) == 0xff800000);
 }
 
-struct CountingBBH : public SkBBoxHierarchy_Base {
+struct CountingBBH : public SkBBoxHierarchy {
     mutable int searchCalls;
 
     CountingBBH() : searchCalls(0) {}
 
-    void search(const SkRect& query, SkTDArray<int>* results) const override {
+    void search(const SkRect& query, std::vector<int>* results) const override {
         this->searchCalls++;
     }
 
@@ -963,10 +962,9 @@
         }
         sk_sp<SkPicture> pic = rec.finishRecordingAsPicture();
 
-        auto base = (const SkBBoxHierarchy_Base*)bbh.get();
-        SkTDArray<int> results;
-        base->search({0,0, 100,100}, &results);
-        REPORTER_ASSERT(r, results.count() == n,
-                        "results.count() == %d, want %d\n", results.count(), n);
+        std::vector<int> results;
+        bbh->search({0,0, 100,100}, &results);
+        REPORTER_ASSERT(r, (int)results.size() == n,
+                        "results.size() == %d, want %d\n", (int)results.size(), n);
     }
 }
diff --git a/tests/RTreeTest.cpp b/tests/RTreeTest.cpp
index 061e4d3..e89c8f7 100644
--- a/tests/RTreeTest.cpp
+++ b/tests/RTreeTest.cpp
@@ -25,8 +25,8 @@
     return rect;
 }
 
-static bool verify_query(SkRect query, SkRect rects[], SkTDArray<int>& found) {
-    SkTDArray<int> expected;
+static bool verify_query(SkRect query, SkRect rects[], const std::vector<int>& found) {
+    std::vector<int> expected;
     // manually intersect with every rectangle
     for (int i = 0; i < NUM_RECTS; ++i) {
         if (SkRect::Intersects(query, rects[i])) {
@@ -34,10 +34,10 @@
         }
     }
 
-    if (expected.count() != found.count()) {
+    if (expected.size() != found.size()) {
         return false;
     }
-    if (0 == expected.count()) {
+    if (0 == expected.size()) {
         return true;
     }
     return found == expected;
@@ -46,7 +46,7 @@
 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[],
                         const SkRTree& tree) {
     for (size_t i = 0; i < NUM_QUERIES; ++i) {
-        SkTDArray<int> hits;
+        std::vector<int> hits;
         SkRect query = random_rect(rand);
         tree.search(query, &hits);
         REPORTER_ASSERT(reporter, verify_query(query, rects, hits));