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