stack_containers.hpp

#pragma once
//-----------------------------------------------------------------------------
// Class:   Stack Containers 
// Authors: Modified by LiXizhi
// Emails:  LiXizhi@yeah.net
// Company: ParaEngine corporation
// Date:    2008.6.20
//-----------------------------------------------------------------------------
// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//    * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//    * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//    * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.

#include <string>
#include <vector>

namespace ParaEngine
{
    // A macro to disallow the copy constructor and operator= functions
    // This should be used in the private: declarations for a class
#define DISALLOW_COPY_AND_ASSIGN(TypeName) \
    TypeName(const TypeName&);               \
    void operator=(const TypeName&)

    // 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>
        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_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);
    };

    // 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);
        }
    };
}   // ParaEngine