Refactor SkDeque's iterator and allocation method

This CL:

loosens up the restrictions on SkDeque's iterator - allowing forward, backward and mixed iteration

allows the user to specify the number of elements that are allocated together in a block

[reed1, 2012-07-13 14:59:40]

I need to understand more about the changes to Deque first

http://codereview.appspot.com/6353098/diff/1/include/core/SkClipStack.h
File include/core/SkClipStack.h (right):

http://codereview.appspot.com/6353098/diff/1/include/core/SkClipStack.h#newco...
include/core/SkClipStack.h:85: 
// What does this do?

http://codereview.appspot.com/6353098/diff/1/include/core/SkDeque.h
File include/core/SkDeque.h (left):

http://codereview.appspot.com/6353098/diff/1/include/core/SkDeque.h#oldcode18
include/core/SkDeque.h:18: SkDeque(size_t elemSize, void* storage, size_t
storageSize);
// What is allocCount?

http://codereview.appspot.com/6353098/diff/1/include/core/SkDeque.h#oldcode41
include/core/SkDeque.h:41: 
// What is this, and why should it be public?

http://codereview.appspot.com/6353098/diff/1/include/core/SkDeque.h#oldcode56
include/core/SkDeque.h:56: void reset(const SkDeque& d);
// What does front mean, esp. in a Front-To-Back iterator?

[robertphillips, 2012-07-13 15:10:22]

http://codereview.appspot.com/6353098/diff/1/include/core/SkClipStack.h
File include/core/SkClipStack.h (right):

http://codereview.appspot.com/6353098/diff/1/include/core/SkClipStack.h#newco...
include/core/SkClipStack.h:85: 
This is just a helper function that updates "fClip" to the current state of
"fIter". Before it was only "used" by "next" but with the addition of "prev" I
didn't want to duplicate the code. "fClip" is a member variable otherwise I
would've made it a static. 

If we add a "cur" entry point to SkDeque::F2BIter we could remove the "rec"
parameter and then get rid of the "Rec" pre-declaration weirdness in this
header.

http://codereview.appspot.com/6353098/diff/1/include/core/SkDeque.h
File include/core/SkDeque.h (left):

http://codereview.appspot.com/6353098/diff/1/include/core/SkDeque.h#oldcode18
include/core/SkDeque.h:18: SkDeque(size_t elemSize, void* storage, size_t
storageSize);
allocCount replaces the old INIT_ELEM_COUNT #define to specify the number of
elements to allocate per block. In a later CL I would like to increase
allocCount from 1 to ~5 for the clip stack. Given the behavior of the clip
stack, it seems wasteful to keep allocating & deallocating a block for each
clip.

http://codereview.appspot.com/6353098/diff/1/include/core/SkDeque.h#oldcode41
include/core/SkDeque.h:41: 
This is only public so that the unit test can verify that allocCount is working.
I would've liked to have friended the DequeTest but it is all static methods. It
returns the number of block the deque has allocated. Before the allocCount
change we would always have 1 block for each stored element. If allocCount is
set to something other than 1 we can have fewer.

http://codereview.appspot.com/6353098/diff/1/include/core/SkDeque.h#oldcode56
include/core/SkDeque.h:56: void reset(const SkDeque& d);
I was considering renaming F2BIter to just Iter since now it can be either front
to back or back to front. Thoughts?

[robertphillips, 2012-07-13 19:41:25]

Added comments.
Renamed Iterators (both in SkDeque & SkClipStack)
Added shallow wrapper Iterators to hide reverse iteration.

[reed1, 2012-07-13 19:54:27]

can we have a CL just for the Deque change? It seems core and important enough
to focus on on its own.

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h
File include/core/SkDeque.h (left):

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h#oldcode18
include/core/SkDeque.h:18: SkDeque(size_t elemSize, void* storage, size_t
storageSize);
If/since these comments should show up in doxygen, you should use

/**
 * ...
 */

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h#oldcode42
include/core/SkDeque.h:42: private:
Perhaps Head should be renamed Block?

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h#oldcode47
include/core/SkDeque.h:47: public:
Enum name should probably be singular, so when its used in a function, it
clearly is asking for a single value.

Enum name is scoped by the class, so it doesn't need the Sk

I wonder if IterStart or StartFrom are better names? Are front/back better or
worse than Beginning/End?
- kFront_IterStart, kBack_IterStart

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h
File include/core/SkDeque.h (right):

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h#newcode45
include/core/SkDeque.h:45: // can be used to gauge the effectiveness of the
selected allocCount.
numBlocksAllocated() ?

[robertphillips, 2012-07-16 13:14:14]

Now focused on SkDeque

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h
File include/core/SkDeque.h (left):

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h#oldcode18
include/core/SkDeque.h:18: SkDeque(size_t elemSize, void* storage, size_t
storageSize);
On 2012/07/13 19:54:27, reed1 wrote:
> If/since these comments should show up in doxygen, you should use
> 
> /**
>  * ...
>  */

Done.

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h#oldcode42
include/core/SkDeque.h:42: private:
On 2012/07/13 19:54:27, reed1 wrote:
> Perhaps Head should be renamed Block?

Done.

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h#oldcode47
include/core/SkDeque.h:47: public:
On 2012/07/13 19:54:27, reed1 wrote:
> Enum name should probably be singular, so when its used in a function, it
> clearly is asking for a single value.
> 
> Enum name is scoped by the class, so it doesn't need the Sk
> 
> I wonder if IterStart or StartFrom are better names? Are front/back better or
> worse than Beginning/End?
> - kFront_IterStart, kBack_IterStart

Done.

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h
File include/core/SkDeque.h (right):

http://codereview.appspot.com/6353098/diff/5001/include/core/SkDeque.h#newcode45
include/core/SkDeque.h:45: // can be used to gauge the effectiveness of the
selected allocCount.
On 2012/07/13 19:54:27, reed1 wrote:
> numBlocksAllocated() ?

Done.

[reed1, 2012-07-16 14:21:45]

much clearer. a few nits/questions, but LGTM

http://codereview.appspot.com/6353098/diff/13001/include/core/SkDeque.h
File include/core/SkDeque.h (right):

http://codereview.appspot.com/6353098/diff/13001/include/core/SkDeque.h#newco...
include/core/SkDeque.h:46: /**
I still don't really like making this part of the real API, but I see that it is
interesting for debugging/testing.

1. can we just compute the block-number when we're asked, instead of storing it?
2. can we make this private, and use friends somehow to allow unittests to call
it?
3. shall I just clam-up over this small issue?

http://codereview.appspot.com/6353098/diff/13001/include/core/SkDeque.h#newco...
include/core/SkDeque.h:94: void reset(const SkDeque& d) {
this->INHERITED::...

[robertphillips, 2012-07-16 15:12:09]

http://codereview.appspot.com/6353098/diff/13001/include/core/SkDeque.h
File include/core/SkDeque.h (right):

http://codereview.appspot.com/6353098/diff/13001/include/core/SkDeque.h#newco...
include/core/SkDeque.h:46: /**
1) Done.
2) I made the method private, added a helper class to the unit test and friended
it in the header. It is a bit ugly/goofy - is there a more standard/nicer way
this has been done?
3) I think it is good to pursue these things.

http://codereview.appspot.com/6353098/diff/13001/include/core/SkDeque.h#newco...
include/core/SkDeque.h:94: void reset(const SkDeque& d) {
On 2012/07/16 14:21:45, reed1 wrote:
> this->INHERITED::...

Done.

[reed1, 2012-07-16 15:29:11]

Do we want to keep the SkASSERT in the iter?

http://codereview.appspot.com/6353098/diff/18001/include/core/SkDeque.h
File include/core/SkDeque.h (right):

http://codereview.appspot.com/6353098/diff/18001/include/core/SkDeque.h#newco...
include/core/SkDeque.h:118: void*   fInitialStorage;
nice clarifying comments! Could also rename these fields in response to that,
but not required.

http://codereview.appspot.com/6353098/diff/18001/src/core/SkDeque.cpp
File src/core/SkDeque.cpp (right):

http://codereview.appspot.com/6353098/diff/18001/src/core/SkDeque.cpp#newcode216
src/core/SkDeque.cpp:216: 
nit: const Block* ?

[robertphillips, 2012-07-16 15:44:14]

Do you mean the asserts in the hidden functions in F2BIter? If so, then I think
we should keep them since we really shouldn't be getting into those methods.

http://codereview.appspot.com/6353098/diff/18001/src/core/SkDeque.cpp
File src/core/SkDeque.cpp (right):

http://codereview.appspot.com/6353098/diff/18001/src/core/SkDeque.cpp#newcode216
src/core/SkDeque.cpp:216: 
On 2012/07/16 15:29:11, reed1 wrote:
> nit: const Block* ?

Done.

[reed1, 2012-07-16 15:46:34]

hiding : ah right

I think a better way might be to either

1. inherit privately
2. embed the base iter, rather than inheriting
?

[robertphillips, 2012-07-16 16:55:41]

Switched over to private inheritance

[reed1, 2012-07-16 16:56:54]

lgtm

[robertphillips, 2012-07-16 16:59:12]

committed as r4624