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
12namespace cc {
13class SharedQuadState;
14class 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// kLargestDrawQuad while BaseElementType is DrawQuad.
24template <class BaseElementType>
25class 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 a single
37  // allocation is needed.
38  ListContainer(size_t max_size_for_derived_class,
39                size_t num_of_elements_to_reserve_for);
40
41  ~ListContainer();
42
43  // This class deals only with char* and void*. It does allocation and passing
44  // out raw pointers, as well as memory deallocation when being destroyed.
45  class CC_EXPORT ListContainerCharAllocator;
46
47  // This class points to a certain position inside memory of
48  // ListContainerCharAllocator. It is a base class for ListContainer iterators.
49  struct CC_EXPORT PositionInListContainerCharAllocator {
50    ListContainerCharAllocator* ptr_to_container;
51    size_t vector_index;
52    char* item_iterator;
53
54    PositionInListContainerCharAllocator(
55        const PositionInListContainerCharAllocator& other);
56
57    PositionInListContainerCharAllocator(ListContainerCharAllocator* container,
58                                         size_t vector_ind,
59                                         char* item_iter);
60
61    bool operator==(const PositionInListContainerCharAllocator& other) const;
62    bool operator!=(const PositionInListContainerCharAllocator& other) const;
63
64    PositionInListContainerCharAllocator Increment();
65    PositionInListContainerCharAllocator ReverseIncrement();
66  };
67
68  // Iterator classes that can be used to access data.
69  /////////////////////////////////////////////////////////////////
70  class CC_EXPORT Iterator : public PositionInListContainerCharAllocator {
71    // This class is only defined to forward iterate through
72    // ListContainerCharAllocator.
73   public:
74    Iterator(ListContainerCharAllocator* container,
75             size_t vector_ind,
76             char* item_iter);
77    ~Iterator();
78    BaseElementType* operator->() const;
79    BaseElementType& operator*() const;
80    Iterator operator++(int unused_post_increment);
81    Iterator operator++();
82  };
83
84  class CC_EXPORT ConstIterator : public PositionInListContainerCharAllocator {
85    // This class is only defined to forward iterate through
86    // ListContainerCharAllocator.
87   public:
88    ConstIterator(ListContainerCharAllocator* container,
89                  size_t vector_ind,
90                  char* item_iter);
91    ConstIterator(const Iterator& other);  // NOLINT
92    ~ConstIterator();
93    const BaseElementType* operator->() const;
94    const BaseElementType& operator*() const;
95    ConstIterator operator++(int unused_post_increment);
96    ConstIterator operator++();
97  };
98
99  class CC_EXPORT ReverseIterator
100      : public PositionInListContainerCharAllocator {
101    // This class is only defined to reverse iterate through
102    // ListContainerCharAllocator.
103   public:
104    ReverseIterator(ListContainerCharAllocator* container,
105                    size_t vector_ind,
106                    char* item_iter);
107    ~ReverseIterator();
108    BaseElementType* operator->() const;
109    BaseElementType& operator*() const;
110    ReverseIterator operator++(int unused_post_increment);
111    ReverseIterator operator++();
112  };
113
114  class CC_EXPORT ConstReverseIterator
115      : public PositionInListContainerCharAllocator {
116    // This class is only defined to reverse iterate through
117    // ListContainerCharAllocator.
118   public:
119    ConstReverseIterator(ListContainerCharAllocator* container,
120                         size_t vector_ind,
121                         char* item_iter);
122    ConstReverseIterator(const ReverseIterator& other);  // NOLINT
123    ~ConstReverseIterator();
124    const BaseElementType* operator->() const;
125    const BaseElementType& operator*() const;
126    ConstReverseIterator operator++(int unused_post_increment);
127    ConstReverseIterator operator++();
128  };
129
130  // When called, all raw pointers that have been handed out are no longer
131  // valid. Use with caution.
132  // This function does not deallocate memory.
133  void EraseAndInvalidateAllPointers(Iterator position);
134
135  ConstReverseIterator rbegin() const;
136  ConstReverseIterator rend() const;
137  ReverseIterator rbegin();
138  ReverseIterator rend();
139  ConstIterator begin() const;
140  ConstIterator end() const;
141  Iterator begin();
142  Iterator end();
143
144  BaseElementType* front();
145  BaseElementType* back();
146  const BaseElementType* front() const;
147  const BaseElementType* back() const;
148
149  BaseElementType* ElementAt(size_t index);
150  const BaseElementType* ElementAt(size_t index) const;
151
152  // Take in derived element type and construct it at location generated by
153  // Allocate().
154  template <typename DerivedElementType>
155  DerivedElementType* AllocateAndConstruct() {
156    return new (Allocate(sizeof(DerivedElementType))) DerivedElementType;
157  }
158  // Take in derived element type and copy construct it at location generated by
159  // Allocate().
160  template <typename DerivedElementType>
161  DerivedElementType* AllocateAndCopyFrom(const DerivedElementType* source) {
162    return new (Allocate(sizeof(DerivedElementType)))
163        DerivedElementType(*source);
164  }
165
166  size_t size() const;
167  bool empty() const;
168  void clear();
169
170  size_t AvailableSizeWithoutAnotherAllocationForTesting() const;
171
172 private:
173  // Hands out memory location for an element at the end of data structure.
174  BaseElementType* Allocate(size_t size_of_actual_element_in_bytes);
175
176  scoped_ptr<ListContainerCharAllocator> data_;
177
178  DISALLOW_COPY_AND_ASSIGN(ListContainer);
179};
180
181#if !defined(COMPILER_MSVC)
182extern template class ListContainer<SharedQuadState>;
183extern template class ListContainer<DrawQuad>;
184#endif
185}  // namespace cc
186
187#endif  // CC_QUADS_LIST_CONTAINER_H_
188