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