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