1 // Copyright (c) 2012 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 // This file is a modified copy of Chromium's /src/base/containers/stack_container.h 6 7 #ifndef COMMON_STACKCONTAINER_H_ 8 #define COMMON_STACKCONTAINER_H_ 9 10 #include "common/Compiler.h" 11 12 #include <cstddef> 13 #include <vector> 14 15 // This allocator can be used with STL containers to provide a stack buffer 16 // from which to allocate memory and overflows onto the heap. This stack buffer 17 // would be allocated on the stack and allows us to avoid heap operations in 18 // some situations. 19 // 20 // STL likes to make copies of allocators, so the allocator itself can't hold 21 // the data. Instead, we make the creator responsible for creating a 22 // StackAllocator::Source which contains the data. Copying the allocator 23 // merely copies the pointer to this shared source, so all allocators created 24 // based on our allocator will share the same stack buffer. 25 // 26 // This stack buffer implementation is very simple. The first allocation that 27 // fits in the stack buffer will use the stack buffer. Any subsequent 28 // allocations will not use the stack buffer, even if there is unused room. 29 // This makes it appropriate for array-like containers, but the caller should 30 // be sure to reserve() in the container up to the stack buffer size. Otherwise 31 // the container will allocate a small array which will "use up" the stack 32 // buffer. 33 template <typename T, size_t stack_capacity> 34 class StackAllocator : public std::allocator<T> { 35 public: 36 typedef typename std::allocator<T>::pointer pointer; 37 typedef typename std::allocator<T>::size_type size_type; 38 39 // Backing store for the allocator. The container owner is responsible for 40 // maintaining this for as long as any containers using this allocator are 41 // live. 42 struct Source { SourceSource43 Source() : used_stack_buffer_(false) { 44 } 45 46 // Casts the buffer in its right type. stack_bufferSource47 T* stack_buffer() { 48 return reinterpret_cast<T*>(stack_buffer_); 49 } stack_bufferSource50 const T* stack_buffer() const { 51 return reinterpret_cast<const T*>(&stack_buffer_); 52 } 53 54 // The buffer itself. It is not of type T because we don't want the 55 // constructors and destructors to be automatically called. Define a POD 56 // buffer of the right size instead. 57 alignas(T) char stack_buffer_[sizeof(T[stack_capacity])]; 58 #if defined(DAWN_COMPILER_GCC) && !defined(__x86_64__) && !defined(__i386__) 59 static_assert(alignof(T) <= 16, "http://crbug.com/115612"); 60 #endif 61 62 // Set when the stack buffer is used for an allocation. We do not track 63 // how much of the buffer is used, only that somebody is using it. 64 bool used_stack_buffer_; 65 }; 66 67 // Used by containers when they want to refer to an allocator of type U. 68 template <typename U> 69 struct rebind { 70 typedef StackAllocator<U, stack_capacity> other; 71 }; 72 73 // For the straight up copy c-tor, we can share storage. StackAllocator(const StackAllocator<T,stack_capacity> & rhs)74 StackAllocator(const StackAllocator<T, stack_capacity>& rhs) 75 : std::allocator<T>(), source_(rhs.source_) { 76 } 77 78 // ISO C++ requires the following constructor to be defined, 79 // and std::vector in VC++2008SP1 Release fails with an error 80 // in the class _Container_base_aux_alloc_real (from <xutility>) 81 // if the constructor does not exist. 82 // For this constructor, we cannot share storage; there's 83 // no guarantee that the Source buffer of Ts is large enough 84 // for Us. 85 // TODO: If we were fancy pants, perhaps we could share storage 86 // iff sizeof(T) == sizeof(U). 87 template <typename U, size_t other_capacity> StackAllocator(const StackAllocator<U,other_capacity> & other)88 StackAllocator(const StackAllocator<U, other_capacity>& other) : source_(nullptr) { 89 } 90 91 // This constructor must exist. It creates a default allocator that doesn't 92 // actually have a stack buffer. glibc's std::string() will compare the 93 // current allocator against the default-constructed allocator, so this 94 // should be fast. StackAllocator()95 StackAllocator() : source_(nullptr) { 96 } 97 StackAllocator(Source * source)98 explicit StackAllocator(Source* source) : source_(source) { 99 } 100 101 // Actually do the allocation. Use the stack buffer if nobody has used it yet 102 // and the size requested fits. Otherwise, fall through to the standard 103 // allocator. allocate(size_type n)104 pointer allocate(size_type n) { 105 if (source_ && !source_->used_stack_buffer_ && n <= stack_capacity) { 106 source_->used_stack_buffer_ = true; 107 return source_->stack_buffer(); 108 } else { 109 return std::allocator<T>::allocate(n); 110 } 111 } 112 113 // Free: when trying to free the stack buffer, just mark it as free. For 114 // non-stack-buffer pointers, just fall though to the standard allocator. deallocate(pointer p,size_type n)115 void deallocate(pointer p, size_type n) { 116 if (source_ && p == source_->stack_buffer()) 117 source_->used_stack_buffer_ = false; 118 else 119 std::allocator<T>::deallocate(p, n); 120 } 121 122 private: 123 Source* source_; 124 }; 125 126 // A wrapper around STL containers that maintains a stack-sized buffer that the 127 // initial capacity of the vector is based on. Growing the container beyond the 128 // stack capacity will transparently overflow onto the heap. The container must 129 // support reserve(). 130 // 131 // This will not work with std::string since some implementations allocate 132 // more bytes than requested in calls to reserve(), forcing the allocation onto 133 // the heap. http://crbug.com/709273 134 // 135 // WATCH OUT: the ContainerType MUST use the proper StackAllocator for this 136 // type. This object is really intended to be used only internally. You'll want 137 // to use the wrappers below for different types. 138 template <typename TContainerType, size_t stack_capacity> 139 class StackContainer { 140 public: 141 typedef TContainerType ContainerType; 142 typedef typename ContainerType::value_type ContainedType; 143 typedef StackAllocator<ContainedType, stack_capacity> Allocator; 144 145 // Allocator must be constructed before the container! StackContainer()146 StackContainer() : allocator_(&stack_data_), container_(allocator_) { 147 // Make the container use the stack allocation by reserving our buffer size 148 // before doing anything else. 149 container_.reserve(stack_capacity); 150 } 151 152 // Getters for the actual container. 153 // 154 // Danger: any copies of this made using the copy constructor must have 155 // shorter lifetimes than the source. The copy will share the same allocator 156 // and therefore the same stack buffer as the original. Use std::copy to 157 // copy into a "real" container for longer-lived objects. container()158 ContainerType& container() { 159 return container_; 160 } container()161 const ContainerType& container() const { 162 return container_; 163 } 164 165 // Support operator-> to get to the container. This allows nicer syntax like: 166 // StackContainer<...> foo; 167 // std::sort(foo->begin(), foo->end()); 168 ContainerType* operator->() { 169 return &container_; 170 } 171 const ContainerType* operator->() const { 172 return &container_; 173 } 174 175 // Retrieves the stack source so that that unit tests can verify that the 176 // buffer is being used properly. stack_data()177 const typename Allocator::Source& stack_data() const { 178 return stack_data_; 179 } 180 181 protected: 182 typename Allocator::Source stack_data_; 183 Allocator allocator_; 184 ContainerType container_; 185 186 private: 187 StackContainer(const StackContainer& rhs) = delete; 188 StackContainer& operator=(const StackContainer& rhs) = delete; 189 StackContainer(StackContainer&& rhs) = delete; 190 StackContainer& operator=(StackContainer&& rhs) = delete; 191 }; 192 193 // Range-based iteration support for StackContainer. 194 template <typename TContainerType, size_t stack_capacity> 195 auto begin(const StackContainer<TContainerType, stack_capacity>& stack_container) 196 -> decltype(begin(stack_container.container())) { 197 return begin(stack_container.container()); 198 } 199 200 template <typename TContainerType, size_t stack_capacity> 201 auto begin(StackContainer<TContainerType, stack_capacity>& stack_container) 202 -> decltype(begin(stack_container.container())) { 203 return begin(stack_container.container()); 204 } 205 206 template <typename TContainerType, size_t stack_capacity> 207 auto end(StackContainer<TContainerType, stack_capacity>& stack_container) 208 -> decltype(end(stack_container.container())) { 209 return end(stack_container.container()); 210 } 211 212 template <typename TContainerType, size_t stack_capacity> 213 auto end(const StackContainer<TContainerType, stack_capacity>& stack_container) 214 -> decltype(end(stack_container.container())) { 215 return end(stack_container.container()); 216 } 217 218 // StackVector ----------------------------------------------------------------- 219 220 // Example: 221 // StackVector<int, 16> foo; 222 // foo->push_back(22); // we have overloaded operator-> 223 // foo[0] = 10; // as well as operator[] 224 template <typename T, size_t stack_capacity> 225 class StackVector 226 : public StackContainer<std::vector<T, StackAllocator<T, stack_capacity>>, stack_capacity> { 227 public: StackVector()228 StackVector() 229 : StackContainer<std::vector<T, StackAllocator<T, stack_capacity>>, stack_capacity>() { 230 } 231 232 // We need to put this in STL containers sometimes, which requires a copy 233 // constructor. We can't call the regular copy constructor because that will 234 // take the stack buffer from the original. Here, we create an empty object 235 // and make a stack buffer of its own. StackVector(const StackVector<T,stack_capacity> & other)236 StackVector(const StackVector<T, stack_capacity>& other) 237 : StackContainer<std::vector<T, StackAllocator<T, stack_capacity>>, stack_capacity>() { 238 this->container().assign(other->begin(), other->end()); 239 } 240 241 StackVector<T, stack_capacity>& operator=(const StackVector<T, stack_capacity>& other) { 242 this->container().assign(other->begin(), other->end()); 243 return *this; 244 } 245 246 // Vectors are commonly indexed, which isn't very convenient even with 247 // operator-> (using "->at()" does exception stuff we don't want). 248 T& operator[](size_t i) { 249 return this->container().operator[](i); 250 } 251 const T& operator[](size_t i) const { 252 return this->container().operator[](i); 253 } 254 255 private: 256 // StackVector(const StackVector& rhs) = delete; 257 // StackVector& operator=(const StackVector& rhs) = delete; 258 StackVector(StackVector&& rhs) = delete; 259 StackVector& operator=(StackVector&& rhs) = delete; 260 }; 261 262 #endif // COMMON_STACKCONTAINER_H_ 263