1// Copyright (c) 2010 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_STACK_CONTAINER_H_
6#define BASE_STACK_CONTAINER_H_
7#pragma once
8
9#include <string>
10#include <vector>
11
12#include "base/basictypes.h"
13
14// This allocator can be used with STL containers to provide a stack buffer
15// from which to allocate memory and overflows onto the heap. This stack buffer
16// would be allocated on the stack and allows us to avoid heap operations in
17// some situations.
18//
19// STL likes to make copies of allocators, so the allocator itself can't hold
20// the data. Instead, we make the creator responsible for creating a
21// StackAllocator::Source which contains the data. Copying the allocator
22// merely copies the pointer to this shared source, so all allocators created
23// based on our allocator will share the same stack buffer.
24//
25// This stack buffer implementation is very simple. The first allocation that
26// fits in the stack buffer will use the stack buffer. Any subsequent
27// allocations will not use the stack buffer, even if there is unused room.
28// This makes it appropriate for array-like containers, but the caller should
29// be sure to reserve() in the container up to the stack buffer size. Otherwise
30// the container will allocate a small array which will "use up" the stack
31// buffer.
32template<typename T, size_t stack_capacity>
33class StackAllocator : public std::allocator<T> {
34 public:
35  typedef typename std::allocator<T>::pointer pointer;
36  typedef typename std::allocator<T>::size_type size_type;
37
38  // Backing store for the allocator. The container owner is responsible for
39  // maintaining this for as long as any containers using this allocator are
40  // live.
41  struct Source {
42    Source() : used_stack_buffer_(false) {
43    }
44
45    // Casts the buffer in its right type.
46    T* stack_buffer() { return reinterpret_cast<T*>(stack_buffer_); }
47    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.
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  explicit StackAllocator(Source* source) : source_(source) {
94  }
95
96  // Actually do the allocation. Use the stack buffer if nobody has used it yet
97  // and the size requested fits. Otherwise, fall through to the standard
98  // allocator.
99  pointer allocate(size_type n, void* hint = 0) {
100    if (source_ != NULL && !source_->used_stack_buffer_
101        && n <= stack_capacity) {
102      source_->used_stack_buffer_ = true;
103      return source_->stack_buffer();
104    } else {
105      return std::allocator<T>::allocate(n, hint);
106    }
107  }
108
109  // Free: when trying to free the stack buffer, just mark it as free. For
110  // non-stack-buffer pointers, just fall though to the standard allocator.
111  void deallocate(pointer p, size_type n) {
112    if (source_ != NULL && p == source_->stack_buffer())
113      source_->used_stack_buffer_ = false;
114    else
115      std::allocator<T>::deallocate(p, n);
116  }
117
118 private:
119  Source* source_;
120};
121
122// A wrapper around STL containers that maintains a stack-sized buffer that the
123// initial capacity of the vector is based on. Growing the container beyond the
124// stack capacity will transparently overflow onto the heap. The container must
125// support reserve().
126//
127// WATCH OUT: the ContainerType MUST use the proper StackAllocator for this
128// type. This object is really intended to be used only internally. You'll want
129// to use the wrappers below for different types.
130template<typename TContainerType, int stack_capacity>
131class StackContainer {
132 public:
133  typedef TContainerType ContainerType;
134  typedef typename ContainerType::value_type ContainedType;
135  typedef StackAllocator<ContainedType, stack_capacity> Allocator;
136
137  // Allocator must be constructed before the container!
138  StackContainer() : allocator_(&stack_data_), container_(allocator_) {
139    // Make the container use the stack allocation by reserving our buffer size
140    // before doing anything else.
141    container_.reserve(stack_capacity);
142  }
143
144  // Getters for the actual container.
145  //
146  // Danger: any copies of this made using the copy constructor must have
147  // shorter lifetimes than the source. The copy will share the same allocator
148  // and therefore the same stack buffer as the original. Use std::copy to
149  // copy into a "real" container for longer-lived objects.
150  ContainerType& container() { return container_; }
151  const ContainerType& container() const { return container_; }
152
153  // Support operator-> to get to the container. This allows nicer syntax like:
154  //   StackContainer<...> foo;
155  //   std::sort(foo->begin(), foo->end());
156  ContainerType* operator->() { return &container_; }
157  const ContainerType* operator->() const { return &container_; }
158
159#ifdef UNIT_TEST
160  // Retrieves the stack source so that that unit tests can verify that the
161  // buffer is being used properly.
162  const typename Allocator::Source& stack_data() const {
163    return stack_data_;
164  }
165#endif
166
167 protected:
168  typename Allocator::Source stack_data_;
169  Allocator allocator_;
170  ContainerType container_;
171
172  DISALLOW_COPY_AND_ASSIGN(StackContainer);
173};
174
175// StackString
176template<size_t stack_capacity>
177class StackString : public StackContainer<
178    std::basic_string<char,
179                      std::char_traits<char>,
180                      StackAllocator<char, stack_capacity> >,
181    stack_capacity> {
182 public:
183  StackString() : StackContainer<
184      std::basic_string<char,
185                        std::char_traits<char>,
186                        StackAllocator<char, stack_capacity> >,
187      stack_capacity>() {
188  }
189
190 private:
191  DISALLOW_COPY_AND_ASSIGN(StackString);
192};
193
194// StackWString
195template<size_t stack_capacity>
196class StackWString : public StackContainer<
197    std::basic_string<wchar_t,
198                      std::char_traits<wchar_t>,
199                      StackAllocator<wchar_t, stack_capacity> >,
200    stack_capacity> {
201 public:
202  StackWString() : StackContainer<
203      std::basic_string<wchar_t,
204                        std::char_traits<wchar_t>,
205                        StackAllocator<wchar_t, stack_capacity> >,
206      stack_capacity>() {
207  }
208
209 private:
210  DISALLOW_COPY_AND_ASSIGN(StackWString);
211};
212
213// StackVector
214//
215// Example:
216//   StackVector<int, 16> foo;
217//   foo->push_back(22);  // we have overloaded operator->
218//   foo[0] = 10;         // as well as operator[]
219template<typename T, size_t stack_capacity>
220class StackVector : public StackContainer<
221    std::vector<T, StackAllocator<T, stack_capacity> >,
222    stack_capacity> {
223 public:
224  StackVector() : StackContainer<
225      std::vector<T, StackAllocator<T, stack_capacity> >,
226      stack_capacity>() {
227  }
228
229  // We need to put this in STL containers sometimes, which requires a copy
230  // constructor. We can't call the regular copy constructor because that will
231  // take the stack buffer from the original. Here, we create an empty object
232  // and make a stack buffer of its own.
233  StackVector(const StackVector<T, stack_capacity>& other)
234      : StackContainer<
235            std::vector<T, StackAllocator<T, stack_capacity> >,
236            stack_capacity>() {
237    this->container().assign(other->begin(), other->end());
238  }
239
240  StackVector<T, stack_capacity>& operator=(
241      const StackVector<T, stack_capacity>& other) {
242    this->container().assign(other->begin(), other->end());
243    return *this;
244  }
245
246  // Vectors are commonly indexed, which isn't very convenient even with
247  // operator-> (using "->at()" does exception stuff we don't want).
248  T& operator[](size_t i) { return this->container().operator[](i); }
249  const T& operator[](size_t i) const {
250    return this->container().operator[](i);
251  }
252};
253
254#endif  // BASE_STACK_CONTAINER_H_
255