Fast implementation of QuadTree

Fast implementation of QuadTree

Rewritten to avoid memory allocations.

BUG=skia:2242
Committed: http://code.google.com/p/skia/source/detail?r=13826

[iancottrell, 2014-03-05 01:39:44]

This cl currently pases all tests, and is faster than the other bbox types, but
it is not really finished yet (although if you want to comment on anything feel
free)
I need to check I am going in the right direction and ask a couple of questions.

Who should be included in the reviewers for this stuff?

The cl includes declarations for SkSList which is an intrusive singly linked
list, and SkFreeList, which manages a self growing free list of objects
allocated in bulk. They are targeted at the needs of SkQuadTree, but they are
generally useful, probably.
Currently I just chucked them in the top of SkQuadTree.h, which is clearly not
the right place. What should they be called, and where should they live?
I think SkFreeList is okay, although maybe a name that indicates it can allocate
more when it runs out would be better?
Maybe SkSList should be SkIntrusiveSList? I am not sure it needs to be that
explicit, it's amazingly rare to see a single linked list that is not intrusive.

Assuming we want them at all, should they be in the public skia api, or in their
own headers in src/core?

[tomhudson, 2014-03-05 11:56:56]

Unless we need to expose them in other public header files, the two new classes
would get their own header(s) in src/core.

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.cpp
File src/core/SkQuadTree.cpp (right):

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:31: SkQuadTree::Node* SkQuadTree::pickChild(Node* node,
const SkIRect& bounds) const {
IIRC in conversation you said you had support for using a QuadTree. Is it
somewhere? The more I think about webpage structures, the more I think about
text spans, which naively are going to tend to frequently cross the page
centerline and therefore be forced into the root node?

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h
File src/core/SkQuadTree.h (right):

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:19: * The list does not maintain ownership of any of it's
elements, or ever delete
Nit: no apostrophe

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:47: while(!other.isEmpty()) {
Can't we just graft the other list onto this one? Or is this safer in some
sense?

(Either way we'll need to traverse *one* of the lists, I guess, so maybe no
win.)

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:146: * An QuadTree implementation. In short, it is a tree
containing a hierarchy of bounding rectangles
Nit-among-nits: An -> A?

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:209: for(int index=0; index<kChildCount; ++index) {
Nit: Skia style has more spaces than you do. (At least one, after the for)

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:215: SkIPoint fCenter;
// Uninitialized until the Node has children (fChildren != NULL and not in free
list).

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:216: union {
// A Node is only in a SkFreeList when it is free, and has no children.

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:223: SkFreeList<Node> fAllNodes;
This isn't really *All*Nodes, it's all nodes not currently part of the universe.
Spare nodes? Free nodes? (Yeah, the type name implies it's a freelist, but the
variable name is what we see at callsites.)

[iancottrell, 2014-03-05 12:11:15]

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.cpp
File src/core/SkQuadTree.cpp (right):

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:31: SkQuadTree::Node* SkQuadTree::pickChild(Node* node,
const SkIRect& bounds) const {
On 2014/03/05 11:56:56, tomhudson wrote:
> IIRC in conversation you said you had support for using a QuadTree. Is it
> somewhere? The more I think about webpage structures, the more I think about
> text spans, which naively are going to tend to frequently cross the page
> centerline and therefore be forced into the root node?

Yes, I worry that web pages might have common pathological structures where many
elements overlap the split points.
There are ways around this, QuadTree's don't *have* to be center point split,
and this implementation would deliberately allow it to not be. Non center point
splits are viable when doing bulk loads, where you can try to work out a good
split point because you have full information, normally you try to find a split
point that is close to the middle that cuts the fewest possible bounds. 
It is horribly complicated to write and understand, and would probably be much
slower at record time though, so unless this is doing such a bad job that we see
it in playback results, I don't think it is worth doing.

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h
File src/core/SkQuadTree.h (right):

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:19: * The list does not maintain ownership of any of it's
elements, or ever delete
On 2014/03/05 11:56:56, tomhudson wrote:
> Nit: no apostrophe

Done.

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:47: while(!other.isEmpty()) {
On 2014/03/05 11:56:56, tomhudson wrote:
> Can't we just graft the other list onto this one? Or is this safer in some
> sense?
> 
> (Either way we'll need to traverse *one* of the lists, I guess, so maybe no
> win.)

Yes, I decided it made the code less readable for no average performance gain,
so I did not bother.

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:146: * An QuadTree implementation. In short, it is a tree
containing a hierarchy of bounding rectangles
On 2014/03/05 11:56:56, tomhudson wrote:
> Nit-among-nits: An -> A?

Done.

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:209: for(int index=0; index<kChildCount; ++index) {
On 2014/03/05 11:56:56, tomhudson wrote:
> Nit: Skia style has more spaces than you do. (At least one, after the for)

Done.

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:215: SkIPoint fCenter;
On 2014/03/05 11:56:56, tomhudson wrote:
> // Uninitialized until the Node has children (fChildren != NULL and not in
free
> list).

Done. Also renamed for clarity.

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:216: union {
On 2014/03/05 11:56:56, tomhudson wrote:
> // A Node is only in a SkFreeList when it is free, and has no children.

Done.

https://codereview.chromium.org/187233002/diff/20001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:223: SkFreeList<Node> fAllNodes;
On 2014/03/05 11:56:56, tomhudson wrote:
> This isn't really *All*Nodes, it's all nodes not currently part of the
universe.
> Spare nodes? Free nodes? (Yeah, the type name implies it's a freelist, but the
> variable name is what we see at callsites.)

Done.

[robertphillips, 2014-03-05 13:08:53]

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.cpp
File src/core/SkQuadTree.cpp (right):

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:82: }
overlength lines

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:121: node->fChildren[index] = NULL;
NULL != child

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h
File src/core/SkQuadTree.h (right):

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:14: 
Might be worth mirroring SkTInternalList.h

[reed1, 2014-03-05 14:33:01]

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h
File src/core/SkQuadTree.h (right):

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:39: * Takes all the items from another list.
Are they added to the head or the tail of this list?
Are they kept in their same order?
Is the "other" head now empty?

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:41: void takeAll(SkSList<T>& other) {
typically in Skia if the argument is changed, we pass a pointer instead of a
reference.

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:74: bool isEmpty() {
const

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:75: return fHead == NULL;
tiny nit: Skia tries to be paranoid, and writes this expression as

return NULL == fHead

to avoid accidental assignment

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:89: int getCount() {
const

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:158: * Create a new QuadTree
What is the bounds parameter?
Can the factory ever return NULL? (e.g. on bad input)

[iancottrell, 2014-03-07 15:06:33]

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.cpp
File src/core/SkQuadTree.cpp (right):

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:82: }
On 2014/03/05 13:08:53, robertphillips wrote:
> overlength lines

Done.

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.cpp#...
src/core/SkQuadTree.cpp:121: node->fChildren[index] = NULL;
On 2014/03/05 13:08:53, robertphillips wrote:
> NULL != child

Done. And all the other NULL tests.

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h
File src/core/SkQuadTree.h (right):

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:14: 
On 2014/03/05 13:08:53, robertphillips wrote:
> Might be worth mirroring SkTInternalList.h

Done.

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:39: * Takes all the items from another list.
On 2014/03/05 14:33:01, reed1 wrote:
> Are they added to the head or the tail of this list?
> Are they kept in their same order?
> Is the "other" head now empty?

Done.

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:41: void takeAll(SkSList<T>& other) {
On 2014/03/05 14:33:01, reed1 wrote:
> typically in Skia if the argument is changed, we pass a pointer instead of a
> reference.

Done.

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:74: bool isEmpty() {
On 2014/03/05 14:33:01, reed1 wrote:
> const

Done.

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:75: return fHead == NULL;
On 2014/03/05 14:33:01, reed1 wrote:
> tiny nit: Skia tries to be paranoid, and writes this expression as
> 
> return NULL == fHead
> 
> to avoid accidental assignment

Done.

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:89: int getCount() {
On 2014/03/05 14:33:01, reed1 wrote:
> const

Done.

https://codereview.chromium.org/187233002/diff/40001/src/core/SkQuadTree.h#ne...
src/core/SkQuadTree.h:158: * Create a new QuadTree
On 2014/03/05 14:33:01, reed1 wrote:
> What is the bounds parameter?
> Can the factory ever return NULL? (e.g. on bad input)

To be honest, I have no idea why this code has a factory method, I had not
actually looked at it. The implementation just calls new SkQuadTree (does not
even use SkNEW).
I don't think we need it, I will remove it and just make the constructor public.

[reed1, 2014-03-07 15:18:38]

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h
File src/core/SkFreeList.h (right):

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:18: * An implementation of a self growing free list of
objects.
I still don't grok what this class does. Is it effectively a heap, returning
space for new objects, and recycling space after they have been destroyed?

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:27: while(!fBlocks.isEmpty()) { SkDELETE(fBlocks.pop()); }
style nit: 

while (..) {
    ...
}

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:41: * Takes all the items from another list.
- what is the state of other after this call?
- in what order were the items added to this?

please answer in the form of more dox

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:57: T* pop() {
wow, this name is really confusing, since pop() is growing the collection.

Does this method return space for a new T to be stored? (like new)
Does this method initialize the space using T()?

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:58: if (fAvailable.isEmpty()) { grow(); }
style nit:

if (...) {
   ...
}

[reed1, 2014-03-07 15:19:35]

can we write some simple tests for SkFreeList?

[robertphillips, 2014-03-07 16:01:34]

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h
File src/core/SkFreeList.h (right):

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:11: #include "SkTInternalSList.h"
Is this needed?

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:12: #include "SkRect.h"
Is this needed?

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:13: #include "SkTDArray.h"
Do we need to include SkBBoxHierarchy.h?

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:18: * An implementation of a self growing free list of
objects.
Apropos this comment, renaming it SkBlockMgr might be clearer. Maybe mention
that it is only for objects that can participate in an internal list?

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:22: */
growth -> numItemsPerBlock?

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:26: ~SkFreeList() {
Couldn't we add an assert here that all the managed object are back in the
fAvailable list?

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:81: for(int index = 0; index < growth; ++index) {
this->push

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSList.h
File src/core/SkTInternalSList.h (right):

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSLis...
src/core/SkTInternalSList.h:27: ClassName* getSListNext() {                     
           \
don't need this-> here

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSLis...
src/core/SkTInternalSList.h:30: void setSListNext(ClassName* next) {            
           \
same here

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSLis...
src/core/SkTInternalSList.h:73: void takeAll(SkTInternalSList<T>* other) {
this->

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSLis...
src/core/SkTInternalSList.h:74: if (isEmpty()) {
this->

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSLis...
src/core/SkTInternalSList.h:78: while(!other->isEmpty()) {
this->

[iancottrell, 2014-03-07 16:02:33]

SkTInternalLList and SkTObjectPool both still need exhaustive tests, I was
waiting for general happiness with the classes before writing them. I will do
that next assuming the approach and names are okay now?

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h
File src/core/SkFreeList.h (right):

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:18: * An implementation of a self growing free list of
objects.
On 2014/03/07 15:18:38, reed1 wrote:
> I still don't grok what this class does. Is it effectively a heap, returning
> space for new objects, and recycling space after they have been destroyed?

I have renamed some stuff and added comments to make it clearer.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:27: while(!fBlocks.isEmpty()) { SkDELETE(fBlocks.pop()); }
On 2014/03/07 15:18:38, reed1 wrote:
> style nit: 
> 
> while (..) {
>     ...
> }

Done.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:41: * Takes all the items from another list.
On 2014/03/07 15:18:38, reed1 wrote:
> - what is the state of other after this call?
> - in what order were the items added to this?
> 
> please answer in the form of more dox

Sorry, I fixed the docs on list, but this was copied earlier.
Order is not relevant because this is not an iterable container.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:57: T* pop() {
On 2014/03/07 15:18:38, reed1 wrote:
> wow, this name is really confusing, since pop() is growing the collection.
> 
> Does this method return space for a new T to be stored? (like new)
> Does this method initialize the space using T()?

Renamed, and comments added.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:58: if (fAvailable.isEmpty()) { grow(); }
On 2014/03/07 15:18:38, reed1 wrote:
> style nit:
> 
> if (...) {
>    ...
> }

Done.

[iancottrell, 2014-03-07 16:11:14]

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h
File src/core/SkFreeList.h (right):

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:11: #include "SkTInternalSList.h"
On 2014/03/07 16:01:35, robertphillips wrote:
> Is this needed?

Yes.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:12: #include "SkRect.h"
On 2014/03/07 16:01:35, robertphillips wrote:
> Is this needed?

Done.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:13: #include "SkTDArray.h"
On 2014/03/07 16:01:35, robertphillips wrote:
> Do we need to include SkBBoxHierarchy.h?

Done.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:22: */
On 2014/03/07 16:01:35, robertphillips wrote:
> growth -> numItemsPerBlock?

Done.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:26: ~SkFreeList() {
On 2014/03/07 16:01:35, robertphillips wrote:
> Couldn't we add an assert here that all the managed object are back in the
> fAvailable list?

There is no reason that should have to be the case. So long as the lifetimes are
coincident, why do the work of putting them all back. QuadTree does not.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkFreeList.h#ne...
src/core/SkFreeList.h:81: for(int index = 0; index < growth; ++index) {
On 2014/03/07 16:01:35, robertphillips wrote:
> this->push

Already changed.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSList.h
File src/core/SkTInternalSList.h (right):

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSLis...
src/core/SkTInternalSList.h:27: ClassName* getSListNext() {                     
           \
On 2014/03/07 16:01:35, robertphillips wrote:
> don't need this-> here

There are cases with template expansion that will insist on it.
I generally try to be over explicit in macros just because you are never sure
where they will be used.
Also will result in compile error if used outside a class declaration this way.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSLis...
src/core/SkTInternalSList.h:30: void setSListNext(ClassName* next) {            
           \
On 2014/03/07 16:01:35, robertphillips wrote:
> same here

as above

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSLis...
src/core/SkTInternalSList.h:73: void takeAll(SkTInternalSList<T>* other) {
On 2014/03/07 16:01:35, robertphillips wrote:
> this->

Done.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSLis...
src/core/SkTInternalSList.h:74: if (isEmpty()) {
On 2014/03/07 16:01:35, robertphillips wrote:
> this->

Done.

https://codereview.chromium.org/187233002/diff/60001/src/core/SkTInternalSLis...
src/core/SkTInternalSList.h:78: while(!other->isEmpty()) {
On 2014/03/07 16:01:35, robertphillips wrote:
> this->

Done.

[iancottrell, 2014-03-11 00:57:00]

Tests added, and fast quadrant search for playback.
This cl is now in a fit state for full review.

[tomhudson, 2014-03-11 14:49:46]

lgtm

[tomhudson, 2014-03-14 10:32:14]

The CQ bit was checked by tomhudson@google.com

[commit-bot: I haz the power, 2014-03-14 10:32:19]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/iancottrell@google.com/187233002/140001

[commit-bot: I haz the power, 2014-03-14 10:32:24]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-03-14 10:32:24]

Failed to apply patch for gyp/tests.gypi:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  patching file gyp/tests.gypi
  Hunk #1 succeeded at 111 (offset 1 line).
  Hunk #2 FAILED at 144.
  1 out of 2 hunks FAILED -- saving rejects to file gyp/tests.gypi.rej

Patch:       gyp/tests.gypi
Index: gyp/tests.gypi
diff --git a/gyp/tests.gypi b/gyp/tests.gypi
index
c2b2c548e33a9a0659e26c6159ce35a3260d02f2..5499267923d47b2000d1958401e9550aeb551f6d
100644
--- a/gyp/tests.gypi
+++ b/gyp/tests.gypi
@@ -110,6 +110,7 @@
     '../tests/MessageBusTest.cpp',
     '../tests/MetaDataTest.cpp',
     '../tests/MipMapTest.cpp',
+    '../tests/ObjectPoolTest.cpp',
     '../tests/OSPathTest.cpp',
     '../tests/OnceTest.cpp',
     '../tests/PDFPrimitivesTest.cpp',
@@ -143,6 +144,7 @@
     '../tests/ShaderImageFilterTest.cpp',
     '../tests/ShaderOpacityTest.cpp',
     '../tests/SkBase64Test.cpp',
+    '../tests/SListTest.cpp',
     '../tests/SortTest.cpp',
     '../tests/SrcOverTest.cpp',
     '../tests/StreamTest.cpp',

[iancottrell, 2014-03-14 11:23:08]

The CQ bit was checked by iancottrell@google.com

[commit-bot: I haz the power, 2014-03-14 11:23:21]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/iancottrell@google.com/187233002/200001

[commit-bot: I haz the power, 2014-03-14 11:34:13]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-03-14 11:34:14]

Retried try job too often on Build-Ubuntu12-GCC-x86_64-Release-Trybot for
step(s) BuildTests
http://108.170.219.164:10117/buildstatus?builder=Build-Ubuntu12-GCC-x86_64-Re...

[Tom Hudson, 2014-03-14 12:02:51]

https://codereview.chromium.org/187233002/diff/200001/tests/SListTest.cpp
File tests/SListTest.cpp (right):

https://codereview.chromium.org/187233002/diff/200001/tests/SListTest.cpp#new...
tests/SListTest.cpp:82: if (!verifyList(reporter, list, "pop",
&testArray[index-1], index, -1)) {
This can go to index[-1], which the compiler is going to warn-as-error about. Do
you really just mean to test down to index >= 1?

[iancottrell, 2014-03-14 13:14:47]

https://codereview.chromium.org/187233002/diff/200001/tests/SListTest.cpp
File tests/SListTest.cpp (right):

https://codereview.chromium.org/187233002/diff/200001/tests/SListTest.cpp#new...
tests/SListTest.cpp:82: if (!verifyList(reporter, list, "pop",
&testArray[index-1], index, -1)) {
On 2014/03/14 12:02:52, Tom Hudson wrote:
> This can go to index[-1], which the compiler is going to warn-as-error about.
Do
> you really just mean to test down to index >= 1?

No, I meant exactly what I wrote, which is totally valid c++ as the calculated
pointer won't be deferenced by verifyList if the count of elements to check is
0.
I guess I can work around the *broken* warning....

[iancottrell, 2014-03-17 10:33:32]

The CQ bit was checked by iancottrell@google.com

[commit-bot: I haz the power, 2014-03-17 10:33:35]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/iancottrell@google.com/187233002/240001

[commit-bot: I haz the power, 2014-03-17 10:38:39]

Change committed as 13826