Home | History | Annotate | Download | only in containers
      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 
     16 namespace 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.
     36 template<typename T, size_t stack_capacity>
     37 class 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.
    137 template<typename TContainerType, int stack_capacity>
    138 class 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 
    184 template<size_t stack_capacity>
    185 class 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 
    204 template<size_t stack_capacity>
    205 class 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[]
    228 template<typename T, size_t stack_capacity>
    229 class 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