boost/container/allocator.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2007-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_ALLOCATOR_HPP
0012 #define BOOST_CONTAINER_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/detail/version_type.hpp>
0026 #include <boost/container/throw_exception.hpp>
0027 #include <boost/container/detail/dlmalloc.hpp>
0028 #include <boost/container/detail/multiallocation_chain.hpp>
0029
0030 #include <boost/move/detail/force_ptr.hpp>
0031
0032 #include <cstddef>
0033 #include <cassert>
0034
0035 //!\file
0036
0037 namespace boost {
0038 namespace container {
0039
0040 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0041
0042 template<unsigned Version, unsigned int AllocationDisableMask>
0043 class allocator<void, Version, AllocationDisableMask>
0044 {
0045    typedef allocator<void, Version, AllocationDisableMask>   self_t;
0046    public:
0047    typedef void                                 value_type;
0048    typedef void *                               pointer;
0049    typedef const void*                          const_pointer;
0050    typedef int &                                reference;
0051    typedef const int &                          const_reference;
0052    typedef std::size_t                          size_type;
0053    typedef std::ptrdiff_t                       difference_type;
0054    typedef boost::container::dtl::
0055       version_type<self_t, Version>             version;
0056
0057    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0058    typedef boost::container::dtl::
0059          basic_multiallocation_chain<void*>        multiallocation_chain;
0060    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0061
0062    //!Obtains an allocator that allocates
0063    //!objects of type T2
0064    template<class T2>
0065    struct rebind
0066    {
0067       typedef allocator< T2
0068                        #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0069                        , Version, AllocationDisableMask
0070                        #endif
0071                        > other;
0072    };
0073
0074    //!Default constructor
0075    //!Never throws
0076    allocator()
0077    {}
0078
0079    //!Constructor from other allocator.
0080    //!Never throws
0081    allocator(const allocator &)
0082    {}
0083
0084    //!Constructor from related allocator.
0085    //!Never throws
0086    template<class T2>
0087       allocator(const allocator<T2, Version, AllocationDisableMask> &)
0088    {}
0089 };
0090
0091 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0092
0093 //! This class is an extended STL-compatible that offers advanced allocation mechanism
0094 //!(in-place expansion, shrinking, burst-allocation...)
0095 //!
0096 //! This allocator is a wrapper around a modified DLmalloc.
0097 //! If Version is 1, the allocator is a STL conforming allocator. If Version is 2,
0098 //! the allocator offers advanced expand in place and burst allocation capabilities.
0099 //!
0100 //! AllocationDisableMask works only if Version is 2 and it can be an inclusive OR
0101 //! of allocation types the user wants to disable.
0102 template< class T
0103         , unsigned Version BOOST_CONTAINER_DOCONLY(=2)
0104         , unsigned int AllocationDisableMask BOOST_CONTAINER_DOCONLY(=0)>
0105 class allocator
0106 {
0107    typedef unsigned int allocation_type;
0108    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0109    private:
0110
0111    //Self type
0112    typedef allocator<T, Version, AllocationDisableMask>   self_t;
0113
0114    //Not assignable from related allocator
0115    template<class T2, unsigned int Version2, unsigned int AllocationDisableMask2>
0116    allocator& operator=(const allocator<T2, Version2, AllocationDisableMask2>&);
0117
0118    BOOST_STATIC_CONSTEXPR unsigned int ForbiddenMask =
0119       BOOST_CONTAINER_ALLOCATE_NEW | BOOST_CONTAINER_EXPAND_BWD | BOOST_CONTAINER_EXPAND_FWD ;
0120
0121    //The mask can't disable all the allocation types
0122    BOOST_CONTAINER_STATIC_ASSERT((  (AllocationDisableMask & ForbiddenMask) != ForbiddenMask  ));
0123
0124    //The mask is only valid for version 2 allocators
0125    BOOST_CONTAINER_STATIC_ASSERT((  Version != 1 || (AllocationDisableMask == 0)  ));
0126
0127    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0128
0129    public:
0130    typedef T                                    value_type;
0131    typedef T *                                  pointer;
0132    typedef const T *                            const_pointer;
0133    typedef T &                                  reference;
0134    typedef const T &                            const_reference;
0135    typedef std::size_t                          size_type;
0136    typedef std::ptrdiff_t                       difference_type;
0137
0138    typedef boost::container::dtl::
0139       version_type<self_t, Version>                version;
0140
0141    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0142    typedef boost::container::dtl::
0143          basic_multiallocation_chain<void*>        void_multiallocation_chain;
0144
0145    typedef boost::container::dtl::
0146       transform_multiallocation_chain
0147          <void_multiallocation_chain, T>           multiallocation_chain;
0148    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0149
0150    //!Obtains an allocator that allocates
0151    //!objects of type T2
0152    template<class T2>
0153    struct rebind
0154    {
0155       typedef allocator<T2, Version, AllocationDisableMask> other;
0156    };
0157
0158    //!Default constructor
0159    //!Never throws
0160    allocator() BOOST_NOEXCEPT_OR_NOTHROW
0161    {}
0162
0163    //!Constructor from other allocator.
0164    //!Never throws
0165    allocator(const allocator &) BOOST_NOEXCEPT_OR_NOTHROW
0166    {}
0167
0168    //!Constructor from related allocator.
0169    //!Never throws
0170    template<class T2>
0171    allocator(const allocator<T2
0172             #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0173             , Version, AllocationDisableMask
0174             #endif
0175             > &) BOOST_NOEXCEPT_OR_NOTHROW
0176    {}
0177
0178    //!Allocates memory for an array of count elements.
0179    //!Throws bad_alloc if there is no enough memory
0180    //!If Version is 2, this allocated memory can only be deallocated
0181    //!with deallocate() or (for Version == 2) deallocate_many()
0182    BOOST_CONTAINER_ATTRIBUTE_NODISCARD pointer allocate(size_type count, const void * hint= 0)
0183    {
0184       (void)hint;
0185       if(count > size_type(-1)/(2u*sizeof(T)))
0186          boost::container::throw_bad_alloc();
0187       void *ret = dlmalloc_malloc(count*sizeof(T));
0188       if(!ret)
0189          boost::container::throw_bad_alloc();
0190       return static_cast<pointer>(ret);
0191    }
0192
0193    //!Deallocates previously allocated memory.
0194    //!Never throws
0195    inline void deallocate(pointer ptr, size_type) BOOST_NOEXCEPT_OR_NOTHROW
0196    {  dlmalloc_free(ptr);  }
0197
0198    //!Returns the maximum number of elements that could be allocated.
0199    //!Never throws
0200    inline size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
0201    {  return size_type(-1)/(2u*sizeof(T));   }
0202
0203    //!Swaps two allocators, does nothing
0204    //!because this allocator is stateless
0205    inline friend void swap(self_t &, self_t &) BOOST_NOEXCEPT_OR_NOTHROW
0206    {}
0207
0208    //!An allocator always compares to true, as memory allocated with one
0209    //!instance can be deallocated by another instance
0210    BOOST_CONTAINER_ATTRIBUTE_NODISCARD
0211       friend bool operator==(const allocator &, const allocator &) BOOST_NOEXCEPT_OR_NOTHROW
0212    {  return true;   }
0213
0214    //!An allocator always compares to false, as memory allocated with one
0215    //!instance can be deallocated by another instance
0216    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0217       friend bool operator!=(const allocator &, const allocator &) BOOST_NOEXCEPT_OR_NOTHROW
0218    {  return false;   }
0219
0220    //!An advanced function that offers in-place expansion shrink to fit and new allocation
0221    //!capabilities. Memory allocated with this function can only be deallocated with deallocate()
0222    //!or deallocate_many().
0223    //!This function is available only with Version == 2
0224    BOOST_CONTAINER_ATTRIBUTE_NODISCARD pointer allocation_command(allocation_type command,
0225                          size_type limit_size,
0226                          size_type &prefer_in_recvd_out_size,
0227                          pointer &reuse)
0228    {
0229       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0230       const allocation_type mask(AllocationDisableMask);
0231       command &= ~mask;
0232       pointer ret = this->priv_allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse);
0233       if(!ret && !(command & BOOST_CONTAINER_NOTHROW_ALLOCATION))
0234          boost::container::throw_bad_alloc();
0235       return ret;
0236    }
0237
0238    //!Returns maximum the number of objects the previously allocated memory
0239    //!pointed by p can hold.
0240    //!Memory must not have been allocated with
0241    //!allocate_one or allocate_individual.
0242    //!This function is available only with Version == 2
0243    BOOST_CONTAINER_ATTRIBUTE_NODISCARD size_type size(pointer p) const BOOST_NOEXCEPT_OR_NOTHROW
0244    {
0245       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0246       return dlmalloc_size(p);
0247    }
0248
0249    //!Allocates just one object. Memory allocated with this function
0250    //!must be deallocated only with deallocate_one().
0251    //!Throws bad_alloc if there is no enough memory
0252    //!This function is available only with Version == 2
0253    BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline pointer allocate_one()
0254    {
0255       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0256       return this->allocate(1);
0257    }
0258
0259    //!Allocates many elements of size == 1.
0260    //!Elements must be individually deallocated with deallocate_one()
0261    //!This function is available only with Version == 2
0262    inline void allocate_individual(std::size_t num_elements, multiallocation_chain &chain)
0263    {
0264       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0265       this->allocate_many(1, num_elements, chain);
0266    }
0267
0268    //!Deallocates memory previously allocated with allocate_one().
0269    //!You should never use deallocate_one to deallocate memory allocated
0270    //!with other functions different from allocate_one() or allocate_individual.
0271    //Never throws
0272    void deallocate_one(pointer p) BOOST_NOEXCEPT_OR_NOTHROW
0273    {
0274       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0275       return this->deallocate(p, 1);
0276    }
0277
0278    //!Deallocates memory allocated with allocate_one() or allocate_individual().
0279    //!This function is available only with Version == 2
0280    inline
0281       void deallocate_individual(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW
0282    {
0283       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0284       return this->deallocate_many(chain);
0285    }
0286
0287    //!Allocates many elements of size elem_size.
0288    //!Elements must be individually deallocated with deallocate()
0289    //!This function is available only with Version == 2
0290    void allocate_many(size_type elem_size, std::size_t n_elements, multiallocation_chain &chain)
0291    {
0292       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0293       dlmalloc_memchain ch;
0294       BOOST_CONTAINER_MEMCHAIN_INIT(&ch);
0295       if(!dlmalloc_multialloc_nodes(n_elements, elem_size*sizeof(T), BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch)){
0296          boost::container::throw_bad_alloc();
0297       }
0298       chain.incorporate_after(chain.before_begin()
0299                              ,(T*)BOOST_CONTAINER_MEMCHAIN_FIRSTMEM(&ch)
0300                              ,(T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
0301                              ,BOOST_CONTAINER_MEMCHAIN_SIZE(&ch) );
0302 /*
0303       if(!dlmalloc_multialloc_nodes( n_elements, elem_size*sizeof(T), BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS
0304                                    , move_detail::force_ptr<dlmalloc_memchain *>(&chain))){
0305          boost::container::throw_bad_alloc();
0306       }*/
0307    }
0308
0309    //!Allocates n_elements elements, each one of size elem_sizes[i]
0310    //!Elements must be individually deallocated with deallocate()
0311    //!This function is available only with Version == 2
0312    void allocate_many(const size_type *elem_sizes, size_type n_elements, multiallocation_chain &chain)
0313    {
0314       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0315       dlmalloc_memchain ch;
0316       BOOST_CONTAINER_MEMCHAIN_INIT(&ch);
0317       if(!dlmalloc_multialloc_arrays(n_elements, elem_sizes, sizeof(T), BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch)){
0318          boost::container::throw_bad_alloc();
0319       }
0320       chain.incorporate_after(chain.before_begin()
0321                              ,(T*)BOOST_CONTAINER_MEMCHAIN_FIRSTMEM(&ch)
0322                              ,(T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
0323                              ,BOOST_CONTAINER_MEMCHAIN_SIZE(&ch) );
0324       /*
0325       if(!dlmalloc_multialloc_arrays( n_elements, elem_sizes, sizeof(T), BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS
0326                                     , move_detail::force_ptr<dlmalloc_memchain *>(&chain))){
0327          boost::container::throw_bad_alloc();
0328       }*/
0329    }
0330
0331    //!Deallocates several elements allocated by
0332    //!allocate_many(), allocate(), or allocation_command().
0333    //!This function is available only with Version == 2
0334    void deallocate_many(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW
0335    {
0336       BOOST_CONTAINER_STATIC_ASSERT(( Version > 1 ));
0337       dlmalloc_memchain ch;
0338       void *beg(&*chain.begin()), *last(&*chain.last());
0339       size_t size(chain.size());
0340       BOOST_CONTAINER_MEMCHAIN_INIT_FROM(&ch, beg, last, size);
0341       dlmalloc_multidealloc(&ch);
0342       //dlmalloc_multidealloc(move_detail::force_ptr<dlmalloc_memchain *>(&chain));
0343    }
0344
0345    private:
0346
0347    pointer priv_allocation_command
0348       (allocation_type command,    std::size_t limit_size
0349       ,size_type &prefer_in_recvd_out_size
0350       ,pointer &reuse_ptr)
0351    {
0352       std::size_t const preferred_size = prefer_in_recvd_out_size;
0353       dlmalloc_command_ret_t ret = {0 , 0};
0354       if((limit_size > this->max_size()) || (preferred_size > this->max_size())){
0355          return pointer();
0356       }
0357       std::size_t l_size = limit_size*sizeof(T);
0358       std::size_t p_size = preferred_size*sizeof(T);
0359       std::size_t r_size;
0360       {
0361          void* reuse_ptr_void = reuse_ptr;
0362          ret = dlmalloc_allocation_command(command, sizeof(T), l_size, p_size, &r_size, reuse_ptr_void);
0363          reuse_ptr = ret.second ? static_cast<T*>(reuse_ptr_void) : 0;
0364       }
0365       prefer_in_recvd_out_size = r_size/sizeof(T);
0366       return (pointer)ret.first;
0367    }
0368 };
0369
0370 }  //namespace container {
0371 }  //namespace boost {
0372
0373 #include <boost/container/detail/config_end.hpp>
0374
0375 #endif   //BOOST_CONTAINER_ALLOCATOR_HPP
0376