Revert "Delete CC."

cc/quads/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/quads/list_container.h"
+
+#include <algorithm>
+#include <vector>
+
+#include "cc/base/scoped_ptr_vector.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];
+  }
+
+  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()) {
+    if (vector_index < ptr_to_container->list_count() - 1) {
+      ++vector_index;
+      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()) {
+    if (vector_index > 0) {
+      --vector_index;
+      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 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(), 0);
+}
+
+template <typename BaseElementType>
+typename ListContainer<BaseElementType>::ConstReverseIterator
+ListContainer<BaseElementType>::crend() const {
+  return ConstReverseIterator(data_.get(), 0, 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 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(), 0);
+}
+
+template <typename BaseElementType>
+typename ListContainer<BaseElementType>::ReverseIterator
+ListContainer<BaseElementType>::rend() {
+  return ReverseIterator(data_.get(), 0, NULL, size());
+}
+
+template <typename BaseElementType>
+typename ListContainer<BaseElementType>::ConstIterator
+ListContainer<BaseElementType>::cbegin() const {
+  if (data_->IsEmpty())
+    return ConstIterator(data_.get(), 0, NULL, 0);
+
+  return ConstIterator(data_.get(), 0, data_->InnerListById(0)->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 last_id = data_->list_count() - 1;
+  return ConstIterator(data_.get(), last_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 Iterator(data_.get(), 0, NULL, 0);
+
+  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, size());
+
+  size_t last_id = data_->list_count() - 1;
+  return Iterator(data_.get(), last_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>
+BaseElementType* ListContainer<BaseElementType>::Allocate(
+    size_t size_of_actual_element_in_bytes) {
+  DCHECK_LE(size_of_actual_element_in_bytes, data_->element_size());
+  void* result = data_->Allocate();
+  return static_cast<BaseElementType*>(result);
+}
+
+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>;
+
+}  // namespace cc