cc/base/list_container.h

   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 #ifndef CC_BASE_LIST_CONTAINER_H_
   6 #define CC_BASE_LIST_CONTAINER_H_
   7
   8 #include "base/logging.h"
   9 #include "base/macros.h"
  10 #include "base/memory/scoped_ptr.h"
  11 #include "cc/base/cc_export.h"
  12 #include "cc/base/list_container_helper.h"
  13
  14 namespace cc {
  15
  16 // ListContainer is a container type that handles allocating contiguous memory
  17 // for new elements and traversing through elements with either iterator or
  18 // reverse iterator. Since this container hands out raw pointers of its
  19 // elements, it is very important that this container never reallocate its
  20 // memory so those raw pointer will continue to be valid.  This class is used to
  21 // contain SharedQuadState or DrawQuad. Since the size of each DrawQuad varies,
  22 // to hold DrawQuads, the allocations size of each element in this class is
  23 // LargestDrawQuadSize while BaseElementType is DrawQuad.
  24 template <class BaseElementType>
  25 class ListContainer {
  26  public:
  27   // BaseElementType is the type of raw pointers this class hands out; however,
  28   // its derived classes might require different memory sizes.
  29   // max_size_for_derived_class the largest memory size required for all the
  30   // derived classes to use for allocation.
  31   explicit ListContainer(size_t max_size_for_derived_class)
  32       : helper_(max_size_for_derived_class) {}
  33
  34   // This constructor omits input variable for max_size_for_derived_class. This
  35   // is used when there is no derived classes from BaseElementType we need to
  36   // worry about, and allocation size is just sizeof(BaseElementType).
  37   ListContainer() : helper_(sizeof(BaseElementType)) {}
  38
  39   // This constructor reserves the requested memory up front so only single
  40   // allocation is needed. When num_of_elements_to_reserve_for is zero, use the
  41   // default size.
  42   ListContainer(size_t max_size_for_derived_class,
  43                 size_t num_of_elements_to_reserve_for)
  44       : helper_(max_size_for_derived_class, num_of_elements_to_reserve_for) {}
  45
  46   ~ListContainer() {
  47     for (Iterator i = begin(); i != end(); ++i) {
  48       i->~BaseElementType();
  49     }
  50   }
  51
  52   class Iterator;
  53   class ConstIterator;
  54   class ReverseIterator;
  55   class ConstReverseIterator;
  56
  57   // Removes the last element of the list and makes its space available for
  58   // allocation.
  59   void RemoveLast() {
  60     DCHECK(!empty());
  61     back()->~BaseElementType();
  62     helper_.RemoveLast();
  63   }
  64
  65   // When called, all raw pointers that have been handed out are no longer
  66   // valid. Use with caution.
  67   // Returns a valid Iterator pointing to the element after the erased element.
  68   // This function does not deallocate memory.
  69   Iterator EraseAndInvalidateAllPointers(Iterator position) {
  70     BaseElementType* item = *position;
  71     item->~BaseElementType();
  72     helper_.EraseAndInvalidateAllPointers(&position);
  73     return empty() ? end() : position;
  74   }
  75
  76   ConstReverseIterator crbegin() const {
  77     return ConstReverseIterator(helper_.crbegin());
  78   }
  79   ConstReverseIterator crend() const {
  80     return ConstReverseIterator(helper_.crend());
  81   }
  82   ConstReverseIterator rbegin() const { return crbegin(); }
  83   ConstReverseIterator rend() const { return crend(); }
  84   ReverseIterator rbegin() { return ReverseIterator(helper_.rbegin()); }
  85   ReverseIterator rend() { return ReverseIterator(helper_.rend()); }
  86   ConstIterator cbegin() const { return ConstIterator(helper_.cbegin()); }
  87   ConstIterator cend() const { return ConstIterator(helper_.cend()); }
  88   ConstIterator begin() const { return cbegin(); }
  89   ConstIterator end() const { return cend(); }
  90   Iterator begin() { return Iterator(helper_.begin()); }
  91   Iterator end() { return Iterator(helper_.end()); }
  92
  93   // TODO(weiliangc): front(), back() and ElementAt() function should return
  94   // reference, consistent with container-of-object.
  95   BaseElementType* front() { return *begin(); }
  96   BaseElementType* back() { return *rbegin(); }
  97   const BaseElementType* front() const { return *begin(); }
  98   const BaseElementType* back() const { return *rbegin(); }
  99
 100   BaseElementType* ElementAt(size_t index) {
 101     return *Iterator(helper_.IteratorAt(index));
 102   }
 103   const BaseElementType* ElementAt(size_t index) const {
 104     return *ConstIterator(helper_.IteratorAt(index));
 105   }
 106
 107   // Take in derived element type and construct it at location generated by
 108   // Allocate().
 109   template <typename DerivedElementType>
 110   DerivedElementType* AllocateAndConstruct() {
 111     return new (helper_.Allocate(sizeof(DerivedElementType)))
 112         DerivedElementType;
 113   }
 114
 115   // Take in derived element type and copy construct it at location generated by
 116   // Allocate().
 117   template <typename DerivedElementType>
 118   DerivedElementType* AllocateAndCopyFrom(const DerivedElementType* source) {
 119     return new (helper_.Allocate(sizeof(DerivedElementType)))
 120         DerivedElementType(*source);
 121   }
 122
 123   // Construct a new element on top of an existing one.
 124   template <typename DerivedElementType>
 125   DerivedElementType* ReplaceExistingElement(Iterator at) {
 126     at->~BaseElementType();
 127     return new (at.item_iterator) DerivedElementType();
 128   }
 129
 130   // Insert |count| new elements of |DerivedElementType| before |at|. This will
 131   // invalidate all outstanding pointers and iterators. Return a valid iterator
 132   // for the beginning of the newly inserted segment.
 133   template <typename DerivedElementType>
 134   Iterator InsertBeforeAndInvalidateAllPointers(Iterator at, size_t count) {
 135     helper_.InsertBeforeAndInvalidateAllPointers(&at, count);
 136     Iterator result = at;
 137     for (size_t i = 0; i < count; ++i) {
 138       new (at.item_iterator) DerivedElementType();
 139       ++at;
 140     }
 141     return result;
 142   }
 143
 144   template <typename DerivedElementType>
 145   void swap(ListContainer<DerivedElementType>& other) {
 146     helper_.data_.swap(other.helper_.data_);
 147   }
 148
 149   // Appends a new item without copying. The original item will not be
 150   // destructed and will be replaced with a new DerivedElementType. The
 151   // DerivedElementType does not have to match the moved type as a full block
 152   // of memory will be moved (up to MaxSizeForDerivedClass()). A pointer to
 153   // the moved element is returned.
 154   template <typename DerivedElementType>
 155   DerivedElementType* AppendByMoving(DerivedElementType* item) {
 156     size_t max_size_for_derived_class = helper_.MaxSizeForDerivedClass();
 157     void* new_item = helper_.Allocate(max_size_for_derived_class);
 158     memcpy(new_item, static_cast<void*>(item), max_size_for_derived_class);
 159     // Construct a new element in-place so it can be destructed safely.
 160     new (item) DerivedElementType;
 161     return static_cast<DerivedElementType*>(new_item);
 162   }
 163
 164   size_t size() const { return helper_.size(); }
 165   bool empty() const { return helper_.empty(); }
 166   size_t GetCapacityInBytes() const { return helper_.GetCapacityInBytes(); }
 167
 168   void clear() {
 169     for (Iterator i = begin(); i != end(); ++i) {
 170       i->~BaseElementType();
 171     }
 172     helper_.clear();
 173   }
 174
 175   size_t AvailableSizeWithoutAnotherAllocationForTesting() const {
 176     return helper_.AvailableSizeWithoutAnotherAllocationForTesting();
 177   }
 178
 179   // Iterator classes that can be used to access data.
 180   /////////////////////////////////////////////////////////////////
 181   class Iterator : public ListContainerHelper::Iterator {
 182     // This class is only defined to forward iterate through
 183     // CharAllocator.
 184    public:
 185     Iterator(ListContainerHelper::CharAllocator* container,
 186              size_t vector_ind,
 187              char* item_iter,
 188              size_t index)
 189         : ListContainerHelper::Iterator(container,
 190                                         vector_ind,
 191                                         item_iter,
 192                                         index) {}
 193     BaseElementType* operator->() const {
 194       return reinterpret_cast<BaseElementType*>(item_iterator);
 195     }
 196     BaseElementType* operator*() const {
 197       return reinterpret_cast<BaseElementType*>(item_iterator);
 198     }
 199     Iterator operator++(int unused_post_increment) {
 200       Iterator tmp = *this;
 201       operator++();
 202       return tmp;
 203     }
 204     Iterator& operator++() {
 205       Increment();
 206       ++index_;
 207       return *this;
 208     }
 209
 210    private:
 211     explicit Iterator(const ListContainerHelper::Iterator& base_iterator)
 212         : ListContainerHelper::Iterator(base_iterator) {}
 213     friend Iterator ListContainer<BaseElementType>::begin();
 214     friend Iterator ListContainer<BaseElementType>::end();
 215     friend BaseElementType* ListContainer<BaseElementType>::ElementAt(
 216         size_t index);
 217   };
 218
 219   class ConstIterator : public ListContainerHelper::ConstIterator {
 220     // This class is only defined to forward iterate through
 221     // CharAllocator.
 222    public:
 223     ConstIterator(ListContainerHelper::CharAllocator* container,
 224                   size_t vector_ind,
 225                   char* item_iter,
 226                   size_t index)
 227         : ListContainerHelper::ConstIterator(container,
 228                                              vector_ind,
 229                                              item_iter,
 230                                              index) {}
 231     ConstIterator(const Iterator& other)  // NOLINT
 232         : ListContainerHelper::ConstIterator(other) {}
 233     const BaseElementType* operator->() const {
 234       return reinterpret_cast<const BaseElementType*>(item_iterator);
 235     }
 236     const BaseElementType* operator*() const {
 237       return reinterpret_cast<const BaseElementType*>(item_iterator);
 238     }
 239     ConstIterator operator++(int unused_post_increment) {
 240       ConstIterator tmp = *this;
 241       operator++();
 242       return tmp;
 243     }
 244     ConstIterator& operator++() {
 245       Increment();
 246       ++index_;
 247       return *this;
 248     }
 249
 250    private:
 251     explicit ConstIterator(
 252         const ListContainerHelper::ConstIterator& base_iterator)
 253         : ListContainerHelper::ConstIterator(base_iterator) {}
 254     friend ConstIterator ListContainer<BaseElementType>::cbegin() const;
 255     friend ConstIterator ListContainer<BaseElementType>::cend() const;
 256     friend const BaseElementType* ListContainer<BaseElementType>::ElementAt(
 257         size_t index) const;
 258   };
 259
 260   class ReverseIterator : public ListContainerHelper::ReverseIterator {
 261     // This class is only defined to reverse iterate through
 262     // CharAllocator.
 263    public:
 264     ReverseIterator(ListContainerHelper::CharAllocator* container,
 265                     size_t vector_ind,
 266                     char* item_iter,
 267                     size_t index)
 268         : ListContainerHelper::ReverseIterator(container,
 269                                                vector_ind,
 270                                                item_iter,
 271                                                index) {}
 272     BaseElementType* operator->() const {
 273       return reinterpret_cast<BaseElementType*>(item_iterator);
 274     }
 275     BaseElementType* operator*() const {
 276       return reinterpret_cast<BaseElementType*>(item_iterator);
 277     }
 278     ReverseIterator operator++(int unused_post_increment) {
 279       ReverseIterator tmp = *this;
 280       operator++();
 281       return tmp;
 282     }
 283     ReverseIterator& operator++() {
 284       ReverseIncrement();
 285       ++index_;
 286       return *this;
 287     }
 288
 289    private:
 290     explicit ReverseIterator(ListContainerHelper::ReverseIterator base_iterator)
 291         : ListContainerHelper::ReverseIterator(base_iterator) {}
 292     friend ReverseIterator ListContainer<BaseElementType>::rbegin();
 293     friend ReverseIterator ListContainer<BaseElementType>::rend();
 294   };
 295
 296   class ConstReverseIterator
 297       : public ListContainerHelper::ConstReverseIterator {
 298     // This class is only defined to reverse iterate through
 299     // CharAllocator.
 300    public:
 301     ConstReverseIterator(ListContainerHelper::CharAllocator* container,
 302                          size_t vector_ind,
 303                          char* item_iter,
 304                          size_t index)
 305         : ListContainerHelper::ConstReverseIterator(container,
 306                                                     vector_ind,
 307                                                     item_iter,
 308                                                     index) {}
 309     ConstReverseIterator(const ReverseIterator& other)  // NOLINT
 310         : ListContainerHelper::ConstReverseIterator(other) {}
 311     const BaseElementType* operator->() const {
 312       return reinterpret_cast<const BaseElementType*>(item_iterator);
 313     }
 314     const BaseElementType* operator*() const {
 315       return reinterpret_cast<const BaseElementType*>(item_iterator);
 316     }
 317     ConstReverseIterator operator++(int unused_post_increment) {
 318       ConstReverseIterator tmp = *this;
 319       operator++();
 320       return tmp;
 321     }
 322     ConstReverseIterator& operator++() {
 323       ReverseIncrement();
 324       ++index_;
 325       return *this;
 326     }
 327
 328    private:
 329     explicit ConstReverseIterator(
 330         ListContainerHelper::ConstReverseIterator base_iterator)
 331         : ListContainerHelper::ConstReverseIterator(base_iterator) {}
 332     friend ConstReverseIterator ListContainer<BaseElementType>::crbegin() const;
 333     friend ConstReverseIterator ListContainer<BaseElementType>::crend() const;
 334   };
 335
 336  private:
 337   ListContainerHelper helper_;
 338
 339   DISALLOW_COPY_AND_ASSIGN(ListContainer);
 340 };
 341
 342 }  // namespace cc
 343
 344 #endif  // CC_BASE_LIST_CONTAINER_H_