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