ceph/src/boost/boost/container/node_allocator.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2008-2013. Distributed under the Boost
   4 // Software License, Version 1.0. (See accompanying file
   5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 //
   7 // See http://www.boost.org/libs/container for documentation.
   8 //
   9 //////////////////////////////////////////////////////////////////////////////
  10
  11 #ifndef BOOST_CONTAINER_POOLED_NODE_ALLOCATOR_HPP
  12 #define BOOST_CONTAINER_POOLED_NODE_ALLOCATOR_HPP
  13
  14 #ifndef BOOST_CONFIG_HPP
  15 #  include <boost/config.hpp>
  16 #endif
  17
  18 #if defined(BOOST_HAS_PRAGMA_ONCE)
  19 #  pragma once
  20 #endif
  21
  22 #include <boost/container/detail/config_begin.hpp>
  23 #include <boost/container/detail/workaround.hpp>
  24 #include <boost/container/container_fwd.hpp>
  25 #include <boost/container/throw_exception.hpp>
  26 #include <boost/container/detail/node_pool.hpp>
  27 #include <boost/container/detail/mpl.hpp>
  28 #include <boost/container/detail/multiallocation_chain.hpp>
  29 #include <boost/container/detail/dlmalloc.hpp>
  30 #include <boost/container/detail/singleton.hpp>
  31
  32 #include <boost/assert.hpp>
  33 #include <boost/static_assert.hpp>
  34 #include <cstddef>
  35
  36 namespace boost {
  37 namespace container {
  38
  39 //!An STL node allocator that uses a modified DlMalloc as memory
  40 //!source.
  41 //!
  42 //!This node allocator shares a segregated storage between all instances
  43 //!of node_allocator with equal sizeof(T).
  44 //!
  45 //!NodesPerBlock is the number of nodes allocated at once when the allocator
  46 //!runs out of nodes
  47 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
  48 template
  49    < class T
  50    , std::size_t NodesPerBlock = NodeAlloc_nodes_per_block>
  51 #else
  52 template
  53    < class T
  54    , std::size_t NodesPerBlock
  55    , std::size_t Version>
  56 #endif
  57 class node_allocator
  58 {
  59    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  60    //! If Version is 1, the allocator is a STL conforming allocator. If Version is 2,
  61    //! the allocator offers advanced expand in place and burst allocation capabilities.
  62    public:
  63    typedef unsigned int allocation_type;
  64    typedef node_allocator<T, NodesPerBlock, Version>   self_t;
  65
  66    static const std::size_t nodes_per_block = NodesPerBlock;
  67
  68    BOOST_STATIC_ASSERT((Version <=2));
  69    #endif
  70
  71    public:
  72    //-------
  73    typedef T                                    value_type;
  74    typedef T *                                  pointer;
  75    typedef const T *                            const_pointer;
  76    typedef typename ::boost::container::
  77       container_detail::unvoid_ref<T>::type     reference;
  78    typedef typename ::boost::container::
  79       container_detail::unvoid_ref<const T>::type     const_reference;
  80    typedef std::size_t                          size_type;
  81    typedef std::ptrdiff_t                       difference_type;
  82
  83    typedef boost::container::container_detail::
  84       version_type<self_t, Version>             version;
  85
  86    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  87    typedef boost::container::container_detail::
  88       basic_multiallocation_chain<void*>              multiallocation_chain_void;
  89    typedef boost::container::container_detail::
  90       transform_multiallocation_chain
  91          <multiallocation_chain_void, T>              multiallocation_chain;
  92    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
  93
  94    //!Obtains node_allocator from
  95    //!node_allocator
  96    template<class T2>
  97    struct rebind
  98    {
  99       typedef node_allocator< T2, NodesPerBlock
 100                             #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 101                             , Version
 102                             #endif
 103                             > other;
 104    };
 105
 106    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 107    private:
 108    //!Not assignable from related node_allocator
 109    template<class T2, std::size_t N2>
 110    node_allocator& operator=
 111       (const node_allocator<T2, N2>&);
 112    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 113
 114    public:
 115
 116    //!Default constructor
 117    node_allocator() BOOST_NOEXCEPT_OR_NOTHROW
 118    {}
 119
 120    //!Copy constructor from other node_allocator.
 121    node_allocator(const node_allocator &) BOOST_NOEXCEPT_OR_NOTHROW
 122    {}
 123
 124    //!Copy constructor from related node_allocator.
 125    template<class T2>
 126    node_allocator
 127       (const node_allocator<T2, NodesPerBlock
 128             #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
 129             , Version
 130             #endif
 131             > &) BOOST_NOEXCEPT_OR_NOTHROW
 132    {}
 133
 134    //!Destructor
 135    ~node_allocator() BOOST_NOEXCEPT_OR_NOTHROW
 136    {}
 137
 138    //!Returns the number of elements that could be allocated.
 139    //!Never throws
 140    size_type max_size() const
 141    {  return size_type(-1)/sizeof(T);   }
 142
 143    //!Allocate memory for an array of count elements.
 144    //!Throws std::bad_alloc if there is no enough memory
 145    pointer allocate(size_type count, const void * = 0)
 146    {
 147       if(BOOST_UNLIKELY(count > this->max_size()))
 148          boost::container::throw_bad_alloc();
 149
 150       if(Version == 1 && count == 1){
 151          typedef container_detail::shared_node_pool
 152             <sizeof(T), NodesPerBlock> shared_pool_t;
 153          typedef container_detail::singleton_default<shared_pool_t> singleton_t;
 154          return pointer(static_cast<T*>(singleton_t::instance().allocate_node()));
 155       }
 156       else{
 157          void *ret = dlmalloc_malloc(count*sizeof(T));
 158          if(BOOST_UNLIKELY(!ret))
 159             boost::container::throw_bad_alloc();
 160          return static_cast<pointer>(ret);
 161       }
 162    }
 163
 164    //!Deallocate allocated memory.
 165    //!Never throws
 166    void deallocate(const pointer &ptr, size_type count) BOOST_NOEXCEPT_OR_NOTHROW
 167    {
 168       (void)count;
 169       if(Version == 1 && count == 1){
 170          typedef container_detail::shared_node_pool
 171             <sizeof(T), NodesPerBlock> shared_pool_t;
 172          typedef container_detail::singleton_default<shared_pool_t> singleton_t;
 173          singleton_t::instance().deallocate_node(ptr);
 174       }
 175       else{
 176          dlmalloc_free(ptr);
 177       }
 178    }
 179
 180    //!Deallocates all free blocks of the pool
 181    static void deallocate_free_blocks() BOOST_NOEXCEPT_OR_NOTHROW
 182    {
 183       typedef container_detail::shared_node_pool
 184          <sizeof(T), NodesPerBlock> shared_pool_t;
 185       typedef container_detail::singleton_default<shared_pool_t> singleton_t;
 186       singleton_t::instance().deallocate_free_blocks();
 187    }
 188
 189    pointer allocation_command
 190       (allocation_type command, size_type limit_size, size_type &prefer_in_recvd_out_size, pointer &reuse)
 191    {
 192       BOOST_STATIC_ASSERT(( Version > 1 ));
 193       pointer ret = this->priv_allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse);
 194       if(BOOST_UNLIKELY(!ret && !(command & BOOST_CONTAINER_NOTHROW_ALLOCATION)))
 195          boost::container::throw_bad_alloc();
 196       return ret;
 197    }
 198
 199    //!Returns maximum the number of objects the previously allocated memory
 200    //!pointed by p can hold.
 201    size_type size(pointer p) const BOOST_NOEXCEPT_OR_NOTHROW
 202    {
 203       BOOST_STATIC_ASSERT(( Version > 1 ));
 204       return dlmalloc_size(p);
 205    }
 206
 207    //!Allocates just one object. Memory allocated with this function
 208    //!must be deallocated only with deallocate_one().
 209    //!Throws bad_alloc if there is no enough memory
 210    pointer allocate_one()
 211    {
 212       BOOST_STATIC_ASSERT(( Version > 1 ));
 213       typedef container_detail::shared_node_pool
 214          <sizeof(T), NodesPerBlock> shared_pool_t;
 215       typedef container_detail::singleton_default<shared_pool_t> singleton_t;
 216       return (pointer)singleton_t::instance().allocate_node();
 217    }
 218
 219    //!Allocates many elements of size == 1.
 220    //!Elements must be individually deallocated with deallocate_one()
 221    void allocate_individual(std::size_t num_elements, multiallocation_chain &chain)
 222    {
 223       BOOST_STATIC_ASSERT(( Version > 1 ));
 224       typedef container_detail::shared_node_pool
 225          <sizeof(T), NodesPerBlock> shared_pool_t;
 226       typedef container_detail::singleton_default<shared_pool_t> singleton_t;
 227       typename shared_pool_t::multiallocation_chain ch;
 228       singleton_t::instance().allocate_nodes(num_elements, ch);
 229       chain.incorporate_after(chain.before_begin(), (T*)&*ch.begin(), (T*)&*ch.last(), ch.size());
 230    }
 231
 232    //!Deallocates memory previously allocated with allocate_one().
 233    //!You should never use deallocate_one to deallocate memory allocated
 234    //!with other functions different from allocate_one(). Never throws
 235    void deallocate_one(pointer p) BOOST_NOEXCEPT_OR_NOTHROW
 236    {
 237       BOOST_STATIC_ASSERT(( Version > 1 ));
 238       typedef container_detail::shared_node_pool
 239          <sizeof(T), NodesPerBlock> shared_pool_t;
 240       typedef container_detail::singleton_default<shared_pool_t> singleton_t;
 241       singleton_t::instance().deallocate_node(p);
 242    }
 243
 244    void deallocate_individual(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW
 245    {
 246       BOOST_STATIC_ASSERT(( Version > 1 ));
 247       typedef container_detail::shared_node_pool
 248          <sizeof(T), NodesPerBlock> shared_pool_t;
 249       typedef container_detail::singleton_default<shared_pool_t> singleton_t;
 250       typename shared_pool_t::multiallocation_chain ch(&*chain.begin(), &*chain.last(), chain.size());
 251       singleton_t::instance().deallocate_nodes(ch);
 252    }
 253
 254    //!Allocates many elements of size elem_size.
 255    //!Elements must be individually deallocated with deallocate()
 256    void allocate_many(size_type elem_size, std::size_t n_elements, multiallocation_chain &chain)
 257    {
 258       BOOST_STATIC_ASSERT(( Version > 1 ));
 259       dlmalloc_memchain ch;
 260       BOOST_CONTAINER_MEMCHAIN_INIT(&ch);
 261       if(BOOST_UNLIKELY(!dlmalloc_multialloc_nodes(n_elements, elem_size*sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch))){
 262          boost::container::throw_bad_alloc();
 263       }
 264       chain.incorporate_after( chain.before_begin()
 265                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
 266                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
 267                              , BOOST_CONTAINER_MEMCHAIN_SIZE(&ch));
 268    }
 269
 270    //!Allocates n_elements elements, each one of size elem_sizes[i]
 271    //!Elements must be individually deallocated with deallocate()
 272    void allocate_many(const size_type *elem_sizes, size_type n_elements, multiallocation_chain &chain)
 273    {
 274       BOOST_STATIC_ASSERT(( Version > 1 ));
 275       dlmalloc_memchain ch;
 276       dlmalloc_multialloc_arrays(n_elements, elem_sizes, sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch);
 277       if(BOOST_UNLIKELY(BOOST_CONTAINER_MEMCHAIN_EMPTY(&ch))){
 278          boost::container::throw_bad_alloc();
 279       }
 280       chain.incorporate_after( chain.before_begin()
 281                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
 282                              , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch)
 283                              , BOOST_CONTAINER_MEMCHAIN_SIZE(&ch));
 284    }
 285
 286    void deallocate_many(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW
 287    {
 288       BOOST_STATIC_ASSERT(( Version > 1 ));
 289       void *first = &*chain.begin();
 290       void *last  = &*chain.last();
 291       size_t num  = chain.size();
 292       dlmalloc_memchain ch;
 293       BOOST_CONTAINER_MEMCHAIN_INIT_FROM(&ch, first, last, num);
 294       dlmalloc_multidealloc(&ch);
 295    }
 296
 297    //!Swaps allocators. Does not throw. If each allocator is placed in a
 298    //!different memory segment, the result is undefined.
 299    friend void swap(self_t &, self_t &) BOOST_NOEXCEPT_OR_NOTHROW
 300    {}
 301
 302    //!An allocator always compares to true, as memory allocated with one
 303    //!instance can be deallocated by another instance
 304    friend bool operator==(const node_allocator &, const node_allocator &) BOOST_NOEXCEPT_OR_NOTHROW
 305    {  return true;   }
 306
 307    //!An allocator always compares to false, as memory allocated with one
 308    //!instance can be deallocated by another instance
 309    friend bool operator!=(const node_allocator &, const node_allocator &) BOOST_NOEXCEPT_OR_NOTHROW
 310    {  return false;   }
 311
 312    private:
 313    pointer priv_allocation_command
 314       (allocation_type command,   std::size_t limit_size
 315       ,size_type &prefer_in_recvd_out_size
 316       ,pointer &reuse)
 317    {
 318       std::size_t const preferred_size = prefer_in_recvd_out_size;
 319       dlmalloc_command_ret_t ret = {0 , 0};
 320       if((limit_size > this->max_size()) | (preferred_size > this->max_size())){
 321          return pointer();
 322       }
 323       std::size_t l_size = limit_size*sizeof(T);
 324       std::size_t p_size = preferred_size*sizeof(T);
 325       std::size_t r_size;
 326       {
 327          void* reuse_ptr_void = reuse;
 328          ret = dlmalloc_allocation_command(command, sizeof(T), l_size, p_size, &r_size, reuse_ptr_void);
 329          reuse = static_cast<T*>(reuse_ptr_void);
 330       }
 331       prefer_in_recvd_out_size = r_size/sizeof(T);
 332       return (pointer)ret.first;
 333    }
 334 };
 335
 336 }  //namespace container {
 337 }  //namespace boost {
 338
 339 #include <boost/container/detail/config_end.hpp>
 340
 341 #endif   //#ifndef BOOST_CONTAINER_POOLED_NODE_ALLOCATOR_HPP