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