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