cc: Move cc/quads/list_container.* files to cc/base.

cc/quads/list_container.cc

Index: cc/quads/list_container.cc
diff --git a/cc/quads/list_container.cc b/cc/quads/list_container.cc
deleted file mode 100644
index 4edcbdfab560a86af305e7946f53852ede0a43ef..0000000000000000000000000000000000000000
--- a/cc/quads/list_container.cc
+++ /dev/null
@@ -1,720 +0,0 @@
-// 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/quads/list_container.h"
-
-#include <algorithm>
-#include <vector>
-
-#include "cc/base/scoped_ptr_vector.h"
-#include "cc/playback/display_item.h"
-#include "cc/quads/draw_quad.h"
-#include "cc/quads/shared_quad_state.h"
-
-namespace {
-const size_t kDefaultNumElementTypesToReserve = 32;
-}  // namespace
-
-namespace cc {
-
-// ListContainerCharAllocator
-////////////////////////////////////////////////////
-// This class deals only with char* and void*. It does allocation and passing
-// out raw pointers, as well as memory deallocation when being destroyed.
-template <typename BaseElementType>
-class ListContainer<BaseElementType>::ListContainerCharAllocator {
- public:
-  // ListContainerCharAllocator::InnerList
-  /////////////////////////////////////////////
-  // This class holds the raw memory chunk, as well as information about its
-  // size and availability.
-  struct InnerList {
-    scoped_ptr<char[]> data;
-    // The number of elements in total the memory can hold. The difference
-    // between capacity and size is the how many more elements this list can
-    // hold.
-    size_t capacity;
-    // The number of elements have been put into this list.
-    size_t size;
-    // The size of each element is in bytes. This is used to move from between
-    // elements' memory locations.
-    size_t step;
-
-    InnerList() : capacity(0), size(0), step(0) {}
-
-    void Erase(char* position) {
-      // Confident that destructor is called by caller of this function. Since
-      // ListContainerCharAllocator does not handle construction after
-      // allocation, it doesn't handle desctrution before deallocation.
-      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 IsFull() { return capacity == size; }
-    size_t NumElementsAvailable() const { return capacity - size; }
-
-    void* AddElement() {
-      DCHECK_LT(size, capacity);
-      ++size;
-      return LastElement();
-    }
-
-    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)
-      : element_size_(element_size),
-        size_(0),
-        list_count_(0),
-        last_list_(NULL) {
-    AllocateNewList(kDefaultNumElementTypesToReserve);
-  }
-
-  ListContainerCharAllocator(size_t element_size, size_t element_count)
-      : element_size_(element_size),
-        size_(0),
-        list_count_(0),
-        last_list_(NULL) {
-    AllocateNewList(element_count > 0 ? element_count
-                                      : kDefaultNumElementTypesToReserve);
-  }
-
-  ~ListContainerCharAllocator() {}
-
-  void* Allocate() {
-    if (last_list_->IsFull())
-      AllocateNewList(last_list_->capacity * 2);
-
-    ++size_;
-    return last_list_->AddElement();
-  }
-
-  size_t element_size() const { return element_size_; }
-  size_t list_count() const { return list_count_; }
-  size_t size() const { return size_; }
-  bool IsEmpty() const { return size() == 0; }
-
-  size_t Capacity() const {
-    size_t capacity_sum = 0;
-    for (typename ScopedPtrVector<InnerList>::const_iterator iter =
-             storage_.begin();
-         iter != storage_.end();
-         ++iter) {
-      capacity_sum += (*iter)->capacity;
-    }
-    return capacity_sum;
-  }
-
-  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 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];
-  }
-
-  size_t FirstInnerListId() const {
-    // |size_| > 0 means that at least one vector in |storage_| will be
-    // non-empty.
-    DCHECK_GT(size_, 0u);
-    size_t id = 0;
-    while (storage_[id]->size == 0)
-      ++id;
-    return id;
-  }
-
-  size_t LastInnerListId() const {
-    // |size_| > 0 means that at least one vector in |storage_| will be
-    // non-empty.
-    DCHECK_GT(size_, 0u);
-    size_t id = list_count_ - 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:
-  ScopedPtrVector<InnerList> storage_;
-  const size_t element_size_;
-  size_t size_;
-  size_t list_count_;
-  InnerList* last_list_;
-
-  DISALLOW_COPY_AND_ASSIGN(ListContainerCharAllocator);
-};
-
-// PositionInListContainerCharAllocator
-//////////////////////////////////////////////////////
-template <typename BaseElementType>
-ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
-    PositionInListContainerCharAllocator(const typename ListContainer<
-        BaseElementType>::PositionInListContainerCharAllocator& other)
-    : ptr_to_container(other.ptr_to_container),
-      vector_index(other.vector_index),
-      item_iterator(other.item_iterator) {
-}
-
-template <typename BaseElementType>
-ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
-    PositionInListContainerCharAllocator(
-        typename ListContainer<BaseElementType>::ListContainerCharAllocator*
-            container,
-        size_t vector_ind,
-        char* item_iter)
-    : ptr_to_container(container),
-      vector_index(vector_ind),
-      item_iterator(item_iter) {
-}
-
-template <typename BaseElementType>
-bool ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
-operator==(const typename ListContainer<
-    BaseElementType>::PositionInListContainerCharAllocator& other) const {
-  DCHECK_EQ(ptr_to_container, other.ptr_to_container);
-  return vector_index == other.vector_index &&
-         item_iterator == other.item_iterator;
-}
-
-template <typename BaseElementType>
-bool ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
-operator!=(const typename ListContainer<
-    BaseElementType>::PositionInListContainerCharAllocator& other) const {
-  return !(*this == other);
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::PositionInListContainerCharAllocator
-ListContainer<
-    BaseElementType>::PositionInListContainerCharAllocator::Increment() {
-  typename ListContainerCharAllocator::InnerList* list =
-      ptr_to_container->InnerListById(vector_index);
-  if (item_iterator == list->LastElement()) {
-    ++vector_index;
-    while (vector_index < ptr_to_container->list_count()) {
-      if (ptr_to_container->InnerListById(vector_index)->size != 0)
-        break;
-      ++vector_index;
-    }
-    if (vector_index < ptr_to_container->list_count())
-      item_iterator = ptr_to_container->InnerListById(vector_index)->Begin();
-    else
-      item_iterator = NULL;
-  } else {
-    item_iterator += list->step;
-  }
-  return *this;
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::PositionInListContainerCharAllocator
-ListContainer<
-    BaseElementType>::PositionInListContainerCharAllocator::ReverseIncrement() {
-  typename ListContainerCharAllocator::InnerList* list =
-      ptr_to_container->InnerListById(vector_index);
-  if (item_iterator == list->Begin()) {
-    --vector_index;
-    // Since |vector_index| is unsigned, we compare < list_count() instead of
-    // comparing >= 0, as the variable will wrap around when it goes out of
-    // range (below 0).
-    while (vector_index < ptr_to_container->list_count()) {
-      if (ptr_to_container->InnerListById(vector_index)->size != 0)
-        break;
-      --vector_index;
-    }
-    if (vector_index < ptr_to_container->list_count()) {
-      item_iterator =
-          ptr_to_container->InnerListById(vector_index)->LastElement();
-    } else {
-      item_iterator = NULL;
-    }
-  } else {
-    item_iterator -= list->step;
-  }
-  return *this;
-}
-
-// ListContainer
-////////////////////////////////////////////
-template <typename BaseElementType>
-ListContainer<BaseElementType>::ListContainer(size_t max_size_for_derived_class)
-    : data_(new ListContainerCharAllocator(max_size_for_derived_class)) {
-}
-
-template <typename BaseElementType>
-ListContainer<BaseElementType>::ListContainer(
-    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)) {
-}
-
-template <typename BaseElementType>
-ListContainer<BaseElementType>::ListContainer()
-    : data_(new ListContainerCharAllocator(sizeof(BaseElementType))) {
-}
-
-template <typename BaseElementType>
-ListContainer<BaseElementType>::~ListContainer() {
-  for (Iterator i = begin(); i != end(); ++i) {
-    i->~BaseElementType();
-  }
-}
-
-template <typename BaseElementType>
-void ListContainer<BaseElementType>::EraseAndInvalidateAllPointers(
-    typename ListContainer<BaseElementType>::Iterator position) {
-  BaseElementType* item = *position;
-  item->~BaseElementType();
-  data_->Erase(position);
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ConstReverseIterator
-ListContainer<BaseElementType>::crbegin() const {
-  if (data_->IsEmpty())
-    return crend();
-
-  size_t id = data_->LastInnerListId();
-  return ConstReverseIterator(data_.get(), id,
-                              data_->InnerListById(id)->LastElement(), 0);
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ConstReverseIterator
-ListContainer<BaseElementType>::crend() const {
-  return ConstReverseIterator(data_.get(), static_cast<size_t>(-1), NULL,
-                              size());
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ConstReverseIterator
-ListContainer<BaseElementType>::rbegin() const {
-  return crbegin();
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ConstReverseIterator
-ListContainer<BaseElementType>::rend() const {
-  return crend();
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ReverseIterator
-ListContainer<BaseElementType>::rbegin() {
-  if (data_->IsEmpty())
-    return rend();
-
-  size_t id = data_->LastInnerListId();
-  return ReverseIterator(data_.get(), id,
-                         data_->InnerListById(id)->LastElement(), 0);
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ReverseIterator
-ListContainer<BaseElementType>::rend() {
-  return ReverseIterator(data_.get(), static_cast<size_t>(-1), NULL, size());
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ConstIterator
-ListContainer<BaseElementType>::cbegin() const {
-  if (data_->IsEmpty())
-    return cend();
-
-  size_t id = data_->FirstInnerListId();
-  return ConstIterator(data_.get(), id, data_->InnerListById(id)->Begin(), 0);
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ConstIterator
-ListContainer<BaseElementType>::cend() const {
-  if (data_->IsEmpty())
-    return ConstIterator(data_.get(), 0, NULL, size());
-
-  size_t id = data_->list_count();
-  return ConstIterator(data_.get(), id, NULL, size());
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ConstIterator
-ListContainer<BaseElementType>::begin() const {
-  return cbegin();
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ConstIterator
-ListContainer<BaseElementType>::end() const {
-  return cend();
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::Iterator
-ListContainer<BaseElementType>::begin() {
-  if (data_->IsEmpty())
-    return end();
-
-  size_t id = data_->FirstInnerListId();
-  return Iterator(data_.get(), id, data_->InnerListById(id)->Begin(), 0);
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::Iterator
-ListContainer<BaseElementType>::end() {
-  if (data_->IsEmpty())
-    return Iterator(data_.get(), 0, NULL, size());
-
-  size_t id = data_->list_count();
-  return Iterator(data_.get(), id, NULL, size());
-}
-
-template <typename BaseElementType>
-BaseElementType* ListContainer<BaseElementType>::front() {
-  Iterator iter = begin();
-  return *iter;
-}
-
-template <typename BaseElementType>
-BaseElementType* ListContainer<BaseElementType>::back() {
-  ReverseIterator iter = rbegin();
-  return *iter;
-}
-
-template <typename BaseElementType>
-const BaseElementType* ListContainer<BaseElementType>::front() const {
-  ConstIterator iter = begin();
-  return *iter;
-}
-
-template <typename BaseElementType>
-const BaseElementType* ListContainer<BaseElementType>::back() const {
-  ConstReverseIterator iter = rbegin();
-  return *iter;
-}
-
-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;
-    if (index < current_size)
-      break;
-    index -= current_size;
-  }
-  return *ConstIterator(data_.get(),
-                        list_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;
-    if (index < current_size)
-      break;
-    index -= current_size;
-  }
-  return *Iterator(data_.get(),
-                   list_index,
-                   data_->InnerListById(list_index)->ElementAt(index),
-                   original_index);
-}
-
-template <typename BaseElementType>
-void* ListContainer<BaseElementType>::Allocate(
-    size_t size_of_actual_element_in_bytes) {
-  DCHECK_LE(size_of_actual_element_in_bytes, data_->element_size());
-  return data_->Allocate();
-}
-
-template <typename BaseElementType>
-size_t ListContainer<BaseElementType>::size() const {
-  return data_->size();
-}
-
-template <typename BaseElementType>
-bool ListContainer<BaseElementType>::empty() const {
-  return data_->IsEmpty();
-}
-
-template <typename BaseElementType>
-void ListContainer<BaseElementType>::clear() {
-  for (Iterator i = begin(); i != end(); ++i) {
-    i->~BaseElementType();
-  }
-  data_->Clear();
-}
-
-template <typename BaseElementType>
-size_t ListContainer<
-    BaseElementType>::AvailableSizeWithoutAnotherAllocationForTesting() const {
-  return data_->NumAvailableElementsInLastList();
-}
-
-// ListContainer::Iterator
-/////////////////////////////////////////////////
-template <typename BaseElementType>
-ListContainer<BaseElementType>::Iterator::Iterator(
-    ListContainerCharAllocator* container,
-    size_t vector_ind,
-    char* item_iter,
-    size_t index)
-    : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
-      index_(index) {
-}
-
-template <typename BaseElementType>
-ListContainer<BaseElementType>::Iterator::~Iterator() {
-}
-
-template <typename BaseElementType>
-BaseElementType* ListContainer<BaseElementType>::Iterator::operator->() const {
-  return reinterpret_cast<BaseElementType*>(this->item_iterator);
-}
-
-template <typename BaseElementType>
-BaseElementType* ListContainer<BaseElementType>::Iterator::operator*() const {
-  return reinterpret_cast<BaseElementType*>(this->item_iterator);
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::Iterator
-ListContainer<BaseElementType>::Iterator::
-operator++(int unused_post_increment) {
-  Iterator tmp = *this;
-  operator++();
-  return tmp;
-}
-
-template <typename BaseElementType>
-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), index_(other.index()) {
-}
-
-template <typename BaseElementType>
-ListContainer<BaseElementType>::ConstIterator::ConstIterator(
-    ListContainerCharAllocator* container,
-    size_t vector_ind,
-    char* item_iter,
-    size_t index)
-    : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
-      index_(index) {
-}
-
-template <typename BaseElementType>
-ListContainer<BaseElementType>::ConstIterator::~ConstIterator() {
-}
-
-template <typename BaseElementType>
-const BaseElementType* ListContainer<BaseElementType>::ConstIterator::
-operator->() const {
-  return reinterpret_cast<const BaseElementType*>(this->item_iterator);
-}
-
-template <typename BaseElementType>
-const BaseElementType* ListContainer<BaseElementType>::ConstIterator::
-operator*() const {
-  return reinterpret_cast<const BaseElementType*>(this->item_iterator);
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ConstIterator
-ListContainer<BaseElementType>::ConstIterator::
-operator++(int unused_post_increment) {
-  ConstIterator tmp = *this;
-  operator++();
-  return tmp;
-}
-
-template <typename BaseElementType>
-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,
-    size_t index)
-    : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
-      index_(index) {
-}
-
-template <typename BaseElementType>
-ListContainer<BaseElementType>::ReverseIterator::~ReverseIterator() {
-}
-
-template <typename BaseElementType>
-BaseElementType* ListContainer<BaseElementType>::ReverseIterator::operator->()
-    const {
-  return reinterpret_cast<BaseElementType*>(this->item_iterator);
-}
-
-template <typename BaseElementType>
-BaseElementType* ListContainer<BaseElementType>::ReverseIterator::operator*()
-    const {
-  return reinterpret_cast<BaseElementType*>(this->item_iterator);
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ReverseIterator
-ListContainer<BaseElementType>::ReverseIterator::
-operator++(int unused_post_increment) {
-  ReverseIterator tmp = *this;
-  operator++();
-  return tmp;
-}
-
-template <typename BaseElementType>
-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), index_(other.index()) {
-}
-
-template <typename BaseElementType>
-ListContainer<BaseElementType>::ConstReverseIterator::ConstReverseIterator(
-    ListContainerCharAllocator* container,
-    size_t vector_ind,
-    char* item_iter,
-    size_t index)
-    : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
-      index_(index) {
-}
-
-template <typename BaseElementType>
-ListContainer<BaseElementType>::ConstReverseIterator::~ConstReverseIterator() {
-}
-
-template <typename BaseElementType>
-const BaseElementType* ListContainer<BaseElementType>::ConstReverseIterator::
-operator->() const {
-  return reinterpret_cast<const BaseElementType*>(this->item_iterator);
-}
-
-template <typename BaseElementType>
-const BaseElementType* ListContainer<BaseElementType>::ConstReverseIterator::
-operator*() const {
-  return reinterpret_cast<const BaseElementType*>(this->item_iterator);
-}
-
-template <typename BaseElementType>
-typename ListContainer<BaseElementType>::ConstReverseIterator
-ListContainer<BaseElementType>::ConstReverseIterator::
-operator++(int unused_post_increment) {
-  ConstReverseIterator tmp = *this;
-  operator++();
-  return tmp;
-}
-
-template <typename BaseElementType>
-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>;
-template class ListContainer<DisplayItem>;
-
-}  // namespace cc