cc: Add RandomAccessListContainer, which has more restricted API.

cc/base/random_access_list_container.h

Index: cc/base/random_access_list_container.h
diff --git a/cc/base/random_access_list_container.h b/cc/base/random_access_list_container.h
new file mode 100644
index 0000000000000000000000000000000000000000..b3e62de70692b64850412a3f3f88042b7ab1445a
--- /dev/null
+++ b/cc/base/random_access_list_container.h
@@ -0,0 +1,97 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CC_BASE_RANDOM_ACCESS_LIST_CONTAINER_H_
+#define CC_BASE_RANDOM_ACCESS_LIST_CONTAINER_H_
+
+#include <deque>
+
+#include "base/logging.h"
+#include "cc/base/list_container_helper.h"
+
+namespace cc {
+
+// RandomAccessListContainer is a container similar to ListContainer (see
+// list_container.h), but it allows random access into its elements via
+// operator[]. In order to have efficient support for random access, some
+// functionality is not available for RandomAccessListContainers, such as
+// insert/deletes in the middle of the list.
+template <class BaseElementType>
+class RandomAccessListContainer {
+ public:
+  // BaseElementType is the type of raw pointers this class hands out; however,
+  // its derived classes might require different memory sizes.
+  // max_size_for_derived_class the largest memory size required for all the
+  // derived classes to use for allocation.
+  explicit RandomAccessListContainer(size_t max_size_for_derived_class)
+      : helper_(max_size_for_derived_class) {}
+
+  // This constructor omits input variable for max_size_for_derived_class. This

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

"omits /the/ input variable for"

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

Done.

+  // is used when there is no derived classes from BaseElementType we need to
+  // worry about, and allocation size is just sizeof(BaseElementType).
+  RandomAccessListContainer() : helper_(sizeof(BaseElementType)) {}

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

will there be any callers of this? do we need it? can't they just sizeof()?

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

Removed.

+
+  // This constructor reserves the requested memory up front so only single

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

only a single

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

Done.

+  // allocation is needed. When num_of_elements_to_reserve_for is zero, use the
+  // default size.
+  RandomAccessListContainer(size_t max_size_for_derived_class,
+                            size_t num_of_elements_to_reserve_for)
+      : helper_(max_size_for_derived_class, num_of_elements_to_reserve_for) {}
+
+  ~RandomAccessListContainer() {
+    for (BaseElementType* item : items_)
+      item->~BaseElementType();
+  }
+
+  void clear() {
+    for (BaseElementType* item : items_)
+      item->~BaseElementType();
+    helper_.clear();
+    items_.clear();
+  }
+
+  bool empty() const { return helper_.empty(); }
+  size_t size() const { return helper_.size(); }
+  size_t GetCapacityInBytes() const { return helper_.GetCapacityInBytes(); }
+
+  template <typename DerivedElementType>
+  DerivedElementType* AllocateAndConstruct() {
+    auto* value =
+        new (helper_.Allocate(sizeof(DerivedElementType))) DerivedElementType;
+    items_.push_back(value);
+    return value;
+  }
+
+  void RemoveLast() {
+    items_.back()->~BaseElementType();
+    items_.pop_back();
+    helper_.RemoveLast();
+  }
+
+  const BaseElementType* operator[](size_t index) const {

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

nit: // Return a const pointer isn't very useful.

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

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

+    DCHECK_GE(index, 0u);
+    DCHECK_LT(index, items_.size());
+    return items_[index];
+  }
+
+  BaseElementType* operator[](size_t index) {

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

can't this still be a const method? it's returning a pointer in its vector

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

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.

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

oh.. ok thanks

+    DCHECK_GE(index, 0u);
+    DCHECK_LT(index, items_.size());
+    return items_[index];
+  }
+
+  // Note that although BaseElementType objects can change, the pointer itself
+  // (in the deque) cannot. So this class only supports a const iterator.
+  using ConstIterator = typename std::deque<BaseElementType*>::const_iterator;
+  ConstIterator begin() const { return items_.begin(); }
+  ConstIterator end() const { return items_.end(); }
+
+ private:
+  ListContainerHelper helper_;
+  std::deque<BaseElementType*> items_;

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

Can you leave a comment about why you're using a deque instead of a vector? What
perf characteristics are you choosing here?

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

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.

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

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]

Switched to a vector.

+};
+
+}  // namespace cc
+
+#endif  // CC_BASE_RANDOM_ACCESS_LIST_CONTAINER_H_