Use Custome ListContainer to Allocate SharedQuadState

In RenderPass use ListContainer for generating SharedQuadState and act
as SharedQuadStateList.

This CL follows 448303002 which use ListContainer for
DrawQuad.

BUG=344962

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

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

5 files changed, 192 insertions, 69 deletions

diff --git a/cc/quads/list_container.cc b/cc/quads/list_container.cc
index b1501c0..fd4e2f4 100644
--- a/cc/quads/list_container.cc
+++ b/cc/quads/list_container.cc
@@ -87,8 +87,8 @@ class ListContainer<BaseElementType>::ListContainerCharAllocator {
         size_(0),
         list_count_(0),
         last_list_(NULL) {
-    DCHECK_NE(0u, element_count);
-    AllocateNewList(element_count);
+    AllocateNewList(element_count > 0 ? element_count
+                                      : kDefaultNumElementTypesToReserve);
   }
 
   ~ListContainerCharAllocator() {}
@@ -281,72 +281,72 @@ template <typename BaseElementType>
 typename ListContainer<BaseElementType>::ConstReverseIterator
 ListContainer<BaseElementType>::rbegin() const {
   if (data_->IsEmpty())
-    return ConstReverseIterator(data_.get(), 0, NULL);
+    return ConstReverseIterator(data_.get(), 0, NULL, 0);
 
   size_t last_id = data_->list_count() - 1;
   return ConstReverseIterator(
-      data_.get(), last_id, data_->InnerListById(last_id)->LastElement());
+      data_.get(), last_id, data_->InnerListById(last_id)->LastElement(), 0);
 }
 
 template <typename BaseElementType>
 typename ListContainer<BaseElementType>::ConstReverseIterator
 ListContainer<BaseElementType>::rend() const {
-  return ConstReverseIterator(data_.get(), 0, NULL);
+  return ConstReverseIterator(data_.get(), 0, NULL, size());
 }
 
 template <typename BaseElementType>
 typename ListContainer<BaseElementType>::ReverseIterator
 ListContainer<BaseElementType>::rbegin() {
   if (data_->IsEmpty())
-    return ReverseIterator(data_.get(), 0, NULL);
+    return ReverseIterator(data_.get(), 0, NULL, 0);
 
   size_t last_id = data_->list_count() - 1;
   return ReverseIterator(
-      data_.get(), last_id, data_->InnerListById(last_id)->LastElement());
+      data_.get(), last_id, data_->InnerListById(last_id)->LastElement(), 0);
 }
 
 template <typename BaseElementType>
 typename ListContainer<BaseElementType>::ReverseIterator
 ListContainer<BaseElementType>::rend() {
-  return ReverseIterator(data_.get(), 0, NULL);
+  return ReverseIterator(data_.get(), 0, NULL, size());
 }
 
 template <typename BaseElementType>
 typename ListContainer<BaseElementType>::ConstIterator
 ListContainer<BaseElementType>::begin() const {
   if (data_->IsEmpty())
-    return ConstIterator(data_.get(), 0, NULL);
+    return ConstIterator(data_.get(), 0, NULL, 0);
 
-  return ConstIterator(data_.get(), 0, data_->InnerListById(0)->Begin());
+  return ConstIterator(data_.get(), 0, data_->InnerListById(0)->Begin(), 0);
 }
 
 template <typename BaseElementType>
 typename ListContainer<BaseElementType>::ConstIterator
 ListContainer<BaseElementType>::end() const {
   if (data_->IsEmpty())
-    return ConstIterator(data_.get(), 0, NULL);
+    return ConstIterator(data_.get(), 0, NULL, size());
 
   size_t last_id = data_->list_count() - 1;
-  return ConstIterator(data_.get(), last_id, NULL);
+  return ConstIterator(data_.get(), last_id, NULL, size());
 }
 
 template <typename BaseElementType>
 typename ListContainer<BaseElementType>::Iterator
 ListContainer<BaseElementType>::begin() {
   if (data_->IsEmpty())
-    return Iterator(data_.get(), 0, NULL);
+    return Iterator(data_.get(), 0, NULL, 0);
 
-  return Iterator(data_.get(), 0, data_->InnerListById(0)->Begin());
+  return Iterator(data_.get(), 0, data_->InnerListById(0)->Begin(), 0);
 }
 
 template <typename BaseElementType>
 typename ListContainer<BaseElementType>::Iterator
 ListContainer<BaseElementType>::end() {
   if (data_->IsEmpty())
-    return Iterator(data_.get(), 0, NULL);
+    return Iterator(data_.get(), 0, NULL, size());
 
   size_t last_id = data_->list_count() - 1;
-  return Iterator(data_.get(), last_id, NULL);
+  return Iterator(data_.get(), last_id, NULL, size());
 }
 
 template <typename BaseElementType>
@@ -377,6 +377,7 @@ template <typename BaseElementType>
 const BaseElementType* ListContainer<BaseElementType>::ElementAt(
     size_t index) const {
   DCHECK_LT(index, size());
+  size_t original_index = index;
   size_t list_index;
   for (list_index = 0; list_index < data_->list_count(); ++list_index) {
     size_t current_size = data_->InnerListById(list_index)->size;
@@ -386,12 +387,14 @@ const BaseElementType* ListContainer<BaseElementType>::ElementAt(
   }
   return &*ConstIterator(data_.get(),
                          list_index,
-                         data_->InnerListById(list_index)->ElementAt(index));
+                         data_->InnerListById(list_index)->ElementAt(index),
+                         original_index);
 }
 
 template <typename BaseElementType>
 BaseElementType* ListContainer<BaseElementType>::ElementAt(size_t index) {
   DCHECK_LT(index, size());
+  size_t original_index = index;
   size_t list_index;
   for (list_index = 0; list_index < data_->list_count(); ++list_index) {
     size_t current_size = data_->InnerListById(list_index)->size;
@@ -401,7 +404,8 @@ BaseElementType* ListContainer<BaseElementType>::ElementAt(size_t index) {
   }
   return &*Iterator(data_.get(),
                     list_index,
-                    data_->InnerListById(list_index)->ElementAt(index));
+                    data_->InnerListById(list_index)->ElementAt(index),
+                    original_index);
 }
 
 template <typename BaseElementType>
@@ -442,8 +446,10 @@ template <typename BaseElementType>
 ListContainer<BaseElementType>::Iterator::Iterator(
     ListContainerCharAllocator* container,
     size_t vector_ind,
-    char* item_iter)
-    : PositionInListContainerCharAllocator(container, vector_ind, item_iter) {
+    char* item_iter,
+    size_t index)
+    : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
+      index_(index) {
 }
 
 template <typename BaseElementType>
@@ -474,23 +480,31 @@ typename ListContainer<BaseElementType>::Iterator
 ListContainer<BaseElementType>::Iterator::
 operator++() {
   this->Increment();
+  ++index_;
   return *this;
 }
 
+template <typename BaseElementType>
+size_t ListContainer<BaseElementType>::Iterator::index() const {
+  return index_;
+}
+
 // ListContainer::ConstIterator
 /////////////////////////////////////////////////
 template <typename BaseElementType>
 ListContainer<BaseElementType>::ConstIterator::ConstIterator(
     const typename ListContainer<BaseElementType>::Iterator& other)
-    : PositionInListContainerCharAllocator(other) {
+    : PositionInListContainerCharAllocator(other), index_(other.index()) {
 }
 
 template <typename BaseElementType>
 ListContainer<BaseElementType>::ConstIterator::ConstIterator(
     ListContainerCharAllocator* container,
     size_t vector_ind,
-    char* item_iter)
-    : PositionInListContainerCharAllocator(container, vector_ind, item_iter) {
+    char* item_iter,
+    size_t index)
+    : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
+      index_(index) {
 }
 
 template <typename BaseElementType>
@@ -523,17 +537,25 @@ typename ListContainer<BaseElementType>::ConstIterator
 ListContainer<BaseElementType>::ConstIterator::
 operator++() {
   this->Increment();
+  ++index_;
   return *this;
 }
 
+template <typename BaseElementType>
+size_t ListContainer<BaseElementType>::ConstIterator::index() const {
+  return index_;
+}
+
 // ListContainer::ReverseIterator
 /////////////////////////////////////////////////
 template <typename BaseElementType>
 ListContainer<BaseElementType>::ReverseIterator::ReverseIterator(
     ListContainerCharAllocator* container,
     size_t vector_ind,
-    char* item_iter)
-    : PositionInListContainerCharAllocator(container, vector_ind, item_iter) {
+    char* item_iter,
+    size_t index)
+    : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
+      index_(index) {
 }
 
 template <typename BaseElementType>
@@ -566,23 +588,31 @@ typename ListContainer<BaseElementType>::ReverseIterator
 ListContainer<BaseElementType>::ReverseIterator::
 operator++() {
   this->ReverseIncrement();
+  ++index_;
   return *this;
 }
 
+template <typename BaseElementType>
+size_t ListContainer<BaseElementType>::ReverseIterator::index() const {
+  return index_;
+}
+
 // ListContainer::ConstReverseIterator
 /////////////////////////////////////////////////
 template <typename BaseElementType>
 ListContainer<BaseElementType>::ConstReverseIterator::ConstReverseIterator(
     const typename ListContainer<BaseElementType>::ReverseIterator& other)
-    : PositionInListContainerCharAllocator(other) {
+    : PositionInListContainerCharAllocator(other), index_(other.index()) {
 }
 
 template <typename BaseElementType>
 ListContainer<BaseElementType>::ConstReverseIterator::ConstReverseIterator(
     ListContainerCharAllocator* container,
     size_t vector_ind,
-    char* item_iter)
-    : PositionInListContainerCharAllocator(container, vector_ind, item_iter) {
+    char* item_iter,
+    size_t index)
+    : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
+      index_(index) {
 }
 
 template <typename BaseElementType>
@@ -615,9 +645,15 @@ typename ListContainer<BaseElementType>::ConstReverseIterator
 ListContainer<BaseElementType>::ConstReverseIterator::
 operator++() {
   this->ReverseIncrement();
+  ++index_;
   return *this;
 }
 
+template <typename BaseElementType>
+size_t ListContainer<BaseElementType>::ConstReverseIterator::index() const {
+  return index_;
+}
+
 template class ListContainer<SharedQuadState>;
 template class ListContainer<DrawQuad>;
 
diff --git a/cc/quads/list_container.h b/cc/quads/list_container.h
index 6c559f6..c3c19b0 100644
--- a/cc/quads/list_container.h
+++ b/cc/quads/list_container.h
@@ -33,8 +33,9 @@ class CC_EXPORT ListContainer {
   // is used when there is no derived classes from BaseElementType we need to
   // worry about, and allocation size is just sizeof(BaseElementType).
   ListContainer();
-  // This constructor reserves the requested memory up front so only a single
-  // allocation is needed.
+  // This constructor reserves the requested memory up front so only single
+  // allocation is needed. When num_of_elements_to_reserve_for is zero, use the
+  // default size.
   ListContainer(size_t max_size_for_derived_class,
                 size_t num_of_elements_to_reserve_for);
 
@@ -73,12 +74,22 @@ class CC_EXPORT ListContainer {
    public:
     Iterator(ListContainerCharAllocator* container,
              size_t vector_ind,
-             char* item_iter);
+             char* item_iter,
+             size_t index);
     ~Iterator();
     BaseElementType* operator->() const;
     BaseElementType& operator*() const;
     Iterator operator++(int unused_post_increment);
     Iterator operator++();
+
+    size_t index() const;
+
+   private:
+    // This is used to track how many increment has happened since begin(). It
+    // is used to avoid double increment at places an index reference is
+    // needed. For iterator this means begin() corresponds to index 0 and end()
+    // corresponds to index |size|.
+    size_t index_;
   };
 
   class CC_EXPORT ConstIterator : public PositionInListContainerCharAllocator {
@@ -87,13 +98,23 @@ class CC_EXPORT ListContainer {
    public:
     ConstIterator(ListContainerCharAllocator* container,
                   size_t vector_ind,
-                  char* item_iter);
+                  char* item_iter,
+                  size_t index);
     ConstIterator(const Iterator& other);  // NOLINT
     ~ConstIterator();
     const BaseElementType* operator->() const;
     const BaseElementType& operator*() const;
     ConstIterator operator++(int unused_post_increment);
     ConstIterator operator++();
+
+    size_t index() const;
+
+   private:
+    // This is used to track how many increment has happened since begin(). It
+    // is used to avoid double increment at places an index reference is
+    // needed. For iterator this means begin() corresponds to index 0 and end()
+    // corresponds to index |size|.
+    size_t index_;
   };
 
   class CC_EXPORT ReverseIterator
@@ -103,12 +124,22 @@ class CC_EXPORT ListContainer {
    public:
     ReverseIterator(ListContainerCharAllocator* container,
                     size_t vector_ind,
-                    char* item_iter);
+                    char* item_iter,
+                    size_t index);
     ~ReverseIterator();
     BaseElementType* operator->() const;
     BaseElementType& operator*() const;
     ReverseIterator operator++(int unused_post_increment);
     ReverseIterator operator++();
+
+    size_t index() const;
+
+   private:
+    // This is used to track how many increment has happened since rbegin(). It
+    // is used to avoid double increment at places an index reference is
+    // needed. For reverse iterator this means rbegin() corresponds to index 0
+    // and rend() corresponds to index |size|.
+    size_t index_;
   };
 
   class CC_EXPORT ConstReverseIterator
@@ -118,13 +149,23 @@ class CC_EXPORT ListContainer {
    public:
     ConstReverseIterator(ListContainerCharAllocator* container,
                          size_t vector_ind,
-                         char* item_iter);
+                         char* item_iter,
+                         size_t index);
     ConstReverseIterator(const ReverseIterator& other);  // NOLINT
     ~ConstReverseIterator();
     const BaseElementType* operator->() const;
     const BaseElementType& operator*() const;
     ConstReverseIterator operator++(int unused_post_increment);
     ConstReverseIterator operator++();
+
+    size_t index() const;
+
+   private:
+    // This is used to track how many increment has happened since rbegin(). It
+    // is used to avoid double increment at places an index reference is
+    // needed. For reverse iterator this means rbegin() corresponds to index 0
+    // and rend() corresponds to index |size|.
+    size_t index_;
   };
 
   // When called, all raw pointers that have been handed out are no longer
diff --git a/cc/quads/list_container_unittest.cc b/cc/quads/list_container_unittest.cc
index dd06877..cb79f7a 100644
--- a/cc/quads/list_container_unittest.cc
+++ b/cc/quads/list_container_unittest.cc
@@ -525,5 +525,32 @@ TEST(ListContainerTest,
   }
 }
 
+TEST(ListContainerTest,
+     SimpleIterationAndReverseIterationWithIndexSharedQuadState) {
+  ListContainer<SharedQuadState> list;
+  std::vector<SharedQuadState*> sqs_list;
+  size_t size = 10;
+  for (size_t i = 0; i < size; ++i) {
+    sqs_list.push_back(list.AllocateAndConstruct<SharedQuadState>());
+  }
+  EXPECT_EQ(size, list.size());
+
+  size_t i = 0;
+  for (ListContainer<SharedQuadState>::Iterator iter = list.begin();
+       iter != list.end();
+       ++iter) {
+    EXPECT_EQ(i, iter.index());
+    ++i;
+  }
+
+  i = 0;
+  for (ListContainer<SharedQuadState>::ReverseIterator iter = list.rbegin();
+       iter != list.rend();
+       ++iter) {
+    EXPECT_EQ(i, iter.index());
+    ++i;
+  }
+}
+
 }  // namespace
 }  // namespace cc
diff --git a/cc/quads/render_pass.cc b/cc/quads/render_pass.cc
index e487c09..2cb72de 100644
--- a/cc/quads/render_pass.cc
+++ b/cc/quads/render_pass.cc
@@ -4,6 +4,8 @@
 
 #include "cc/quads/render_pass.h"
 
+#include <algorithm>
+
 #include "base/debug/trace_event_argument.h"
 #include "base/values.h"
 #include "cc/base/math_util.h"
@@ -44,20 +46,36 @@ scoped_ptr<RenderPass> RenderPass::Create(size_t num_layers) {
   return make_scoped_ptr(new RenderPass(num_layers));
 }
 
+scoped_ptr<RenderPass> RenderPass::Create(size_t shared_quad_state_list_size,
+                                          size_t quad_list_size) {
+  return make_scoped_ptr(
+      new RenderPass(shared_quad_state_list_size, quad_list_size));
+}
+
 RenderPass::RenderPass()
     : id(RenderPassId(-1, -1)),
       has_transparent_background(true),
-      quad_list(kDefaultNumQuadsToReserve) {
-  shared_quad_state_list.reserve(kDefaultNumSharedQuadStatesToReserve);
+      quad_list(kDefaultNumQuadsToReserve),
+      shared_quad_state_list(sizeof(SharedQuadState),
+                             kDefaultNumSharedQuadStatesToReserve) {
 }
 
+// Each layer usually produces one shared quad state, so the number of layers
+// is a good hint for what to reserve here.
 RenderPass::RenderPass(size_t num_layers)
     : id(RenderPassId(-1, -1)),
       has_transparent_background(true),
-      quad_list(kDefaultNumQuadsToReserve) {
-  // Each layer usually produces one shared quad state, so the number of layers
-  // is a good hint for what to reserve here.
-  shared_quad_state_list.reserve(num_layers);
+      quad_list(kDefaultNumQuadsToReserve),
+      shared_quad_state_list(sizeof(SharedQuadState), num_layers) {
+}
+
+RenderPass::RenderPass(size_t shared_quad_state_list_size,
+                       size_t quad_list_size)
+    : id(RenderPassId(-1, -1)),
+      has_transparent_background(true),
+      quad_list(quad_list_size),
+      shared_quad_state_list(sizeof(SharedQuadState),
+                             shared_quad_state_list_size) {
 }
 
 RenderPass::~RenderPass() {
@@ -67,7 +85,8 @@ RenderPass::~RenderPass() {
 }
 
 scoped_ptr<RenderPass> RenderPass::Copy(RenderPassId new_id) const {
-  scoped_ptr<RenderPass> copy_pass(Create());
+  scoped_ptr<RenderPass> copy_pass(
+      Create(shared_quad_state_list.size(), quad_list.size()));
   copy_pass->SetAll(new_id,
                     output_rect,
                     damage_rect,
@@ -86,39 +105,39 @@ void RenderPass::CopyAll(const ScopedPtrVector<RenderPass>& in,
     // you may have copy_requests present.
     DCHECK_EQ(source->copy_requests.size(), 0u);
 
-    scoped_ptr<RenderPass> copy_pass(Create());
+    scoped_ptr<RenderPass> copy_pass(Create(
+        source->shared_quad_state_list.size(), source->quad_list.size()));
     copy_pass->SetAll(source->id,
                       source->output_rect,
                       source->damage_rect,
                       source->transform_to_root_target,
                       source->has_transparent_background);
-    for (size_t i = 0; i < source->shared_quad_state_list.size(); ++i) {
+    for (const auto& shared_quad_state : source->shared_quad_state_list) {
       SharedQuadState* copy_shared_quad_state =
           copy_pass->CreateAndAppendSharedQuadState();
-      copy_shared_quad_state->CopyFrom(source->shared_quad_state_list[i]);
+      copy_shared_quad_state->CopyFrom(&shared_quad_state);
     }
-    size_t sqs_i = 0;
-    for (QuadList::Iterator iter = source->quad_list.begin();
-         iter != source->quad_list.end();
-         ++iter) {
-      while (iter->shared_quad_state != source->shared_quad_state_list[sqs_i]) {
-        ++sqs_i;
-        DCHECK_LT(sqs_i, source->shared_quad_state_list.size());
+    SharedQuadStateList::Iterator sqs_iter =
+        source->shared_quad_state_list.begin();
+    SharedQuadStateList::Iterator copy_sqs_iter =
+        copy_pass->shared_quad_state_list.begin();
+    for (const auto& quad : source->quad_list) {
+      while (quad.shared_quad_state != &*sqs_iter) {
+        ++sqs_iter;
+        ++copy_sqs_iter;
+        DCHECK(sqs_iter != source->shared_quad_state_list.end());
       }
-      DCHECK(iter->shared_quad_state == source->shared_quad_state_list[sqs_i]);
+      DCHECK(quad.shared_quad_state == &*sqs_iter);
 
-      DrawQuad* quad = &*iter;
+      SharedQuadState* copy_shared_quad_state = &*copy_sqs_iter;
 
-      if (quad->material == DrawQuad::RENDER_PASS) {
+      if (quad.material == DrawQuad::RENDER_PASS) {
         const RenderPassDrawQuad* pass_quad =
-            RenderPassDrawQuad::MaterialCast(quad);
+            RenderPassDrawQuad::MaterialCast(&quad);
         copy_pass->CopyFromAndAppendRenderPassDrawQuad(
-            pass_quad,
-            copy_pass->shared_quad_state_list[sqs_i],
-            pass_quad->render_pass_id);
+            pass_quad, copy_shared_quad_state, pass_quad->render_pass_id);
       } else {
-        copy_pass->CopyFromAndAppendDrawQuad(
-            quad, copy_pass->shared_quad_state_list[sqs_i]);
+        copy_pass->CopyFromAndAppendDrawQuad(&quad, copy_shared_quad_state);
       }
     }
     out->push_back(copy_pass.Pass());
@@ -175,19 +194,17 @@ void RenderPass::AsValueInto(base::debug::TracedValue* value) const {
   value->SetInteger("copy_requests", copy_requests.size());
 
   value->BeginArray("shared_quad_state_list");
-  for (size_t i = 0; i < shared_quad_state_list.size(); ++i) {
+  for (const auto& shared_quad_state : shared_quad_state_list) {
     value->BeginDictionary();
-    shared_quad_state_list[i]->AsValueInto(value);
+    shared_quad_state.AsValueInto(value);
     value->EndDictionary();
   }
   value->EndArray();
 
   value->BeginArray("quad_list");
-  for (QuadList::ConstIterator iter = quad_list.begin();
-       iter != quad_list.end();
-       ++iter) {
+  for (const auto& quad : quad_list) {
     value->BeginDictionary();
-    iter->AsValueInto(value);
+    quad.AsValueInto(value);
     value->EndDictionary();
   }
   value->EndArray();
@@ -200,8 +217,7 @@ void RenderPass::AsValueInto(base::debug::TracedValue* value) const {
 }
 
 SharedQuadState* RenderPass::CreateAndAppendSharedQuadState() {
-  shared_quad_state_list.push_back(make_scoped_ptr(new SharedQuadState));
-  return shared_quad_state_list.back();
+  return shared_quad_state_list.AllocateAndConstruct<SharedQuadState>();
 }
 
 RenderPassDrawQuad* RenderPass::CopyFromAndAppendRenderPassDrawQuad(
diff --git a/cc/quads/render_pass.h b/cc/quads/render_pass.h
index db42faf..65c712d 100644
--- a/cc/quads/render_pass.h
+++ b/cc/quads/render_pass.h
@@ -47,7 +47,7 @@ class QuadList : public ListContainer<DrawQuad> {
   inline ConstBackToFrontIterator BackToFrontEnd() const { return rend(); }
 };
 
-typedef ScopedPtrVector<SharedQuadState> SharedQuadStateList;
+typedef ListContainer<SharedQuadState> SharedQuadStateList;
 
 class CC_EXPORT RenderPass {
  public:
@@ -55,6 +55,8 @@ class CC_EXPORT RenderPass {
 
   static scoped_ptr<RenderPass> Create();
   static scoped_ptr<RenderPass> Create(size_t num_layers);
+  static scoped_ptr<RenderPass> Create(size_t shared_quad_state_list_size,
+                                       size_t quad_list_size);
 
   // A shallow copy of the render pass, which does not include its quads or copy
   // requests.
@@ -117,6 +119,7 @@ class CC_EXPORT RenderPass {
  protected:
   explicit RenderPass(size_t num_layers);
   RenderPass();
+  RenderPass(size_t shared_quad_state_list_size, size_t quad_list_size);
 
  private:
   template <typename DrawQuadType>