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

7 files changed, 51 insertions, 111 deletions

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;