src/cc/quads/list_container.cc

   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