stack_container.h 9.62 KB
Newer Older
gejun's avatar
gejun committed
1 2 3 4
// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6
#ifndef BUTIL_CONTAINERS_STACK_CONTAINER_H_
#define BUTIL_CONTAINERS_STACK_CONTAINER_H_
gejun's avatar
gejun committed
7 8 9 10

#include <string>
#include <vector>

11 12 13 14
#include "butil/basictypes.h"
#include "butil/memory/aligned_memory.h"
#include "butil/strings/string16.h"
#include "butil/build_config.h"
gejun's avatar
gejun committed
15

16
namespace butil {
gejun's avatar
gejun committed
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

// This allocator can be used with STL containers to provide a stack buffer
// from which to allocate memory and overflows onto the heap. This stack buffer
// would be allocated on the stack and allows us to avoid heap operations in
// some situations.
//
// STL likes to make copies of allocators, so the allocator itself can't hold
// the data. Instead, we make the creator responsible for creating a
// StackAllocator::Source which contains the data. Copying the allocator
// merely copies the pointer to this shared source, so all allocators created
// based on our allocator will share the same stack buffer.
//
// This stack buffer implementation is very simple. The first allocation that
// fits in the stack buffer will use the stack buffer. Any subsequent
// allocations will not use the stack buffer, even if there is unused room.
// This makes it appropriate for array-like containers, but the caller should
// be sure to reserve() in the container up to the stack buffer size. Otherwise
// the container will allocate a small array which will "use up" the stack
// buffer.
template<typename T, size_t stack_capacity>
class StackAllocator : public std::allocator<T> {
 public:
  typedef typename std::allocator<T>::pointer pointer;
  typedef typename std::allocator<T>::size_type size_type;

  // Backing store for the allocator. The container owner is responsible for
  // maintaining this for as long as any containers using this allocator are
  // live.
  struct Source {
    Source() : used_stack_buffer_(false) {
    }

    // Casts the buffer in its right type.
    T* stack_buffer() { return stack_buffer_.template data_as<T>(); }
    const T* stack_buffer() const {
      return stack_buffer_.template data_as<T>();
    }

    // The buffer itself. It is not of type T because we don't want the
    // constructors and destructors to be automatically called. Define a POD
    // buffer of the right size instead.
58
    butil::AlignedMemory<sizeof(T[stack_capacity]), ALIGNOF(T)> stack_buffer_;
gejun's avatar
gejun committed
59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
#if defined(__GNUC__) && !defined(ARCH_CPU_X86_FAMILY)
    COMPILE_ASSERT(ALIGNOF(T) <= 16, crbug_115612);
#endif

    // Set when the stack buffer is used for an allocation. We do not track
    // how much of the buffer is used, only that somebody is using it.
    bool used_stack_buffer_;
  };

  // Used by containers when they want to refer to an allocator of type U.
  template<typename U>
  struct rebind {
    typedef StackAllocator<U, stack_capacity> other;
  };

  // For the straight up copy c-tor, we can share storage.
  StackAllocator(const StackAllocator<T, stack_capacity>& rhs)
      : std::allocator<T>(), source_(rhs.source_) {
  }

  // ISO C++ requires the following constructor to be defined,
  // and std::vector in VC++2008SP1 Release fails with an error
  // in the class _Container_base_aux_alloc_real (from <xutility>)
  // if the constructor does not exist.
  // For this constructor, we cannot share storage; there's
  // no guarantee that the Source buffer of Ts is large enough
  // for Us.
  // TODO: If we were fancy pants, perhaps we could share storage
  // iff sizeof(T) == sizeof(U).
  template<typename U, size_t other_capacity>
  StackAllocator(const StackAllocator<U, other_capacity>& other)
      : source_(NULL) {
  }

  // This constructor must exist. It creates a default allocator that doesn't
  // actually have a stack buffer. glibc's std::string() will compare the
  // current allocator against the default-constructed allocator, so this
  // should be fast.
  StackAllocator() : source_(NULL) {
  }

  explicit StackAllocator(Source* source) : source_(source) {
  }

  // Actually do the allocation. Use the stack buffer if nobody has used it yet
  // and the size requested fits. Otherwise, fall through to the standard
  // allocator.
  pointer allocate(size_type n, void* hint = 0) {
    if (source_ != NULL && !source_->used_stack_buffer_
        && n <= stack_capacity) {
      source_->used_stack_buffer_ = true;
      return source_->stack_buffer();
    } else {
      return std::allocator<T>::allocate(n, hint);
    }
  }

  // Free: when trying to free the stack buffer, just mark it as free. For
  // non-stack-buffer pointers, just fall though to the standard allocator.
  void deallocate(pointer p, size_type n) {
    if (source_ != NULL && p == source_->stack_buffer())
      source_->used_stack_buffer_ = false;
    else
      std::allocator<T>::deallocate(p, n);
  }

 private:
  Source* source_;
};

// A wrapper around STL containers that maintains a stack-sized buffer that the
// initial capacity of the vector is based on. Growing the container beyond the
// stack capacity will transparently overflow onto the heap. The container must
// support reserve().
//
// WATCH OUT: the ContainerType MUST use the proper StackAllocator for this
// type. This object is really intended to be used only internally. You'll want
// to use the wrappers below for different types.
template<typename TContainerType, int stack_capacity>
class StackContainer {
 public:
  typedef TContainerType ContainerType;
  typedef typename ContainerType::value_type ContainedType;
  typedef StackAllocator<ContainedType, stack_capacity> Allocator;

  // Allocator must be constructed before the container!
  StackContainer() : allocator_(&stack_data_), container_(allocator_) {
    // Make the container use the stack allocation by reserving our buffer size
    // before doing anything else.
    container_.reserve(stack_capacity);
  }

  // Getters for the actual container.
  //
  // Danger: any copies of this made using the copy constructor must have
  // shorter lifetimes than the source. The copy will share the same allocator
  // and therefore the same stack buffer as the original. Use std::copy to
  // copy into a "real" container for longer-lived objects.
  ContainerType& container() { return container_; }
  const ContainerType& container() const { return container_; }

  // Support operator-> to get to the container. This allows nicer syntax like:
  //   StackContainer<...> foo;
  //   std::sort(foo->begin(), foo->end());
  ContainerType* operator->() { return &container_; }
  const ContainerType* operator->() const { return &container_; }

#ifdef UNIT_TEST
  // Retrieves the stack source so that that unit tests can verify that the
  // buffer is being used properly.
  const typename Allocator::Source& stack_data() const {
    return stack_data_;
  }
#endif

 protected:
  typename Allocator::Source stack_data_;
  Allocator allocator_;
  ContainerType container_;

  DISALLOW_COPY_AND_ASSIGN(StackContainer);
};

// StackString -----------------------------------------------------------------

template<size_t stack_capacity>
class StackString : public StackContainer<
    std::basic_string<char,
                      std::char_traits<char>,
                      StackAllocator<char, stack_capacity> >,
    stack_capacity> {
 public:
  StackString() : StackContainer<
      std::basic_string<char,
                        std::char_traits<char>,
                        StackAllocator<char, stack_capacity> >,
      stack_capacity>() {
  }

 private:
  DISALLOW_COPY_AND_ASSIGN(StackString);
};

// StackStrin16 ----------------------------------------------------------------

template<size_t stack_capacity>
class StackString16 : public StackContainer<
    std::basic_string<char16,
207
                      butil::string16_char_traits,
gejun's avatar
gejun committed
208 209 210 211 212
                      StackAllocator<char16, stack_capacity> >,
    stack_capacity> {
 public:
  StackString16() : StackContainer<
      std::basic_string<char16,
213
                        butil::string16_char_traits,
gejun's avatar
gejun committed
214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262
                        StackAllocator<char16, stack_capacity> >,
      stack_capacity>() {
  }

 private:
  DISALLOW_COPY_AND_ASSIGN(StackString16);
};

// StackVector -----------------------------------------------------------------

// Example:
//   StackVector<int, 16> foo;
//   foo->push_back(22);  // we have overloaded operator->
//   foo[0] = 10;         // as well as operator[]
template<typename T, size_t stack_capacity>
class StackVector : public StackContainer<
    std::vector<T, StackAllocator<T, stack_capacity> >,
    stack_capacity> {
 public:
  StackVector() : StackContainer<
      std::vector<T, StackAllocator<T, stack_capacity> >,
      stack_capacity>() {
  }

  // We need to put this in STL containers sometimes, which requires a copy
  // constructor. We can't call the regular copy constructor because that will
  // take the stack buffer from the original. Here, we create an empty object
  // and make a stack buffer of its own.
  StackVector(const StackVector<T, stack_capacity>& other)
      : StackContainer<
            std::vector<T, StackAllocator<T, stack_capacity> >,
            stack_capacity>() {
    this->container().assign(other->begin(), other->end());
  }

  StackVector<T, stack_capacity>& operator=(
      const StackVector<T, stack_capacity>& other) {
    this->container().assign(other->begin(), other->end());
    return *this;
  }

  // Vectors are commonly indexed, which isn't very convenient even with
  // operator-> (using "->at()" does exception stuff we don't want).
  T& operator[](size_t i) { return this->container().operator[](i); }
  const T& operator[](size_t i) const {
    return this->container().operator[](i);
  }
};

263
}  // namespace butil
gejun's avatar
gejun committed
264

265
#endif  // BUTIL_CONTAINERS_STACK_CONTAINER_H_