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