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 18namespace 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. 38template<typename T, size_t stack_capacity> 39class 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 { 48 Source() : used_stack_buffer_(false) { 49 } 50 51 // Casts the buffer in its right type. 52 T* stack_buffer() { return stack_buffer_.template data_as<T>(); } 53 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. 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> 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. 99 StackAllocator() : source_(NULL) { 100 } 101 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. 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. 139template<typename TContainerType, int stack_capacity> 140class 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! 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. 159 ContainerType& container() { return 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. 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 187template<size_t stack_capacity> 188class StackString : public StackContainer< 189 std::basic_string<char, 190 std::char_traits<char>, 191 StackAllocator<char, stack_capacity> >, 192 stack_capacity> { 193 public: 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 207template<size_t stack_capacity> 208class StackString16 : public StackContainer< 209 std::basic_string<char16, 210 base::string16_char_traits, 211 StackAllocator<char16, stack_capacity> >, 212 stack_capacity> { 213 public: 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[] 231template<typename T, size_t stack_capacity> 232class StackVector : public StackContainer< 233 std::vector<T, StackAllocator<T, stack_capacity> >, 234 stack_capacity> { 235 public: 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. 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