1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/ipc/chromium/src/base/stack_container.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,253 @@
1.4 +// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
1.5 +// Use of this source code is governed by a BSD-style license that can be
1.6 +// found in the LICENSE file.
1.7 +
1.8 +#ifndef BASE_STACK_CONTAINER_H_
1.9 +#define BASE_STACK_CONTAINER_H_
1.10 +
1.11 +#include <string>
1.12 +#include <vector>
1.13 +
1.14 +#include "base/basictypes.h"
1.15 +
1.16 +// This allocator can be used with STL containers to provide a stack buffer
1.17 +// from which to allocate memory and overflows onto the heap. This stack buffer
1.18 +// would be allocated on the stack and allows us to avoid heap operations in
1.19 +// some situations.
1.20 +//
1.21 +// STL likes to make copies of allocators, so the allocator itself can't hold
1.22 +// the data. Instead, we make the creator responsible for creating a
1.23 +// StackAllocator::Source which contains the data. Copying the allocator
1.24 +// merely copies the pointer to this shared source, so all allocators created
1.25 +// based on our allocator will share the same stack buffer.
1.26 +//
1.27 +// This stack buffer implementation is very simple. The first allocation that
1.28 +// fits in the stack buffer will use the stack buffer. Any subsequent
1.29 +// allocations will not use the stack buffer, even if there is unused room.
1.30 +// This makes it appropriate for array-like containers, but the caller should
1.31 +// be sure to reserve() in the container up to the stack buffer size. Otherwise
1.32 +// the container will allocate a small array which will "use up" the stack
1.33 +// buffer.
1.34 +template<typename T, size_t stack_capacity>
1.35 +class StackAllocator : public std::allocator<T> {
1.36 + public:
1.37 + typedef typename std::allocator<T>::pointer pointer;
1.38 + typedef typename std::allocator<T>::size_type size_type;
1.39 +
1.40 + // Backing store for the allocator. The container owner is responsible for
1.41 + // maintaining this for as long as any containers using this allocator are
1.42 + // live.
1.43 + struct Source {
1.44 + Source() : used_stack_buffer_(false) {
1.45 + }
1.46 +
1.47 + // Casts the buffer in its right type.
1.48 + T* stack_buffer() { return reinterpret_cast<T*>(stack_buffer_); }
1.49 + const T* stack_buffer() const {
1.50 + return reinterpret_cast<const T*>(stack_buffer_);
1.51 + }
1.52 +
1.53 + //
1.54 + // IMPORTANT: Take care to ensure that stack_buffer_ is aligned
1.55 + // since it is used to mimic an array of T.
1.56 + // Be careful while declaring any unaligned types (like bool)
1.57 + // before stack_buffer_.
1.58 + //
1.59 +
1.60 + // The buffer itself. It is not of type T because we don't want the
1.61 + // constructors and destructors to be automatically called. Define a POD
1.62 + // buffer of the right size instead.
1.63 + char stack_buffer_[sizeof(T[stack_capacity])];
1.64 +
1.65 + // Set when the stack buffer is used for an allocation. We do not track
1.66 + // how much of the buffer is used, only that somebody is using it.
1.67 + bool used_stack_buffer_;
1.68 + };
1.69 +
1.70 + // Used by containers when they want to refer to an allocator of type U.
1.71 + template<typename U>
1.72 + struct rebind {
1.73 + typedef StackAllocator<U, stack_capacity> other;
1.74 + };
1.75 +
1.76 + // For the straight up copy c-tor, we can share storage.
1.77 + StackAllocator(const StackAllocator<T, stack_capacity>& rhs)
1.78 + : source_(rhs.source_) {
1.79 + }
1.80 +
1.81 + // ISO C++ requires the following constructor to be defined,
1.82 + // and std::vector in VC++2008SP1 Release fails with an error
1.83 + // in the class _Container_base_aux_alloc_real (from <xutility>)
1.84 + // if the constructor does not exist.
1.85 + // For this constructor, we cannot share storage; there's
1.86 + // no guarantee that the Source buffer of Ts is large enough
1.87 + // for Us.
1.88 + // TODO: If we were fancy pants, perhaps we could share storage
1.89 + // iff sizeof(T) == sizeof(U).
1.90 + template<typename U, size_t other_capacity>
1.91 + StackAllocator(const StackAllocator<U, other_capacity>& other)
1.92 + : source_(NULL) {
1.93 + }
1.94 +
1.95 + explicit StackAllocator(Source* source) : source_(source) {
1.96 + }
1.97 +
1.98 + // Actually do the allocation. Use the stack buffer if nobody has used it yet
1.99 + // and the size requested fits. Otherwise, fall through to the standard
1.100 + // allocator.
1.101 + pointer allocate(size_type n, void* hint = 0) {
1.102 + if (source_ != NULL && !source_->used_stack_buffer_
1.103 + && n <= stack_capacity) {
1.104 + source_->used_stack_buffer_ = true;
1.105 + return source_->stack_buffer();
1.106 + } else {
1.107 + return std::allocator<T>::allocate(n, hint);
1.108 + }
1.109 + }
1.110 +
1.111 + // Free: when trying to free the stack buffer, just mark it as free. For
1.112 + // non-stack-buffer pointers, just fall though to the standard allocator.
1.113 + void deallocate(pointer p, size_type n) {
1.114 + if (source_ != NULL && p == source_->stack_buffer())
1.115 + source_->used_stack_buffer_ = false;
1.116 + else
1.117 + std::allocator<T>::deallocate(p, n);
1.118 + }
1.119 +
1.120 + private:
1.121 + Source* source_;
1.122 +};
1.123 +
1.124 +// A wrapper around STL containers that maintains a stack-sized buffer that the
1.125 +// initial capacity of the vector is based on. Growing the container beyond the
1.126 +// stack capacity will transparently overflow onto the heap. The container must
1.127 +// support reserve().
1.128 +//
1.129 +// WATCH OUT: the ContainerType MUST use the proper StackAllocator for this
1.130 +// type. This object is really intended to be used only internally. You'll want
1.131 +// to use the wrappers below for different types.
1.132 +template<typename TContainerType, int stack_capacity>
1.133 +class StackContainer {
1.134 + public:
1.135 + typedef TContainerType ContainerType;
1.136 + typedef typename ContainerType::value_type ContainedType;
1.137 + typedef StackAllocator<ContainedType, stack_capacity> Allocator;
1.138 +
1.139 + // Allocator must be constructed before the container!
1.140 + StackContainer() : allocator_(&stack_data_), container_(allocator_) {
1.141 + // Make the container use the stack allocation by reserving our buffer size
1.142 + // before doing anything else.
1.143 + container_.reserve(stack_capacity);
1.144 + }
1.145 +
1.146 + // Getters for the actual container.
1.147 + //
1.148 + // Danger: any copies of this made using the copy constructor must have
1.149 + // shorter lifetimes than the source. The copy will share the same allocator
1.150 + // and therefore the same stack buffer as the original. Use std::copy to
1.151 + // copy into a "real" container for longer-lived objects.
1.152 + ContainerType& container() { return container_; }
1.153 + const ContainerType& container() const { return container_; }
1.154 +
1.155 + // Support operator-> to get to the container. This allows nicer syntax like:
1.156 + // StackContainer<...> foo;
1.157 + // std::sort(foo->begin(), foo->end());
1.158 + ContainerType* operator->() { return &container_; }
1.159 + const ContainerType* operator->() const { return &container_; }
1.160 +
1.161 +#ifdef UNIT_TEST
1.162 + // Retrieves the stack source so that that unit tests can verify that the
1.163 + // buffer is being used properly.
1.164 + const typename Allocator::Source& stack_data() const {
1.165 + return stack_data_;
1.166 + }
1.167 +#endif
1.168 +
1.169 + protected:
1.170 + typename Allocator::Source stack_data_;
1.171 + Allocator allocator_;
1.172 + ContainerType container_;
1.173 +
1.174 + DISALLOW_EVIL_CONSTRUCTORS(StackContainer);
1.175 +};
1.176 +
1.177 +// StackString
1.178 +template<size_t stack_capacity>
1.179 +class StackString : public StackContainer<
1.180 + std::basic_string<char,
1.181 + std::char_traits<char>,
1.182 + StackAllocator<char, stack_capacity> >,
1.183 + stack_capacity> {
1.184 + public:
1.185 + StackString() : StackContainer<
1.186 + std::basic_string<char,
1.187 + std::char_traits<char>,
1.188 + StackAllocator<char, stack_capacity> >,
1.189 + stack_capacity>() {
1.190 + }
1.191 +
1.192 + private:
1.193 + DISALLOW_EVIL_CONSTRUCTORS(StackString);
1.194 +};
1.195 +
1.196 +// StackWString
1.197 +template<size_t stack_capacity>
1.198 +class StackWString : public StackContainer<
1.199 + std::basic_string<wchar_t,
1.200 + std::char_traits<wchar_t>,
1.201 + StackAllocator<wchar_t, stack_capacity> >,
1.202 + stack_capacity> {
1.203 + public:
1.204 + StackWString() : StackContainer<
1.205 + std::basic_string<wchar_t,
1.206 + std::char_traits<wchar_t>,
1.207 + StackAllocator<wchar_t, stack_capacity> >,
1.208 + stack_capacity>() {
1.209 + }
1.210 +
1.211 + private:
1.212 + DISALLOW_EVIL_CONSTRUCTORS(StackWString);
1.213 +};
1.214 +
1.215 +// StackVector
1.216 +//
1.217 +// Example:
1.218 +// StackVector<int, 16> foo;
1.219 +// foo->push_back(22); // we have overloaded operator->
1.220 +// foo[0] = 10; // as well as operator[]
1.221 +template<typename T, size_t stack_capacity>
1.222 +class StackVector : public StackContainer<
1.223 + std::vector<T, StackAllocator<T, stack_capacity> >,
1.224 + stack_capacity> {
1.225 + public:
1.226 + StackVector() : StackContainer<
1.227 + std::vector<T, StackAllocator<T, stack_capacity> >,
1.228 + stack_capacity>() {
1.229 + }
1.230 +
1.231 + // We need to put this in STL containers sometimes, which requires a copy
1.232 + // constructor. We can't call the regular copy constructor because that will
1.233 + // take the stack buffer from the original. Here, we create an empty object
1.234 + // and make a stack buffer of its own.
1.235 + StackVector(const StackVector<T, stack_capacity>& other)
1.236 + : StackContainer<
1.237 + std::vector<T, StackAllocator<T, stack_capacity> >,
1.238 + stack_capacity>() {
1.239 + this->container().assign(other->begin(), other->end());
1.240 + }
1.241 +
1.242 + StackVector<T, stack_capacity>& operator=(
1.243 + const StackVector<T, stack_capacity>& other) {
1.244 + this->container().assign(other->begin(), other->end());
1.245 + return *this;
1.246 + }
1.247 +
1.248 + // Vectors are commonly indexed, which isn't very convenient even with
1.249 + // operator-> (using "->at()" does exception stuff we don't want).
1.250 + T& operator[](size_t i) { return this->container().operator[](i); }
1.251 + const T& operator[](size_t i) const {
1.252 + return this->container().operator[](i);
1.253 + }
1.254 +};
1.255 +
1.256 +#endif // BASE_STACK_CONTAINER_H_
