cc: Add RandomAccessListContainer, which has more restricted API.

cc: Add RandomAccessListContainer, which has more restricted API.

This patch adds RandomAccessListContainer, which is similar to
ListContainer with two important differences:
- It supports random access via operator[]
  - This is important for DisplayItemList use-case where an access into
    an rtree returns indices of elements to be rasterized. With this,
    we can access those elements directly.
- It doesn't support middle-of-list operations (inserts/deletes)
  - This is done in order to simplify maintaining random access capabilities

BUG=527245
R=weiliangc, danakj
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

Committed: https://crrev.com/b10241fcd596d102733731b3d2db8e9ba875e41c
Cr-Commit-Position: refs/heads/master@{#349564}

[vmpstr, 2015-09-14 18:34:50]

Please take a look. This depends on https://codereview.chromium.org/1336763006/.
Also, let me know if you'd prefer to have this in a separate file (ie
random_access_list_container.h). Also, let me know if you can think of a better
name.

[weiliangc, 2015-09-14 20:02:47]

We can add comment to RandomAccessListContainer to say it's used for
DisplayItemList and its general functionality?

Possibly we can call the other SequentialListContainers and add similar
comments?

Name for ListContainers aren't exposed too much so maybe it's fine?
*hand-waving*

https://codereview.chromium.org/1340703002/diff/20001/cc/base/list_container.h
File cc/base/list_container.h (right):

https://codereview.chromium.org/1340703002/diff/20001/cc/base/list_container....
cc/base/list_container.h:561: const BaseElementType* operator[](size_t index)
const {
Can you also add at()? Or explain in comment this class doesn't support at?

https://codereview.chromium.org/1340703002/diff/20001/cc/base/list_container....
cc/base/list_container.h:567: using ConstIterator = typename
std::deque<BaseElementType*>::const_iterator;
Seems like only have const access, is this intended? Can you add it to comment?

[vmpstr, 2015-09-15 00:17:48]

https://codereview.chromium.org/1340703002/diff/20001/cc/base/list_container.h
File cc/base/list_container.h (right):

https://codereview.chromium.org/1340703002/diff/20001/cc/base/list_container....
cc/base/list_container.h:561: const BaseElementType* operator[](size_t index)
const {
On 2015/09/14 20:02:47, weiliangc wrote:
> Can you also add at()? Or explain in comment this class doesn't support at?

I'm not sure why we need at() as well. I assume you mean something similar to
vector::at, which is equivalent to operator[] except it does bounds checking. I
do bounds checking with dchecks in operator[] here.

https://codereview.chromium.org/1340703002/diff/20001/cc/base/list_container....
cc/base/list_container.h:567: using ConstIterator = typename
std::deque<BaseElementType*>::const_iterator;
On 2015/09/14 20:02:47, weiliangc wrote:
> Seems like only have const access, is this intended? Can you add it to
comment?

Hmm. The const access is to the iterator whose value_type is a BaseElementType*
const, so you technically can still change the value pointed to, you just can't
change the deque directly... That is,

*it = new_ptr; // error
(*it)->base_value = new_base_value; // ok
**it = new_object; // also ok

This is by design, but maybe this mimics more of the non-const ListContainer
iterators?

FWIW, For ListContainers, both const and non-const iterators don't allow *it =
new_ptr;

[weiliangc, 2015-09-15 15:25:16]

On 2015/09/15 at 00:17:48, vmpstr wrote:
> https://codereview.chromium.org/1340703002/diff/20001/cc/base/list_container.h
> File cc/base/list_container.h (right):
> 
>
https://codereview.chromium.org/1340703002/diff/20001/cc/base/list_container....
> cc/base/list_container.h:561: const BaseElementType* operator[](size_t index)
const {
> On 2015/09/14 20:02:47, weiliangc wrote:
> > Can you also add at()? Or explain in comment this class doesn't support at?
> 
> I'm not sure why we need at() as well. I assume you mean something similar to
vector::at, which is equivalent to operator[] except it does bounds checking. I
do bounds checking with dchecks in operator[] here.

I'm thinking at DisplayList level might be hard to tell that operator[] is ok to
use but not at()?

More of a nit than hard requirement, up to you. :)
> 
>
https://codereview.chromium.org/1340703002/diff/20001/cc/base/list_container....
> cc/base/list_container.h:567: using ConstIterator = typename
std::deque<BaseElementType*>::const_iterator;
> On 2015/09/14 20:02:47, weiliangc wrote:
> > Seems like only have const access, is this intended? Can you add it to
comment?
> 
> Hmm. The const access is to the iterator whose value_type is a
BaseElementType* const, so you technically can still change the value pointed
to, you just can't change the deque directly... That is,
> 
> *it = new_ptr; // error
> (*it)->base_value = new_base_value; // ok
> **it = new_object; // also ok
> 
> This is by design, but maybe this mimics more of the non-const ListContainer
iterators?
> 
> FWIW, For ListContainers, both const and non-const iterators don't allow *it =
new_ptr;

Sorry, my comment needs better placement. I was thinking why only const version
of [] and iterator but I agree non-const iterator is weird.

[weiliangc, 2015-09-15 15:25:40]

https://codereview.chromium.org/1340703002/diff/60001/cc/base/random_access_l...
File cc/base/random_access_list_container.h (right):

https://codereview.chromium.org/1340703002/diff/60001/cc/base/random_access_l...
cc/base/random_access_list_container.h:72: const BaseElementType*
operator[](size_t index) const {
BaseElementType* const here?

[vmpstr, 2015-09-15 18:10:25]

Please take a look

> I'm thinking at DisplayList level might be hard to tell that operator[] is ok
to
> use but not at()?
> 
> More of a nit than hard requirement, up to you. :)

Cool.. I'd prefer to not add at(), since it can be confusing since I don't think
we should encourage people to use it for things like vectors.

https://codereview.chromium.org/1340703002/diff/60001/cc/base/random_access_l...
File cc/base/random_access_list_container.h (right):

https://codereview.chromium.org/1340703002/diff/60001/cc/base/random_access_l...
cc/base/random_access_list_container.h:72: const BaseElementType*
operator[](size_t index) const {
On 2015/09/15 15:25:40, weiliangc wrote:
> BaseElementType* const here?

I've added a non const overload.

[vmpstr, 2015-09-15 18:54:43]

As per discussion, also added a comment. PTAL

[weiliangc, 2015-09-15 19:01:17]

LGTM

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
File cc/base/random_access_list_container.h (right):

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:72: const BaseElementType*
operator[](size_t index) const {
nit: // Return a const pointer isn't very useful.

[danakj, 2015-09-15 20:11:09]

> - It supports random access via operator[]
> - It doesn't support middle-of-list operations (inserts/deletes)

Can you explain why these are important in the description?

[vmpstr, 2015-09-15 20:20:00]

On 2015/09/15 20:11:09, danakj wrote:
> > - It supports random access via operator[]
> > - It doesn't support middle-of-list operations (inserts/deletes)
> 
> Can you explain why these are important in the description?

Done.

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
File cc/base/random_access_list_container.h (right):

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:72: const BaseElementType*
operator[](size_t index) const {
On 2015/09/15 19:01:17, weiliangc wrote:
> nit: // Return a const pointer isn't very useful.

Ehh I'd prefer to leave that comment off, unless you insist :)

[danakj, 2015-09-15 20:21:37]

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
File cc/base/random_access_list_container.h (right):

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:30: // This constructor omits input
variable for max_size_for_derived_class. This
"omits /the/ input variable for"

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:33: RandomAccessListContainer() :
helper_(sizeof(BaseElementType)) {}
will there be any callers of this? do we need it? can't they just sizeof()?

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:35: // This constructor reserves the
requested memory up front so only single
only a single

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:78: BaseElementType* operator[](size_t
index) {
can't this still be a const method? it's returning a pointer in its vector

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:92: std::deque<BaseElementType*> items_;
Can you leave a comment about why you're using a deque instead of a vector? What
perf characteristics are you choosing here?

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
File cc/base/random_access_list_container_unittest.cc (right):

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container_unittest.cc:9: #include
"testing/gmock/include/gmock/gmock.h"
whitespace above this

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container_unittest.cc:53:
TEST(RandomAccessListContainerTest, RandomAccess) {
Is it possible to test clear() doesn't leave things behind in items_?

Maybe clear(), insert, and verify your new item is at [0]? Or something?

[vmpstr, 2015-09-15 21:05:52]

PTAL.

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
File cc/base/random_access_list_container.h (right):

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:30: // This constructor omits input
variable for max_size_for_derived_class. This
On 2015/09/15 20:21:37, danakj wrote:
> "omits /the/ input variable for"

Done.

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:33: RandomAccessListContainer() :
helper_(sizeof(BaseElementType)) {}
On 2015/09/15 20:21:37, danakj wrote:
> will there be any callers of this? do we need it? can't they just sizeof()?

Removed.

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:35: // This constructor reserves the
requested memory up front so only single
On 2015/09/15 20:21:37, danakj wrote:
> only a single

Done.

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:78: BaseElementType* operator[](size_t
index) {
On 2015/09/15 20:21:37, danakj wrote:
> can't this still be a const method? it's returning a pointer in its vector

Can't overload methods on the return type. This is a common pattern of
accessors. See https://isocpp.org/wiki/faq/const-correctness#const-overloading

Let me know if you'd like me to change it.

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:92: std::deque<BaseElementType*> items_;
On 2015/09/15 20:21:37, danakj wrote:
> Can you leave a comment about why you're using a deque instead of a vector?
What
> perf characteristics are you choosing here?

I can change it to a vector, if you'd prefer. I went with a deque because of a
constant time push back / pop, but I don't think there are any other benefits
that I'm relying on. Vector would provide amortized same complexity, so it
doesn't really matter (in my eyes) which one we pick. 

I would also like to avoid putting a comment in the code that says all of this,
since I don't think that's a common practice in cc. That is, we usually justify
choices on reviews, not as code comments? I might be wrong.

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
File cc/base/random_access_list_container_unittest.cc (right):

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container_unittest.cc:9: #include
"testing/gmock/include/gmock/gmock.h"
On 2015/09/15 20:21:37, danakj wrote:
> whitespace above this

Done.

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container_unittest.cc:53:
TEST(RandomAccessListContainerTest, RandomAccess) {
On 2015/09/15 20:21:37, danakj wrote:
> Is it possible to test clear() doesn't leave things behind in items_?
> 
> Maybe clear(), insert, and verify your new item is at [0]? Or something?

Done.

[danakj, 2015-09-15 21:19:50]

LGTM

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
File cc/base/random_access_list_container.h (right):

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:78: BaseElementType* operator[](size_t
index) {
On 2015/09/15 21:05:52, vmpstr wrote:
> On 2015/09/15 20:21:37, danakj wrote:
> > can't this still be a const method? it's returning a pointer in its vector
> 
> Can't overload methods on the return type. This is a common pattern of
> accessors. See https://isocpp.org/wiki/faq/const-correctness#const-overloading
> 
> Let me know if you'd like me to change it.

oh.. ok thanks

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:92: std::deque<BaseElementType*> items_;
On 2015/09/15 21:05:52, vmpstr wrote:
> On 2015/09/15 20:21:37, danakj wrote:
> > Can you leave a comment about why you're using a deque instead of a vector?
> What
> > perf characteristics are you choosing here?
> 
> I can change it to a vector, if you'd prefer. I went with a deque because of a
> constant time push back / pop, but I don't think there are any other benefits
> that I'm relying on. Vector would provide amortized same complexity, so it
> doesn't really matter (in my eyes) which one we pick. 
> 
> I would also like to avoid putting a comment in the code that says all of
this,
> since I don't think that's a common practice in cc. That is, we usually
justify
> choices on reviews, not as code comments? I might be wrong.

I'd like to change that when we choose a specific type for performance
characteristics then. If there's no reason to prefer deque then I'd prefer a
more common vector, I think. In this case there are a lot of inserts so
amortized # of mallocs, but a bunch of memcpy that deque won't have? But this is
a set of pointers, so they aren't that big anyways.

[vmpstr, 2015-09-15 22:06:58]

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
File cc/base/random_access_list_container.h (right):

https://codereview.chromium.org/1340703002/diff/140001/cc/base/random_access_...
cc/base/random_access_list_container.h:92: std::deque<BaseElementType*> items_;
On 2015/09/15 21:19:50, danakj wrote:
> On 2015/09/15 21:05:52, vmpstr wrote:
> > On 2015/09/15 20:21:37, danakj wrote:
> > > Can you leave a comment about why you're using a deque instead of a
vector?
> > What
> > > perf characteristics are you choosing here?
> > 
> > I can change it to a vector, if you'd prefer. I went with a deque because of
a
> > constant time push back / pop, but I don't think there are any other
benefits
> > that I'm relying on. Vector would provide amortized same complexity, so it
> > doesn't really matter (in my eyes) which one we pick. 
> > 
> > I would also like to avoid putting a comment in the code that says all of
> this,
> > since I don't think that's a common practice in cc. That is, we usually
> justify
> > choices on reviews, not as code comments? I might be wrong.
> 
> I'd like to change that when we choose a specific type for performance
> characteristics then. If there's no reason to prefer deque then I'd prefer a
> more common vector, I think. In this case there are a lot of inserts so
> amortized # of mallocs, but a bunch of memcpy that deque won't have? But this
is
> a set of pointers, so they aren't that big anyways.

Switched to a vector.

[vmpstr, 2015-09-17 21:25:53]

The CQ bit was checked by vmpstr@chromium.org

[vmpstr, 2015-09-17 21:25:53]

The patchset sent to the CQ was uploaded after l-g-t-m from
weiliangc@chromium.org, danakj@chromium.org
Link to the patchset: https://codereview.chromium.org/1340703002/#ps220001
(title: " ")

[vmpstr, 2015-09-17 21:26:52]

The CQ bit was unchecked by vmpstr@chromium.org

[vmpstr, 2015-09-17 21:27:09]

The CQ bit was checked by vmpstr@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2015-09-17 21:29:07]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1340703002/220001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1340703002/220001

[commit-bot: I haz the power, 2015-09-17 23:14:10]

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

[commit-bot: I haz the power, 2015-09-17 23:14:11]

Dry run: This issue passed the CQ dry run.

[vmpstr, 2015-09-18 01:03:02]

The CQ bit was checked by vmpstr@chromium.org

[commit-bot: I haz the power, 2015-09-18 01:03:58]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1340703002/220001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1340703002/220001

[commit-bot: I haz the power, 2015-09-18 01:10:21]

Committed patchset #12 (id:220001)

[commit-bot: I haz the power, 2015-09-18 01:11:05]

Patchset 12 (id:??) landed as
https://crrev.com/b10241fcd596d102733731b3d2db8e9ba875e41c
Cr-Commit-Position: refs/heads/master@{#349564}