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     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   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>::crbegin() const {
 283   if (data_->IsEmpty())
 284     return ConstReverseIterator(data_.get(), 0, NULL, 0);
 285
 286   size_t last_id = data_->list_count() - 1;
 287   return ConstReverseIterator(
 288       data_.get(), last_id, data_->InnerListById(last_id)->LastElement(), 0);
 289 }
 290
 291 template <typename BaseElementType>
 292 typename ListContainer<BaseElementType>::ConstReverseIterator
 293 ListContainer<BaseElementType>::crend() const {
 294   return ConstReverseIterator(data_.get(), 0, NULL, size());
 295 }
 296
 297 template <typename BaseElementType>
 298 typename ListContainer<BaseElementType>::ConstReverseIterator
 299 ListContainer<BaseElementType>::rbegin() const {
 300   return crbegin();
 301 }
 302
 303 template <typename BaseElementType>
 304 typename ListContainer<BaseElementType>::ConstReverseIterator
 305 ListContainer<BaseElementType>::rend() const {
 306   return crend();
 307 }
 308
 309 template <typename BaseElementType>
 310 typename ListContainer<BaseElementType>::ReverseIterator
 311 ListContainer<BaseElementType>::rbegin() {
 312   if (data_->IsEmpty())
 313     return ReverseIterator(data_.get(), 0, NULL, 0);
 314
 315   size_t last_id = data_->list_count() - 1;
 316   return ReverseIterator(
 317       data_.get(), last_id, data_->InnerListById(last_id)->LastElement(), 0);
 318 }
 319
 320 template <typename BaseElementType>
 321 typename ListContainer<BaseElementType>::ReverseIterator
 322 ListContainer<BaseElementType>::rend() {
 323   return ReverseIterator(data_.get(), 0, NULL, size());
 324 }
 325
 326 template <typename BaseElementType>
 327 typename ListContainer<BaseElementType>::ConstIterator
 328 ListContainer<BaseElementType>::cbegin() const {
 329   if (data_->IsEmpty())
 330     return ConstIterator(data_.get(), 0, NULL, 0);
 331
 332   return ConstIterator(data_.get(), 0, data_->InnerListById(0)->Begin(), 0);
 333 }
 334
 335 template <typename BaseElementType>
 336 typename ListContainer<BaseElementType>::ConstIterator
 337 ListContainer<BaseElementType>::cend() const {
 338   if (data_->IsEmpty())
 339     return ConstIterator(data_.get(), 0, NULL, size());
 340
 341   size_t last_id = data_->list_count() - 1;
 342   return ConstIterator(data_.get(), last_id, NULL, size());
 343 }
 344
 345 template <typename BaseElementType>
 346 typename ListContainer<BaseElementType>::ConstIterator
 347 ListContainer<BaseElementType>::begin() const {
 348   return cbegin();
 349 }
 350
 351 template <typename BaseElementType>
 352 typename ListContainer<BaseElementType>::ConstIterator
 353 ListContainer<BaseElementType>::end() const {
 354   return cend();
 355 }
 356
 357 template <typename BaseElementType>
 358 typename ListContainer<BaseElementType>::Iterator
 359 ListContainer<BaseElementType>::begin() {
 360   if (data_->IsEmpty())
 361     return Iterator(data_.get(), 0, NULL, 0);
 362
 363   return Iterator(data_.get(), 0, data_->InnerListById(0)->Begin(), 0);
 364 }
 365
 366 template <typename BaseElementType>
 367 typename ListContainer<BaseElementType>::Iterator
 368 ListContainer<BaseElementType>::end() {
 369   if (data_->IsEmpty())
 370     return Iterator(data_.get(), 0, NULL, size());
 371
 372   size_t last_id = data_->list_count() - 1;
 373   return Iterator(data_.get(), last_id, NULL, size());
 374 }
 375
 376 template <typename BaseElementType>
 377 BaseElementType* ListContainer<BaseElementType>::front() {
 378   Iterator iter = begin();
 379   return *iter;
 380 }
 381
 382 template <typename BaseElementType>
 383 BaseElementType* ListContainer<BaseElementType>::back() {
 384   ReverseIterator iter = rbegin();
 385   return *iter;
 386 }
 387
 388 template <typename BaseElementType>
 389 const BaseElementType* ListContainer<BaseElementType>::front() const {
 390   ConstIterator iter = begin();
 391   return *iter;
 392 }
 393
 394 template <typename BaseElementType>
 395 const BaseElementType* ListContainer<BaseElementType>::back() const {
 396   ConstReverseIterator iter = rbegin();
 397   return *iter;
 398 }
 399
 400 template <typename BaseElementType>
 401 const BaseElementType* ListContainer<BaseElementType>::ElementAt(
 402     size_t index) const {
 403   DCHECK_LT(index, size());
 404   size_t original_index = index;
 405   size_t list_index;
 406   for (list_index = 0; list_index < data_->list_count(); ++list_index) {
 407     size_t current_size = data_->InnerListById(list_index)->size;
 408     if (index < current_size)
 409       break;
 410     index -= current_size;
 411   }
 412   return *ConstIterator(data_.get(),
 413                         list_index,
 414                         data_->InnerListById(list_index)->ElementAt(index),
 415                         original_index);
 416 }
 417
 418 template <typename BaseElementType>
 419 BaseElementType* ListContainer<BaseElementType>::ElementAt(size_t index) {
 420   DCHECK_LT(index, size());
 421   size_t original_index = index;
 422   size_t list_index;
 423   for (list_index = 0; list_index < data_->list_count(); ++list_index) {
 424     size_t current_size = data_->InnerListById(list_index)->size;
 425     if (index < current_size)
 426       break;
 427     index -= current_size;
 428   }
 429   return *Iterator(data_.get(),
 430                    list_index,
 431                    data_->InnerListById(list_index)->ElementAt(index),
 432                    original_index);
 433 }
 434
 435 template <typename BaseElementType>
 436 BaseElementType* ListContainer<BaseElementType>::Allocate(
 437     size_t size_of_actual_element_in_bytes) {
 438   DCHECK_LE(size_of_actual_element_in_bytes, data_->element_size());
 439   void* result = data_->Allocate();
 440   return static_cast<BaseElementType*>(result);
 441 }
 442
 443 template <typename BaseElementType>
 444 size_t ListContainer<BaseElementType>::size() const {
 445   return data_->size();
 446 }
 447
 448 template <typename BaseElementType>
 449 bool ListContainer<BaseElementType>::empty() const {
 450   return data_->IsEmpty();
 451 }
 452
 453 template <typename BaseElementType>
 454 void ListContainer<BaseElementType>::clear() {
 455   for (Iterator i = begin(); i != end(); ++i) {
 456     i->~BaseElementType();
 457   }
 458   data_->Clear();
 459 }
 460
 461 template <typename BaseElementType>
 462 size_t ListContainer<
 463     BaseElementType>::AvailableSizeWithoutAnotherAllocationForTesting() const {
 464   return data_->NumAvailableElementsInLastList();
 465 }
 466
 467 // ListContainer::Iterator
 468 /////////////////////////////////////////////////
 469 template <typename BaseElementType>
 470 ListContainer<BaseElementType>::Iterator::Iterator(
 471     ListContainerCharAllocator* container,
 472     size_t vector_ind,
 473     char* item_iter,
 474     size_t index)
 475     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 476       index_(index) {
 477 }
 478
 479 template <typename BaseElementType>
 480 ListContainer<BaseElementType>::Iterator::~Iterator() {
 481 }
 482
 483 template <typename BaseElementType>
 484 BaseElementType* ListContainer<BaseElementType>::Iterator::operator->() const {
 485   return reinterpret_cast<BaseElementType*>(this->item_iterator);
 486 }
 487
 488 template <typename BaseElementType>
 489 BaseElementType* ListContainer<BaseElementType>::Iterator::operator*() const {
 490   return reinterpret_cast<BaseElementType*>(this->item_iterator);
 491 }
 492
 493 template <typename BaseElementType>
 494 typename ListContainer<BaseElementType>::Iterator
 495 ListContainer<BaseElementType>::Iterator::
 496 operator++(int unused_post_increment) {
 497   Iterator tmp = *this;
 498   operator++();
 499   return tmp;
 500 }
 501
 502 template <typename BaseElementType>
 503 typename ListContainer<BaseElementType>::Iterator&
 504     ListContainer<BaseElementType>::Iterator::
 505     operator++() {
 506   this->Increment();
 507   ++index_;
 508   return *this;
 509 }
 510
 511 template <typename BaseElementType>
 512 size_t ListContainer<BaseElementType>::Iterator::index() const {
 513   return index_;
 514 }
 515
 516 // ListContainer::ConstIterator
 517 /////////////////////////////////////////////////
 518 template <typename BaseElementType>
 519 ListContainer<BaseElementType>::ConstIterator::ConstIterator(
 520     const typename ListContainer<BaseElementType>::Iterator& other)
 521     : PositionInListContainerCharAllocator(other), index_(other.index()) {
 522 }
 523
 524 template <typename BaseElementType>
 525 ListContainer<BaseElementType>::ConstIterator::ConstIterator(
 526     ListContainerCharAllocator* container,
 527     size_t vector_ind,
 528     char* item_iter,
 529     size_t index)
 530     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 531       index_(index) {
 532 }
 533
 534 template <typename BaseElementType>
 535 ListContainer<BaseElementType>::ConstIterator::~ConstIterator() {
 536 }
 537
 538 template <typename BaseElementType>
 539 const BaseElementType* ListContainer<BaseElementType>::ConstIterator::
 540 operator->() const {
 541   return reinterpret_cast<const BaseElementType*>(this->item_iterator);
 542 }
 543
 544 template <typename BaseElementType>
 545 const BaseElementType* ListContainer<BaseElementType>::ConstIterator::
 546 operator*() const {
 547   return reinterpret_cast<const BaseElementType*>(this->item_iterator);
 548 }
 549
 550 template <typename BaseElementType>
 551 typename ListContainer<BaseElementType>::ConstIterator
 552 ListContainer<BaseElementType>::ConstIterator::
 553 operator++(int unused_post_increment) {
 554   ConstIterator tmp = *this;
 555   operator++();
 556   return tmp;
 557 }
 558
 559 template <typename BaseElementType>
 560 typename ListContainer<BaseElementType>::ConstIterator&
 561     ListContainer<BaseElementType>::ConstIterator::
 562     operator++() {
 563   this->Increment();
 564   ++index_;
 565   return *this;
 566 }
 567
 568 template <typename BaseElementType>
 569 size_t ListContainer<BaseElementType>::ConstIterator::index() const {
 570   return index_;
 571 }
 572
 573 // ListContainer::ReverseIterator
 574 /////////////////////////////////////////////////
 575 template <typename BaseElementType>
 576 ListContainer<BaseElementType>::ReverseIterator::ReverseIterator(
 577     ListContainerCharAllocator* container,
 578     size_t vector_ind,
 579     char* item_iter,
 580     size_t index)
 581     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 582       index_(index) {
 583 }
 584
 585 template <typename BaseElementType>
 586 ListContainer<BaseElementType>::ReverseIterator::~ReverseIterator() {
 587 }
 588
 589 template <typename BaseElementType>
 590 BaseElementType* ListContainer<BaseElementType>::ReverseIterator::operator->()
 591     const {
 592   return reinterpret_cast<BaseElementType*>(this->item_iterator);
 593 }
 594
 595 template <typename BaseElementType>
 596 BaseElementType* ListContainer<BaseElementType>::ReverseIterator::operator*()
 597     const {
 598   return reinterpret_cast<BaseElementType*>(this->item_iterator);
 599 }
 600
 601 template <typename BaseElementType>
 602 typename ListContainer<BaseElementType>::ReverseIterator
 603 ListContainer<BaseElementType>::ReverseIterator::
 604 operator++(int unused_post_increment) {
 605   ReverseIterator tmp = *this;
 606   operator++();
 607   return tmp;
 608 }
 609
 610 template <typename BaseElementType>
 611 typename ListContainer<BaseElementType>::ReverseIterator&
 612     ListContainer<BaseElementType>::ReverseIterator::
 613     operator++() {
 614   this->ReverseIncrement();
 615   ++index_;
 616   return *this;
 617 }
 618
 619 template <typename BaseElementType>
 620 size_t ListContainer<BaseElementType>::ReverseIterator::index() const {
 621   return index_;
 622 }
 623
 624 // ListContainer::ConstReverseIterator
 625 /////////////////////////////////////////////////
 626 template <typename BaseElementType>
 627 ListContainer<BaseElementType>::ConstReverseIterator::ConstReverseIterator(
 628     const typename ListContainer<BaseElementType>::ReverseIterator& other)
 629     : PositionInListContainerCharAllocator(other), index_(other.index()) {
 630 }
 631
 632 template <typename BaseElementType>
 633 ListContainer<BaseElementType>::ConstReverseIterator::ConstReverseIterator(
 634     ListContainerCharAllocator* container,
 635     size_t vector_ind,
 636     char* item_iter,
 637     size_t index)
 638     : PositionInListContainerCharAllocator(container, vector_ind, item_iter),
 639       index_(index) {
 640 }
 641
 642 template <typename BaseElementType>
 643 ListContainer<BaseElementType>::ConstReverseIterator::~ConstReverseIterator() {
 644 }
 645
 646 template <typename BaseElementType>
 647 const BaseElementType* ListContainer<BaseElementType>::ConstReverseIterator::
 648 operator->() const {
 649   return reinterpret_cast<const BaseElementType*>(this->item_iterator);
 650 }
 651
 652 template <typename BaseElementType>
 653 const BaseElementType* ListContainer<BaseElementType>::ConstReverseIterator::
 654 operator*() const {
 655   return reinterpret_cast<const BaseElementType*>(this->item_iterator);
 656 }
 657
 658 template <typename BaseElementType>
 659 typename ListContainer<BaseElementType>::ConstReverseIterator
 660 ListContainer<BaseElementType>::ConstReverseIterator::
 661 operator++(int unused_post_increment) {
 662   ConstReverseIterator tmp = *this;
 663   operator++();
 664   return tmp;
 665 }
 666
 667 template <typename BaseElementType>
 668 typename ListContainer<BaseElementType>::ConstReverseIterator&
 669     ListContainer<BaseElementType>::ConstReverseIterator::
 670     operator++() {
 671   this->ReverseIncrement();
 672   ++index_;
 673   return *this;
 674 }
 675
 676 template <typename BaseElementType>
 677 size_t ListContainer<BaseElementType>::ConstReverseIterator::index() const {
 678   return index_;
 679 }
 680
 681 template class ListContainer<SharedQuadState>;
 682 template class ListContainer<DrawQuad>;
 683
 684 }  // namespace cc