boost/container/node_allocator.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2008-2013. Distributed under the Boost
0004 // Software License, Version 1.0. (See accompanying file
0005 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // See http://www.boost.org/libs/container for documentation.
0008 //
0009 //////////////////////////////////////////////////////////////////////////////
0010
0011 #ifndef BOOST_CONTAINER_POOLED_NODE_ALLOCATOR_HPP
0012 #define BOOST_CONTAINER_POOLED_NODE_ALLOCATOR_HPP
0013
0014 #ifndef BOOST_CONFIG_HPP
0015 #  include <boost/config.hpp>
0016 #endif
0017
0018 #if defined(BOOST_HAS_PRAGMA_ONCE)
0019 #  pragma once
0020 #endif
0021
0022 #include <boost/container/detail/config_begin.hpp>
0023 #include <boost/container/detail/workaround.hpp>
0024 #include <boost/container/container_fwd.hpp>
0025 #include <boost/container/throw_exception.hpp>
0026 #include <boost/container/detail/node_pool.hpp>
0027 #include <boost/container/detail/mpl.hpp>
0028 #include <boost/container/detail/multiallocation_chain.hpp>
0029 #include <boost/container/detail/dlmalloc.hpp>
0030 #include <boost/container/detail/singleton.hpp>
0031
0032 #include <boost/assert.hpp>
0033 #include <boost/static_assert.hpp>
0034 #include <cstddef>
0035
0036 namespace boost {
0037 namespace container {
0038
0039 //!An STL node allocator that uses a modified DlMalloc as memory
0040 //!source.
0041 //!
0042 //!This node allocator shares a segregated storage between all instances
0043 //!of node_allocator with equal sizeof(T).
0044 //!
0045 //!NodesPerBlock is the number of nodes allocated at once when the allocator
0046 //!runs out of nodes
0047 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
0048 template
0049    < class T
0050    , std::size_t NodesPerBlock = NodeAlloc_nodes_per_block>
0051 #else
0052 template
0053    < class T
0054    , std::size_t NodesPerBlock
0055    , std::size_t Version>
0056 #endif
0057 class node_allocator
0058 {
0059    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0060    //! If Version is 1, the allocator is a STL conforming allocator. If Version is 2,
0061    //! the allocator offers advanced expand in place and burst allocation capabilities.
0062    public:
0063    typedef unsigned int allocation_type;
0064    typedef node_allocator<T, NodesPerBlock, Version>   self_t;
0065
0066    static const std::size_t nodes_per_block = NodesPerBlock;
0067
0068    BOOST_STATIC_ASSERT((Version <=2));
0069    #endif
0070
0071    public:
0072    //-------
0073    typedef T                                    value_type;
0074    typedef T *                                  pointer;
0075    typedef const T *                            const_pointer;
0076    typedef typename ::boost::container::
0077       dtl::unvoid_ref<T>::type     reference;
0078    typedef typename ::boost::container::
0079       dtl::unvoid_ref<const T>::type     const_reference;
0080    typedef std::size_t                          size_type;
0081    typedef std::ptrdiff_t                       difference_type;
0082
0083    typedef boost::container::dtl::
0084       version_type<self_t, (unsigned int) Version>             version;
0085
0086    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0087    typedef boost::container::dtl::
0088       basic_multiallocation_chain<void*>              multiallocation_chain_void;
0089    typedef boost::container::dtl::
0090       transform_multiallocation_chain
0091          <multiallocation_chain_void, T>              multiallocation_chain;
0092    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0093
0094    //!Obtains node_allocator from
0095    //!node_allocator
0096    template<class T2>
0097    struct rebind
0098    {
0099       typedef node_allocator< T2, NodesPerBlock
0100                             #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0101                             , Version
0102                             #endif
0103                             > other;
0104    };
0105
0106    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0107    private:
0108    //!Not assignable from related node_allocator
0109    template<class T2, std::size_t N2>
0110    node_allocator& operator=
0111       (const node_allocator<T2, N2>&);
0112    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0113
0114    public:
0115
0116    //!Default constructor
0117    node_allocator() BOOST_NOEXCEPT_OR_NOTHROW
0118    {}
0119
0120    //!Copy constructor from other node_allocator.
0121    node_allocator(const node_allocator &) BOOST_NOEXCEPT_OR_NOTHROW
0122    {}
0123
0124    //!Copy constructor from related node_allocator.
0125    template<class T2>
0126    node_allocator
0127       (const node_allocator<T2, NodesPerBlock
0128             #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0129             , Version
0130             #endif
0131             > &) BOOST_NOEXCEPT_OR_NOTHROW
0132    {}
0133
0134    //!Destructor
0135    ~node_allocator() BOOST_NOEXCEPT_OR_NOTHROW
0136    {}
0137
0138    //!Returns the number of elements that could be allocated.
0139    //!Never throws
0140    size_type max_size() const
0141    {  return size_type(-1)/sizeof(T);   }
0142
0143    //!Allocate memory for an array of count elements.
0144    //!Throws bad_alloc if there is no enough memory
0145    pointer allocate(size_type count, const void * = 0)
0146    {
0147       if(BOOST_UNLIKELY(count > this->max_size()))
0148          boost::container::throw_bad_alloc();
0149
0150       if(Version == 1 && count == 1){
0151          typedef dtl::shared_node_pool
0152             <sizeof(T), NodesPerBlock> shared_pool_t;
0153          typedef dtl::singleton_default<shared_pool_t> singleton_t;
0154          return pointer(static_cast<T*>(singleton_t::instance().allocate_node()));
0155       }
0156       else{
0157          void *ret = dlmalloc_malloc(count*sizeof(T));
0158          if(BOOST_UNLIKELY(!ret))
0159             boost::container::throw_bad_alloc();
0160          return static_cast<pointer>(ret);
0161       }
0162    }
0163
0164    //!Deallocate allocated memory.
0165    //!Never throws
0166    void deallocate(const pointer &ptr, size_type count) BOOST_NOEXCEPT_OR_NOTHROW
0167    {
0168       (void)count;
0169       if(Version == 1 && count == 1){
0170          typedef dtl::shared_node_pool
0171             <sizeof(T), NodesPerBlock> shared_pool_t;
0172          typedef dtl::singleton_default<shared_pool_t> singleton_t;
0173          singleton_t::instance().deallocate_node(ptr);
0174       }
0175       else{
0176          dlmalloc_free(ptr);
0177       }
0178    }
0179
0180    //!Deallocates all free blocks of the pool
0181    static void deallocate_free_blocks() BOOST_NOEXCEPT_OR_NOTHROW
0182    {
0183       typedef dtl::shared_node_pool
0184          <sizeof(T), NodesPerBlock> shared_pool_t;
0185       typedef dtl::singleton_default<shared_pool_t> singleton_t;
0186       singleton_t::instance().deallocate_free_blocks();
0187    }
0188
0189    pointer allocation_command
0190       (allocation_type command, size_type limit_size, size_type &prefer_in_recvd_out_size, pointer &reuse)
0191    {
0192       BOOST_STATIC_ASSERT(( Version > 1 ));
0193       pointer ret = this->priv_allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse);
0194       if(BOOST_UNLIKELY(!ret && !(command & BOOST_CONTAINER_NOTHROW_ALLOCATION)))
0195          boost::container::throw_bad_alloc();
0196       return ret;
0197    }
0198
0199    //!Returns maximum the number of objects the previously allocated memory
0200    //!pointed by p can hold.
0201    size_type size(pointer p) const BOOST_NOEXCEPT_OR_NOTHROW
0202    {
0203       BOOST_STATIC_ASSERT(( Version > 1 ));
0204       return dlmalloc_size(p);
0205    }
0206
0207    //!Allocates just one object. Memory allocated with this function
0208    //!must be deallocated only with deallocate_one().
0209    //!Throws bad_alloc if there is no enough memory
0210    pointer allocate_one()
0211    {
0212       BOOST_STATIC_ASSERT(( Version > 1 ));
0213       typedef dtl::shared_node_pool
0214          <sizeof(T), NodesPerBlock> shared_pool_t;
0215       typedef dtl::singleton_default<shared_pool_t> singleton_t;
0216       return (pointer)singleton_t::instance().allocate_node();
0217    }
0218
0219    //!Allocates many elements of size == 1.
0220    //!Elements must be individually deallocated with deallocate_one()
0221    void allocate_individual(std::size_t num_elements, multiallocation_chain &chain)
0222    {
0223       BOOST_STATIC_ASSERT(( Version > 1 ));
0224       typedef dtl::shared_node_pool
0225          <sizeof(T), NodesPerBlock> shared_pool_t;
0226       typedef dtl::singleton_default<shared_pool_t> singleton_t;
0227       typename shared_pool_t::multiallocation_chain ch;
0228       singleton_t::instance().allocate_nodes(num_elements, ch);
0229       chain.incorporate_after(chain.before_begin(), (T*)&*ch.begin(), (T*)&*ch.last(), ch.size());
0230    }
0231
0232    //!Deallocates memory previously allocated with allocate_one().
0233    //!You should never use deallocate_one to deallocate memory allocated
0234    //!with other functions different from allocate_one(). Never throws
0235    void deallocate_one(pointer p) BOOST_NOEXCEPT_OR_NOTHROW
0236    {
0237       BOOST_STATIC_ASSERT(( Version > 1 ));
0238       typedef dtl::shared_node_pool
0239          <sizeof(T), NodesPerBlock> shared_pool_t;
0240       typedef dtl::singleton_default<shared_pool_t> singleton_t;
0241       singleton_t::instance().deallocate_node(p);
0242    }
0243
0244    void deallocate_individual(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW
0245    {
0246       BOOST_STATIC_ASSERT(( Version > 1 ));
0247       typedef dtl::shared_node_pool
0248          <sizeof(T), NodesPerBlock> shared_pool_t;
0249       typedef dtl::singleton_default<shared_pool_t> singleton_t;
0250       typename shared_pool_t::multiallocation_chain ch(&*chain.begin(), &*chain.last(), chain.size());
0251       singleton_t::instance().deallocate_nodes(ch);
0252    }
0253
0254    //!Allocates many elements of size elem_size.
0255    //!Elements must be individually deallocated with deallocate()
0256    void allocate_many(size_type elem_size, std::size_t n_elements, multiallocation_chain &chain)
0257    {
0258       BOOST_STATIC_ASSERT(( Version > 1 ));
0259       dlmalloc_memchain ch;
0260       BOOST_CONTAINER_MEMCHAIN_INIT(&ch);
0261       if(BOOST_UNLIKELY(!dlmalloc_multialloc_nodes(n_elements, elem_size*sizeof(T), BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch))){
0262          boost::container::throw_bad_alloc();
0263       }
0264       chain.incorporate_after( chain.before_begin()
0265                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
0266                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
0267                              , BOOST_CONTAINER_MEMCHAIN_SIZE(&ch));
0268    }
0269
0270    //!Allocates n_elements elements, each one of size elem_sizes[i]
0271    //!Elements must be individually deallocated with deallocate()
0272    void allocate_many(const size_type *elem_sizes, size_type n_elements, multiallocation_chain &chain)
0273    {
0274       BOOST_STATIC_ASSERT(( Version > 1 ));
0275       dlmalloc_memchain ch;
0276       dlmalloc_multialloc_arrays(n_elements, elem_sizes, sizeof(T), BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch);
0277       if(BOOST_UNLIKELY(BOOST_CONTAINER_MEMCHAIN_EMPTY(&ch))){
0278          boost::container::throw_bad_alloc();
0279       }
0280       chain.incorporate_after( chain.before_begin()
0281                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
0282                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
0283                              , BOOST_CONTAINER_MEMCHAIN_SIZE(&ch));
0284    }
0285
0286    void deallocate_many(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW
0287    {
0288       BOOST_STATIC_ASSERT(( Version > 1 ));
0289       void *first = &*chain.begin();
0290       void *last  = &*chain.last();
0291       size_t num  = chain.size();
0292       dlmalloc_memchain ch;
0293       BOOST_CONTAINER_MEMCHAIN_INIT_FROM(&ch, first, last, num);
0294       dlmalloc_multidealloc(&ch);
0295    }
0296
0297    //!Swaps allocators. Does not throw. If each allocator is placed in a
0298    //!different memory segment, the result is undefined.
0299    friend void swap(self_t &, self_t &) BOOST_NOEXCEPT_OR_NOTHROW
0300    {}
0301
0302    //!An allocator always compares to true, as memory allocated with one
0303    //!instance can be deallocated by another instance
0304    friend bool operator==(const node_allocator &, const node_allocator &) BOOST_NOEXCEPT_OR_NOTHROW
0305    {  return true;   }
0306
0307    //!An allocator always compares to false, as memory allocated with one
0308    //!instance can be deallocated by another instance
0309    friend bool operator!=(const node_allocator &, const node_allocator &) BOOST_NOEXCEPT_OR_NOTHROW
0310    {  return false;   }
0311
0312    private:
0313    pointer priv_allocation_command
0314       (allocation_type command,   std::size_t limit_size
0315       ,size_type &prefer_in_recvd_out_size
0316       ,pointer &reuse)
0317    {
0318       std::size_t const preferred_size = prefer_in_recvd_out_size;
0319       dlmalloc_command_ret_t ret = {0 , 0};
0320       if((limit_size > this->max_size()) || (preferred_size > this->max_size())){
0321          return pointer();
0322       }
0323       std::size_t l_size = limit_size*sizeof(T);
0324       std::size_t p_size = preferred_size*sizeof(T);
0325       std::size_t r_size;
0326       {
0327          void* reuse_ptr_void = reuse;
0328          ret = dlmalloc_allocation_command(command, sizeof(T), l_size, p_size, &r_size, reuse_ptr_void);
0329          reuse = static_cast<T*>(reuse_ptr_void);
0330       }
0331       prefer_in_recvd_out_size = r_size/sizeof(T);
0332       return (pointer)ret.first;
0333    }
0334 };
0335
0336 }  //namespace container {
0337 }  //namespace boost {
0338
0339 #include <boost/container/detail/config_end.hpp>
0340
0341 #endif   //#ifndef BOOST_CONTAINER_POOLED_NODE_ALLOCATOR_HPP