BBHs: void* data -> unsigned data

Now that the old backend's not using BBHs, we can specialize them for
SkRecord's needs.  The only thing we really want to store is op index, which
should always be small enough to fit into an unsigned (unsigned also helps keep
it straight from other ints floating around).

This means we'll need half (32-bit) or a quarter (64-bit) the bytes in SkTileGrid,
because we don't have to store an extra int for ordering.

BUG=skia:2834

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

14 files changed, 115 insertions, 361 deletions

diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp
index 5442f7e261..21c1d79a94 100644
--- a/bench/RTreeBench.cpp
+++ b/bench/RTreeBench.cpp
@@ -51,8 +51,7 @@ protected:
         SkRandom rand;
         for (int i = 0; i < loops; ++i) {
             for (int j = 0; j < NUM_BUILD_RECTS; ++j) {
-                fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS),
-                              fBulkLoad);
+                fTree->insert(j, fProc(rand, j, NUM_BUILD_RECTS), fBulkLoad);
             }
             fTree->flushDeferredInserts();
             fTree->clear();
@@ -104,9 +103,7 @@ protected:
     virtual void onPreDraw() SK_OVERRIDE {
         SkRandom rand;
         for (int j = 0; j < NUM_QUERY_RECTS; ++j) {
-            fTree->insert(reinterpret_cast<void*>(j),
-                          fProc(rand, j, NUM_QUERY_RECTS),
-                          fBulkLoad);
+            fTree->insert(j, fProc(rand, j, NUM_QUERY_RECTS), fBulkLoad);
         }
         fTree->flushDeferredInserts();
     }
@@ -114,7 +111,7 @@ protected:
     virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
         SkRandom rand;
         for (int i = 0; i < loops; ++i) {
-            SkTDArray<void*> hits;
+            SkTDArray<unsigned> hits;
             SkRect query;
             switch(fQuery) {
                 case kSmall_QueryType:
diff --git a/gyp/tests.gypi b/gyp/tests.gypi
index 6afc7f07ad..d176cb9cd6 100644
--- a/gyp/tests.gypi
+++ b/gyp/tests.gypi
@@ -49,7 +49,6 @@
     '../tests/AnnotationTest.cpp',
     '../tests/AsADashTest.cpp',
     '../tests/AtomicTest.cpp',
-    '../tests/BBoxHierarchyTest.cpp',
     '../tests/BitSetTest.cpp',
     '../tests/BitmapCopyTest.cpp',
     '../tests/BitmapGetColorTest.cpp',
diff --git a/src/core/SkBBoxHierarchy.h b/src/core/SkBBoxHierarchy.h
index fd9680c6aa..53eabc8b88 100644
--- a/src/core/SkBBoxHierarchy.h
+++ b/src/core/SkBBoxHierarchy.h
@@ -14,42 +14,25 @@
 #include "SkRefCnt.h"
 
 /**
- * Interface for a client class that implements utility methods needed
- * by SkBBoxHierarchy that require intrinsic knowledge of the data
- * object type that is stored in the bounding box hierarchy.
- */
-class SkBBoxHierarchyClient {
-public:
-    virtual ~SkBBoxHierarchyClient() {}
-
-    /**
-     * Implements a rewind stop condition used by rewindInserts
-     * Must returns true if 'data' points to an object that should be re-wound
-     * by rewinfInserts.
-     */
-    virtual bool shouldRewind(void* data) = 0;
-};
-
-/**
- * Interface for a spatial data structure that associates user data pointers with axis-aligned
+ * Interface for a spatial data structure that associates user data with axis-aligned
  * bounding boxes, and allows efficient retrieval of intersections with query rectangles.
  */
 class SkBBoxHierarchy : public SkRefCnt {
 public:
     SK_DECLARE_INST_COUNT(SkBBoxHierarchy)
 
-    SkBBoxHierarchy() : fClient(NULL) {}
+    SkBBoxHierarchy() {}
 
     /**
-     * Insert a data pointer and corresponding bounding box
-     * @param data The data pointer, may be NULL
+     * 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(void* data, const SkRect& bounds, bool defer = false) = 0;
+    virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer = false) = 0;
 
     /**
      * If any insertions have been deferred, this forces them to be inserted
@@ -57,9 +40,9 @@ public:
     virtual void flushDeferredInserts() = 0;
 
     /**
-     * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query'
+     * Populate results with sorted opIndex corresponding to bounding boxes that intersect query.
      */
-    virtual void search(const SkRect& query, SkTDArray<void*>* results) const = 0;
+    virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const = 0;
 
     virtual void clear() = 0;
 
@@ -78,19 +61,6 @@ public:
      */
     virtual int getDepth() const = 0;
 
-    /**
-     * Rewinds all the most recently inserted data elements until an element
-     * is encountered for which client->shouldRewind(data) returns false. May
-     * not rewind elements that were inserted prior to the last call to
-     * flushDeferredInserts.
-     */
-    virtual void rewindInserts() = 0;
-
-    void setClient(SkBBoxHierarchyClient* client) { fClient = client; }
-
-protected:
-    SkBBoxHierarchyClient* fClient;
-
 private:
     typedef SkRefCnt INHERITED;
 };
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index 17872badc3..4a081db26d 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -44,7 +44,7 @@ SkRTree::~SkRTree() {
     this->clear();
 }
 
-void SkRTree::insert(void* data, const SkRect& fbounds, bool defer) {
+void SkRTree::insert(unsigned opIndex, const SkRect& fbounds, bool defer) {
     SkIRect bounds;
     if (fbounds.isLargest()) {
         bounds.setLargest();
@@ -59,7 +59,7 @@ void SkRTree::insert(void* data, const SkRect& fbounds, bool defer) {
     }
     Branch newBranch;
     newBranch.fBounds = bounds;
-    newBranch.fChild.data = data;
+    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.
@@ -109,7 +109,7 @@ void SkRTree::flushDeferredInserts() {
     this->validate();
 }
 
-void SkRTree::search(const SkRect& fquery, SkTDArray<void*>* results) const {
+void SkRTree::search(const SkRect& fquery, SkTDArray<unsigned>* results) const {
     SkIRect query;
     fquery.roundOut(&query);
     this->validate();
@@ -309,11 +309,11 @@ int SkRTree::distributeChildren(Branch* children) {
     return fMinChildren - 1 + k;
 }
 
-void SkRTree::search(Node* root, const SkIRect query, SkTDArray<void*>* results) const {
+void SkRTree::search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) const {
     for (int i = 0; i < root->fNumChildren; ++i) {
         if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) {
             if (root->isLeaf()) {
-                results->push(root->child(i)->fChild.data);
+                results->push(root->child(i)->fChild.opIndex);
             } else {
                 this->search(root->child(i)->fChild.subtree, query, results);
             }
@@ -448,14 +448,6 @@ int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) const {
     }
 }
 
-void SkRTree::rewindInserts() {
-    SkASSERT(this->isEmpty()); // Currently only supports deferred inserts
-    while (!fDeferredInserts.isEmpty() &&
-           fClient->shouldRewind(fDeferredInserts.top().fChild.data)) {
-        fDeferredInserts.pop();
-    }
-}
-
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
 static inline uint32_t get_area(const SkIRect& rect) {
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 8e980246ac..85469ccc4c 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -63,11 +63,11 @@ public:
      * 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 data The data value
+     *  @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(void* data, const SkRect& bounds, bool defer = false) SK_OVERRIDE;
+    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
@@ -77,7 +77,7 @@ public:
     /**
      * Given a query rectangle, populates the passed-in array with the elements it intersects
      */
-    virtual void search(const SkRect& query, SkTDArray<void*>* results) const SK_OVERRIDE;
+    virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
 
     virtual void clear() SK_OVERRIDE;
     bool isEmpty() const { return 0 == fCount; }
@@ -94,8 +94,6 @@ public:
      */
     virtual int getCount() const SK_OVERRIDE { return fCount; }
 
-    virtual void rewindInserts() SK_OVERRIDE;
-
 private:
 
     struct Node;
@@ -106,7 +104,7 @@ private:
     struct Branch {
         union {
             Node* subtree;
-            void* data;
+            unsigned opIndex;
         } fChild;
         SkIRect fBounds;
     };
@@ -162,7 +160,7 @@ private:
     int chooseSubtree(Node* root, Branch* branch);
     SkIRect computeBounds(Node* n);
     int distributeChildren(Branch* children);
-    void search(Node* root, const SkIRect query, SkTDArray<void*>* results) const;
+    void search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) const;
 
     /**
      * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this
diff --git a/src/core/SkRecordDraw.cpp b/src/core/SkRecordDraw.cpp
index c693b05c63..13b06b5efc 100644
--- a/src/core/SkRecordDraw.cpp
+++ b/src/core/SkRecordDraw.cpp
@@ -23,7 +23,7 @@ void SkRecordDraw(const SkRecord& record,
         SkRect query = { 0, 0, 0, 0 };
         (void)canvas->getClipBounds(&query);
 
-        SkTDArray<void*> ops;
+        SkTDArray<unsigned> ops;
         bbh->search(query, &ops);
 
         SkRecords::Draw draw(canvas);
@@ -31,7 +31,7 @@ void SkRecordDraw(const SkRecord& record,
             if (callback && callback->abortDrawing()) {
                 return;
             }
-            record.visit<void>((uintptr_t)ops[i], draw);  // See FillBounds below.
+            record.visit<void>(ops[i], draw);
         }
     } else {
         // Draw all ops.
@@ -156,9 +156,9 @@ public:
 
         // Finally feed all stored bounds into the BBH.  They'll be returned in this order.
         SkASSERT(bbh);
-        for (uintptr_t i = 0; i < record.count(); i++) {
+        for (unsigned i = 0; i < record.count(); i++) {
             if (!fBounds[i].isEmpty()) {
-                bbh->insert((void*)i, fBounds[i], true/*ok to defer*/);
+                bbh->insert(i, fBounds[i], true/*ok to defer*/);
             }
         }
         bbh->flushDeferredInserts();
diff --git a/src/core/SkTileGrid.cpp b/src/core/SkTileGrid.cpp
index 2eea6dbf36..8cdebcb0b6 100644
--- a/src/core/SkTileGrid.cpp
+++ b/src/core/SkTileGrid.cpp
@@ -12,7 +12,7 @@ SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGrid
     , fYTiles(yTiles)
     , fInfo(info)
     , fCount(0)
-    , fTiles(SkNEW_ARRAY(SkTDArray<Entry>, xTiles * yTiles)) {
+    , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) {
     // Margin is offset by 1 as a provision for AA and
     // to cancel-out the outset applied by getClipDeviceBounds.
     fInfo.fMargin.fHeight++;
@@ -23,7 +23,7 @@ SkTileGrid::~SkTileGrid() {
     SkDELETE_ARRAY(fTiles);
 }
 
-void SkTileGrid::insert(void* data, const SkRect& fbounds, bool) {
+void SkTileGrid::insert(unsigned opIndex, const SkRect& fbounds, bool) {
     SkASSERT(!fbounds.isEmpty());
     SkIRect dilatedBounds;
     if (fbounds.isLargest()) {
@@ -51,10 +51,9 @@ void SkTileGrid::insert(void* data, const SkRect& fbounds, bool) {
     int maxY = SkMax32(0, SkMin32((dilatedBounds.bottom() - 1) / fInfo.fTileInterval.height(),
                                   fYTiles - 1));
 
-    Entry entry = { fCount++, data };
     for (int y = minY; y <= maxY; y++) {
         for (int x = minX; x <= maxX; x++) {
-            fTiles[y * fXTiles + x].push(entry);
+            fTiles[y * fXTiles + x].push(opIndex);
         }
     }
 }
@@ -69,7 +68,7 @@ static int divide_ceil(int x, int y) {
 // require 512 tiles of size 256 x 256 pixels.
 static const int kStackAllocationTileCount = 1024;
 
-void SkTileGrid::search(const SkRect& query, SkTDArray<void*>* results) const {
+void SkTileGrid::search(const SkRect& query, SkTDArray<unsigned>* results) const {
     SkIRect adjusted;
     query.roundOut(&adjusted);
 
@@ -102,24 +101,20 @@ void SkTileGrid::search(const SkRect& query, SkTDArray<void*>* results) const {
 
     if (tilesHit == 1) {
         // A performance shortcut.  The merging code below would work fine here too.
-        const SkTDArray<Entry>& tile = fTiles[startY * fXTiles + startX];
-        results->setCount(tile.count());
-        for (int i = 0; i < tile.count(); i++) {
-            (*results)[i] = tile[i].data;
-        }
+        *results = fTiles[startY * fXTiles + startX];
         return;
     }
 
     // We've got to merge the data in many tiles into a single sorted and deduplicated stream.
-    // We do a simple k-way merge based on the order the data was inserted.
+    // We do a simple k-way merge based on the value of opIndex.
 
     // Gather pointers to the starts and ends of the tiles to merge.
-    SkAutoSTArray<kStackAllocationTileCount, const Entry*> starts(tilesHit), ends(tilesHit);
+    SkAutoSTArray<kStackAllocationTileCount, const unsigned*> starts(tilesHit), ends(tilesHit);
     int i = 0;
     for (int x = startX; x < endX; x++) {
         for (int y = startY; y < endY; y++) {
             starts[i] = fTiles[y * fXTiles + x].begin();
-            ends[i]  = fTiles[y * fXTiles + x].end();
+            ends[i]   = fTiles[y * fXTiles + x].end();
             i++;
         }
     }
@@ -129,10 +124,10 @@ void SkTileGrid::search(const SkRect& query, SkTDArray<void*>* results) const {
     while (true) {
         // The tiles themselves are already ordered, so the earliest is at the front of some tile.
         // It may be at the front of several, even all, tiles.
-        const Entry* earliest = NULL;
+        const unsigned* earliest = NULL;
         for (int i = 0; i < starts.count(); i++) {
             if (starts[i] < ends[i]) {
-                if (NULL == earliest || starts[i]->order < earliest->order) {
+                if (NULL == earliest || *starts[i]< *earliest) {
                     earliest = starts[i];
                 }
             }
@@ -144,9 +139,9 @@ void SkTileGrid::search(const SkRect& query, SkTDArray<void*>* results) const {
         }
 
         // We did find an earliest entry. Output it, and step forward every tile that contains it.
-        results->push(earliest->data);
+        results->push(*earliest);
         for (int i = 0; i < starts.count(); i++) {
-            if (starts[i] < ends[i] && starts[i]->order == earliest->order) {
+            if (starts[i] < ends[i] && *starts[i] == *earliest) {
                 starts[i]++;
             }
         }
@@ -159,11 +154,3 @@ void SkTileGrid::clear() {
     }
 }
 
-void SkTileGrid::rewindInserts() {
-    SkASSERT(fClient);
-    for (int i = 0; i < fXTiles * fYTiles; i++) {
-        while (!fTiles[i].isEmpty() && fClient->shouldRewind(fTiles[i].top().data)) {
-            fTiles[i].pop();
-        }
-    }
-}
diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h
index 1e34a61d52..97564c64ad 100644
--- a/src/core/SkTileGrid.h
+++ b/src/core/SkTileGrid.h
@@ -23,20 +23,20 @@ public:
     virtual ~SkTileGrid();
 
     /**
-     * Insert a data pointer and corresponding bounding box
-     * @param data   An arbitrary data pointer, may be NULL.
+     * 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(void* data, const SkRect& bounds, bool) SK_OVERRIDE;
+    virtual void insert(unsigned opIndex, const SkRect& bounds, bool) SK_OVERRIDE;
 
     virtual void flushDeferredInserts() SK_OVERRIDE {};
 
     /**
-     * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query'.
+     * 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 search(const SkRect& query, SkTDArray<void*>* results) const SK_OVERRIDE;
+    virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
 
     virtual void clear() SK_OVERRIDE;
 
@@ -44,23 +44,16 @@ public:
 
     virtual int getDepth() const SK_OVERRIDE { return -1; }
 
-    virtual void rewindInserts() SK_OVERRIDE;
-
     // For testing.
     int tileCount(int x, int y) { return fTiles[y * fXTiles + x].count(); }
 
 private:
-    struct Entry {
-        size_t order;  // Insertion order.  Used to preserve order when merging multiple tiles.
-        void*  data;
-    };
-
     const int fXTiles, fYTiles;
     SkTileGridFactory::TileGridInfo fInfo;
     size_t fCount;
 
-    // (fXTiles * fYTiles) SkTDArrays, each listing data overlapping that tile in insertion order.
-    SkTDArray<Entry>* fTiles;
+    // (fXTiles * fYTiles) SkTDArrays, each listing ops overlapping that tile in order.
+    SkTDArray<unsigned>* fTiles;
 
     typedef SkBBoxHierarchy INHERITED;
 };
diff --git a/src/gpu/GrRecordReplaceDraw.cpp b/src/gpu/GrRecordReplaceDraw.cpp
index c8b2670943..b069e60f6e 100644
--- a/src/gpu/GrRecordReplaceDraw.cpp
+++ b/src/gpu/GrRecordReplaceDraw.cpp
@@ -11,7 +11,7 @@
 #include "SkRecordDraw.h"
 #include "SkRecords.h"
 
-GrReplacements::ReplacementInfo* GrReplacements::newReplacement(uint32_t pictureID, 
+GrReplacements::ReplacementInfo* GrReplacements::newReplacement(uint32_t pictureID,
                                                                 unsigned int start,
                                                                 const SkMatrix& ctm) {
     ReplacementInfo* replacement = SkNEW_ARGS(ReplacementInfo, (pictureID, start, ctm));
@@ -30,8 +30,8 @@ void GrReplacements::freeAll() {
     fReplacementHash.reset();
 }
 
-const GrReplacements::ReplacementInfo* GrReplacements::lookupByStart(uint32_t pictureID, 
-                                                                     size_t start, 
+const GrReplacements::ReplacementInfo* GrReplacements::lookupByStart(uint32_t pictureID,
+                                                                     size_t start,
                                                                      const SkMatrix& ctm) const {
     return fReplacementHash.find(ReplacementInfo::Key(pictureID, start, ctm));
 }
@@ -94,7 +94,7 @@ public:
                     return;
                 }
 
-                record->visit<void>((uintptr_t)fOps[fIndex], *this);
+                record->visit<void>(fOps[fIndex], *this);
             }
 
         } else {
@@ -121,29 +121,29 @@ public:
         draw.draw();
     }
     void operator()(const SkRecords::SaveLayer& sl) {
-        
+
         // For a saveLayer command, check if it can be replaced by a drawBitmap
         // call and, if so, draw it and then update the current op index accordingly.
         size_t startOffset;
         if (fOps.count()) {
-            startOffset = (uintptr_t)fOps[fIndex];
+            startOffset = fOps[fIndex];
         } else {
             startOffset = fIndex;
         }
 
         const GrReplacements::ReplacementInfo* ri = fReplacements->lookupByStart(
-                                                            fPicture->uniqueID(), 
-                                                            startOffset, 
+                                                            fPicture->uniqueID(),
+                                                            startOffset,
                                                             fCanvas->getTotalMatrix());
 
         if (ri) {
             draw_replacement_bitmap(ri, fCanvas, fInitialMatrix);
 
             if (fPicture->fBBH.get()) {
-                while ((uintptr_t)fOps[fIndex] < ri->fStop) {
+                while (fOps[fIndex] < ri->fStop) {
                     ++fIndex;
                 }
-                SkASSERT((uintptr_t)fOps[fIndex] == ri->fStop);
+                SkASSERT(fOps[fIndex] == ri->fStop);
             } else {
                 fIndex = ri->fStop;
             }
@@ -161,7 +161,7 @@ private:
     const SkMatrix         fInitialMatrix;
     SkDrawPictureCallback* fCallback;
 
-    SkTDArray<void*>       fOps;
+    SkTDArray<unsigned>    fOps;
     int                    fIndex;
 
     typedef Draw INHERITED;
diff --git a/tests/BBoxHierarchyTest.cpp b/tests/BBoxHierarchyTest.cpp
deleted file mode 100644
index 71b96994f2..0000000000
--- a/tests/BBoxHierarchyTest.cpp
+++ /dev/null
@@ -1,170 +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.
- */
-
-#include "Test.h"
-#include "SkRandom.h"
-#include "SkRTree.h"
-#include "SkTSort.h"
-
-static const size_t RTREE_MIN_CHILDREN = 6;
-static const size_t RTREE_MAX_CHILDREN = 11;
-
-static const int NUM_RECTS = 200;
-static const size_t NUM_ITERATIONS = 100;
-static const size_t NUM_QUERIES = 50;
-
-static const SkScalar MAX_SIZE = 1000.0f;
-
-struct DataRect {
-    SkRect rect;
-    void* data;
-};
-
-static SkRect random_rect(SkRandom& rand) {
-    SkRect rect = {0,0,0,0};
-    while (rect.isEmpty()) {
-        rect.fLeft   = rand.nextRangeF(0, MAX_SIZE);
-        rect.fRight  = rand.nextRangeF(0, MAX_SIZE);
-        rect.fTop    = rand.nextRangeF(0, MAX_SIZE);
-        rect.fBottom = rand.nextRangeF(0, MAX_SIZE);
-        rect.sort();
-    }
-    return rect;
-}
-
-static void random_data_rects(SkRandom& rand, DataRect out[], int n) {
-    for (int i = 0; i < n; ++i) {
-        out[i].rect = random_rect(rand);
-        out[i].data = reinterpret_cast<void*>(i);
-    }
-}
-
-static bool verify_query(SkRect query, DataRect rects[],
-                         SkTDArray<void*>& found) {
-    // TODO(mtklein): no need to do this after everything's SkRects
-    query.roundOut();
-
-    SkTDArray<void*> expected;
-    // manually intersect with every rectangle
-    for (int i = 0; i < NUM_RECTS; ++i) {
-        if (SkRect::Intersects(query, rects[i].rect)) {
-            expected.push(rects[i].data);
-        }
-    }
-
-    if (expected.count() != found.count()) {
-        return false;
-    }
-
-    if (0 == expected.count()) {
-        return true;
-    }
-
-    // Just cast to long since sorting by the value of the void*'s was being problematic...
-    SkTQSort(reinterpret_cast<long*>(expected.begin()),
-             reinterpret_cast<long*>(expected.end() - 1));
-    SkTQSort(reinterpret_cast<long*>(found.begin()),
-             reinterpret_cast<long*>(found.end() - 1));
-    return found == expected;
-}
-
-static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[],
-                        SkBBoxHierarchy& tree) {
-    for (size_t i = 0; i < NUM_QUERIES; ++i) {
-        SkTDArray<void*> hits;
-        SkRect query = random_rect(rand);
-        tree.search(query, &hits);
-        REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
-    }
-}
-
-static void tree_test_main(SkBBoxHierarchy* tree, int minChildren, int maxChildren,
-                           skiatest::Reporter* reporter) {
-    DataRect rects[NUM_RECTS];
-    SkRandom rand;
-    REPORTER_ASSERT(reporter, tree);
-
-    int expectedDepthMin = -1;
-    int expectedDepthMax = -1;
-
-    int tmp = NUM_RECTS;
-    if (maxChildren > 0) {
-        while (tmp > 0) {
-            tmp -= static_cast<int>(pow(static_cast<double>(maxChildren),
-                                    static_cast<double>(expectedDepthMin + 1)));
-            ++expectedDepthMin;
-        }
-    }
-
-    tmp = NUM_RECTS;
-    if (minChildren > 0) {
-        while (tmp > 0) {
-            tmp -= static_cast<int>(pow(static_cast<double>(minChildren),
-                                    static_cast<double>(expectedDepthMax + 1)));
-            ++expectedDepthMax;
-        }
-    }
-
-    for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
-        random_data_rects(rand, rects, NUM_RECTS);
-
-        // First try bulk-loaded inserts
-        for (int i = 0; i < NUM_RECTS; ++i) {
-            tree->insert(rects[i].data, rects[i].rect, true);
-        }
-        tree->flushDeferredInserts();
-        run_queries(reporter, rand, rects, *tree);
-        REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
-        REPORTER_ASSERT(reporter,
-            ((expectedDepthMin <= 0) || (expectedDepthMin <= tree->getDepth())) &&
-            ((expectedDepthMax <= 0) || (expectedDepthMax >= tree->getDepth())));
-        tree->clear();
-        REPORTER_ASSERT(reporter, 0 == tree->getCount());
-
-        // Then try immediate inserts
-        tree->insert(rects[0].data, rects[0].rect);
-        tree->flushDeferredInserts();
-        for (int i = 1; i < NUM_RECTS; ++i) {
-            tree->insert(rects[i].data, rects[i].rect);
-        }
-        run_queries(reporter, rand, rects, *tree);
-        REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
-        REPORTER_ASSERT(reporter,
-            ((expectedDepthMin <= 0) || (expectedDepthMin <= tree->getDepth())) &&
-            ((expectedDepthMax <= 0) || (expectedDepthMax >= tree->getDepth())));
-        tree->clear();
-        REPORTER_ASSERT(reporter, 0 == tree->getCount());
-
-        // And for good measure try immediate inserts, but in reversed order
-        tree->insert(rects[NUM_RECTS - 1].data, rects[NUM_RECTS - 1].rect);
-        tree->flushDeferredInserts();
-        for (int i = NUM_RECTS - 2; i >= 0; --i) {
-            tree->insert(rects[i].data, rects[i].rect);
-        }
-        run_queries(reporter, rand, rects, *tree);
-        REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
-        REPORTER_ASSERT(reporter,
-            ((expectedDepthMin < 0) || (expectedDepthMin <= tree->getDepth())) &&
-            ((expectedDepthMax < 0) || (expectedDepthMax >= tree->getDepth())));
-        tree->clear();
-        REPORTER_ASSERT(reporter, 0 == tree->getCount());
-    }
-}
-
-DEF_TEST(BBoxHierarchy, reporter) {
-    // RTree
-    {
-        SkRTree* rtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN);
-        SkAutoUnref au(rtree);
-        tree_test_main(rtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter);
-
-        // Rtree that orders input rectangles on deferred insert.
-        SkRTree* unsortedRtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, 1, false);
-        SkAutoUnref auo(unsortedRtree);
-        tree_test_main(unsortedRtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter);
-    }
-}
diff --git a/tests/PictureTest.cpp b/tests/PictureTest.cpp
index c41b327dab..0518dd3333 100644
--- a/tests/PictureTest.cpp
+++ b/tests/PictureTest.cpp
@@ -1865,17 +1865,16 @@ struct CountingBBH : public SkBBoxHierarchy {
 
     CountingBBH() : searchCalls(0) {}
 
-    virtual void search(const SkRect& query, SkTDArray<void*>* results) const {
+    virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE {
         this->searchCalls++;
     }
 
     // All other methods unimplemented.
-    virtual void insert(void* data, const SkRect& bounds, bool defer) {}
-    virtual void flushDeferredInserts() {}
-    virtual void clear() {}
-    virtual int getCount() const { return 0; }
-    virtual int getDepth() const { return 0; }
-    virtual void rewindInserts() {}
+    virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer) SK_OVERRIDE {}
+    virtual void flushDeferredInserts() SK_OVERRIDE {}
+    virtual void clear() SK_OVERRIDE {}
+    virtual int getCount() const SK_OVERRIDE { return 0; }
+    virtual int getDepth() const SK_OVERRIDE { return 0; }
 };
 
 class SpoonFedBBHFactory : public SkBBHFactory {
diff --git a/tests/RTreeTest.cpp b/tests/RTreeTest.cpp
index 40af5fe55b..6e0622c2fb 100644
--- a/tests/RTreeTest.cpp
+++ b/tests/RTreeTest.cpp
@@ -17,11 +17,6 @@ static const int NUM_RECTS = 200;
 static const size_t NUM_ITERATIONS = 100;
 static const size_t NUM_QUERIES = 50;
 
-struct DataRect {
-    SkRect rect;
-    void* data;
-};
-
 static SkRect random_rect(SkRandom& rand) {
     SkRect rect = {0,0,0,0};
     while (rect.isEmpty()) {
@@ -34,24 +29,22 @@ static SkRect random_rect(SkRandom& rand) {
     return rect;
 }
 
-static void random_data_rects(SkRandom& rand, DataRect out[], int n) {
+static void random_data_rects(SkRandom& rand, SkRect out[], int n) {
     for (int i = 0; i < n; ++i) {
-        out[i].rect = random_rect(rand);
-        out[i].data = reinterpret_cast<void*>(i);
+        out[i] = random_rect(rand);
     }
 }
 
-static bool verify_query(SkRect query, DataRect rects[],
-                         SkTDArray<void*>& found) {
+static bool verify_query(SkRect query, SkRect rects[], SkTDArray<unsigned>& found) {
     // TODO(mtklein): no need to do this after everything's SkRects
     query.roundOut();
 
-    SkTDArray<void*> expected;
+    SkTDArray<unsigned> expected;
 
     // manually intersect with every rectangle
     for (int i = 0; i < NUM_RECTS; ++i) {
-        if (SkRect::Intersects(query, rects[i].rect)) {
-            expected.push(rects[i].data);
+        if (SkRect::Intersects(query, rects[i])) {
+            expected.push(i);
         }
     }
 
@@ -63,18 +56,16 @@ static bool verify_query(SkRect query, DataRect rects[],
         return true;
     }
 
-    // Just cast to long since sorting by the value of the void*'s was being problematic...
-    SkTQSort(reinterpret_cast<long*>(expected.begin()),
-             reinterpret_cast<long*>(expected.end() - 1));
-    SkTQSort(reinterpret_cast<long*>(found.begin()),
-             reinterpret_cast<long*>(found.end() - 1));
+    // skia:2834.  RTree doesn't always return results in order.
+    SkTQSort(expected.begin(), expected.end() -1);
+    SkTQSort(found.begin(), found.end() -1);
     return found == expected;
 }
 
-static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[],
+static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[],
                        SkRTree& tree) {
     for (size_t i = 0; i < NUM_QUERIES; ++i) {
-        SkTDArray<void*> hits;
+        SkTDArray<unsigned> hits;
         SkRect query = random_rect(rand);
         tree.search(query, &hits);
         REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
@@ -82,7 +73,7 @@ static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect r
 }
 
 static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
-    DataRect rects[NUM_RECTS];
+    SkRect rects[NUM_RECTS];
     SkRandom rand;
     REPORTER_ASSERT(reporter, rtree);
 
@@ -108,7 +99,7 @@ static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
 
         // First try bulk-loaded inserts
         for (int i = 0; i < NUM_RECTS; ++i) {
-            rtree->insert(rects[i].data, rects[i].rect, true);
+            rtree->insert(i, rects[i], true);
         }
         rtree->flushDeferredInserts();
         run_queries(reporter, rand, rects, *rtree);
@@ -120,7 +111,7 @@ static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
 
         // Then try immediate inserts
         for (int i = 0; i < NUM_RECTS; ++i) {
-            rtree->insert(rects[i].data, rects[i].rect);
+            rtree->insert(i, rects[i]);
         }
         run_queries(reporter, rand, rects, *rtree);
         REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
@@ -131,7 +122,7 @@ static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
 
         // And for good measure try immediate inserts, but in reversed order
         for (int i = NUM_RECTS - 1; i >= 0; --i) {
-            rtree->insert(rects[i].data, rects[i].rect);
+            rtree->insert(i, rects[i]);
         }
         run_queries(reporter, rand, rects, *rtree);
         REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
diff --git a/tests/RecordDrawTest.cpp b/tests/RecordDrawTest.cpp
index 33efbd83ad..ac3883b2d6 100644
--- a/tests/RecordDrawTest.cpp
+++ b/tests/RecordDrawTest.cpp
@@ -98,24 +98,23 @@ DEF_TEST(RecordDraw_SetMatrixClobber, r) {
 }
 
 struct TestBBH : public SkBBoxHierarchy {
-    virtual void insert(void* data, const SkRect& bounds, bool defer) SK_OVERRIDE {
-        Entry e = { (uintptr_t)data, bounds };
-        entries.push(e);
+    virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer) SK_OVERRIDE {
+        Entry e = { opIndex, bounds };
+        fEntries.push(e);
     }
-    virtual int getCount() const SK_OVERRIDE { return entries.count(); }
+    virtual int getCount() const SK_OVERRIDE { return fEntries.count(); }
 
     virtual void flushDeferredInserts() SK_OVERRIDE {}
 
-    virtual void search(const SkRect& query, SkTDArray<void*>* results) const SK_OVERRIDE {}
+    virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE {}
     virtual void clear() SK_OVERRIDE {}
-    virtual void rewindInserts() SK_OVERRIDE {}
     virtual int getDepth() const SK_OVERRIDE { return -1; }
 
     struct Entry {
-        uintptr_t data;
+        unsigned opIndex;
         SkRect bounds;
     };
-    SkTDArray<Entry> entries;
+    SkTDArray<Entry> fEntries;
 };
 
 // Like a==b, with a little slop recognizing that float equality can be weird.
@@ -140,11 +139,11 @@ DEF_TEST(RecordDraw_BBH, r) {
     TestBBH bbh;
     SkRecordFillBounds(record, &bbh);
 
-    REPORTER_ASSERT(r, bbh.entries.count() == 5);
-    for (int i = 0; i < bbh.entries.count(); i++) {
-        REPORTER_ASSERT(r, bbh.entries[i].data == (uintptr_t)i);
+    REPORTER_ASSERT(r, bbh.fEntries.count() == 5);
+    for (int i = 0; i < bbh.fEntries.count(); i++) {
+        REPORTER_ASSERT(r, bbh.fEntries[i].opIndex == (unsigned)i);
 
-        REPORTER_ASSERT(r, sloppy_rect_eq(SkRect::MakeWH(400, 480), bbh.entries[i].bounds));
+        REPORTER_ASSERT(r, sloppy_rect_eq(SkRect::MakeWH(400, 480), bbh.fEntries[i].bounds));
     }
 }
 
@@ -165,13 +164,13 @@ DEF_TEST(RecordDraw_TextBounds, r) {
 
     TestBBH bbh;
     SkRecordFillBounds(record, &bbh);
-    REPORTER_ASSERT(r, bbh.entries.count() == 2);
+    REPORTER_ASSERT(r, bbh.fEntries.count() == 2);
 
     // We can make these next assertions confidently because SkRecordFillBounds
     // builds its bounds by overestimating font metrics in a platform-independent way.
     // If that changes, these tests will need to be more flexible.
-    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[0].bounds, SkRect::MakeLTRB(-86,  6, 116, 54)));
-    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[1].bounds, SkRect::MakeLTRB(-56, 26, 156, 94)));
+    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[0].bounds, SkRect::MakeLTRB(-86,  6, 116, 54)));
+    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[1].bounds, SkRect::MakeLTRB(-56, 26, 156, 94)));
 }
 
 // Base test to ensure start/stop range is respected
@@ -252,9 +251,9 @@ DEF_TEST(RecordDraw_SaveLayerAffectsClipBounds, r) {
     // The saveLayer, clipRect, and restore bounds were incorrectly (0,0,70,50).
     TestBBH bbh;
     SkRecordFillBounds(record, &bbh);
-    REPORTER_ASSERT(r, bbh.entries.count() == 4);
-    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[0].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
-    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[1].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
-    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[2].bounds, SkRect::MakeLTRB(0, 0, 40, 40)));
-    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.entries[3].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
+    REPORTER_ASSERT(r, bbh.fEntries.count() == 4);
+    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[0].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
+    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[1].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
+    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[2].bounds, SkRect::MakeLTRB(0, 0, 40, 40)));
+    REPORTER_ASSERT(r, sloppy_rect_eq(bbh.fEntries[3].bounds, SkRect::MakeLTRB(0, 0, 50, 50)));
 }
diff --git a/tests/TileGridTest.cpp b/tests/TileGridTest.cpp
index 16434abdc6..6529901dcc 100644
--- a/tests/TileGridTest.cpp
+++ b/tests/TileGridTest.cpp
@@ -31,14 +31,14 @@ public:
     SkTDArray<SkRect> fRects;
 };
 
-static void verifyTileHits(skiatest::Reporter* reporter, SkRect rect,
-                           uint32_t tileMask, int borderPixels = 0) {
+static void verify_tile_hits(skiatest::Reporter* reporter, SkRect rect,
+                             uint32_t tileMask, int borderPixels = 0) {
     SkTileGridFactory::TileGridInfo info;
     info.fMargin.set(borderPixels, borderPixels);
     info.fOffset.setZero();
     info.fTileInterval.set(10 - 2 * borderPixels, 10 - 2 * borderPixels);
     SkTileGrid grid(2, 2, info);
-    grid.insert(NULL, rect, false);
+    grid.insert(0, rect, false);
     REPORTER_ASSERT(reporter, grid.tileCount(0, 0) ==
                     ((tileMask & kTopLeft_Tile)? 1 : 0));
     REPORTER_ASSERT(reporter, grid.tileCount(1, 0) ==
@@ -223,29 +223,28 @@ DEF_TEST(TileGrid_OverlapOffsetQueryAlignment, reporter) {
 
 DEF_TEST(TileGrid, reporter) {
     // Out of bounds
-    verifyTileHits(reporter, SkRect::MakeXYWH(30, 0, 1, 1),  0);
-    verifyTileHits(reporter, SkRect::MakeXYWH(0, 30, 1, 1),  0);
-    verifyTileHits(reporter, SkRect::MakeXYWH(-10, 0, 1, 1),  0);
-    verifyTileHits(reporter, SkRect::MakeXYWH(0, -10, 1, 1),  0);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(30, 0, 1, 1),  0);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(0, 30, 1, 1),  0);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(-10, 0, 1, 1), 0);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(0, -10, 1, 1), 0);
 
     // Dilation for AA consideration
-    verifyTileHits(reporter, SkRect::MakeXYWH(0, 0, 9, 9),  kTopLeft_Tile);
-    verifyTileHits(reporter, SkRect::MakeXYWH(0, 0, 10, 10),  kAll_Tile);
-    verifyTileHits(reporter, SkRect::MakeXYWH(9, 9, 1, 1),  kAll_Tile);
-    verifyTileHits(reporter, SkRect::MakeXYWH(10, 10, 1, 1),  kAll_Tile);
-    verifyTileHits(reporter, SkRect::MakeXYWH(11, 11, 1, 1),  kBottomRight_Tile);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(0, 0, 9, 9),   kTopLeft_Tile);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(0, 0, 10, 10), kAll_Tile);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(9, 9, 1, 1),   kAll_Tile);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(10, 10, 1, 1), kAll_Tile);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(11, 11, 1, 1), kBottomRight_Tile);
 
     // BorderPixels
-    verifyTileHits(reporter, SkRect::MakeXYWH(0, 0, 6, 6),  kTopLeft_Tile, 1);
-    verifyTileHits(reporter, SkRect::MakeXYWH(0, 0, 7, 7),  kAll_Tile, 1);
-    verifyTileHits(reporter, SkRect::MakeXYWH(9, 9, 1, 1),  kAll_Tile, 1);
-    verifyTileHits(reporter, SkRect::MakeXYWH(10, 10, 1, 1),  kBottomRight_Tile, 1);
-    verifyTileHits(reporter, SkRect::MakeXYWH(17, 17, 1, 1),  kBottomRight_Tile, 1);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(0, 0, 6, 6),   kTopLeft_Tile,     1);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(0, 0, 7, 7),   kAll_Tile,         1);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(9, 9, 1, 1),   kAll_Tile,         1);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(10, 10, 1, 1), kBottomRight_Tile, 1);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(17, 17, 1, 1), kBottomRight_Tile, 1);
 
     // BBoxes that overlap tiles
-    verifyTileHits(reporter, SkRect::MakeXYWH(5, 5, 10, 1),  kTopLeft_Tile | kTopRight_Tile);
-    verifyTileHits(reporter, SkRect::MakeXYWH(5, 5, 1, 10),  kTopLeft_Tile |
-                   kBottomLeft_Tile);
-    verifyTileHits(reporter, SkRect::MakeXYWH(5, 5, 10, 10),  kAll_Tile);
-    verifyTileHits(reporter, SkRect::MakeXYWH(-10, -10, 40, 40),  kAll_Tile);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(5, 5, 10, 1),     kTopLeft_Tile | kTopRight_Tile);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(5, 5, 1, 10),     kTopLeft_Tile | kBottomLeft_Tile);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(5, 5, 10, 10),    kAll_Tile);
+    verify_tile_hits(reporter, SkRect::MakeXYWH(-10, -10, 40, 40),kAll_Tile);
 }