Chris@16: // Copyright (C) 2000, 2001 Stephen Cleary
Chris@16: // Copyright (C) 2010 Paul A. Bristow added Doxygen comments.
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // See http://www.boost.org for updates, documentation, and revision history.
Chris@16: 
Chris@16: #ifndef BOOST_POOL_ALLOC_HPP
Chris@16: #define BOOST_POOL_ALLOC_HPP
Chris@16: 
Chris@16: /*!
Chris@16:   \file
Chris@16:   \brief C++ Standard Library compatible pool-based allocators.
Chris@16:   \details  This header provides two template types - 
Chris@16:   \ref pool_allocator and \ref fast_pool_allocator -
Chris@16:   that can be used for fast and efficient memory allocation
Chris@16:   in conjunction with the C++ Standard Library containers.
Chris@16: 
Chris@16:   These types both satisfy the Standard Allocator requirements [20.1.5]
Chris@16:   and the additional requirements in [20.1.5/4],
Chris@16:   so they can be used with either Standard or user-supplied containers.
Chris@16: 
Chris@16:   In addition, the fast_pool_allocator also provides an additional allocation
Chris@16:   and an additional deallocation function:
Chris@16: 
Chris@16: <table>
Chris@16: <tr><th>Expression</th><th>Return Type</th><th>Semantic Equivalence<th></tr>
Chris@16: <tr><td><tt>PoolAlloc::allocate()</tt></td><td><tt>T *</tt></td><td><tt>PoolAlloc::allocate(1)</tt></tr>
Chris@16: <tr><td><tt>PoolAlloc::deallocate(p)</tt></td><td>void</tt></td><td><tt>PoolAlloc::deallocate(p, 1)</tt></tr>
Chris@16: </table>
Chris@16: 
Chris@16: The typedef user_allocator publishes the value of the UserAllocator template parameter.
Chris@16: 
Chris@16: <b>Notes</b>
Chris@16: 
Chris@16: If the allocation functions run out of memory, they will throw <tt>std::bad_alloc</tt>.
Chris@16: 
Chris@16: The underlying Pool type used by the allocators is accessible through the Singleton Pool Interface.
Chris@16: The identifying tag used for pool_allocator is pool_allocator_tag,
Chris@16: and the tag used for fast_pool_allocator is fast_pool_allocator_tag.
Chris@16: All template parameters of the allocators (including implementation-specific ones)
Chris@16: determine the type of the underlying Pool,
Chris@16: with the exception of the first parameter T, whose size is used instead.
Chris@16: 
Chris@16: Since the size of T is used to determine the type of the underlying Pool,
Chris@16: each allocator for different types of the same size will share the same underlying pool.
Chris@16: The tag class prevents pools from being shared between pool_allocator and fast_pool_allocator.
Chris@16: For example, on a system where
Chris@16: <tt>sizeof(int) == sizeof(void *)</tt>, <tt>pool_allocator<int></tt> and <tt>pool_allocator<void *></tt>
Chris@16: will both allocate/deallocate from/to the same pool.
Chris@16: 
Chris@16: If there is only one thread running before main() starts and after main() ends,
Chris@16: then both allocators are completely thread-safe.
Chris@16: 
Chris@16: <b>Compiler and STL Notes</b>
Chris@16: 
Chris@16: A number of common STL libraries contain bugs in their using of allocators.
Chris@16: Specifically, they pass null pointers to the deallocate function,
Chris@16: which is explicitly forbidden by the Standard [20.1.5 Table 32].
Chris@16: PoolAlloc will work around these libraries if it detects them;
Chris@16: currently, workarounds are in place for:
Chris@16: Borland C++ (Builder and command-line compiler)
Chris@16: with default (RogueWave) library, ver. 5 and earlier,
Chris@16: STLport (with any compiler), ver. 4.0 and earlier.
Chris@16: */
Chris@16: 
Chris@16: // std::numeric_limits
Chris@16: #include <boost/limits.hpp>
Chris@16: // new, std::bad_alloc
Chris@16: #include <new>
Chris@16: 
Chris@16: #include <boost/throw_exception.hpp>
Chris@16: #include <boost/pool/poolfwd.hpp>
Chris@16: 
Chris@16: // boost::singleton_pool
Chris@16: #include <boost/pool/singleton_pool.hpp>
Chris@16: 
Chris@16: #include <boost/detail/workaround.hpp>
Chris@16: 
Chris@16: #ifdef BOOST_POOL_INSTRUMENT
Chris@16: #include <iostream>
Chris@16: #include <iomanip>
Chris@16: #endif
Chris@16: 
Chris@16: // The following code will be put into Boost.Config in a later revision
Chris@16: #if defined(_RWSTD_VER) || defined(__SGI_STL_PORT) || \
Chris@16:     BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x582))
Chris@16:  #define BOOST_NO_PROPER_STL_DEALLOCATE
Chris@16: #endif
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: #ifdef BOOST_POOL_INSTRUMENT
Chris@16: 
Chris@16: template <bool b>
Chris@16: struct debug_info
Chris@16: {
Chris@16:    static unsigned allocated;
Chris@16: };
Chris@16: 
Chris@16: template <bool b>
Chris@16: unsigned debug_info<b>::allocated = 0;
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16:  //! Simple tag type used by pool_allocator as an argument to the
Chris@16:  //! underlying singleton_pool.
Chris@16:  struct pool_allocator_tag
Chris@16: {
Chris@16: };
Chris@16: 
Chris@16: /*!  \brief A C++ Standard Library conforming allocator, based on an underlying pool.
Chris@16: 
Chris@16:   Template parameters for pool_allocator are defined as follows:
Chris@16: 
Chris@16:   <b>T</b> Type of object to allocate/deallocate.
Chris@16: 
Chris@16:   <b>UserAllocator</B>. Defines the method that the underlying Pool will use to allocate memory from the system. See 
Chris@16:   <a href="boost_pool/pool/pooling.html#boost_pool.pool.pooling.user_allocator">User Allocators</a> for details.
Chris@16: 
Chris@16:   <b>Mutex</b> Allows the user to determine the type of synchronization to be used on the underlying singleton_pool. 
Chris@16: 
Chris@16:   <b>NextSize</b> The value of this parameter is passed to the underlying singleton_pool when it is created.
Chris@16: 
Chris@16:   <b>MaxSize</b> Limit on the maximum size used.
Chris@16: 
Chris@16:   \attention
Chris@16:   The underlying singleton_pool used by the this allocator
Chris@16:   constructs a pool instance that
Chris@16:   <b>is never freed</b>.  This means that memory allocated
Chris@16:   by the allocator can be still used after main() has
Chris@16:   completed, but may mean that some memory checking programs
Chris@16:   will complain about leaks.
Chris@16:  
Chris@16:   
Chris@16:   */
Chris@16: template <typename T,
Chris@16:     typename UserAllocator,
Chris@16:     typename Mutex,
Chris@16:     unsigned NextSize,
Chris@16:     unsigned MaxSize >
Chris@16: class pool_allocator
Chris@16: {
Chris@16:   public:
Chris@16:     typedef T value_type;  //!< value_type of template parameter T.
Chris@16:     typedef UserAllocator user_allocator;  //!< allocator that defines the method that the underlying Pool will use to allocate memory from the system.
Chris@16:     typedef Mutex mutex; //!< typedef mutex publishes the value of the template parameter Mutex.
Chris@16:     BOOST_STATIC_CONSTANT(unsigned, next_size = NextSize); //!< next_size publishes the values of the template parameter NextSize.
Chris@16: 
Chris@16:     typedef value_type * pointer; //!<
Chris@16:     typedef const value_type * const_pointer;
Chris@16:     typedef value_type & reference;
Chris@16:     typedef const value_type & const_reference;
Chris@16:     typedef typename pool<UserAllocator>::size_type size_type;
Chris@16:     typedef typename pool<UserAllocator>::difference_type difference_type;
Chris@16: 
Chris@16:     //! \brief Nested class rebind allows for transformation from
Chris@16:     //! pool_allocator<T> to pool_allocator<U>.
Chris@16:     //!
Chris@16:     //! Nested class rebind allows for transformation from
Chris@16:     //! pool_allocator<T> to pool_allocator<U> via the member
Chris@16:     //! typedef other.
Chris@16:     template <typename U>
Chris@16:     struct rebind
Chris@16:     { //
Chris@16:       typedef pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other;
Chris@16:     };
Chris@16: 
Chris@16:   public:
Chris@16:     pool_allocator()
Chris@16:     { /*! Results in default construction of the underlying singleton_pool IFF an
Chris@16:        instance of this allocator is constructed during global initialization (
Chris@16:          required to ensure construction of singleton_pool IFF an
Chris@16:          instance of this allocator is constructed during global
Chris@16:          initialization. See ticket #2359 for a complete explanation at
Chris@16:          http://svn.boost.org/trac/boost/ticket/2359) .
Chris@16:        */
Chris@16:       singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex,
Chris@16:                      NextSize, MaxSize>::is_from(0);
Chris@16:     }
Chris@16: 
Chris@16:     // default copy constructor.
Chris@16: 
Chris@16:     // default assignment operator.
Chris@16: 
Chris@16:     // not explicit, mimicking std::allocator [20.4.1]
Chris@16:     template <typename U>
Chris@16:     pool_allocator(const pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> &)
Chris@16:     { /*! Results in the default construction of the underlying singleton_pool, this
Chris@16:          is required to ensure construction of singleton_pool IFF an
Chris@16:          instance of this allocator is constructed during global
Chris@16:          initialization. See ticket #2359 for a complete explanation
Chris@16:          at http://svn.boost.org/trac/boost/ticket/2359 .
Chris@16:        */
Chris@16:       singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex,
Chris@16:                      NextSize, MaxSize>::is_from(0);
Chris@16:     }
Chris@16: 
Chris@16:     // default destructor
Chris@16: 
Chris@16:     static pointer address(reference r)
Chris@16:     { return &r; }
Chris@16:     static const_pointer address(const_reference s)
Chris@16:     { return &s; }
Chris@16:     static size_type max_size()
Chris@16:     { return (std::numeric_limits<size_type>::max)(); }
Chris@16:     static void construct(const pointer ptr, const value_type & t)
Chris@16:     { new (ptr) T(t); }
Chris@16:     static void destroy(const pointer ptr)
Chris@16:     {
Chris@16:       ptr->~T();
Chris@16:       (void) ptr; // avoid unused variable warning.
Chris@16:     }
Chris@16: 
Chris@16:     bool operator==(const pool_allocator &) const
Chris@16:     { return true; }
Chris@16:     bool operator!=(const pool_allocator &) const
Chris@16:     { return false; }
Chris@16: 
Chris@16:     static pointer allocate(const size_type n)
Chris@16:     {
Chris@16: #ifdef BOOST_POOL_INSTRUMENT
Chris@16:        debug_info<true>::allocated += n * sizeof(T);
Chris@16:        std::cout << "Allocating " << n << " * " << sizeof(T) << " bytes...\n"
Chris@16:           "Total allocated is now " << debug_info<true>::allocated << std::endl;
Chris@16: #endif
Chris@16:       const pointer ret = static_cast<pointer>(
Chris@16:           singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex,
Chris@16:               NextSize, MaxSize>::ordered_malloc(n) );
Chris@16:       if ((ret == 0) && n)
Chris@16:         boost::throw_exception(std::bad_alloc());
Chris@16:       return ret;
Chris@16:     }
Chris@16:     static pointer allocate(const size_type n, const void * const)
Chris@16:     { //! allocate n bytes
Chris@16:     //! \param n bytes to allocate.
Chris@16:     //! \param unused.
Chris@16:       return allocate(n);
Chris@16:     }
Chris@16:     static void deallocate(const pointer ptr, const size_type n)
Chris@16:     {  //! Deallocate n bytes from ptr
Chris@16:        //! \param ptr location to deallocate from.
Chris@16:        //! \param n number of bytes to deallocate.
Chris@16: #ifdef BOOST_POOL_INSTRUMENT
Chris@16:        debug_info<true>::allocated -= n * sizeof(T);
Chris@16:        std::cout << "Deallocating " << n << " * " << sizeof(T) << " bytes...\n"
Chris@16:           "Total allocated is now " << debug_info<true>::allocated << std::endl;
Chris@16: #endif
Chris@16: #ifdef BOOST_NO_PROPER_STL_DEALLOCATE
Chris@16:       if (ptr == 0 || n == 0)
Chris@16:         return;
Chris@16: #endif
Chris@16:       singleton_pool<pool_allocator_tag, sizeof(T), UserAllocator, Mutex,
Chris@16:           NextSize, MaxSize>::ordered_free(ptr, n);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: /*! \brief Specialization of pool_allocator<void>.
Chris@16: 
Chris@16: Specialization of pool_allocator for type void: required by the standard to make this a conforming allocator type.
Chris@16: */
Chris@16: template<
Chris@16:     typename UserAllocator,
Chris@16:     typename Mutex,
Chris@16:     unsigned NextSize,
Chris@16:     unsigned MaxSize>
Chris@16: class pool_allocator<void, UserAllocator, Mutex, NextSize, MaxSize>
Chris@16: {
Chris@16: public:
Chris@16:     typedef void*       pointer;
Chris@16:     typedef const void* const_pointer;
Chris@16:     typedef void        value_type;
Chris@16:     //! \brief Nested class rebind allows for transformation from
Chris@16:     //! pool_allocator<T> to pool_allocator<U>.
Chris@16:     //!
Chris@16:     //! Nested class rebind allows for transformation from
Chris@16:     //! pool_allocator<T> to pool_allocator<U> via the member
Chris@16:     //! typedef other.
Chris@16:     template <class U> 
Chris@16:     struct rebind
Chris@16:     {
Chris@16:        typedef pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other;
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: //! Simple tag type used by fast_pool_allocator as a template parameter to the underlying singleton_pool.
Chris@16: struct fast_pool_allocator_tag
Chris@16: {
Chris@16: };
Chris@16: 
Chris@16:  /*! \brief A C++ Standard Library conforming allocator geared towards allocating single chunks.
Chris@16: 
Chris@16:   While class template <tt>pool_allocator</tt> is a more general-purpose solution geared towards
Chris@16:   efficiently servicing requests for any number of contiguous chunks,
Chris@16:   <tt>fast_pool_allocator</tt> is also a general-purpose solution,
Chris@16:   but is geared towards efficiently servicing requests for one chunk at a time;
Chris@16:   it will work for contiguous chunks, but not as well as <tt>pool_allocator</tt>.
Chris@16: 
Chris@16:   If you are seriously concerned about performance,
Chris@16:   use <tt>fast_pool_allocator</tt> when dealing with containers such as <tt>std::list</tt>,
Chris@16:   and use <tt>pool_allocator</tt> when dealing with containers such as <tt>std::vector</tt>.
Chris@16: 
Chris@16:   The template parameters are defined as follows:
Chris@16: 
Chris@16:   <b>T</b> Type of object to allocate/deallocate.
Chris@16: 
Chris@16:   <b>UserAllocator</b>. Defines the method that the underlying Pool will use to allocate memory from the system. 
Chris@16:   See <a href="boost_pool/pool/pooling.html#boost_pool.pool.pooling.user_allocator">User Allocators</a> for details.
Chris@16: 
Chris@16:   <b>Mutex</b> Allows the user to determine the type of synchronization to be used on the underlying <tt>singleton_pool</tt>.
Chris@16: 
Chris@16:   <b>NextSize</b> The value of this parameter is passed to the underlying Pool when it is created.
Chris@16: 
Chris@16:   <b>MaxSize</b> Limit on the maximum size used.
Chris@16: 
Chris@16:    \attention
Chris@16:   The underlying singleton_pool used by the this allocator
Chris@16:   constructs a pool instance that
Chris@16:   <b>is never freed</b>.  This means that memory allocated
Chris@16:   by the allocator can be still used after main() has
Chris@16:   completed, but may mean that some memory checking programs
Chris@16:   will complain about leaks.
Chris@16:  
Chris@16:  */
Chris@16: 
Chris@16: template <typename T,
Chris@16:     typename UserAllocator,
Chris@16:     typename Mutex,
Chris@16:     unsigned NextSize,
Chris@16:     unsigned MaxSize >
Chris@16: class fast_pool_allocator
Chris@16: {
Chris@16:   public:
Chris@16:     typedef T value_type;
Chris@16:     typedef UserAllocator user_allocator;
Chris@16:     typedef Mutex mutex;
Chris@16:     BOOST_STATIC_CONSTANT(unsigned, next_size = NextSize);
Chris@16: 
Chris@16:     typedef value_type * pointer;
Chris@16:     typedef const value_type * const_pointer;
Chris@16:     typedef value_type & reference;
Chris@16:     typedef const value_type & const_reference;
Chris@16:     typedef typename pool<UserAllocator>::size_type size_type;
Chris@16:     typedef typename pool<UserAllocator>::difference_type difference_type;
Chris@16: 
Chris@16:     //! \brief Nested class rebind allows for transformation from
Chris@16:     //! fast_pool_allocator<T> to fast_pool_allocator<U>.
Chris@16:     //!
Chris@16:     //! Nested class rebind allows for transformation from
Chris@16:     //! fast_pool_allocator<T> to fast_pool_allocator<U> via the member
Chris@16:     //! typedef other.
Chris@16:     template <typename U>
Chris@16:     struct rebind
Chris@16:     {
Chris@16:       typedef fast_pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other;
Chris@16:     };
Chris@16: 
Chris@16:   public:
Chris@16:     fast_pool_allocator()
Chris@16:     {
Chris@16:       //! Ensures construction of the underlying singleton_pool IFF an
Chris@16:       //! instance of this allocator is constructed during global
Chris@16:       //! initialization. See ticket #2359 for a complete explanation
Chris@16:       //! at http://svn.boost.org/trac/boost/ticket/2359 .
Chris@16:       singleton_pool<fast_pool_allocator_tag, sizeof(T),
Chris@16:                      UserAllocator, Mutex, NextSize, MaxSize>::is_from(0);
Chris@16:     }
Chris@16: 
Chris@16:     // Default copy constructor used.
Chris@16: 
Chris@16:     // Default assignment operator used.
Chris@16: 
Chris@16:     // Not explicit, mimicking std::allocator [20.4.1]
Chris@16:     template <typename U>
Chris@16:     fast_pool_allocator(
Chris@16:         const fast_pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> &)
Chris@16:     {
Chris@16:       //! Ensures construction of the underlying singleton_pool IFF an
Chris@16:       //! instance of this allocator is constructed during global
Chris@16:       //! initialization. See ticket #2359 for a complete explanation
Chris@16:       //! at http://svn.boost.org/trac/boost/ticket/2359 .
Chris@16:       singleton_pool<fast_pool_allocator_tag, sizeof(T),
Chris@16:                      UserAllocator, Mutex, NextSize, MaxSize>::is_from(0);
Chris@16:     }
Chris@16: 
Chris@16:     // Default destructor used.
Chris@16: 
Chris@16:     static pointer address(reference r)
Chris@16:     {
Chris@16:       return &r;
Chris@16:     }
Chris@16:     static const_pointer address(const_reference s)
Chris@16:     { return &s; }
Chris@16:     static size_type max_size()
Chris@16:     { return (std::numeric_limits<size_type>::max)(); }
Chris@16:     void construct(const pointer ptr, const value_type & t)
Chris@16:     { new (ptr) T(t); }
Chris@16:     void destroy(const pointer ptr)
Chris@16:     { //! Destroy ptr using destructor.
Chris@16:       ptr->~T();
Chris@16:       (void) ptr; // Avoid unused variable warning.
Chris@16:     }
Chris@16: 
Chris@16:     bool operator==(const fast_pool_allocator &) const
Chris@16:     { return true; }
Chris@16:     bool operator!=(const fast_pool_allocator &) const
Chris@16:     { return false; }
Chris@16: 
Chris@16:     static pointer allocate(const size_type n)
Chris@16:     {
Chris@16:       const pointer ret = (n == 1) ?
Chris@16:           static_cast<pointer>(
Chris@16:               (singleton_pool<fast_pool_allocator_tag, sizeof(T),
Chris@16:                   UserAllocator, Mutex, NextSize, MaxSize>::malloc)() ) :
Chris@16:           static_cast<pointer>(
Chris@16:               singleton_pool<fast_pool_allocator_tag, sizeof(T),
Chris@16:                   UserAllocator, Mutex, NextSize, MaxSize>::ordered_malloc(n) );
Chris@16:       if (ret == 0)
Chris@16:         boost::throw_exception(std::bad_alloc());
Chris@16:       return ret;
Chris@16:     }
Chris@16:     static pointer allocate(const size_type n, const void * const)
Chris@16:     { //! Allocate memory .
Chris@16:       return allocate(n);
Chris@16:     }
Chris@16:     static pointer allocate()
Chris@16:     { //! Allocate memory.
Chris@16:       const pointer ret = static_cast<pointer>(
Chris@16:           (singleton_pool<fast_pool_allocator_tag, sizeof(T),
Chris@16:               UserAllocator, Mutex, NextSize, MaxSize>::malloc)() );
Chris@16:       if (ret == 0)
Chris@16:         boost::throw_exception(std::bad_alloc());
Chris@16:       return ret;
Chris@16:     }
Chris@16:     static void deallocate(const pointer ptr, const size_type n)
Chris@16:     { //! Deallocate memory.
Chris@16: 
Chris@16: #ifdef BOOST_NO_PROPER_STL_DEALLOCATE
Chris@16:       if (ptr == 0 || n == 0)
Chris@16:         return;
Chris@16: #endif
Chris@16:       if (n == 1)
Chris@16:         (singleton_pool<fast_pool_allocator_tag, sizeof(T),
Chris@16:             UserAllocator, Mutex, NextSize, MaxSize>::free)(ptr);
Chris@16:       else
Chris@16:         (singleton_pool<fast_pool_allocator_tag, sizeof(T),
Chris@16:             UserAllocator, Mutex, NextSize, MaxSize>::free)(ptr, n);
Chris@16:     }
Chris@16:     static void deallocate(const pointer ptr)
Chris@16:     { //! deallocate/free
Chris@16:       (singleton_pool<fast_pool_allocator_tag, sizeof(T),
Chris@16:           UserAllocator, Mutex, NextSize, MaxSize>::free)(ptr);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: /*!  \brief Specialization of fast_pool_allocator<void>.
Chris@16: 
Chris@16: Specialization of fast_pool_allocator<void> required to make the allocator standard-conforming.
Chris@16: */
Chris@16: template<
Chris@16:     typename UserAllocator,
Chris@16:     typename Mutex,
Chris@16:     unsigned NextSize,
Chris@16:     unsigned MaxSize >
Chris@16: class fast_pool_allocator<void, UserAllocator, Mutex, NextSize, MaxSize>
Chris@16: {
Chris@16: public:
Chris@16:     typedef void*       pointer;
Chris@16:     typedef const void* const_pointer;
Chris@16:     typedef void        value_type;
Chris@16: 
Chris@16:     //! \brief Nested class rebind allows for transformation from
Chris@16:     //! fast_pool_allocator<T> to fast_pool_allocator<U>.
Chris@16:     //!
Chris@16:     //! Nested class rebind allows for transformation from
Chris@16:     //! fast_pool_allocator<T> to fast_pool_allocator<U> via the member
Chris@16:     //! typedef other.
Chris@16:     template <class U> struct rebind
Chris@16:     {
Chris@16:         typedef fast_pool_allocator<U, UserAllocator, Mutex, NextSize, MaxSize> other;
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif