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 { 46 Source() : used_stack_buffer_(false) { 47 } 48 49 // Casts the buffer in its right type. 50 T* stack_buffer() { return stack_buffer_.template data_as<T>(); } 51 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. 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> 89 StackAllocator(const StackAllocator<U, other_capacity>& other) 90 : source_(NULL) { 91 } 92 93 explicit StackAllocator(Source* source) : source_(source) { 94 } 95 96 // Actually do the allocation. Use the stack buffer if nobody has used it yet 97 // and the size requested fits. Otherwise, fall through to the standard 98 // allocator. 99 pointer allocate(size_type n, void* hint = 0) { 100 if (source_ != NULL && !source_->used_stack_buffer_ 101 && n <= stack_capacity) { 102 source_->used_stack_buffer_ = true; 103 return source_->stack_buffer(); 104 } else { 105 return std::allocator<T>::allocate(n, hint); 106 } 107 } 108 109 // Free: when trying to free the stack buffer, just mark it as free. For 110 // non-stack-buffer pointers, just fall though to the standard allocator. 111 void deallocate(pointer p, size_type n) { 112 if (source_ != NULL && p == source_->stack_buffer()) 113 source_->used_stack_buffer_ = false; 114 else 115 std::allocator<T>::deallocate(p, n); 116 } 117 118 private: 119 Source* source_; 120 }; 121 122 // A wrapper around STL containers that maintains a stack-sized buffer that the 123 // initial capacity of the vector is based on. Growing the container beyond the 124 // stack capacity will transparently overflow onto the heap. The container must 125 // support reserve(). 126 // 127 // WATCH OUT: the ContainerType MUST use the proper StackAllocator for this 128 // type. This object is really intended to be used only internally. You'll want 129 // to use the wrappers below for different types. 130 template<typename TContainerType, int stack_capacity> 131 class StackContainer { 132 public: 133 typedef TContainerType ContainerType; 134 typedef typename ContainerType::value_type ContainedType; 135 typedef StackAllocator<ContainedType, stack_capacity> Allocator; 136 137 // Allocator must be constructed before the container! 138 StackContainer() : allocator_(&stack_data_), container_(allocator_) { 139 // Make the container use the stack allocation by reserving our buffer size 140 // before doing anything else. 141 container_.reserve(stack_capacity); 142 } 143 144 // Getters for the actual container. 145 // 146 // Danger: any copies of this made using the copy constructor must have 147 // shorter lifetimes than the source. The copy will share the same allocator 148 // and therefore the same stack buffer as the original. Use std::copy to 149 // copy into a "real" container for longer-lived objects. 150 ContainerType& container() { return container_; } 151 const ContainerType& container() const { return container_; } 152 153 // Support operator-> to get to the container. This allows nicer syntax like: 154 // StackContainer<...> foo; 155 // std::sort(foo->begin(), foo->end()); 156 ContainerType* operator->() { return &container_; } 157 const ContainerType* operator->() const { return &container_; } 158 159 #ifdef UNIT_TEST 160 // Retrieves the stack source so that that unit tests can verify that the 161 // buffer is being used properly. 162 const typename Allocator::Source& stack_data() const { 163 return stack_data_; 164 } 165 #endif 166 167 protected: 168 typename Allocator::Source stack_data_; 169 Allocator allocator_; 170 ContainerType container_; 171 172 DISALLOW_COPY_AND_ASSIGN(StackContainer); 173 }; 174 175 // StackString ----------------------------------------------------------------- 176 177 template<size_t stack_capacity> 178 class StackString : public StackContainer< 179 std::basic_string<char, 180 std::char_traits<char>, 181 StackAllocator<char, stack_capacity> >, 182 stack_capacity> { 183 public: 184 StackString() : StackContainer< 185 std::basic_string<char, 186 std::char_traits<char>, 187 StackAllocator<char, stack_capacity> >, 188 stack_capacity>() { 189 } 190 191 private: 192 DISALLOW_COPY_AND_ASSIGN(StackString); 193 }; 194 195 // StackStrin16 ---------------------------------------------------------------- 196 197 template<size_t stack_capacity> 198 class StackString16 : public StackContainer< 199 std::basic_string<char16, 200 base::string16_char_traits, 201 StackAllocator<char16, stack_capacity> >, 202 stack_capacity> { 203 public: 204 StackString16() : StackContainer< 205 std::basic_string<char16, 206 base::string16_char_traits, 207 StackAllocator<char16, stack_capacity> >, 208 stack_capacity>() { 209 } 210 211 private: 212 DISALLOW_COPY_AND_ASSIGN(StackString16); 213 }; 214 215 // StackVector ----------------------------------------------------------------- 216 217 // Example: 218 // StackVector<int, 16> foo; 219 // foo->push_back(22); // we have overloaded operator-> 220 // foo[0] = 10; // as well as operator[] 221 template<typename T, size_t stack_capacity> 222 class StackVector : public StackContainer< 223 std::vector<T, StackAllocator<T, stack_capacity> >, 224 stack_capacity> { 225 public: 226 StackVector() : StackContainer< 227 std::vector<T, StackAllocator<T, stack_capacity> >, 228 stack_capacity>() { 229 } 230 231 // We need to put this in STL containers sometimes, which requires a copy 232 // constructor. We can't call the regular copy constructor because that will 233 // take the stack buffer from the original. Here, we create an empty object 234 // and make a stack buffer of its own. 235 StackVector(const StackVector<T, stack_capacity>& other) 236 : StackContainer< 237 std::vector<T, StackAllocator<T, stack_capacity> >, 238 stack_capacity>() { 239 this->container().assign(other->begin(), other->end()); 240 } 241 242 StackVector<T, stack_capacity>& operator=( 243 const StackVector<T, stack_capacity>& other) { 244 this->container().assign(other->begin(), other->end()); 245 return *this; 246 } 247 248 // Vectors are commonly indexed, which isn't very convenient even with 249 // operator-> (using "->at()" does exception stuff we don't want). 250 T& operator[](size_t i) { return this->container().operator[](i); } 251 const T& operator[](size_t i) const { 252 return this->container().operator[](i); 253 } 254 }; 255 256 } // namespace base 257 258 #endif // BASE_CONTAINERS_STACK_CONTAINER_H_ 259