1 // Copyright 2015 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 THIRD_PARTY_BLINK_RENDERER_PLATFORM_GRAPHICS_CONTIGUOUS_CONTAINER_H_ 6 #define THIRD_PARTY_BLINK_RENDERER_PLATFORM_GRAPHICS_CONTIGUOUS_CONTAINER_H_ 7 8 #include <cstddef> 9 #include <iterator> 10 #include <memory> 11 #include <utility> 12 13 #include "base/compiler_specific.h" 14 #include "base/macros.h" 15 #include "third_party/blink/renderer/platform/platform_export.h" 16 #include "third_party/blink/renderer/platform/wtf/allocator/allocator.h" 17 #include "third_party/blink/renderer/platform/wtf/type_traits.h" 18 #include "third_party/blink/renderer/platform/wtf/vector.h" 19 20 namespace blink { 21 22 // ContiguousContainer is a container which stores a list of heterogeneous 23 // objects (in particular, of varying sizes), packed next to one another in 24 // memory. Objects are never relocated, so it is safe to store pointers to them 25 // for the lifetime of the container (unless the object is removed). 26 // 27 // Memory is allocated in a series of buffers (with exponential growth). When an 28 // object is allocated, it is given only the space it requires (possibly with 29 // enough padding to preserve alignment), rather than the maximum possible size. 30 // This allows small and large objects to coexist without wasting much space. 31 // 32 // Since it stores pointers to all of the objects it allocates in a vector, it 33 // supports efficient iteration and indexing. However, for mutation the 34 // supported operations are limited to appending to, and removing from, the end 35 // of the list. 36 // 37 // Clients should instantiate ContiguousContainer; ContiguousContainerBase is an 38 // artifact of the implementation. 39 40 class PLATFORM_EXPORT ContiguousContainerBase { 41 DISALLOW_NEW(); 42 43 protected: 44 explicit ContiguousContainerBase(wtf_size_t max_object_size); 45 ContiguousContainerBase(ContiguousContainerBase&&); 46 ~ContiguousContainerBase(); 47 48 ContiguousContainerBase& operator=(ContiguousContainerBase&&); 49 size()50 wtf_size_t size() const { return elements_.size(); } IsEmpty()51 bool IsEmpty() const { return !size(); } 52 wtf_size_t CapacityInBytes() const; 53 wtf_size_t UsedCapacityInBytes() const; 54 wtf_size_t MemoryUsageInBytes() const; 55 56 // These do not invoke constructors or destructors. 57 void ReserveInitialCapacity(wtf_size_t, const char* type_name); 58 void* Allocate(wtf_size_t object_size, const char* type_name); 59 void RemoveLast(); 60 void Clear(); 61 void Swap(ContiguousContainerBase&); 62 63 // Discards excess buffer capacity. Intended for use when no more appending 64 // is anticipated. 65 void ShrinkToFit(); 66 67 Vector<void*> elements_; 68 69 private: 70 class Buffer; 71 72 Buffer* AllocateNewBufferForNextAllocation(wtf_size_t, const char* type_name); 73 74 Vector<std::unique_ptr<Buffer>> buffers_; 75 unsigned end_index_; 76 wtf_size_t max_object_size_; 77 78 DISALLOW_COPY_AND_ASSIGN(ContiguousContainerBase); 79 }; 80 81 // For most cases, no alignment stricter than pointer alignment is required. If 82 // one of the derived classes has stronger alignment requirements (and the 83 // static_assert fires), set alignment to the LCM of the derived class 84 // alignments. For small structs without pointers, it may be possible to reduce 85 // alignment for tighter packing. 86 87 template <class BaseElementType, unsigned alignment = sizeof(void*)> 88 class ContiguousContainer : public ContiguousContainerBase { 89 private: 90 // Declares itself as a forward iterator, but also supports a few more 91 // things. The whole random access iterator interface is a bit much. 92 template <typename BaseIterator, typename ValueType> 93 class IteratorWrapper 94 : public std::iterator<std::forward_iterator_tag, ValueType> { 95 DISALLOW_NEW(); 96 97 public: 98 IteratorWrapper() = default; 99 bool operator==(const IteratorWrapper& other) const { 100 return it_ == other.it_; 101 } 102 bool operator!=(const IteratorWrapper& other) const { 103 return it_ != other.it_; 104 } 105 ValueType& operator*() const { return *static_cast<ValueType*>(*it_); } 106 ValueType* operator->() const { return &operator*(); } 107 IteratorWrapper operator+(std::ptrdiff_t n) const { 108 return IteratorWrapper(it_ + n); 109 } 110 IteratorWrapper operator++(int) { 111 IteratorWrapper tmp = *this; 112 ++it_; 113 return tmp; 114 } 115 std::ptrdiff_t operator-(const IteratorWrapper& other) const { 116 return it_ - other.it_; 117 } 118 IteratorWrapper& operator++() { 119 ++it_; 120 return *this; 121 } 122 123 private: IteratorWrapper(const BaseIterator & it)124 explicit IteratorWrapper(const BaseIterator& it) : it_(it) {} 125 BaseIterator it_; 126 friend class ContiguousContainer; 127 }; 128 129 public: 130 using iterator = IteratorWrapper<Vector<void*>::iterator, BaseElementType>; 131 using const_iterator = 132 IteratorWrapper<Vector<void*>::const_iterator, const BaseElementType>; 133 using reverse_iterator = 134 IteratorWrapper<Vector<void*>::reverse_iterator, BaseElementType>; 135 using const_reverse_iterator = 136 IteratorWrapper<Vector<void*>::const_reverse_iterator, 137 const BaseElementType>; 138 139 using value_type = BaseElementType; 140 ContiguousContainer(wtf_size_t max_object_size)141 explicit ContiguousContainer(wtf_size_t max_object_size) 142 : ContiguousContainerBase(Align(max_object_size)) {} 143 ContiguousContainer(wtf_size_t max_object_size,wtf_size_t initial_size_bytes)144 ContiguousContainer(wtf_size_t max_object_size, wtf_size_t initial_size_bytes) 145 : ContiguousContainer(max_object_size) { 146 ReserveInitialCapacity(std::max(max_object_size, initial_size_bytes), 147 WTF_HEAP_PROFILER_TYPE_NAME(BaseElementType)); 148 } 149 ContiguousContainer(ContiguousContainer && source)150 ContiguousContainer(ContiguousContainer&& source) 151 : ContiguousContainerBase(std::move(source)) {} 152 ~ContiguousContainer()153 ~ContiguousContainer() { 154 for (auto& element : *this) { 155 (void)element; // MSVC incorrectly reports this variable as unused. 156 element.~BaseElementType(); 157 } 158 } 159 160 ContiguousContainer& operator=(ContiguousContainer&& source) { 161 // Must clear in the derived class to ensure that element destructors 162 // care called. 163 Clear(); 164 165 ContiguousContainerBase::operator=(std::move(source)); 166 return *this; 167 } 168 169 using ContiguousContainerBase::CapacityInBytes; 170 using ContiguousContainerBase::IsEmpty; 171 using ContiguousContainerBase::MemoryUsageInBytes; 172 using ContiguousContainerBase::ShrinkToFit; 173 using ContiguousContainerBase::size; 174 using ContiguousContainerBase::UsedCapacityInBytes; 175 begin()176 iterator begin() { return iterator(elements_.begin()); } end()177 iterator end() { return iterator(elements_.end()); } begin()178 const_iterator begin() const { return const_iterator(elements_.begin()); } end()179 const_iterator end() const { return const_iterator(elements_.end()); } rbegin()180 reverse_iterator rbegin() { return reverse_iterator(elements_.rbegin()); } rend()181 reverse_iterator rend() { return reverse_iterator(elements_.rend()); } rbegin()182 const_reverse_iterator rbegin() const { 183 return const_reverse_iterator(elements_.rbegin()); 184 } rend()185 const_reverse_iterator rend() const { 186 return const_reverse_iterator(elements_.rend()); 187 } 188 First()189 BaseElementType& First() { return *begin(); } First()190 const BaseElementType& First() const { return *begin(); } Last()191 BaseElementType& Last() { return *rbegin(); } Last()192 const BaseElementType& Last() const { return *rbegin(); } 193 BaseElementType& operator[](wtf_size_t index) { return *(begin() + index); } 194 const BaseElementType& operator[](wtf_size_t index) const { 195 return *(begin() + index); 196 } 197 198 template <class DerivedElementType, typename... Args> AllocateAndConstruct(Args &&...args)199 DerivedElementType& AllocateAndConstruct(Args&&... args) { 200 static_assert(WTF::IsSubclass<DerivedElementType, BaseElementType>::value, 201 "Must use subclass of BaseElementType."); 202 static_assert(alignment % alignof(DerivedElementType) == 0, 203 "Derived type requires stronger alignment."); 204 return *new (AlignedAllocate(sizeof(DerivedElementType))) 205 DerivedElementType(std::forward<Args>(args)...); 206 } 207 RemoveLast()208 void RemoveLast() { 209 DCHECK(!IsEmpty()); 210 Last().~BaseElementType(); 211 ContiguousContainerBase::RemoveLast(); 212 } 213 214 DISABLE_CFI_PERF Clear()215 void Clear() { 216 for (auto& element : *this) { 217 (void)element; // MSVC incorrectly reports this variable as unused. 218 element.~BaseElementType(); 219 } 220 ContiguousContainerBase::Clear(); 221 } 222 Swap(ContiguousContainer & other)223 void Swap(ContiguousContainer& other) { 224 ContiguousContainerBase::Swap(other); 225 } 226 227 // Appends a new element using memcpy, then default-constructs a base 228 // element in its place. Use with care. AppendByMoving(BaseElementType & item,wtf_size_t size)229 BaseElementType& AppendByMoving(BaseElementType& item, wtf_size_t size) { 230 DCHECK_GE(size, sizeof(BaseElementType)); 231 void* new_item = AlignedAllocate(size); 232 memcpy(new_item, static_cast<void*>(&item), size); 233 new (&item) BaseElementType; 234 return *static_cast<BaseElementType*>(new_item); 235 } 236 237 private: AlignedAllocate(wtf_size_t size)238 void* AlignedAllocate(wtf_size_t size) { 239 void* result = ContiguousContainerBase::Allocate( 240 Align(size), WTF_HEAP_PROFILER_TYPE_NAME(BaseElementType)); 241 DCHECK_EQ(reinterpret_cast<intptr_t>(result) & (alignment - 1), 0u); 242 return result; 243 } 244 Align(wtf_size_t size)245 static wtf_size_t Align(wtf_size_t size) { 246 wtf_size_t aligned_size = alignment * ((size + alignment - 1) / alignment); 247 DCHECK_EQ(aligned_size % alignment, 0u); 248 DCHECK_GE(aligned_size, size); 249 DCHECK_LT(aligned_size, size + alignment); 250 return aligned_size; 251 } 252 }; 253 254 } // namespace blink 255 256 #endif // THIRD_PARTY_BLINK_RENDERER_PLATFORM_GRAPHICS_CONTIGUOUS_CONTAINER_H_ 257