Home | History | Annotate | Download | only in quads 
      1 // Copyright 2014 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "cc/quads/list_container.h"
      6 
      7 #include <algorithm>
      8 #include <vector>
      9 
     10 #include "cc/base/scoped_ptr_vector.h"
     11 #include "cc/quads/draw_quad.h"
     12 #include "cc/quads/shared_quad_state.h"
     13 
     14 namespace {
     15 const size_t kDefaultNumElementTypesToReserve = 32;
     16 }  // namespace
     17 
     18 namespace cc {
     19 
     20 // ListContainerCharAllocator
     21 ////////////////////////////////////////////////////
     22 // This class deals only with char* and void*. It does allocation and passing
     23 // out raw pointers, as well as memory deallocation when being destroyed.
     24 template <typename BaseElementType>
     25 class ListContainer<BaseElementType>::ListContainerCharAllocator {
     26  public:
     27   // ListContainerCharAllocator::InnerList
     28   /////////////////////////////////////////////
     29   // This class holds the raw memory chunk, as well as information about its
     30   // size and availability.
     31   struct InnerList {
     32     scoped_ptr<char[]> data;
     33     // The number of elements in total the memory can hold. The difference
     34     // between capacity and size is the how many more elements this list can
     35     // hold.
     36     size_t capacity;
     37     // The number of elements have been put into this list.
     38     size_t size;
     39     // The size of each element is in bytes. This is used to move from between
     40     // elements' memory locations.
     41     size_t step;
     42 
     43     InnerList() : capacity(0), size(0), step(0) {}
     44 
     45     void Erase(char* position) {
     46       // Confident that destructor is called by caller of this function. Since
     47       // ListContainerCharAllocator does not handle construction after
     48       // allocation, it doesn't handle desctrution before deallocation.
     49       DCHECK_LE(position, LastElement());
     50       DCHECK_GE(position, Begin());
     51       char* start = position + step;
     52       std::copy(start, End(), position);
     53 
     54       --size;
     55       // Decrease capacity to avoid creating not full not last InnerList.
     56       --capacity;
     57     }
     58 
     59     bool IsFull() { return capacity == size; }
     60     size_t NumElementsAvailable() const { return capacity - size; }
     61 
     62     void* AddElement() {
     63       DCHECK_LT(size, capacity);
     64       ++size;
     65       return LastElement();
     66     }
     67 
     68     char* Begin() const { return data.get(); }
     69     char* End() const { return data.get() + size * step; }
     70     char* LastElement() const { return data.get() + (size - 1) * step; }
     71     char* ElementAt(size_t index) const { return data.get() + index * step; }
     72 
     73    private:
     74     DISALLOW_COPY_AND_ASSIGN(InnerList);
     75   };
     76 
     77   explicit ListContainerCharAllocator(size_t element_size)
     78       : element_size_(element_size),
     79         size_(0),
     80         list_count_(0),
     81         last_list_(NULL) {
     82     AllocateNewList(kDefaultNumElementTypesToReserve);
     83   }
     84 
     85   ListContainerCharAllocator(size_t element_size, size_t element_count)
     86       : element_size_(element_size),
     87         size_(0),
     88         list_count_(0),
     89         last_list_(NULL) {
     90     DCHECK_NE(0u, element_count);
     91     AllocateNewList(element_count);
     92   }
     93 
     94   ~ListContainerCharAllocator() {}
     95 
     96   void* Allocate() {
     97     if (last_list_->IsFull())
     98       AllocateNewList(last_list_->capacity * 2);
     99 
    100     ++size_;
    101     return last_list_->AddElement();
    102   }
    103 
    104   size_t element_size() const { return element_size_; }
    105   size_t list_count() const { return list_count_; }
    106   size_t size() const { return size_; }
    107   bool IsEmpty() const { return size() == 0; }
    108 
    109   size_t Capacity() const {
    110     size_t capacity_sum = 0;
    111     for (typename ScopedPtrVector<InnerList>::const_iterator iter =
    112              storage_.begin();
    113          iter != storage_.end();
    114          ++iter) {
    115       capacity_sum += (*iter)->capacity;
    116     }
    117     return capacity_sum;
    118   }
    119 
    120   void Clear() {
    121     size_t initial_allocation_size = storage_.front()->capacity;
    122     storage_.clear();
    123     list_count_ = 0;
    124     last_list_ = NULL;
    125     size_ = 0;
    126     AllocateNewList(initial_allocation_size);
    127   }
    128 
    129   void Erase(PositionInListContainerCharAllocator position) {
    130     DCHECK_EQ(this, position.ptr_to_container);
    131     storage_[position.vector_index]->Erase(position.item_iterator);
    132     // TODO(weiliangc): Free the InnerList if it is empty.
    133     --size_;
    134   }
    135 
    136   InnerList* InnerListById(size_t id) const {
    137     DCHECK_LT(id, list_count_);
    138     return storage_[id];
    139   }
    140 
    141   void AllocateNewList(size_t list_size) {
    142     ++list_count_;
    143     scoped_ptr<InnerList> new_list(new InnerList);
    144     storage_.push_back(new_list.Pass());
    145     last_list_ = storage_.back();
    146     InnerList* list = last_list_;
    147     list->capacity = list_size;
    148     list->size = 0;
    149     list->step = element_size_;
    150     list->data.reset(new char[list->capacity * list->step]);
    151   }
    152 
    153   size_t NumAvailableElementsInLastList() const {
    154     return last_list_->NumElementsAvailable();
    155   }
    156 
    157  private:
    158   ScopedPtrVector<InnerList> storage_;
    159   const size_t element_size_;
    160   size_t size_;
    161   size_t list_count_;
    162   InnerList* last_list_;
    163 
    164   DISALLOW_COPY_AND_ASSIGN(ListContainerCharAllocator);
    165 };
    166 
    167 // PositionInListContainerCharAllocator
    168 //////////////////////////////////////////////////////
    169 template <typename BaseElementType>
    170 ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
    171     PositionInListContainerCharAllocator(const typename ListContainer<
    172         BaseElementType>::PositionInListContainerCharAllocator& other)
    173     : ptr_to_container(other.ptr_to_container),
    174       vector_index(other.vector_index),
    175       item_iterator(other.item_iterator) {
    176 }
    177 
    178 template <typename BaseElementType>
    179 ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
    180     PositionInListContainerCharAllocator(
    181         typename ListContainer<BaseElementType>::ListContainerCharAllocator*
    182             container,
    183         size_t vector_ind,
    184         char* item_iter)
    185     : ptr_to_container(container),
    186       vector_index(vector_ind),
    187       item_iterator(item_iter) {
    188 }
    189 
    190 template <typename BaseElementType>
    191 bool ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
    192 operator==(const typename ListContainer<
    193     BaseElementType>::PositionInListContainerCharAllocator& other) const {
    194   DCHECK_EQ(ptr_to_container, other.ptr_to_container);
    195   return vector_index == other.vector_index &&
    196          item_iterator == other.item_iterator;
    197 }
    198 
    199 template <typename BaseElementType>
    200 bool ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
    201 operator!=(const typename ListContainer<
    202     BaseElementType>::PositionInListContainerCharAllocator& other) const {
    203   return !(*this == other);
    204 }
    205 
    206 template <typename BaseElementType>
    207 typename ListContainer<BaseElementType>::PositionInListContainerCharAllocator
    208 ListContainer<
    209     BaseElementType>::PositionInListContainerCharAllocator::Increment() {
    210   typename ListContainerCharAllocator::InnerList* list =
    211       ptr_to_container->InnerListById(vector_index);
    212   if (item_iterator == list->LastElement()) {
    213     if (vector_index < ptr_to_container->list_count() - 1) {
    214       ++vector_index;
    215       item_iterator = ptr_to_container->InnerListById(vector_index)->Begin();
    216     } else {
    217       item_iterator = NULL;
    218     }
    219   } else {
    220     item_iterator += list->step;
    221   }
    222   return *this;
    223 }
    224 
    225 template <typename BaseElementType>
    226 typename ListContainer<BaseElementType>::PositionInListContainerCharAllocator
    227 ListContainer<
    228     BaseElementType>::PositionInListContainerCharAllocator::ReverseIncrement() {
    229   typename ListContainerCharAllocator::InnerList* list =
    230       ptr_to_container->InnerListById(vector_index);
    231   if (item_iterator == list->Begin()) {
    232     if (vector_index > 0) {
    233       --vector_index;
    234       item_iterator =
    235           ptr_to_container->InnerListById(vector_index)->LastElement();
    236     } else {
    237       item_iterator = NULL;
    238     }
    239   } else {
    240     item_iterator -= list->step;
    241   }
    242   return *this;
    243 }
    244 
    245 // ListContainer
    246 ////////////////////////////////////////////
    247 template <typename BaseElementType>
    248 ListContainer<BaseElementType>::ListContainer(size_t max_size_for_derived_class)
    249     : data_(new ListContainerCharAllocator(max_size_for_derived_class)) {
    250 }
    251 
    252 template <typename BaseElementType>
    253 ListContainer<BaseElementType>::ListContainer(
    254     size_t max_size_for_derived_class,
    255     size_t num_of_elements_to_reserve_for)
    256     : data_(new ListContainerCharAllocator(max_size_for_derived_class,
    257                                            num_of_elements_to_reserve_for)) {
    258 }
    259 
    260 template <typename BaseElementType>
    261 ListContainer<BaseElementType>::ListContainer()
    262     : data_(new ListContainerCharAllocator(sizeof(BaseElementType))) {
    263 }
    264 
    265 template <typename BaseElementType>
    266 ListContainer<BaseElementType>::~ListContainer() {
    267   for (Iterator i = begin(); i != end(); ++i) {
    268     i->~BaseElementType();
    269   }
    270 }
    271 
    272 template <typename BaseElementType>
    273 void ListContainer<BaseElementType>::EraseAndInvalidateAllPointers(
    274     typename ListContainer<BaseElementType>::Iterator position) {
    275   BaseElementType* item = &*position;
    276   item->~BaseElementType();
    277   data_->Erase(position);
    278 }
    279 
    280 template <typename BaseElementType>
    281 typename ListContainer<BaseElementType>::ConstReverseIterator
    282 ListContainer<BaseElementType>::rbegin() const {
    283   if (data_->IsEmpty())
    284     return ConstReverseIterator(data_.get(), 0, NULL);
    285 
    286   size_t last_id = data_->list_count() - 1;
    287   return ConstReverseIterator(
    288       data_.get(), last_id, data_->InnerListById(last_id)->LastElement());
    289 }
    290 
    291 template <typename BaseElementType>
    292 typename ListContainer<BaseElementType>::ConstReverseIterator
    293 ListContainer<BaseElementType>::rend() const {
    294   return ConstReverseIterator(data_.get(), 0, NULL);
    295 }
    296 
    297 template <typename BaseElementType>
    298 typename ListContainer<BaseElementType>::ReverseIterator
    299 ListContainer<BaseElementType>::rbegin() {
    300   if (data_->IsEmpty())
    301     return ReverseIterator(data_.get(), 0, NULL);
    302 
    303   size_t last_id = data_->list_count() - 1;
    304   return ReverseIterator(
    305       data_.get(), last_id, data_->InnerListById(last_id)->LastElement());
    306 }
    307 
    308 template <typename BaseElementType>
    309 typename ListContainer<BaseElementType>::ReverseIterator
    310 ListContainer<BaseElementType>::rend() {
    311   return ReverseIterator(data_.get(), 0, NULL);
    312 }
    313 
    314 template <typename BaseElementType>
    315 typename ListContainer<BaseElementType>::ConstIterator
    316 ListContainer<BaseElementType>::begin() const {
    317   if (data_->IsEmpty())
    318     return ConstIterator(data_.get(), 0, NULL);
    319 
    320   return ConstIterator(data_.get(), 0, data_->InnerListById(0)->Begin());
    321 }
    322 
    323 template <typename BaseElementType>
    324 typename ListContainer<BaseElementType>::ConstIterator
    325 ListContainer<BaseElementType>::end() const {
    326   if (data_->IsEmpty())
    327     return ConstIterator(data_.get(), 0, NULL);
    328 
    329   size_t last_id = data_->list_count() - 1;
    330   return ConstIterator(data_.get(), last_id, NULL);
    331 }
    332 
    333 template <typename BaseElementType>
    334 typename ListContainer<BaseElementType>::Iterator
    335 ListContainer<BaseElementType>::begin() {
    336   if (data_->IsEmpty())
    337     return Iterator(data_.get(), 0, NULL);
    338 
    339   return Iterator(data_.get(), 0, data_->InnerListById(0)->Begin());
    340 }
    341 
    342 template <typename BaseElementType>
    343 typename ListContainer<BaseElementType>::Iterator
    344 ListContainer<BaseElementType>::end() {
    345   if (data_->IsEmpty())
    346     return Iterator(data_.get(), 0, NULL);
    347 
    348   size_t last_id = data_->list_count() - 1;
    349   return Iterator(data_.get(), last_id, NULL);
    350 }
    351 
    352 template <typename BaseElementType>
    353 BaseElementType* ListContainer<BaseElementType>::front() {
    354   Iterator iter = begin();
    355   return &*iter;
    356 }
    357 
    358 template <typename BaseElementType>
    359 BaseElementType* ListContainer<BaseElementType>::back() {
    360   ReverseIterator iter = rbegin();
    361   return &*iter;
    362 }
    363 
    364 template <typename BaseElementType>
    365 const BaseElementType* ListContainer<BaseElementType>::front() const {
    366   ConstIterator iter = begin();
    367   return &*iter;
    368 }
    369 
    370 template <typename BaseElementType>
    371 const BaseElementType* ListContainer<BaseElementType>::back() const {
    372   ConstReverseIterator iter = rbegin();
    373   return &*iter;
    374 }
    375 
    376 template <typename BaseElementType>
    377 const BaseElementType* ListContainer<BaseElementType>::ElementAt(
    378     size_t index) const {
    379   DCHECK_LT(index, size());
    380   size_t list_index;
    381   for (list_index = 0; list_index < data_->list_count(); ++list_index) {
    382     size_t current_size = data_->InnerListById(list_index)->size;
    383     if (index < current_size)
    384       break;
    385     index -= current_size;
    386   }
    387   return &*ConstIterator(data_.get(),
    388                          list_index,
    389                          data_->InnerListById(list_index)->ElementAt(index));
    390 }
    391 
    392 template <typename BaseElementType>
    393 BaseElementType* ListContainer<BaseElementType>::ElementAt(size_t index) {
    394   DCHECK_LT(index, size());
    395   size_t list_index;
    396   for (list_index = 0; list_index < data_->list_count(); ++list_index) {
    397     size_t current_size = data_->InnerListById(list_index)->size;
    398     if (index < current_size)
    399       break;
    400     index -= current_size;
    401   }
    402   return &*Iterator(data_.get(),
    403                     list_index,
    404                     data_->InnerListById(list_index)->ElementAt(index));
    405 }
    406 
    407 template <typename BaseElementType>
    408 BaseElementType* ListContainer<BaseElementType>::Allocate(
    409     size_t size_of_actual_element_in_bytes) {
    410   DCHECK_LE(size_of_actual_element_in_bytes, data_->element_size());
    411   void* result = data_->Allocate();
    412   return static_cast<BaseElementType*>(result);
    413 }
    414 
    415 template <typename BaseElementType>
    416 size_t ListContainer<BaseElementType>::size() const {
    417   return data_->size();
    418 }
    419 
    420 template <typename BaseElementType>
    421 bool ListContainer<BaseElementType>::empty() const {
    422   return data_->IsEmpty();
    423 }
    424 
    425 template <typename BaseElementType>
    426 void ListContainer<BaseElementType>::clear() {
    427   for (Iterator i = begin(); i != end(); ++i) {
    428     i->~BaseElementType();
    429   }
    430   data_->Clear();
    431 }
    432 
    433 template <typename BaseElementType>
    434 size_t ListContainer<
    435     BaseElementType>::AvailableSizeWithoutAnotherAllocationForTesting() const {
    436   return data_->NumAvailableElementsInLastList();
    437 }
    438 
    439 // ListContainer::Iterator
    440 /////////////////////////////////////////////////
    441 template <typename BaseElementType>
    442 ListContainer<BaseElementType>::Iterator::Iterator(
    443     ListContainerCharAllocator* container,
    444     size_t vector_ind,
    445     char* item_iter)
    446     : PositionInListContainerCharAllocator(container, vector_ind, item_iter) {
    447 }
    448 
    449 template <typename BaseElementType>
    450 ListContainer<BaseElementType>::Iterator::~Iterator() {
    451 }
    452 
    453 template <typename BaseElementType>
    454 BaseElementType* ListContainer<BaseElementType>::Iterator::operator->() const {
    455   return reinterpret_cast<BaseElementType*>(this->item_iterator);
    456 }
    457 
    458 template <typename BaseElementType>
    459 BaseElementType& ListContainer<BaseElementType>::Iterator::operator*() const {
    460   return *(reinterpret_cast<BaseElementType*>(this->item_iterator));
    461 }
    462 
    463 template <typename BaseElementType>
    464 typename ListContainer<BaseElementType>::Iterator
    465 ListContainer<BaseElementType>::Iterator::
    466 operator++(int unused_post_increment) {
    467   Iterator tmp = *this;
    468   operator++();
    469   return tmp;
    470 }
    471 
    472 template <typename BaseElementType>
    473 typename ListContainer<BaseElementType>::Iterator
    474 ListContainer<BaseElementType>::Iterator::
    475 operator++() {
    476   this->Increment();
    477   return *this;
    478 }
    479 
    480 // ListContainer::ConstIterator
    481 /////////////////////////////////////////////////
    482 template <typename BaseElementType>
    483 ListContainer<BaseElementType>::ConstIterator::ConstIterator(
    484     const typename ListContainer<BaseElementType>::Iterator& other)
    485     : PositionInListContainerCharAllocator(other) {
    486 }
    487 
    488 template <typename BaseElementType>
    489 ListContainer<BaseElementType>::ConstIterator::ConstIterator(
    490     ListContainerCharAllocator* container,
    491     size_t vector_ind,
    492     char* item_iter)
    493     : PositionInListContainerCharAllocator(container, vector_ind, item_iter) {
    494 }
    495 
    496 template <typename BaseElementType>
    497 ListContainer<BaseElementType>::ConstIterator::~ConstIterator() {
    498 }
    499 
    500 template <typename BaseElementType>
    501 const BaseElementType* ListContainer<BaseElementType>::ConstIterator::
    502 operator->() const {
    503   return reinterpret_cast<const BaseElementType*>(this->item_iterator);
    504 }
    505 
    506 template <typename BaseElementType>
    507 const BaseElementType& ListContainer<BaseElementType>::ConstIterator::
    508 operator*() const {
    509   return *(reinterpret_cast<const BaseElementType*>(this->item_iterator));
    510 }
    511 
    512 template <typename BaseElementType>
    513 typename ListContainer<BaseElementType>::ConstIterator
    514 ListContainer<BaseElementType>::ConstIterator::
    515 operator++(int unused_post_increment) {
    516   ConstIterator tmp = *this;
    517   operator++();
    518   return tmp;
    519 }
    520 
    521 template <typename BaseElementType>
    522 typename ListContainer<BaseElementType>::ConstIterator
    523 ListContainer<BaseElementType>::ConstIterator::
    524 operator++() {
    525   this->Increment();
    526   return *this;
    527 }
    528 
    529 // ListContainer::ReverseIterator
    530 /////////////////////////////////////////////////
    531 template <typename BaseElementType>
    532 ListContainer<BaseElementType>::ReverseIterator::ReverseIterator(
    533     ListContainerCharAllocator* container,
    534     size_t vector_ind,
    535     char* item_iter)
    536     : PositionInListContainerCharAllocator(container, vector_ind, item_iter) {
    537 }
    538 
    539 template <typename BaseElementType>
    540 ListContainer<BaseElementType>::ReverseIterator::~ReverseIterator() {
    541 }
    542 
    543 template <typename BaseElementType>
    544 BaseElementType* ListContainer<BaseElementType>::ReverseIterator::operator->()
    545     const {
    546   return reinterpret_cast<BaseElementType*>(this->item_iterator);
    547 }
    548 
    549 template <typename BaseElementType>
    550 BaseElementType& ListContainer<BaseElementType>::ReverseIterator::operator*()
    551     const {
    552   return *(reinterpret_cast<BaseElementType*>(this->item_iterator));
    553 }
    554 
    555 template <typename BaseElementType>
    556 typename ListContainer<BaseElementType>::ReverseIterator
    557 ListContainer<BaseElementType>::ReverseIterator::
    558 operator++(int unused_post_increment) {
    559   ReverseIterator tmp = *this;
    560   operator++();
    561   return tmp;
    562 }
    563 
    564 template <typename BaseElementType>
    565 typename ListContainer<BaseElementType>::ReverseIterator
    566 ListContainer<BaseElementType>::ReverseIterator::
    567 operator++() {
    568   this->ReverseIncrement();
    569   return *this;
    570 }
    571 
    572 // ListContainer::ConstReverseIterator
    573 /////////////////////////////////////////////////
    574 template <typename BaseElementType>
    575 ListContainer<BaseElementType>::ConstReverseIterator::ConstReverseIterator(
    576     const typename ListContainer<BaseElementType>::ReverseIterator& other)
    577     : PositionInListContainerCharAllocator(other) {
    578 }
    579 
    580 template <typename BaseElementType>
    581 ListContainer<BaseElementType>::ConstReverseIterator::ConstReverseIterator(
    582     ListContainerCharAllocator* container,
    583     size_t vector_ind,
    584     char* item_iter)
    585     : PositionInListContainerCharAllocator(container, vector_ind, item_iter) {
    586 }
    587 
    588 template <typename BaseElementType>
    589 ListContainer<BaseElementType>::ConstReverseIterator::~ConstReverseIterator() {
    590 }
    591 
    592 template <typename BaseElementType>
    593 const BaseElementType* ListContainer<BaseElementType>::ConstReverseIterator::
    594 operator->() const {
    595   return reinterpret_cast<const BaseElementType*>(this->item_iterator);
    596 }
    597 
    598 template <typename BaseElementType>
    599 const BaseElementType& ListContainer<BaseElementType>::ConstReverseIterator::
    600 operator*() const {
    601   return *(reinterpret_cast<const BaseElementType*>(this->item_iterator));
    602 }
    603 
    604 template <typename BaseElementType>
    605 typename ListContainer<BaseElementType>::ConstReverseIterator
    606 ListContainer<BaseElementType>::ConstReverseIterator::
    607 operator++(int unused_post_increment) {
    608   ConstReverseIterator tmp = *this;
    609   operator++();
    610   return tmp;
    611 }
    612 
    613 template <typename BaseElementType>
    614 typename ListContainer<BaseElementType>::ConstReverseIterator
    615 ListContainer<BaseElementType>::ConstReverseIterator::
    616 operator++() {
    617   this->ReverseIncrement();
    618   return *this;
    619 }
    620 
    621 template class ListContainer<SharedQuadState>;
    622 template class ListContainer<DrawQuad>;
    623 
    624 }  // namespace cc
    625