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