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