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     AllocateNewList(element_count > 0 ? element_count
  91                                       : kDefaultNumElementTypesToReserve);
  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   size_t FirstInnerListId() const {
 142     // |size_| > 0 means that at least one vector in |storage_| will be
 143     // non-empty.
 144     DCHECK_GT(size_, 0u);
 145     size_t id = 0;
 146     while (storage_[id]->size == 0)
 147       ++id;
 148     return id;
 149   }
 150
 151   size_t LastInnerListId() const {
 152     // |size_| > 0 means that at least one vector in |storage_| will be
 153     // non-empty.
 154     DCHECK_GT(size_, 0u);
 155     size_t id = list_count_ - 1;
 156     while (storage_[id]->size == 0)
 157       --id;
 158     return id;
 159   }
 160
 161   void AllocateNewList(size_t list_size) {
 162     ++list_count_;
 163     scoped_ptr<InnerList> new_list(new InnerList);
 164     storage_.push_back(new_list.Pass());
 165     last_list_ = storage_.back();
 166     InnerList* list = last_list_;
 167     list->capacity = list_size;
 168     list->size = 0;
 169     list->step = element_size_;
 170     list->data.reset(new char[list->capacity * list->step]);
 171   }
 172
 173   size_t NumAvailableElementsInLastList() const {
 174     return last_list_->NumElementsAvailable();
 175   }
 176
 177  private:
 178   ScopedPtrVector<InnerList> storage_;
 179   const size_t element_size_;
 180   size_t size_;
 181   size_t list_count_;
 182   InnerList* last_list_;
 183
 184   DISALLOW_COPY_AND_ASSIGN(ListContainerCharAllocator);
 185 };
 186
 187 // PositionInListContainerCharAllocator
 188 //////////////////////////////////////////////////////
 189 template <typename BaseElementType>
 190 ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
 191     PositionInListContainerCharAllocator(const typename ListContainer<
 192         BaseElementType>::PositionInListContainerCharAllocator& other)
 193     : ptr_to_container(other.ptr_to_container),
 194       vector_index(other.vector_index),
 195       item_iterator(other.item_iterator) {
 196 }
 197
 198 template <typename BaseElementType>
 199 ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
 200     PositionInListContainerCharAllocator(
 201         typename ListContainer<BaseElementType>::ListContainerCharAllocator*
 202             container,
 203         size_t vector_ind,
 204         char* item_iter)
 205     : ptr_to_container(container),
 206       vector_index(vector_ind),
 207       item_iterator(item_iter) {
 208 }
 209
 210 template <typename BaseElementType>
 211 bool ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
 212 operator==(const typename ListContainer<
 213     BaseElementType>::PositionInListContainerCharAllocator& other) const {
 214   DCHECK_EQ(ptr_to_container, other.ptr_to_container);
 215   return vector_index == other.vector_index &&
 216          item_iterator == other.item_iterator;
 217 }
 218
 219 template <typename BaseElementType>
 220 bool ListContainer<BaseElementType>::PositionInListContainerCharAllocator::
 221 operator!=(const typename ListContainer<
 222     BaseElementType>::PositionInListContainerCharAllocator& other) const {
 223   return !(*this == other);
 224 }
 225
 226 template <typename BaseElementType>
 227 typename ListContainer<BaseElementType>::PositionInListContainerCharAllocator
 228 ListContainer<
 229     BaseElementType>::PositionInListContainerCharAllocator::Increment() {
 230   typename ListContainerCharAllocator::InnerList* list =
 231       ptr_to_container->InnerListById(vector_index);
 232   if (item_iterator == list->LastElement()) {
 233     ++vector_index;
 234     while (vector_index < ptr_to_container->list_count()) {
 235       if (ptr_to_container->InnerListById(vector_index)->size != 0)
 236         break;
 237       ++vector_index;
 238     }
 239     if (vector_index < ptr_to_container->list_count())
 240       item_iterator = ptr_to_container->InnerListById(vector_index)->Begin();
 241     else
 242       item_iterator = NULL;
 243   } else {
 244     item_iterator += list->step;
 245   }
 246   return *this;
 247 }
 248
 249 template <typename BaseElementType>
 250 typename ListContainer<BaseElementType>::PositionInListContainerCharAllocator
 251 ListContainer<
 252     BaseElementType>::PositionInListContainerCharAllocator::ReverseIncrement() {
 253   typename ListContainerCharAllocator::InnerList* list =
 254       ptr_to_container->InnerListById(vector_index);
 255   if (item_iterator == list->Begin()) {
 256     --vector_index;
 257     // Since |vector_index| is unsigned, we compare < list_count() instead of
 258     // comparing >= 0, as the variable will wrap around when it goes out of
 259     // range (below 0).
 260     while (vector_index < ptr_to_container->list_count()) {
 261       if (ptr_to_container->InnerListById(vector_index)->size != 0)
 262         break;
 263       --vector_index;
 264     }
 265     if (vector_index < ptr_to_container->list_count()) {
 266       item_iterator =
 267           ptr_to_container->InnerListById(vector_index)->LastElement();
 268     } else {
 269       item_iterator = NULL;
 270     }
 271   } else {
 272     item_iterator -= list->step;
 273   }
 274   return *this;
 275 }
 276
 277 // ListContainer
 278 ////////////////////////////////////////////
 279 template <typename BaseElementType>
 280 ListContainer<BaseElementType>::ListContainer(size_t max_size_for_derived_class)
 281     : data_(new ListContainerCharAllocator(max_size_for_derived_class)) {
 282 }
 283
 284 template <typename BaseElementType>
 285 ListContainer<BaseElementType>::ListContainer(
 286     size_t max_size_for_derived_class,
 287     size_t num_of_elements_to_reserve_for)
 288     : data_(new ListContainerCharAllocator(max_size_for_derived_class,
 289                                            num_of_elements_to_reserve_for)) {
 290 }
 291
 292 template <typename BaseElementType>
 293 ListContainer<BaseElementType>::ListContainer()
 294     : data_(new ListContainerCharAllocator(sizeof(BaseElementType))) {
 295 }
 296
 297 template <typename BaseElementType>
 298 ListContainer<BaseElementType>::~ListContainer() {
 299   for (Iterator i = begin(); i != end(); ++i) {
 300     i->~BaseElementType();
 301   }
 302 }
 303
 304 template <typename BaseElementType>
 305 void ListContainer<BaseElementType>::EraseAndInvalidateAllPointers(
 306     typename ListContainer<BaseElementType>::Iterator position) {
 307   BaseElementType* item = *position;
 308   item->~BaseElementType();
 309   data_->Erase(position);
 310 }
 311
 312 template <typename BaseElementType>
 313 typename ListContainer<BaseElementType>::ConstReverseIterator
 314 ListContainer<BaseElementType>::crbegin() const {
 315   if (data_->IsEmpty())
 316     return crend();
 317
 318   size_t id = data_->LastInnerListId();
 319   return ConstReverseIterator(data_.get(), id,
 320                               data_->InnerListById(id)->LastElement(), 0);
 321 }
 322
 323 template <typename BaseElementType>
 324 typename ListContainer<BaseElementType>::ConstReverseIterator
 325 ListContainer<BaseElementType>::crend() const {
 326   return ConstReverseIterator(data_.get(), static_cast<size_t>(-1), NULL,
 327                               size());
 328 }
 329
 330 template <typename BaseElementType>
 331 typename ListContainer<BaseElementType>::ConstReverseIterator
 332 ListContainer<BaseElementType>::rbegin() const {
 333   return crbegin();
 334 }
 335
 336 template <typename BaseElementType>
 337 typename ListContainer<BaseElementType>::ConstReverseIterator
 338 ListContainer<BaseElementType>::rend() const {
 339   return crend();
 340 }
 341
 342 template <typename BaseElementType>
 343 typename ListContainer<BaseElementType>::ReverseIterator
 344 ListContainer<BaseElementType>::rbegin() {
 345   if (data_->IsEmpty())
 346     return rend();
 347
 348   size_t id = data_->LastInnerListId();
 349   return ReverseIterator(data_.get(), id,
 350                          data_->InnerListById(id)->LastElement(), 0);
 351 }
 352
 353 template <typename BaseElementType>
 354 typename ListContainer<BaseElementType>::ReverseIterator
 355 ListContainer<BaseElementType>::rend() {
 356   return ReverseIterator(data_.get(), static_cast<size_t>(-1), NULL, size());
 357 }
 358
 359 template <typename BaseElementType>
 360 typename ListContainer<BaseElementType>::ConstIterator
 361 ListContainer<BaseElementType>::cbegin() const {
 362   if (data_->IsEmpty())
 363     return cend();
 364
 365   size_t id = data_->FirstInnerListId();
 366   return ConstIterator(data_.get(), id, data_->InnerListById(id)->Begin(), 0);
 367 }
 368
 369 template <typename BaseElementType>
 370 typename ListContainer<BaseElementType>::ConstIterator
 371 ListContainer<BaseElementType>::cend() const {
 372   if (data_->IsEmpty())
 373     return ConstIterator(data_.get(), 0, NULL, size());
 374
 375   size_t id = data_->list_count();
 376   return ConstIterator(data_.get(), id, NULL, size());
 377 }
 378
 379 template <typename BaseElementType>
 380 typename ListContainer<BaseElementType>::ConstIterator
 381 ListContainer<BaseElementType>::begin() const {
 382   return cbegin();
 383 }
 384
 385 template <typename BaseElementType>
 386 typename ListContainer<BaseElementType>::ConstIterator
 387 ListContainer<BaseElementType>::end() const {
 388   return cend();
 389 }
 390
 391 template <typename BaseElementType>
 392 typename ListContainer<BaseElementType>::Iterator
 393 ListContainer<BaseElementType>::begin() {
 394   if (data_->IsEmpty())
 395     return end();
 396
 397   size_t id = data_->FirstInnerListId();
 398   return Iterator(data_.get(), id, data_->InnerListById(id)->Begin(), 0);
 399 }
 400
 401 template <typename BaseElementType>
 402 typename ListContainer<BaseElementType>::Iterator
 403 ListContainer<BaseElementType>::end() {
 404   if (data_->IsEmpty())
 405     return Iterator(data_.get(), 0, NULL, size());
 406
 407   size_t id = data_->list_count();
 408   return Iterator(data_.get(), id, NULL, size());
 409 }
 410
 411 template <typename BaseElementType>
 412 BaseElementType* ListContainer<BaseElementType>::front() {
 413   Iterator iter = begin();
 414   return *iter;
 415 }
 416
 417 template <typename BaseElementType>
 418 BaseElementType* ListContainer<BaseElementType>::back() {
 419   ReverseIterator iter = rbegin();
 420   return *iter;
 421 }
 422
 423 template <typename BaseElementType>
 424 const BaseElementType* ListContainer<BaseElementType>::front() const {
 425   ConstIterator iter = begin();
 426   return *iter;
 427 }
 428
 429 template <typename BaseElementType>
 430 const BaseElementType* ListContainer<BaseElementType>::back() const {
 431   ConstReverseIterator iter = rbegin();
 432   return *iter;
 433 }
 434
 435 template <typename BaseElementType>
 436 const BaseElementType* ListContainer<BaseElementType>::ElementAt(
 437     size_t index) const {
 438   DCHECK_LT(index, size());
 439   size_t original_index = index;
 440   size_t list_index;
 441   for (list_index = 0; list_index < data_->list_count(); ++list_index) {
 442     size_t current_size = data_->InnerListById(list_index)->size;
 443     if (index < current_size)
 444       break;
 445     index -= current_size;
 446   }
 447   return *ConstIterator(data_.get(),
 448                         list_index,
 449                         data_->InnerListById(list_index)->ElementAt(index),
 450                         original_index);
 451 }
 452
 453 template <typename BaseElementType>
 454 BaseElementType* ListContainer<BaseElementType>::ElementAt(size_t index) {
 455   DCHECK_LT(index, size());
 456   size_t original_index = index;
 457   size_t list_index;
 458   for (list_index = 0; list_index < data_->list_count(); ++list_index) {
 459     size_t current_size = data_->InnerListById(list_index)->size;
 460     if (index < current_size)
 461       break;
 462     index -= current_size;
 463   }
 464   return *Iterator(data_.get(),
 465                    list_index,
 466                    data_->InnerListById(list_index)->ElementAt(index),
 467                    original_index);
 468 }
 469
 470 template <typename BaseElementType>
 471 void* ListContainer<BaseElementType>::Allocate(
 472     size_t size_of_actual_element_in_bytes) {
 473   DCHECK_LE(size_of_actual_element_in_bytes, data_->element_size());
 474   return data_->Allocate();
 475 }
 476
 477 template <typename BaseElementType>
 478 size_t ListContainer<BaseElementType>::size() const {
 479   return data_->size();
 480 }
 481
 482 template <typename BaseElementType>
 483 bool ListContainer<BaseElementType>::empty() const {
 484   return data_->IsEmpty();
 485 }
 486
 487 template <typename BaseElementType>
 488 void ListContainer<BaseElementType>::clear() {
 489   for (Iterator i = begin(); i != end(); ++i) {
 490     i->~BaseElementType();
 491   }
 492   data_->Clear();
 493 }
 494
 495 template <typename BaseElementType>
 496 size_t ListContainer<
 497     BaseElementType>::AvailableSizeWithoutAnotherAllocationForTesting() const {
 498   return data_->NumAvailableElementsInLastList();
 499 }
 500
 501 // ListContainer::Iterator
 502 /////////////////////////////////////////////////
 503 template <typename BaseElementType>
 504 ListContainer<BaseElementType>::Iterator::Iterator(
 505     ListContainerCharAllocator* container,
 506     size_t vector_ind,
 507     char* item_iter,
 508     size_t index)
 509     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 510       index_(index) {
 511 }
 512
 513 template <typename BaseElementType>
 514 ListContainer<BaseElementType>::Iterator::~Iterator() {
 515 }
 516
 517 template <typename BaseElementType>
 518 BaseElementType* ListContainer<BaseElementType>::Iterator::operator->() const {
 519   return reinterpret_cast<BaseElementType*>(this->item_iterator);
 520 }
 521
 522 template <typename BaseElementType>
 523 BaseElementType* ListContainer<BaseElementType>::Iterator::operator*() const {
 524   return reinterpret_cast<BaseElementType*>(this->item_iterator);
 525 }
 526
 527 template <typename BaseElementType>
 528 typename ListContainer<BaseElementType>::Iterator
 529 ListContainer<BaseElementType>::Iterator::
 530 operator++(int unused_post_increment) {
 531   Iterator tmp = *this;
 532   operator++();
 533   return tmp;
 534 }
 535
 536 template <typename BaseElementType>
 537 typename ListContainer<BaseElementType>::Iterator&
 538     ListContainer<BaseElementType>::Iterator::
 539     operator++() {
 540   this->Increment();
 541   ++index_;
 542   return *this;
 543 }
 544
 545 template <typename BaseElementType>
 546 size_t ListContainer<BaseElementType>::Iterator::index() const {
 547   return index_;
 548 }
 549
 550 // ListContainer::ConstIterator
 551 /////////////////////////////////////////////////
 552 template <typename BaseElementType>
 553 ListContainer<BaseElementType>::ConstIterator::ConstIterator(
 554     const typename ListContainer<BaseElementType>::Iterator& other)
 555     : PositionInListContainerCharAllocator(other), index_(other.index()) {
 556 }
 557
 558 template <typename BaseElementType>
 559 ListContainer<BaseElementType>::ConstIterator::ConstIterator(
 560     ListContainerCharAllocator* container,
 561     size_t vector_ind,
 562     char* item_iter,
 563     size_t index)
 564     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 565       index_(index) {
 566 }
 567
 568 template <typename BaseElementType>
 569 ListContainer<BaseElementType>::ConstIterator::~ConstIterator() {
 570 }
 571
 572 template <typename BaseElementType>
 573 const BaseElementType* ListContainer<BaseElementType>::ConstIterator::
 574 operator->() const {
 575   return reinterpret_cast<const BaseElementType*>(this->item_iterator);
 576 }
 577
 578 template <typename BaseElementType>
 579 const BaseElementType* ListContainer<BaseElementType>::ConstIterator::
 580 operator*() const {
 581   return reinterpret_cast<const BaseElementType*>(this->item_iterator);
 582 }
 583
 584 template <typename BaseElementType>
 585 typename ListContainer<BaseElementType>::ConstIterator
 586 ListContainer<BaseElementType>::ConstIterator::
 587 operator++(int unused_post_increment) {
 588   ConstIterator tmp = *this;
 589   operator++();
 590   return tmp;
 591 }
 592
 593 template <typename BaseElementType>
 594 typename ListContainer<BaseElementType>::ConstIterator&
 595     ListContainer<BaseElementType>::ConstIterator::
 596     operator++() {
 597   this->Increment();
 598   ++index_;
 599   return *this;
 600 }
 601
 602 template <typename BaseElementType>
 603 size_t ListContainer<BaseElementType>::ConstIterator::index() const {
 604   return index_;
 605 }
 606
 607 // ListContainer::ReverseIterator
 608 /////////////////////////////////////////////////
 609 template <typename BaseElementType>
 610 ListContainer<BaseElementType>::ReverseIterator::ReverseIterator(
 611     ListContainerCharAllocator* container,
 612     size_t vector_ind,
 613     char* item_iter,
 614     size_t index)
 615     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 616       index_(index) {
 617 }
 618
 619 template <typename BaseElementType>
 620 ListContainer<BaseElementType>::ReverseIterator::~ReverseIterator() {
 621 }
 622
 623 template <typename BaseElementType>
 624 BaseElementType* ListContainer<BaseElementType>::ReverseIterator::operator->()
 625     const {
 626   return reinterpret_cast<BaseElementType*>(this->item_iterator);
 627 }
 628
 629 template <typename BaseElementType>
 630 BaseElementType* ListContainer<BaseElementType>::ReverseIterator::operator*()
 631     const {
 632   return reinterpret_cast<BaseElementType*>(this->item_iterator);
 633 }
 634
 635 template <typename BaseElementType>
 636 typename ListContainer<BaseElementType>::ReverseIterator
 637 ListContainer<BaseElementType>::ReverseIterator::
 638 operator++(int unused_post_increment) {
 639   ReverseIterator tmp = *this;
 640   operator++();
 641   return tmp;
 642 }
 643
 644 template <typename BaseElementType>
 645 typename ListContainer<BaseElementType>::ReverseIterator&
 646     ListContainer<BaseElementType>::ReverseIterator::
 647     operator++() {
 648   this->ReverseIncrement();
 649   ++index_;
 650   return *this;
 651 }
 652
 653 template <typename BaseElementType>
 654 size_t ListContainer<BaseElementType>::ReverseIterator::index() const {
 655   return index_;
 656 }
 657
 658 // ListContainer::ConstReverseIterator
 659 /////////////////////////////////////////////////
 660 template <typename BaseElementType>
 661 ListContainer<BaseElementType>::ConstReverseIterator::ConstReverseIterator(
 662     const typename ListContainer<BaseElementType>::ReverseIterator& other)
 663     : PositionInListContainerCharAllocator(other), index_(other.index()) {
 664 }
 665
 666 template <typename BaseElementType>
 667 ListContainer<BaseElementType>::ConstReverseIterator::ConstReverseIterator(
 668     ListContainerCharAllocator* container,
 669     size_t vector_ind,
 670     char* item_iter,
 671     size_t index)
 672     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 673       index_(index) {
 674 }
 675
 676 template <typename BaseElementType>
 677 ListContainer<BaseElementType>::ConstReverseIterator::~ConstReverseIterator() {
 678 }
 679
 680 template <typename BaseElementType>
 681 const BaseElementType* ListContainer<BaseElementType>::ConstReverseIterator::
 682 operator->() const {
 683   return reinterpret_cast<const BaseElementType*>(this->item_iterator);
 684 }
 685
 686 template <typename BaseElementType>
 687 const BaseElementType* ListContainer<BaseElementType>::ConstReverseIterator::
 688 operator*() const {
 689   return reinterpret_cast<const BaseElementType*>(this->item_iterator);
 690 }
 691
 692 template <typename BaseElementType>
 693 typename ListContainer<BaseElementType>::ConstReverseIterator
 694 ListContainer<BaseElementType>::ConstReverseIterator::
 695 operator++(int unused_post_increment) {
 696   ConstReverseIterator tmp = *this;
 697   operator++();
 698   return tmp;
 699 }
 700
 701 template <typename BaseElementType>
 702 typename ListContainer<BaseElementType>::ConstReverseIterator&
 703     ListContainer<BaseElementType>::ConstReverseIterator::
 704     operator++() {
 705   this->ReverseIncrement();
 706   ++index_;
 707   return *this;
 708 }
 709
 710 template <typename BaseElementType>
 711 size_t ListContainer<BaseElementType>::ConstReverseIterator::index() const {
 712   return index_;
 713 }
 714
 715 template class ListContainer<SharedQuadState>;
 716 template class ListContainer<DrawQuad>;
 717
 718 }  // namespace cc