cc/quads/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_QUADS_LIST_CONTAINER_H_
   6 #define CC_QUADS_LIST_CONTAINER_H_
   7
   8 #include "base/macros.h"
   9 #include "base/memory/scoped_ptr.h"
  10 #include "cc/base/cc_export.h"
  11
  12 namespace cc {
  13 class SharedQuadState;
  14 class DrawQuad;
  15
  16 // This class is a container type that handles allocating contiguous memory for
  17 // new elements and traversing through elements with either iterator or reverse
  18 // iterator. Since this container hands out raw pointers of its elements, it is
  19 // very important that this container never reallocate its memory so those raw
  20 // pointer will continue to be valid.  This class is used to contain
  21 // SharedQuadState or DrawQuad. Since the size of each DrawQuad varies, to hold
  22 // DrawQuads, the allocations size of each element in this class is
  23 // LargestDrawQuadSize while BaseElementType is DrawQuad.
  24 template <class BaseElementType>
  25 class CC_EXPORT 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   // This constructor omits input variable for max_size_for_derived_class. This
  33   // is used when there is no derived classes from BaseElementType we need to
  34   // worry about, and allocation size is just sizeof(BaseElementType).
  35   ListContainer();
  36   // This constructor reserves the requested memory up front so only single
  37   // allocation is needed. When num_of_elements_to_reserve_for is zero, use the
  38   // default size.
  39   ListContainer(size_t max_size_for_derived_class,
  40                 size_t num_of_elements_to_reserve_for);
  41
  42   ~ListContainer();
  43
  44   // This class deals only with char* and void*. It does allocation and passing
  45   // out raw pointers, as well as memory deallocation when being destroyed.
  46   class CC_EXPORT ListContainerCharAllocator;
  47
  48   // This class points to a certain position inside memory of
  49   // ListContainerCharAllocator. It is a base class for ListContainer iterators.
  50   struct CC_EXPORT PositionInListContainerCharAllocator {
  51     ListContainerCharAllocator* ptr_to_container;
  52     size_t vector_index;
  53     char* item_iterator;
  54
  55     PositionInListContainerCharAllocator(
  56         const PositionInListContainerCharAllocator& other);
  57
  58     PositionInListContainerCharAllocator(ListContainerCharAllocator* container,
  59                                          size_t vector_ind,
  60                                          char* item_iter);
  61
  62     bool operator==(const PositionInListContainerCharAllocator& other) const;
  63     bool operator!=(const PositionInListContainerCharAllocator& other) const;
  64
  65     PositionInListContainerCharAllocator Increment();
  66     PositionInListContainerCharAllocator ReverseIncrement();
  67   };
  68
  69   // Iterator classes that can be used to access data.
  70   /////////////////////////////////////////////////////////////////
  71   class CC_EXPORT Iterator : public PositionInListContainerCharAllocator {
  72     // This class is only defined to forward iterate through
  73     // ListContainerCharAllocator.
  74    public:
  75     Iterator(ListContainerCharAllocator* container,
  76              size_t vector_ind,
  77              char* item_iter,
  78              size_t index);
  79     ~Iterator();
  80     BaseElementType* operator->() const;
  81     BaseElementType* operator*() const;
  82     Iterator operator++(int unused_post_increment);
  83     Iterator& operator++();
  84
  85     size_t index() const;
  86
  87    private:
  88     // This is used to track how many increment has happened since begin(). It
  89     // is used to avoid double increment at places an index reference is
  90     // needed. For iterator this means begin() corresponds to index 0 and end()
  91     // corresponds to index |size|.
  92     size_t index_;
  93   };
  94
  95   class CC_EXPORT ConstIterator : public PositionInListContainerCharAllocator {
  96     // This class is only defined to forward iterate through
  97     // ListContainerCharAllocator.
  98    public:
  99     ConstIterator(ListContainerCharAllocator* container,
 100                   size_t vector_ind,
 101                   char* item_iter,
 102                   size_t index);
 103     ConstIterator(const Iterator& other);  // NOLINT
 104     ~ConstIterator();
 105     const BaseElementType* operator->() const;
 106     const BaseElementType* operator*() const;
 107     ConstIterator operator++(int unused_post_increment);
 108     ConstIterator& operator++();
 109
 110     size_t index() const;
 111
 112    private:
 113     // This is used to track how many increment has happened since begin(). It
 114     // is used to avoid double increment at places an index reference is
 115     // needed. For iterator this means begin() corresponds to index 0 and end()
 116     // corresponds to index |size|.
 117     size_t index_;
 118   };
 119
 120   class CC_EXPORT ReverseIterator
 121       : public PositionInListContainerCharAllocator {
 122     // This class is only defined to reverse iterate through
 123     // ListContainerCharAllocator.
 124    public:
 125     ReverseIterator(ListContainerCharAllocator* container,
 126                     size_t vector_ind,
 127                     char* item_iter,
 128                     size_t index);
 129     ~ReverseIterator();
 130     BaseElementType* operator->() const;
 131     BaseElementType* operator*() const;
 132     ReverseIterator operator++(int unused_post_increment);
 133     ReverseIterator& operator++();
 134
 135     size_t index() const;
 136
 137    private:
 138     // This is used to track how many increment has happened since rbegin(). It
 139     // is used to avoid double increment at places an index reference is
 140     // needed. For reverse iterator this means rbegin() corresponds to index 0
 141     // and rend() corresponds to index |size|.
 142     size_t index_;
 143   };
 144
 145   class CC_EXPORT ConstReverseIterator
 146       : public PositionInListContainerCharAllocator {
 147     // This class is only defined to reverse iterate through
 148     // ListContainerCharAllocator.
 149    public:
 150     ConstReverseIterator(ListContainerCharAllocator* container,
 151                          size_t vector_ind,
 152                          char* item_iter,
 153                          size_t index);
 154     ConstReverseIterator(const ReverseIterator& other);  // NOLINT
 155     ~ConstReverseIterator();
 156     const BaseElementType* operator->() const;
 157     const BaseElementType* operator*() const;
 158     ConstReverseIterator operator++(int unused_post_increment);
 159     ConstReverseIterator& operator++();
 160
 161     size_t index() const;
 162
 163    private:
 164     // This is used to track how many increment has happened since rbegin(). It
 165     // is used to avoid double increment at places an index reference is
 166     // needed. For reverse iterator this means rbegin() corresponds to index 0
 167     // and rend() corresponds to index |size|.
 168     size_t index_;
 169   };
 170
 171   // When called, all raw pointers that have been handed out are no longer
 172   // valid. Use with caution.
 173   // This function does not deallocate memory.
 174   void EraseAndInvalidateAllPointers(Iterator position);
 175
 176   ConstReverseIterator crbegin() const;
 177   ConstReverseIterator crend() const;
 178   ConstReverseIterator rbegin() const;
 179   ConstReverseIterator rend() const;
 180   ReverseIterator rbegin();
 181   ReverseIterator rend();
 182   ConstIterator cbegin() const;
 183   ConstIterator cend() const;
 184   ConstIterator begin() const;
 185   ConstIterator end() const;
 186   Iterator begin();
 187   Iterator end();
 188
 189   // TODO(weiliangc): front(), back() and ElementAt() function should return
 190   // reference, consistent with container-of-object.
 191   BaseElementType* front();
 192   BaseElementType* back();
 193   const BaseElementType* front() const;
 194   const BaseElementType* back() const;
 195
 196   BaseElementType* ElementAt(size_t index);
 197   const BaseElementType* ElementAt(size_t index) const;
 198
 199   // Take in derived element type and construct it at location generated by
 200   // Allocate().
 201   template <typename DerivedElementType>
 202   DerivedElementType* AllocateAndConstruct() {
 203     return new (Allocate(sizeof(DerivedElementType))) DerivedElementType;
 204   }
 205   // Take in derived element type and copy construct it at location generated by
 206   // Allocate().
 207   template <typename DerivedElementType>
 208   DerivedElementType* AllocateAndCopyFrom(const DerivedElementType* source) {
 209     return new (Allocate(sizeof(DerivedElementType)))
 210         DerivedElementType(*source);
 211   }
 212   // Construct a new element on top of an existing one.
 213   template <typename DerivedElementType>
 214   DerivedElementType* ReplaceExistingElement(Iterator at) {
 215     at->~BaseElementType();
 216     return new (*at) DerivedElementType();
 217   }
 218
 219   size_t size() const;
 220   bool empty() const;
 221   void clear();
 222
 223   size_t AvailableSizeWithoutAnotherAllocationForTesting() const;
 224
 225  private:
 226   // Hands out memory location for an element at the end of data structure.
 227   void* Allocate(size_t size_of_actual_element_in_bytes);
 228
 229   scoped_ptr<ListContainerCharAllocator> data_;
 230
 231   DISALLOW_COPY_AND_ASSIGN(ListContainer);
 232 };
 233
 234 #if !defined(COMPILER_MSVC)
 235 extern template class ListContainer<SharedQuadState>;
 236 extern template class ListContainer<DrawQuad>;
 237 #endif
 238 }  // namespace cc
 239
 240 #endif  // CC_QUADS_LIST_CONTAINER_H_