diff options
Diffstat (limited to 'ipc/chromium/src/base/stack_container.h')
| -rw-r--r-- | ipc/chromium/src/base/stack_container.h | 244 |
1 files changed, 244 insertions, 0 deletions
diff --git a/ipc/chromium/src/base/stack_container.h b/ipc/chromium/src/base/stack_container.h new file mode 100644 index 0000000000..d9add9904c --- /dev/null +++ b/ipc/chromium/src/base/stack_container.h @@ -0,0 +1,244 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +// Copyright (c) 2006-2008 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. + +#ifndef BASE_STACK_CONTAINER_H_ +#define BASE_STACK_CONTAINER_H_ + +#include <string> +#include <vector> + +#include "base/basictypes.h" + +// 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 reinterpret_cast<T*>(stack_buffer_); } + const T* stack_buffer() const { + return reinterpret_cast<const T*>(stack_buffer_); + } + + // + // IMPORTANT: Take care to ensure that stack_buffer_ is aligned + // since it is used to mimic an array of T. + // Be careful while declaring any unaligned types (like bool) + // before stack_buffer_. + // + + // 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. + char stack_buffer_[sizeof(T[stack_capacity])]; + + // 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) + : 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> + explicit StackAllocator(const StackAllocator<U, other_capacity>& other) + : 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_EVIL_CONSTRUCTORS(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_EVIL_CONSTRUCTORS(StackString); +}; + +// StackWString +template <size_t stack_capacity> +class StackWString + : public StackContainer< + std::basic_string<wchar_t, std::char_traits<wchar_t>, + StackAllocator<wchar_t, stack_capacity> >, + stack_capacity> { + public: + StackWString() + : StackContainer< + std::basic_string<wchar_t, std::char_traits<wchar_t>, + StackAllocator<wchar_t, stack_capacity> >, + stack_capacity>() {} + + private: + DISALLOW_EVIL_CONSTRUCTORS(StackWString); +}; + +// 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); + } +}; + +#endif // BASE_STACK_CONTAINER_H_ |