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