summaryrefslogtreecommitdiffstats
path: root/ipc/chromium/src/base/stack_container.h
diff options
context:
space:
mode:
Diffstat (limited to 'ipc/chromium/src/base/stack_container.h')
-rw-r--r--ipc/chromium/src/base/stack_container.h255
1 files changed, 255 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 000000000..23991c2f9
--- /dev/null
+++ b/ipc/chromium/src/base/stack_container.h
@@ -0,0 +1,255 @@
+/* -*- 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_