Modifying SkTileGrid to support arbitrary query rectangles.

Modifying SkTileGrid to support arbitrary query rectangles.
Exposing SkTileGrid functionality in the public API through SkTileGridPicture.
This patch also makes TileGrid and Rtree testable in gm, which revealed errors.

TEST=gm with '--tileGrid'
BUG=http://code.google.com/p/chromium/issues/detail?id=164636
Committed: https://code.google.com/p/skia/source/detail?r=6783

[TomH, 2012-12-11 16:41:02]

It's really not clear to me why you had to templatize, or why your merge is so
complex.

[junov1, 2012-12-11 16:49:45]

A naive implementation of an order-preserving merge would be O(n^2).  This one
is O(n).

The template is to preserve the generic interface of BBoxHierarchy. The cleaner
approach would be to use an BBoxElement base class, from which
SkPictureStateTree::Draw would be derived, and use that instead of void*. 
Unfortunately that would introduce virtual call overhead on operator <, which is
used in inner loops.

[reed1, 2012-12-11 18:35:40]

https://codereview.appspot.com/6933044/diff/4001/src/core/SkTileGrid.cpp
File src/core/SkTileGrid.cpp (right):

https://codereview.appspot.com/6933044/diff/4001/src/core/SkTileGrid.cpp#newc...
src/core/SkTileGrid.cpp:64: // The +1/-1 is to compensate for the outset in
applied SkCanvas::getClipBounds
icky icky Capitalized Local Variables. ?

[reed1, 2012-12-11 18:45:09]

1. have you tried just templating the search method, rather than then entire
class?

e.g.

class TRect : public SkRect {
public:
    template <typename T> bool equals(const T& src) const {
        return *(T*)this == src;
    }
};


2. Have you tried to refactor the double-inner-loop code to just be a tempated
helper function, that you call with your data?

[junov1, 2012-12-11 21:32:23]

On 2012/12/11 18:45:09, reed1 wrote:
> 1. have you tried just templating the search method, rather than then entire
> class?
> 
Can't do that because search() is a virtual overload.

> 2. Have you tried to refactor the double-inner-loop code to just be a tempated
> helper function, that you call with your data?

Ah, this gives me a better idea.  With a helper I can get rid of templates
entirely.

[junov1, 2012-12-12 15:22:26]

Patch.

[TomH, 2012-12-12 15:26:51]

Test is out of date? Still templated, chunks commented out, ...

What about the helper class? Nowhere defined?

https://codereview.appspot.com/6933044/diff/3002/src/core/SkTileGrid.cpp
File src/core/SkTileGrid.cpp (right):

https://codereview.appspot.com/6933044/diff/3002/src/core/SkTileGrid.cpp#newc...
src/core/SkTileGrid.cpp:78: (SkTDArray<void *>**)alloca(queryTileCount *
sizeof(void*));
shouldn't this be sizeof(SkTDArray<void*>*)?

[junov1, 2012-12-12 19:01:09]

On 2012/12/12 15:26:51, TomH wrote:
> Test is out of date? Still templated, chunks commented out, ...

Gah! I was so focused on gm that I completely forgot about the unit test.
> 
> What about the helper class? Nowhere defined?

I forgot to add new files to source control!  Coming right up.

[junov1, 2012-12-12 20:10:23]

Patch

[reed1, 2012-12-12 20:49:27]

works for me. should we wait for tom?

[junov1, 2012-12-12 21:18:56]

On 2012/12/12 20:49:27, reed1 wrote:
> works for me. should we wait for tom?

I won't be blocked on this until tomorrow so we can wait.

[TomH, 2012-12-13 10:38:32]

I think there's a memory leak; modulo that, LGTM enough to commit in face of
deadline. Lots of bikeshedding follows:

https://codereview.appspot.com/6933044/diff/2002/include/core/SkTileGridPictu...
File include/core/SkTileGridPicture.h (right):

https://codereview.appspot.com/6933044/diff/2002/include/core/SkTileGridPictu...
include/core/SkTileGridPicture.h:13: class SkTileGridPicture : public SkPicture
{
A brief description of class would be appropriate, since we're exposing this
publicly.

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGrid.cpp
File src/core/SkTileGrid.cpp (right):

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGrid.cpp#newc...
src/core/SkTileGrid.cpp:69: int queryTileCount = (tileEndX - tileStartX) *
(tileEndY - tileStartY);
Just for the sake of my understanding: you expect that tileEndX != tileStartX.
That means tileEndX is actually the tile *after* the end of the query area.
Right?

You use it to bound for loops consistently below, so I suppose it's easy enough
to figure out.

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGrid.cpp#newc...
src/core/SkTileGrid.cpp:77: (SkTDArray<void *>**)alloca(queryTileCount *
sizeof(SkTDArray<void *>*));
Nit: use appropriate SkNEW macro?

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGrid.cpp#newc...
src/core/SkTileGrid.cpp:89: }
Aren't we leaking tileRange [] here?

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGrid.cpp#newc...
src/core/SkTileGrid.cpp:101: }
Nit: I guess housekeeping bot will fix up trailing returns...

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGrid.h
File src/core/SkTileGrid.h (right):

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGrid.h#newcode18
src/core/SkTileGrid.h:18: * Must return the datum that comes next in insertion
order, based on current indices
"based on current indices" doesn't tell me anything. A first draft might be:
"Returns the next element of tileData[i][tileIndices[i]] for all i and advances
tileIndices[] past them.", but that still isn't really clear. In comments,
explain why this class exists, and what this function does?

P.S. Nit: I'm sad that this class exists. Why don't we get rid of it? Just have
a typedef for the function with a clear contract, and each client can declare
its function in an anonymous namespace. Your example in this CL doesn't gain
anything from being a member of an (instantiable!) class; will it ever?

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGridPicture.cpp
File src/core/SkTileGridPicture.cpp (right):

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGridPicture.c...
src/core/SkTileGridPicture.cpp:15: virtual void* nextDatum(SkTDArray<void*>**
tileData, SkTDArray<int>& tileIndices) const {
Nit: overall I find this function a bit of work to understand. I've got a couple
of specific nits below, but you might find some other way to make it more
comprehensible.

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGridPicture.c...
src/core/SkTileGridPicture.cpp:26: SkPictureStateTree::Draw* candidate =
(SkPictureStateTree::Draw*)(*tileData[tile])[pos];
Nit: if you move this declaration before the enclosing if() you can get rid code
duplication and the nested if:

if (!haveVal || (*candidate) < (*minVal)) {
    minVal = candidate;
    haveVal = true;
}

Half as many LOC; is it clearer?

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGridPicture.c...
src/core/SkTileGridPicture.cpp:34: for (int tile = 0; tile < tileCount; ++tile){
Nit-of-nits: space between ) and {

https://codereview.appspot.com/6933044/diff/2002/src/core/SkTileGridPicture.c...
src/core/SkTileGridPicture.cpp:38: (pos + 1) : SkTileGrid::kTileFinished;
Nit: not sure if it'd be clearer as:

tileIndices[tile]++;
if (tileIndices[tile] >= tileData[tile]->count()) {
    tileIndices[tile] = SkTileGrid::kTileFinished;
}

[junov1, 2012-12-13 15:02:53]

There is no SkNEW macro for alloca, and it is not leakable.
FYI: alloca allocates on the stack rather than the heap, so the allocation is
automatically freed when the stack is unrolled.

[junov1, 2012-12-13 16:17:28]

Patch

[TomH, 2012-12-13 16:22:10]

Do it!