cc: Implement RemoveLast for DisplayItemList.

Blink currently does this operation on its display item lists to remove
superfluous begin/end pairs. To port Blink's current display item list
operations, such an operation is required.

This is not possible when in "cached picture" mode, but Blink currently only
does this on the unmerged list (in blink::DisplayItemList::add), so this should
be sufficient (if unfortunately asymmetric).

BUG=484943
CQ_INCLUDE_TRYBOTS=tryserver.blink:linux_blink_rel

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

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

4 files changed, 91 insertions, 23 deletions

diff --git a/cc/base/list_container.cc b/cc/base/list_container.cc
index df21a5b..ef4d08c 100644
--- a/cc/base/list_container.cc
+++ b/cc/base/list_container.cc
@@ -53,6 +53,7 @@ class ListContainerBase::ListContainerCharAllocator {
       --capacity;
     }
 
+    bool IsEmpty() const { return !size; }
     bool IsFull() { return capacity == size; }
     size_t NumElementsAvailable() const { return capacity - size; }
 
@@ -62,6 +63,11 @@ class ListContainerBase::ListContainerCharAllocator {
       return LastElement();
     }
 
+    void RemoveLast() {
+      DCHECK(!IsEmpty());
+      --size;
+    }
+
     char* Begin() const { return data.get(); }
     char* End() const { return data.get() + size * step; }
     char* LastElement() const { return data.get() + (size - 1) * step; }
@@ -74,32 +80,41 @@ class ListContainerBase::ListContainerCharAllocator {
   explicit ListContainerCharAllocator(size_t element_size)
       : element_size_(element_size),
         size_(0),
-        list_count_(0),
+        last_list_index_(0),
         last_list_(NULL) {
     AllocateNewList(kDefaultNumElementTypesToReserve);
+    last_list_ = storage_[last_list_index_];
   }
 
   ListContainerCharAllocator(size_t element_size, size_t element_count)
       : element_size_(element_size),
         size_(0),
-        list_count_(0),
+        last_list_index_(0),
         last_list_(NULL) {
     AllocateNewList(element_count > 0 ? element_count
                                       : kDefaultNumElementTypesToReserve);
+    last_list_ = storage_[last_list_index_];
   }
 
   ~ListContainerCharAllocator() {}
 
   void* Allocate() {
-    if (last_list_->IsFull())
-      AllocateNewList(last_list_->capacity * 2);
+    if (last_list_->IsFull()) {
+      // Only allocate a new list if there isn't a spare one still there from
+      // previous usage.
+      if (last_list_index_ + 1 >= storage_.size())
+        AllocateNewList(last_list_->capacity * 2);
+
+      ++last_list_index_;
+      last_list_ = storage_[last_list_index_];
+    }
 
     ++size_;
     return last_list_->AddElement();
   }
 
   size_t element_size() const { return element_size_; }
-  size_t list_count() const { return list_count_; }
+  size_t list_count() const { return storage_.size(); }
   size_t size() const { return size_; }
   bool IsEmpty() const { return size() == 0; }
 
@@ -115,10 +130,25 @@ class ListContainerBase::ListContainerCharAllocator {
   void Clear() {
     size_t initial_allocation_size = storage_.front()->capacity;
     storage_.clear();
-    list_count_ = 0;
     last_list_ = NULL;
+    last_list_index_ = 0;
     size_ = 0;
     AllocateNewList(initial_allocation_size);
+    last_list_ = storage_[last_list_index_];
+  }
+
+  void RemoveLast() {
+    DCHECK(!IsEmpty());
+    last_list_->RemoveLast();
+    if (last_list_->IsEmpty() && last_list_index_ > 0) {
+      --last_list_index_;
+      last_list_ = storage_[last_list_index_];
+
+      // If there are now two empty inner lists, free one of them.
+      if (last_list_index_ + 2 < storage_.size())
+        storage_.pop_back();
+    }
+    --size_;
   }
 
   void Erase(PositionInListContainerCharAllocator position) {
@@ -129,7 +159,7 @@ class ListContainerBase::ListContainerCharAllocator {
   }
 
   InnerList* InnerListById(size_t id) const {
-    DCHECK_LT(id, list_count_);
+    DCHECK_LT(id, storage_.size());
     return storage_[id];
   }
 
@@ -147,33 +177,37 @@ class ListContainerBase::ListContainerCharAllocator {
     // |size_| > 0 means that at least one vector in |storage_| will be
     // non-empty.
     DCHECK_GT(size_, 0u);
-    size_t id = list_count_ - 1;
+    size_t id = storage_.size() - 1;
     while (storage_[id]->size == 0)
       --id;
     return id;
   }
 
-  void AllocateNewList(size_t list_size) {
-    ++list_count_;
-    scoped_ptr<InnerList> new_list(new InnerList);
-    storage_.push_back(new_list.Pass());
-    last_list_ = storage_.back();
-    InnerList* list = last_list_;
-    list->capacity = list_size;
-    list->size = 0;
-    list->step = element_size_;
-    list->data.reset(new char[list->capacity * list->step]);
-  }
-
   size_t NumAvailableElementsInLastList() const {
     return last_list_->NumElementsAvailable();
   }
 
  private:
+  void AllocateNewList(size_t list_size) {
+    scoped_ptr<InnerList> new_list(new InnerList);
+    new_list->capacity = list_size;
+    new_list->size = 0;
+    new_list->step = element_size_;
+    new_list->data.reset(new char[list_size * element_size_]);
+    storage_.push_back(new_list.Pass());
+  }
+
   ScopedPtrVector<InnerList> storage_;
   const size_t element_size_;
+
+  // The number of elements in the list.
   size_t size_;
-  size_t list_count_;
+
+  // The index of the last list to have had elements added to it, or the only
+  // list if the container has not had elements added since being cleared.
+  size_t last_list_index_;
+
+  // This is equivalent to |storage_[last_list_index_]|.
   InnerList* last_list_;
 
   DISALLOW_COPY_AND_ASSIGN(ListContainerCharAllocator);
@@ -275,6 +309,10 @@ ListContainerBase::ListContainerBase(size_t max_size_for_derived_class,
 ListContainerBase::~ListContainerBase() {
 }
 
+void ListContainerBase::RemoveLast() {
+  data_->RemoveLast();
+}
+
 void ListContainerBase::EraseAndInvalidateAllPointers(
     ListContainerBase::Iterator position) {
   data_->Erase(position);
diff --git a/cc/base/list_container.h b/cc/base/list_container.h
index 2ed69c2..0c3772b 100644
--- a/cc/base/list_container.h
+++ b/cc/base/list_container.h
@@ -5,6 +5,7 @@
 #ifndef CC_BASE_LIST_CONTAINER_H_
 #define CC_BASE_LIST_CONTAINER_H_
 
+#include "base/logging.h"
 #include "base/macros.h"
 #include "base/memory/scoped_ptr.h"
 #include "cc/base/cc_export.h"
@@ -141,8 +142,8 @@ class CC_EXPORT ListContainerBase {
     size_t index_;
   };
 
-  // Unlike the ListContainer method, this one does not invoke element
-  // destructors.
+  // Unlike the ListContainer methods, these do not invoke element destructors.
+  void RemoveLast();
   void EraseAndInvalidateAllPointers(Iterator position);
 
   ConstReverseIterator crbegin() const;
@@ -209,6 +210,14 @@ class ListContainer : public ListContainerBase {
   class ReverseIterator;
   class ConstReverseIterator;
 
+  // Removes the last element of the list and makes its space available for
+  // allocation.
+  void RemoveLast() {
+    DCHECK(!empty());
+    back()->~BaseElementType();
+    ListContainerBase::RemoveLast();
+  }
+
   // When called, all raw pointers that have been handed out are no longer
   // valid. Use with caution.
   // This function does not deallocate memory.
diff --git a/cc/base/sidecar_list_container.h b/cc/base/sidecar_list_container.h
index 52deaf4..842795f 100644
--- a/cc/base/sidecar_list_container.h
+++ b/cc/base/sidecar_list_container.h
@@ -29,6 +29,10 @@ class SidecarListContainer {
   using SidecarDestroyer = void (*)(void* sidecar);
   using Iterator = typename ListContainer<BaseElementType>::Iterator;
   using ConstIterator = typename ListContainer<BaseElementType>::ConstIterator;
+  using ReverseIterator =
+      typename ListContainer<BaseElementType>::ReverseIterator;
+  using ConstReverseIterator =
+      typename ListContainer<BaseElementType>::ConstReverseIterator;
 
   explicit SidecarListContainer(size_t max_size_for_derived_class,
                                 size_t max_size_for_sidecar,
@@ -60,6 +64,11 @@ class SidecarListContainer {
     list_.clear();
   }
 
+  void RemoveLast() {
+    destroyer_(GetSidecar(*list_.rbegin()));
+    list_.RemoveLast();
+  }
+
   // This permits a client to exchange a pointer to an element to a pointer to
   // its corresponding sidecar.
   void* GetSidecar(BaseElementType* element) {
diff --git a/cc/base/sidecar_list_container_unittest.cc b/cc/base/sidecar_list_container_unittest.cc
index d8fc9ef..0012014 100644
--- a/cc/base/sidecar_list_container_unittest.cc
+++ b/cc/base/sidecar_list_container_unittest.cc
@@ -182,5 +182,17 @@ TEST(SidecarListContainerTest, AddingAndRemovingElements) {
   EXPECT_EQ(container.end(), container.begin());
 }
 
+TEST(SidecarListContainerTest, RemoveLast) {
+  // We need only ensure that the sidecar is also destroyed on RemoveLast.
+  // The rest is logic already present in ListContainer.
+  bool sidecar_destroyed = false;
+  TestContainer container;
+  TestElement* element = container.AllocateAndConstruct<TestElement>();
+  new (container.GetSidecar(element)) TestSidecar(&sidecar_destroyed);
+  ASSERT_FALSE(sidecar_destroyed);
+  container.RemoveLast();
+  ASSERT_TRUE(sidecar_destroyed);
+}
+
 }  // namespace
 }  // namespace cc