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_NODE_ALLOCATOR_HPP
0012 #define BOOST_CONTAINER_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/move/detail/iterator_to_raw_pointer.hpp>
0030 #include <boost/container/detail/dlmalloc.hpp>
0031 #include <boost/container/detail/singleton.hpp>
0032
0033 #include <boost/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    BOOST_STATIC_CONSTEXPR std::size_t nodes_per_block = NodesPerBlock;
0067
0068    BOOST_CONTAINER_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_CONTAINER_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_CONTAINER_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_CONTAINER_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_CONTAINER_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()
0230                              , (T*)boost::movelib::iterator_to_raw_pointer(ch.begin())
0231                              , (T*)boost::movelib::iterator_to_raw_pointer(ch.last())
0232                              , ch.size());
0233    }
0234
0235    //!Deallocates memory previously allocated with allocate_one().
0236    //!You should never use deallocate_one to deallocate memory allocated
0237    //!with other functions different from allocate_one(). Never throws
0238    void deallocate_one(pointer p) BOOST_NOEXCEPT_OR_NOTHROW
0239    {
0240       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0241       typedef dtl::shared_node_pool
0242          <sizeof(T), NodesPerBlock> shared_pool_t;
0243       typedef dtl::singleton_default<shared_pool_t> singleton_t;
0244       singleton_t::instance().deallocate_node(p);
0245    }
0246
0247    void deallocate_individual(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW
0248    {
0249       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0250       typedef dtl::shared_node_pool
0251          <sizeof(T), NodesPerBlock> shared_pool_t;
0252       typedef dtl::singleton_default<shared_pool_t> singleton_t;
0253       typename shared_pool_t::multiallocation_chain ch
0254          ( boost::movelib::iterator_to_raw_pointer(chain.begin())
0255          , boost::movelib::iterator_to_raw_pointer(chain.last())
0256          , chain.size());
0257       singleton_t::instance().deallocate_nodes(ch);
0258    }
0259
0260    //!Allocates many elements of size elem_size.
0261    //!Elements must be individually deallocated with deallocate()
0262    void allocate_many(size_type elem_size, std::size_t n_elements, multiallocation_chain &chain)
0263    {
0264       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0265       dlmalloc_memchain ch;
0266       BOOST_CONTAINER_MEMCHAIN_INIT(&ch);
0267       if(BOOST_UNLIKELY(!dlmalloc_multialloc_nodes(n_elements, elem_size*sizeof(T), BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch))){
0268          boost::container::throw_bad_alloc();
0269       }
0270       chain.incorporate_after( chain.before_begin()
0271                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
0272                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
0273                              , BOOST_CONTAINER_MEMCHAIN_SIZE(&ch));
0274    }
0275
0276    //!Allocates n_elements elements, each one of size elem_sizes[i]
0277    //!Elements must be individually deallocated with deallocate()
0278    void allocate_many(const size_type *elem_sizes, size_type n_elements, multiallocation_chain &chain)
0279    {
0280       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0281       dlmalloc_memchain ch;
0282       dlmalloc_multialloc_arrays(n_elements, elem_sizes, sizeof(T), BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch);
0283       if(BOOST_UNLIKELY(BOOST_CONTAINER_MEMCHAIN_EMPTY(&ch))){
0284          boost::container::throw_bad_alloc();
0285       }
0286       chain.incorporate_after( chain.before_begin()
0287                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
0288                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
0289                              , BOOST_CONTAINER_MEMCHAIN_SIZE(&ch));
0290    }
0291
0292    void deallocate_many(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW
0293    {
0294       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0295       void *first = boost::movelib::iterator_to_raw_pointer(chain.begin());
0296       void *last  = boost::movelib::iterator_to_raw_pointer(chain.last());
0297       size_t num  = chain.size();
0298       dlmalloc_memchain ch;
0299       BOOST_CONTAINER_MEMCHAIN_INIT_FROM(&ch, first, last, num);
0300       dlmalloc_multidealloc(&ch);
0301    }
0302
0303    //!Swaps allocators. Does not throw. If each allocator is placed in a
0304    //!different memory segment, the result is undefined.
0305    friend void swap(self_t &, self_t &) BOOST_NOEXCEPT_OR_NOTHROW
0306    {}
0307
0308    //!An allocator always compares to true, as memory allocated with one
0309    //!instance can be deallocated by another instance
0310    friend bool operator==(const node_allocator &, const node_allocator &) BOOST_NOEXCEPT_OR_NOTHROW
0311    {  return true;   }
0312
0313    //!An allocator always compares to false, as memory allocated with one
0314    //!instance can be deallocated by another instance
0315    friend bool operator!=(const node_allocator &, const node_allocator &) BOOST_NOEXCEPT_OR_NOTHROW
0316    {  return false;   }
0317
0318    private:
0319    pointer priv_allocation_command
0320       (allocation_type command,   std::size_t limit_size
0321       ,size_type &prefer_in_recvd_out_size
0322       ,pointer &reuse)
0323    {
0324       std::size_t const preferred_size = prefer_in_recvd_out_size;
0325       dlmalloc_command_ret_t ret = {0 , 0};
0326       if((limit_size > this->max_size()) || (preferred_size > this->max_size())){
0327          return pointer();
0328       }
0329       std::size_t l_size = limit_size*sizeof(T);
0330       std::size_t p_size = preferred_size*sizeof(T);
0331       std::size_t r_size;
0332       {
0333          void* reuse_ptr_void = reuse;
0334          ret = dlmalloc_allocation_command(command, sizeof(T), l_size, p_size, &r_size, reuse_ptr_void);
0335          reuse = static_cast<T*>(reuse_ptr_void);
0336       }
0337       prefer_in_recvd_out_size = r_size/sizeof(T);
0338       return (pointer)ret.first;
0339    }
0340 };
0341
0342 }  //namespace container {
0343 }  //namespace boost {
0344
0345 #include <boost/container/detail/config_end.hpp>
0346
0347 #endif   //#ifndef BOOST_CONTAINER_NODE_ALLOCATOR_HPP