First version of bitmap use tracking in SkPictureRecord

src/core/SkPictureRecord.h

 /*
  * Copyright 2011 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef SkPictureRecord_DEFINED
 #define SkPictureRecord_DEFINED
 
 #include "SkCanvas.h"
 #include "SkFlattenable.h"
 #ifdef SK_COLLAPSE_MATRIX_CLIP_STATE
 #include "SkMatrixClipStateMgr.h"
 #endif
 #include "SkPathHeap.h"
 #include "SkPicture.h"
 #include "SkPictureFlat.h"
 #include "SkTemplates.h"
 #include "SkWriter32.h"
 
 class SkPictureStateTree;
 class SkBBoxHierarchy;
 
+// A 2D table of skp offsets. Each row is indexed by an int. This is used
+// to store the command offsets that reference a particular bitmap using
+// the bitmap's index in the bitmap heap as the 'id' here. It has to be
+// ref-countable so SkPicturePlayback can take ownership of it.
+class SkOffsetTable : public SkRefCnt {

[mtklein, 2014/03/06 16:20:38]

Give this class its own .h/.cpp pair?

[robertphillips, 2014/03/06 20:18:26]

Will do. I will leave that as a final refactoring so there is some continuity in
the code review.

+public:
+    SkOffsetTable() {}
+    ~SkOffsetTable() {
+        for (int i = 0; i < fOffsetArrays.count(); ++i) {

[mtklein, 2014/03/06 16:20:38]

fOffsetArrays.deleteAll(); ?

[robertphillips, 2014/03/06 20:18:26]

Done.

+            SkDELETE(fOffsetArrays[i]);
+        }
+    }
+
+    void add(int id, size_t offset) {

[mtklein, 2014/03/06 16:20:38]

// Record that this ID is used by the command starting at this offset.

[robertphillips, 2014/03/06 20:18:26]

Done.

+        if (id >= fOffsetArrays.count()) {

[mtklein, 2014/03/06 16:20:38]

Can you note somewhere, maybe at the top of the class, that we expect IDs to be
dense?

[robertphillips, 2014/03/06 20:18:26]

Done.

+            int oldCount = fOffsetArrays.count();
+            fOffsetArrays.setCount(id+1);
+            for (int i = oldCount; i <= id; ++i) {
+                fOffsetArrays[i] = NULL;
+            }
+        }

[mtklein, 2014/03/06 16:20:38]

Are we assuming |IDs| << |offsets|?  If there are many IDs, add is going to
scale badly.  (Might tack on O(|IDs|)?)

[robertphillips, 2014/03/06 20:18:26]

|IDs| is < |offsets| but it varies widely between pages (e.g., for baidu |IDs|
== 1). We can always gather some stats about how many textures webpages have but
I think this will ultimately wind up being a hash table and then the stats we're
concerned about change a bit.

+
+        if (NULL == fOffsetArrays[id]) {
+            fOffsetArrays[id] = SkNEW(OffsetArray);
+        }
+        fOffsetArrays[id]->add(offset);
+    }
+
+    int numIDs() const {
+        return fOffsetArrays.count(); 
+    }
+
+    bool overlap(int id, size_t min, size_t max) {

[mtklein, 2014/03/06 16:20:38]

// Do the offsets of any commands referencing this ID fall in the range [min,
max] (both inclusive)?

[robertphillips, 2014/03/06 20:18:26]

Done.

+        SkASSERT(id < fOffsetArrays.count());
+
+        if (NULL == fOffsetArrays[id]) {
+            return false;
+        }
+
+        SkASSERT(fOffsetArrays[id]->count() > 0);

[mtklein, 2014/03/06 16:20:38]

->front() and ->back() are about to check this anyway, right?  I guess it
doesn't hurt to leave it in.

[robertphillips, 2014/03/06 20:18:26]

I've added a comment. The assert here was basically "if there is an offset array
there should be at least one use". The ones in front & back are more for if they
are ever used elsewhere. 

+        if (max < fOffsetArrays[id]->front() || min > fOffsetArrays[id]->back()) {

[mtklein, 2014/03/06 16:20:38]

Might help readability here to rename front to low or min, and back to high or
max?

[robertphillips, 2014/03/06 20:18:26]

Done.

+            return false;
+        }
+
+        return true;
+    }
+
+    bool includes(int id, size_t offset) {

[mtklein, 2014/03/06 16:20:38]

Note that this is linear in the number of commands referencing ID?

This table seems like something we could implement with O(1) guarantees for all
its operations.  If we're not going to do that, I'd want to be pretty clear
about the cost of each of these methods.  I'm worried these linear ops are going
to cause some picture screw case to take quadratic time.

Alternatively, maybe we should just make it all O(1)?  Should work with a
top-level hash table of IDs to (min offset, max offset, hash set of offsets)? 
And looks like if we make includes fast enough, we can eliminate overlaps() and
the need to track min and max altogether?

If the pairs of (ID, offset) are sparse enough, there's no real benefit even to
having a two layer hash: we could just make a single hash set of (ID, offset)
pairs directly.

[robertphillips, 2014/03/06 20:18:26]

Yep - right now I'm just trying to get it working. I think it will ultimately
wind up being a hash table. I've added a TODO to capture this.

+        SkASSERT(id < fOffsetArrays.count());
+
+        OffsetArray* array = fOffsetArrays[id];
+
+        for (int i = 0; i < array->fOffsets.count(); ++i) {
+            if (array->fOffsets[i] == offset) {
+                return true;
+            } else if (array->fOffsets[i] > offset) {
+                return false;
+            }
+        }
+
+        SkASSERT(0);

[mtklein, 2014/03/06 16:20:38]

Why this assert?  I guess we don't expect people to be asking questions about
offsets we haven't yet swept past?

[robertphillips, 2014/03/06 20:18:26]

Given that this should always be guarded by a 'overlap' call, we should always
have some entry in 'array' that is >= to 'offset' (and return from within the
loop).

[mtklein, 2014/03/07 13:04:08]

Ah, can you add // We're guarded by an overlap() call, so we should always find
something.  ?

[robertphillips, 2014/03/07 13:23:00]

Done.

+        return false;
+    }
+
+protected:
+    class OffsetArray {
+    public:
+        void add(size_t offset) { *fOffsets.append() = offset;  }

[mtklein, 2014/03/06 16:20:38]

Seems like we'd want to add
  SkASSERT(fOffsets.count() == 0 || offset > this->back());
to make the ordering assumption clear?  It's probably worth mentioning that
offsets must be added in increasing order on SkOffsetTable::add()?

[robertphillips, 2014/03/06 20:18:26]

Done.

+        size_t front() const { 
+            SkASSERT(fOffsets.count() > 0);
+            return fOffsets[0]; 
+        }
+        size_t back() const { 
+            SkASSERT(fOffsets.count() > 0);
+            return fOffsets[fOffsets.count()-1]; 
+        }
+        int count() const {
+            return fOffsets.count();
+        }
+
+        SkTDArray<size_t> fOffsets;
+    };
+
+    SkTDArray<OffsetArray*> fOffsetArrays;
+
+private:
+    typedef SkRefCnt INHERITED;
+};
+
 // These macros help with packing and unpacking a single byte value and
 // a 3 byte value into/out of a uint32_t
 #define MASK_24 0x00FFFFFF
 #define UNPACK_8_24(combined, small, large)             \
     small = (combined >> 24) & 0xFF;                    \
     large = combined & MASK_24;
 #define PACK_8_24(small, large) ((small << 24) | large)
 
 
 class SkPictureRecord : public SkCanvas {
@@ skipping 122 matching lines @@
         return offset;
     }
 
     void addInt(int value) {
         fWriter.writeInt(value);
     }
     void addScalar(SkScalar scalar) {
         fWriter.writeScalar(scalar);
     }
 
-    void addBitmap(const SkBitmap& bitmap);
+    // The command at 'offset' in the skp uses the specified bitmap
+    void trackBitmapUse(int bitmapID, size_t offset);
+    int addBitmap(const SkBitmap& bitmap);
     void addMatrix(const SkMatrix& matrix);
     const SkFlatData* addPaint(const SkPaint& paint) { return this->addPaintPtr(&paint); }
     const SkFlatData* addPaintPtr(const SkPaint* paint);
     void addFlatPaint(const SkFlatData* flatPaint);
     void addPath(const SkPath& path);
     void addPicture(SkPicture& picture);
     void addPoint(const SkPoint& point);
     void addPoints(const SkPoint pts[], int count);
     void addRect(const SkRect& rect);
     void addRectPtr(const SkRect* rect);
@@ skipping 109 matching lines @@
     SkPathHeap* fPathHeap;  // reference counted
     SkWriter32 fWriter;
 
     // we ref each item in these arrays
     SkTDArray<SkPicture*> fPictureRefs;
 
     uint32_t fRecordFlags;
     bool     fOptsEnabled;
     int      fInitialSaveCount;
 
+    SkOffsetTable* fBitmapUseOffsets;

[mtklein, 2014/03/06 16:20:38]

SkAutoTUnref<SkOffsetTable> ?

[robertphillips, 2014/03/06 20:18:26]

Done.

+
     friend class SkPicturePlayback;
     friend class SkPictureTester; // for unit testing
 
 #ifdef SK_COLLAPSE_MATRIX_CLIP_STATE
     SkMatrixClipStateMgr fMCMgr;
 #endif
 
     typedef SkCanvas INHERITED;
 };
 
 #endif