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

Review URL: https://codereview.chromium.org/1340703002

Cr-Commit-Position: refs/heads/master@{#349564}

diff --git a/cc/BUILD.gn b/cc/BUILD.gn
index 095c6dea..922ac34a 100644
--- a/cc/BUILD.gn
+++ b/cc/BUILD.gn

@@ -725,6 +725,7 @@
     "base/histograms_unittest.cc",
     "base/list_container_unittest.cc",
     "base/math_util_unittest.cc",
+    "base/random_access_list_container_unittest.cc",
     "base/region_unittest.cc",
     "base/rolling_time_delta_history_unittest.cc",
     "base/scoped_ptr_vector_unittest.cc",

diff --git a/cc/base/BUILD.gn b/cc/base/BUILD.gn
index 974f8a3..53194c9 100644
--- a/cc/base/BUILD.gn
+++ b/cc/base/BUILD.gn

@@ -18,6 +18,7 @@
     "list_container_helper.h",
     "math_util.cc",
     "math_util.h",
+    "random_access_list_container.h",
     "region.cc",
     "region.h",
     "resource_id.h",

diff --git a/cc/base/list_container_helper.h b/cc/base/list_container_helper.h
index fb953a6..31b2310 100644
--- a/cc/base/list_container_helper.h
+++ b/cc/base/list_container_helper.h

@@ -18,6 +18,9 @@
   template <typename T>
   friend class ListContainer;
 
+  template <typename T>
+  friend class RandomAccessListContainer;
+
   explicit ListContainerHelper(size_t max_size_for_derived_class);
   ListContainerHelper(size_t max_size_for_derived_class,
                       size_t num_of_elements_to_reserve_for);

diff --git a/cc/base/random_access_list_container.h b/cc/base/random_access_list_container.h
new file mode 100644
index 0000000..b2baf30
--- /dev/null
+++ b/cc/base/random_access_list_container.h

@@ -0,0 +1,94 @@
+// 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 <vector>
+
+#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 reserves the requested memory up front so only a single
+  // 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) {
+    items_.reserve(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 {
+    DCHECK_GE(index, 0u);
+    DCHECK_LT(index, items_.size());
+    return items_[index];
+  }
+
+  BaseElementType* operator[](size_t index) {
+    DCHECK_GE(index, 0u);
+    DCHECK_LT(index, items_.size());
+    return items_[index];
+  }
+
+  // Note that although BaseElementType objects can change, the pointer itself
+  // (in the vector) cannot. So this class only supports a const iterator.
+  using ConstIterator = typename std::vector<BaseElementType*>::const_iterator;
+  ConstIterator begin() const { return items_.begin(); }
+  ConstIterator end() const { return items_.end(); }
+
+ private:
+  ListContainerHelper helper_;
+  std::vector<BaseElementType*> items_;
+};
+
+}  // namespace cc
+
+#endif  // CC_BASE_RANDOM_ACCESS_LIST_CONTAINER_H_

diff --git a/cc/base/random_access_list_container_unittest.cc b/cc/base/random_access_list_container_unittest.cc
new file mode 100644
index 0000000..78004b4
--- /dev/null
+++ b/cc/base/random_access_list_container_unittest.cc

@@ -0,0 +1,107 @@
+// 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.
+
+#include "cc/base/random_access_list_container.h"
+
+#include <algorithm>
+#include <vector>
+
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace cc {
+namespace {
+
+class Base {
+ public:
+  virtual ~Base() {}
+  int get_value() const { return value_; }
+
+ protected:
+  explicit Base(int value) : value_(value) {}
+
+  int value_;
+};
+
+const int kMagicNumberOne = 1;
+const int kMagicNumberTwo = 2;
+const int kMagicNumberThree = 3;
+
+class Derived1 : public Base {
+ public:
+  Derived1() : Base(kMagicNumberOne) {}
+};
+
+class Derived2 : public Base {
+ public:
+  Derived2() : Base(kMagicNumberTwo) {}
+};
+
+class Derived3 : public Base {
+ public:
+  Derived3() : Base(kMagicNumberThree) {}
+};
+
+size_t LargestDerivedElementSize() {
+  static_assert(sizeof(Derived1) >= sizeof(Derived2),
+                "Derived2 is larger than Derived1");
+  static_assert(sizeof(Derived1) >= sizeof(Derived3),
+                "Derived3 is larger than Derived1");
+  return sizeof(Derived1);
+}
+
+TEST(RandomAccessListContainerTest, RandomAccess) {
+  RandomAccessListContainer<Base> list(LargestDerivedElementSize(), 1);
+
+  list.AllocateAndConstruct<Derived1>();
+  list.AllocateAndConstruct<Derived2>();
+  list.AllocateAndConstruct<Derived3>();
+  list.AllocateAndConstruct<Derived1>();
+  list.AllocateAndConstruct<Derived2>();
+  list.AllocateAndConstruct<Derived3>();
+
+  EXPECT_EQ(kMagicNumberOne, list[0]->get_value());
+  EXPECT_EQ(kMagicNumberTwo, list[1]->get_value());
+  EXPECT_EQ(kMagicNumberThree, list[2]->get_value());
+  EXPECT_EQ(kMagicNumberOne, list[3]->get_value());
+  EXPECT_EQ(kMagicNumberTwo, list[4]->get_value());
+  EXPECT_EQ(kMagicNumberThree, list[5]->get_value());
+
+  list.RemoveLast();
+  list.RemoveLast();
+  list.RemoveLast();
+
+  EXPECT_EQ(kMagicNumberOne, list[0]->get_value());
+  EXPECT_EQ(kMagicNumberTwo, list[1]->get_value());
+  EXPECT_EQ(kMagicNumberThree, list[2]->get_value());
+
+  list.AllocateAndConstruct<Derived3>();
+  list.AllocateAndConstruct<Derived2>();
+  list.AllocateAndConstruct<Derived1>();
+
+  EXPECT_EQ(kMagicNumberOne, list[0]->get_value());
+  EXPECT_EQ(kMagicNumberTwo, list[1]->get_value());
+  EXPECT_EQ(kMagicNumberThree, list[2]->get_value());
+  EXPECT_EQ(kMagicNumberThree, list[3]->get_value());
+  EXPECT_EQ(kMagicNumberTwo, list[4]->get_value());
+  EXPECT_EQ(kMagicNumberOne, list[5]->get_value());
+}
+
+TEST(RandomAccessListContainerTest, Clear) {
+  RandomAccessListContainer<Base> list(LargestDerivedElementSize(), 1);
+
+  list.AllocateAndConstruct<Derived1>();
+  list.AllocateAndConstruct<Derived2>();
+
+  EXPECT_EQ(kMagicNumberOne, list[0]->get_value());
+  EXPECT_EQ(kMagicNumberTwo, list[1]->get_value());
+
+  list.clear();
+  list.AllocateAndConstruct<Derived3>();
+
+  EXPECT_EQ(kMagicNumberThree, list[0]->get_value());
+}
+
+}  // namespace
+}  // namespace cc

diff --git a/cc/cc.gyp b/cc/cc.gyp
index 8bb61c3..2c6c280d3 100644
--- a/cc/cc.gyp
+++ b/cc/cc.gyp

@@ -85,6 +85,7 @@
         'base/list_container_helper.h',
         'base/math_util.cc',
         'base/math_util.h',
+        'base/random_access_list_container.h',
         'base/region.cc',
         'base/region.h',
         'base/resource_id.h',

diff --git a/cc/cc_tests.gyp b/cc/cc_tests.gyp
index 0ce77be5..c5a0124 100644
--- a/cc/cc_tests.gyp
+++ b/cc/cc_tests.gyp

@@ -22,6 +22,7 @@
       'base/histograms_unittest.cc',
       'base/list_container_unittest.cc',
       'base/math_util_unittest.cc',
+      'base/random_access_list_container_unittest.cc',
       'base/region_unittest.cc',
       'base/rolling_time_delta_history_unittest.cc',
       'base/scoped_ptr_vector_unittest.cc',