cc: Implement RemoveLast for DisplayItemList.

cc/base/list_container.cc

 // Copyright 2014 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/list_container.h"
 
 #include <algorithm>
 #include <vector>
 
 #include "cc/base/scoped_ptr_vector.h"
@@ skipping 35 matching lines @@
       DCHECK_LE(position, LastElement());
       DCHECK_GE(position, Begin());
       char* start = position + step;
       std::copy(start, End(), position);
 
       --size;
       // Decrease capacity to avoid creating not full not last InnerList.
       --capacity;
     }
 
+    bool IsEmpty() const { return !size; }
     bool IsFull() { return capacity == size; }
     size_t NumElementsAvailable() const { return capacity - size; }
 
     void* AddElement() {
       DCHECK_LT(size, capacity);
       ++size;
       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; }
     char* ElementAt(size_t index) const { return data.get() + index * step; }
 
    private:
     DISALLOW_COPY_AND_ASSIGN(InnerList);
   };
 
   explicit ListContainerCharAllocator(size_t element_size)
@@ skipping 39 matching lines @@
 
   void Clear() {
     size_t initial_allocation_size = storage_.front()->capacity;
     storage_.clear();
     list_count_ = 0;
     last_list_ = NULL;
     size_ = 0;
     AllocateNewList(initial_allocation_size);
   }
 
+  void RemoveLast() {
+    DCHECK(!IsEmpty());
+    last_list_->RemoveLast();
+    if (last_list_->IsEmpty())
+      DeallocateLastList();

[danakj, 2015/06/02 20:04:32]

Is it possible to avoid this deallocate and just leave the empty last list
around with size 0?

This could lead to a huge performance cliff, and it'll be rare/random/hard to
reproduce.

+    --size_;
+  }
+
   void Erase(PositionInListContainerCharAllocator position) {
     DCHECK_EQ(this, position.ptr_to_container);
     storage_[position.vector_index]->Erase(position.item_iterator);
     // TODO(weiliangc): Free the InnerList if it is empty.
     --size_;
   }
 
   InnerList* InnerListById(size_t id) const {
     DCHECK_LT(id, list_count_);
     return storage_[id];
@@ skipping 29 matching lines @@
     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 DeallocateLastList() {
+    // Don't deallocate the only list; we always expect there to be one.
+    if (list_count_ <= 1)
+      return;
+    --list_count_;
+    storage_.pop_back();
+    last_list_ = list_count_ ? storage_.back() : nullptr;
+  }
+
   ScopedPtrVector<InnerList> storage_;
   const size_t element_size_;
   size_t size_;
   size_t list_count_;
   InnerList* last_list_;
 
   DISALLOW_COPY_AND_ASSIGN(ListContainerCharAllocator);
 };
 
 // PositionInListContainerCharAllocator
@@ skipping 85 matching lines @@
 
 ListContainerBase::ListContainerBase(size_t max_size_for_derived_class,
                                      size_t num_of_elements_to_reserve_for)
     : data_(new ListContainerCharAllocator(max_size_for_derived_class,
                                            num_of_elements_to_reserve_for)) {
 }
 
 ListContainerBase::~ListContainerBase() {
 }
 
+void ListContainerBase::RemoveLast() {
+  data_->RemoveLast();
+}
+
 void ListContainerBase::EraseAndInvalidateAllPointers(
     ListContainerBase::Iterator position) {
   data_->Erase(position);
 }
 
 ListContainerBase::ConstReverseIterator ListContainerBase::crbegin() const {
   if (data_->IsEmpty())
     return crend();
 
   size_t id = data_->LastInnerListId();
@@ skipping 179 matching lines @@
 }
 
 ListContainerBase::ConstReverseIterator::~ConstReverseIterator() {
 }
 
 size_t ListContainerBase::ConstReverseIterator::index() const {
   return index_;
 }
 
 }  // namespace cc