stack_container.h - mozsearch

/* -*- 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_

Source code

Revision control

Copy as Markdown

Other Tools