container/detail/adaptive_node_pool_impl.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2005-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_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP
0012 #define BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_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
0025 // container
0026 #include <boost/container/container_fwd.hpp>
0027 #include <boost/container/throw_exception.hpp>
0028 // container/detail
0029 #include <boost/container/detail/pool_common.hpp>
0030 #include <boost/container/detail/iterator.hpp>
0031 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
0032 #include <boost/container/detail/math_functions.hpp>
0033 #include <boost/container/detail/placement_new.hpp>
0034 #include <boost/container/detail/mpl.hpp>
0035 #include <boost/move/detail/to_raw_pointer.hpp>
0036 #include <boost/move/detail/force_ptr.hpp>
0037 #include <boost/container/detail/type_traits.hpp>
0038 // intrusive
0039 #include <boost/intrusive/pointer_traits.hpp>
0040 #include <boost/intrusive/set.hpp>
0041 #include <boost/intrusive/list.hpp>
0042 #include <boost/intrusive/slist.hpp>
0043 // other
0044 #include <boost/assert.hpp>
0045 #include <cstddef>
0046
0047 namespace boost {
0048 namespace container {
0049
0050 namespace adaptive_pool_flag {
0051
0052 static const unsigned int none            = 0u;
0053 static const unsigned int align_only      = 1u << 0u;
0054 static const unsigned int size_ordered    = 1u << 1u;
0055 static const unsigned int address_ordered = 1u << 2u;
0056
0057 }  //namespace adaptive_pool_flag{
0058
0059 namespace dtl {
0060
0061 template<class size_type>
0062 struct hdr_offset_holder_t
0063 {
0064    hdr_offset_holder_t(size_type offset = 0)
0065       : hdr_offset(offset)
0066    {}
0067    size_type hdr_offset;
0068 };
0069
0070 template<class SizeType, unsigned int Flags>
0071 struct less_func;
0072
0073 template<class SizeType>
0074 struct less_func<SizeType, adaptive_pool_flag::none>
0075 {
0076    static bool less(SizeType, SizeType, const void *, const void *)
0077    {  return true;   }
0078 };
0079
0080 template<class SizeType>
0081 struct less_func<SizeType, adaptive_pool_flag::size_ordered>
0082 {
0083    static bool less(SizeType ls, SizeType rs, const void *, const void *)
0084    {  return ls < rs;   }
0085 };
0086
0087 template<class SizeType>
0088 struct less_func<SizeType, adaptive_pool_flag::address_ordered>
0089 {
0090    static bool less(SizeType, SizeType, const void *la, const void *ra)
0091    {  return la < ra;   }
0092 };
0093
0094 template<class SizeType>
0095 struct less_func<SizeType, adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered>
0096 {
0097    static bool less(SizeType ls, SizeType rs, const void *la, const void *ra)
0098    {  return (ls < rs) || ((ls == rs) && (la < ra));  }
0099 };
0100
0101 template<class VoidPointer, class SizeType, unsigned OrderFlags>
0102 struct block_container_traits
0103 {
0104    typedef typename bi::make_set_base_hook
0105       < bi::void_pointer<VoidPointer>
0106       , bi::optimize_size<true>
0107       , bi::link_mode<bi::normal_link> >::type hook_t;
0108
0109    template<class T>
0110    struct container
0111    {
0112       typedef typename bi::make_multiset
0113          <T, bi::base_hook<hook_t>, bi::size_type<SizeType> >::type  type;
0114    };
0115
0116    template<class Container>
0117    static void reinsert_was_used(Container &container, typename Container::reference v, bool)
0118    {
0119       typedef typename Container::const_iterator const_block_iterator;
0120       typedef typename Container::iterator       block_iterator;
0121       typedef typename Container::value_compare  value_compare;
0122
0123       const block_iterator this_block(Container::s_iterator_to(v));
0124       const const_block_iterator cendit(container.cend());
0125       block_iterator next_block(this_block);
0126
0127       if(++next_block != cendit && value_compare()(*next_block, v)){
0128          const_block_iterator next2_block(next_block);
0129          //Test if v should be swapped with next (optimization)
0130          if(++next2_block == cendit || !value_compare()(*next2_block, v)){
0131             v.swap_nodes(*next_block);
0132             BOOST_ASSERT(++next_block == this_block);
0133          }
0134          else{
0135             container.erase(this_block);
0136             container.insert(v);
0137          }
0138       }
0139    }
0140
0141    template<class Container>
0142    static void insert_was_empty(Container &container, typename Container::value_type &v, bool)
0143    {
0144       container.insert(v);
0145    }
0146
0147    template<class Container>
0148    static void erase_first(Container &container)
0149    {
0150       container.erase(container.cbegin());
0151    }
0152
0153    template<class Container>
0154    static void erase_last(Container &container)
0155    {
0156       container.erase(--container.cend());
0157    }
0158 };
0159
0160 template<class VoidPointer, class SizeType>
0161 struct block_container_traits<VoidPointer, SizeType, 0u>
0162 {
0163    typedef typename bi::make_list_base_hook
0164       < bi::void_pointer<VoidPointer>
0165       , bi::link_mode<bi::normal_link> >::type hook_t;
0166
0167    template<class T>
0168    struct container
0169    {
0170       typedef typename bi::make_list
0171          <T, bi::base_hook<hook_t>, bi::size_type<SizeType>, bi::constant_time_size<false> >::type  type;
0172    };
0173
0174    template<class Container>
0175    static void reinsert_was_used(Container &container, typename Container::value_type &v, bool is_full)
0176    {
0177       if(is_full){
0178          container.erase(Container::s_iterator_to(v));
0179          container.push_back(v);
0180       }
0181    }
0182
0183    template<class Container>
0184    static void insert_was_empty(Container &container, typename Container::value_type &v, bool is_full)
0185    {
0186       if(is_full){
0187          container.push_back(v);
0188       }
0189       else{
0190          container.push_front(v);
0191       }
0192    }
0193
0194    template<class Container>
0195    static void erase_first(Container &container)
0196    {
0197       container.pop_front();
0198    }
0199
0200    template<class Container>
0201    static void erase_last(Container &container)
0202    {
0203       container.pop_back();
0204    }
0205 };
0206
0207 /////////////////////////////
0208 //
0209 //    adaptive_pool_types
0210 //
0211 /////////////////////////////
0212 template<class MultiallocationChain, class VoidPointer, class SizeType, unsigned int Flags>
0213 struct adaptive_pool_types
0214 {
0215    typedef VoidPointer void_pointer;
0216    static const unsigned ordered = (Flags & (adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered));
0217    typedef block_container_traits<VoidPointer, SizeType, ordered> block_container_traits_t;
0218    typedef typename block_container_traits_t::hook_t hook_t;
0219    typedef hdr_offset_holder_t<SizeType> hdr_offset_holder;
0220    static const unsigned int order_flags = Flags & (adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered);
0221    typedef MultiallocationChain free_nodes_t;
0222
0223    struct block_info_t
0224       : public hdr_offset_holder,
0225         public hook_t
0226    {
0227       //An intrusive list of free node from this block
0228       free_nodes_t free_nodes;
0229       friend bool operator <(const block_info_t &l, const block_info_t &r)
0230       {
0231          return less_func<SizeType, order_flags>::
0232             less(l.free_nodes.size(), r.free_nodes.size(), &l , &r);
0233       }
0234
0235       friend bool operator ==(const block_info_t &l, const block_info_t &r)
0236       {  return &l == &r;  }
0237    };
0238    typedef typename block_container_traits_t:: template container<block_info_t>::type  block_container_t;
0239 };
0240
0241
0242 /////////////////////////////////////////////
0243 //
0244 //       candidate_power_of_2_ct
0245 //
0246 /////////////////////////////////////////////
0247 template< std::size_t alignment
0248         , std::size_t real_node_size
0249         , std::size_t payload_per_allocation
0250         , std::size_t min_elements_per_block
0251         , std::size_t hdr_size
0252         , std::size_t hdr_offset_size
0253         , std::size_t overhead_percent>
0254 struct candidate_power_of_2_ct_helper
0255 {
0256    static const std::size_t hdr_subblock_elements_alone = (alignment - hdr_size - payload_per_allocation)/real_node_size;
0257    static const std::size_t hdr_subblock_elements_first = (alignment - hdr_size - payload_per_allocation)/real_node_size;
0258    static const std::size_t elements_per_b_subblock_mid = (alignment - hdr_offset_size)/real_node_size;
0259    static const std::size_t elements_per_b_subblock_end = (alignment - hdr_offset_size - payload_per_allocation)/real_node_size;
0260    static const std::size_t num_b_subblock =
0261       hdr_subblock_elements_alone >= min_elements_per_block
0262          ? 0
0263          : (   ((hdr_subblock_elements_first + elements_per_b_subblock_end) >= min_elements_per_block)
0264                ? 1
0265                : 2 + (min_elements_per_block - hdr_subblock_elements_first - elements_per_b_subblock_end - 1)/elements_per_b_subblock_mid
0266             )
0267          ;
0268
0269    static const std::size_t num_b_subblock_mid = (num_b_subblock > 1) ? (num_b_subblock - 1) : 0;
0270
0271    static const std::size_t total_nodes = (num_b_subblock == 0)
0272                                          ? hdr_subblock_elements_alone
0273                                          : ( (num_b_subblock == 1)
0274                                            ? (hdr_subblock_elements_first + elements_per_b_subblock_end)
0275                                            : (hdr_subblock_elements_first + num_b_subblock_mid*elements_per_b_subblock_mid + elements_per_b_subblock_end)
0276                                            )
0277                                          ;
0278    static const std::size_t total_data = total_nodes*real_node_size;
0279    static const std::size_t total_size = alignment*(num_b_subblock+1);
0280    static const bool overhead_satisfied = (total_size - total_data)*100/total_size < overhead_percent;
0281 };
0282
0283 template< std::size_t initial_alignment
0284         , std::size_t real_node_size
0285         , std::size_t payload_per_allocation
0286         , std::size_t min_elements_per_block
0287         , std::size_t hdr_size
0288         , std::size_t hdr_offset_size
0289         , std::size_t overhead_percent
0290         , bool Loop = true>
0291 struct candidate_power_of_2_ct
0292 {
0293    typedef candidate_power_of_2_ct_helper
0294         < initial_alignment
0295         , real_node_size
0296         , payload_per_allocation
0297         , min_elements_per_block
0298         , hdr_size
0299         , hdr_offset_size
0300         , overhead_percent> helper_t;
0301
0302    static const std::size_t candidate_power_of_2 = initial_alignment << std::size_t(!helper_t::overhead_satisfied);
0303
0304    typedef typename candidate_power_of_2_ct
0305       < candidate_power_of_2
0306       , real_node_size
0307       , payload_per_allocation
0308       , min_elements_per_block
0309       , hdr_size
0310       , hdr_offset_size
0311       , overhead_percent
0312       , !helper_t::overhead_satisfied
0313       >::type type;
0314
0315    static const std::size_t alignment     = type::alignment;
0316    static const std::size_t num_subblocks = type::num_subblocks;
0317    static const std::size_t real_num_node = type::real_num_node;
0318 };
0319
0320 template< std::size_t initial_alignment
0321         , std::size_t real_node_size
0322         , std::size_t payload_per_allocation
0323         , std::size_t min_elements_per_block
0324         , std::size_t hdr_size
0325         , std::size_t hdr_offset_size
0326         , std::size_t overhead_percent
0327         >
0328 struct candidate_power_of_2_ct
0329       < initial_alignment
0330       , real_node_size
0331       , payload_per_allocation
0332       , min_elements_per_block
0333       , hdr_size
0334       , hdr_offset_size
0335       , overhead_percent
0336       , false>
0337 {
0338    typedef candidate_power_of_2_ct
0339       < initial_alignment
0340       , real_node_size
0341       , payload_per_allocation
0342       , min_elements_per_block
0343       , hdr_size
0344       , hdr_offset_size
0345       , overhead_percent
0346       , false> type;
0347
0348    typedef candidate_power_of_2_ct_helper
0349         < initial_alignment
0350         , real_node_size
0351         , payload_per_allocation
0352         , min_elements_per_block
0353         , hdr_size
0354         , hdr_offset_size
0355         , overhead_percent> helper_t;
0356
0357    static const std::size_t alignment = initial_alignment;
0358    static const std::size_t num_subblocks = helper_t::num_b_subblock+1;
0359    static const std::size_t real_num_node = helper_t::total_nodes;
0360 };
0361
0362 /////////////////////////////////////////////
0363 //
0364 //       candidate_power_of_2_rt
0365 //
0366 /////////////////////////////////////////////
0367 inline void candidate_power_of_2_rt ( std::size_t initial_alignment
0368                                     , std::size_t real_node_size
0369                                     , std::size_t payload_per_allocation
0370                                     , std::size_t min_elements_per_block
0371                                     , std::size_t hdr_size
0372                                     , std::size_t hdr_offset_size
0373                                     , std::size_t overhead_percent
0374                                     , std::size_t &alignment
0375                                     , std::size_t &num_subblocks
0376                                     , std::size_t &real_num_node)
0377 {
0378    bool overhead_satisfied = false;
0379    std::size_t num_b_subblock = 0;
0380    std::size_t total_nodes = 0;
0381
0382    while(!overhead_satisfied)
0383    {
0384       std::size_t hdr_subblock_elements_alone = (initial_alignment - hdr_size - payload_per_allocation)/real_node_size;
0385       std::size_t hdr_subblock_elements_first = (initial_alignment - hdr_size - payload_per_allocation)/real_node_size;
0386       std::size_t elements_per_b_subblock_mid = (initial_alignment - hdr_offset_size)/real_node_size;
0387       std::size_t elements_per_b_subblock_end = (initial_alignment - hdr_offset_size - payload_per_allocation)/real_node_size;
0388
0389       num_b_subblock =
0390          hdr_subblock_elements_alone >= min_elements_per_block
0391             ? 0
0392             : (   ((hdr_subblock_elements_first + elements_per_b_subblock_end) >= min_elements_per_block)
0393                   ? 1
0394                   : 2 + (min_elements_per_block - hdr_subblock_elements_first - elements_per_b_subblock_end - 1)/elements_per_b_subblock_mid
0395                )
0396             ;
0397
0398       std::size_t num_b_subblock_mid = (num_b_subblock > 1) ? (num_b_subblock - 1) : 0;
0399
0400       total_nodes = (num_b_subblock == 0)
0401                                           ? hdr_subblock_elements_alone
0402                                           : ( (num_b_subblock == 1)
0403                                              ? (hdr_subblock_elements_first + elements_per_b_subblock_end)
0404                                              : (hdr_subblock_elements_first + num_b_subblock_mid*elements_per_b_subblock_mid + elements_per_b_subblock_end)
0405                                              )
0406                                           ;
0407       std::size_t total_data = total_nodes*real_node_size;
0408       std::size_t total_size = initial_alignment*(num_b_subblock+1);
0409       overhead_satisfied = (total_size - total_data)*100/total_size < overhead_percent;
0410       initial_alignment = initial_alignment << std::size_t(!overhead_satisfied);
0411    }
0412    alignment     = initial_alignment;
0413    num_subblocks = num_b_subblock+1;
0414    real_num_node = total_nodes;
0415 }
0416
0417 /////////////////////////////////////////////
0418 //
0419 // private_adaptive_node_pool_impl_common
0420 //
0421 /////////////////////////////////////////////
0422 template< class SegmentManagerBase, unsigned int Flags>
0423 class private_adaptive_node_pool_impl_common
0424 {
0425    public:
0426    //!Segment manager typedef
0427    typedef SegmentManagerBase                                        segment_manager_base_type;
0428    typedef typename SegmentManagerBase::multiallocation_chain        multiallocation_chain;
0429    typedef typename SegmentManagerBase::size_type                    size_type;
0430    //Flags
0431    //align_only
0432    static const bool AlignOnly      = (Flags & adaptive_pool_flag::align_only) != 0;
0433    typedef bool_<AlignOnly>            IsAlignOnly;
0434    typedef true_                       AlignOnlyTrue;
0435    typedef false_                      AlignOnlyFalse;
0436
0437    typedef typename SegmentManagerBase::void_pointer void_pointer;
0438    static const typename SegmentManagerBase::
0439       size_type PayloadPerAllocation = SegmentManagerBase::PayloadPerAllocation;
0440
0441    typedef typename boost::intrusive::pointer_traits
0442       <void_pointer>::template rebind_pointer<segment_manager_base_type>::type   segment_mngr_base_ptr_t;
0443
0444    protected:
0445    typedef adaptive_pool_types
0446       <multiallocation_chain, void_pointer, size_type, Flags>        adaptive_pool_types_t;
0447    typedef typename adaptive_pool_types_t::free_nodes_t              free_nodes_t;
0448    typedef typename adaptive_pool_types_t::block_info_t              block_info_t;
0449    typedef typename adaptive_pool_types_t::block_container_t         block_container_t;
0450    typedef typename adaptive_pool_types_t::block_container_traits_t  block_container_traits_t;
0451    typedef typename block_container_t::iterator                      block_iterator;
0452    typedef typename block_container_t::const_iterator                const_block_iterator;
0453    typedef typename adaptive_pool_types_t::hdr_offset_holder         hdr_offset_holder;
0454    typedef private_adaptive_node_pool_impl_common                    this_type;
0455
0456    static const size_type MaxAlign = alignment_of<void_pointer>::value;
0457    static const size_type HdrSize  = ((sizeof(block_info_t)-1)/MaxAlign+1)*MaxAlign;
0458    static const size_type HdrOffsetSize = ((sizeof(hdr_offset_holder)-1)/MaxAlign+1)*MaxAlign;
0459
0460    segment_mngr_base_ptr_t             mp_segment_mngr_base;   //Segment manager
0461    block_container_t                   m_block_container;      //Intrusive block list
0462    size_type                           m_totally_free_blocks;  //Free blocks
0463
0464    class block_destroyer;
0465    friend class block_destroyer;
0466
0467    class block_destroyer
0468    {
0469       public:
0470       block_destroyer(const this_type *impl, multiallocation_chain &chain, const size_type num_subblocks, const size_type real_block_alignment, const size_type real_num_node)
0471          :  mp_impl(impl), m_chain(chain), m_num_subblocks(num_subblocks), m_real_block_alignment(real_block_alignment), m_real_num_node(real_num_node)
0472       {}
0473
0474       void operator()(typename block_container_t::pointer to_deallocate)
0475       {  return this->do_destroy(to_deallocate, IsAlignOnly()); }
0476
0477       private:
0478       void do_destroy(typename block_container_t::pointer to_deallocate, AlignOnlyTrue)
0479       {
0480          BOOST_ASSERT(to_deallocate->free_nodes.size() == m_real_num_node);
0481          m_chain.push_back(to_deallocate);
0482       }
0483
0484       void do_destroy(typename block_container_t::pointer to_deallocate, AlignOnlyFalse)
0485       {
0486          BOOST_ASSERT(to_deallocate->free_nodes.size() == m_real_num_node);
0487          BOOST_ASSERT(0 == to_deallocate->hdr_offset);
0488          hdr_offset_holder *hdr_off_holder =
0489             mp_impl->priv_first_subblock_from_block(boost::movelib::to_raw_pointer(to_deallocate), m_num_subblocks, m_real_block_alignment);
0490          m_chain.push_back(hdr_off_holder);
0491       }
0492
0493       const this_type *mp_impl;
0494       multiallocation_chain &m_chain;
0495       const size_type m_num_subblocks;
0496       const size_type m_real_block_alignment;
0497       const size_type m_real_num_node;
0498    };
0499
0500    //This macro will activate invariant checking. Slow, but helpful for debugging the code.
0501    //#define BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
0502    void priv_invariants(const size_type real_num_node, const size_type num_subblocks, const size_type real_block_alignment) const
0503    {
0504       (void)real_num_node; (void)num_subblocks; (void)real_block_alignment;
0505    #ifdef BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
0506       //Check that the total totally free blocks are correct
0507       BOOST_ASSERT(m_block_container.size() >= m_totally_free_blocks);
0508
0509       const const_block_iterator itend(m_block_container.cend());
0510       const const_block_iterator itbeg(m_block_container.cbegin());
0511
0512       {  //Try to do checks in a single iteration
0513          const_block_iterator it(itbeg);
0514          size_type total_free_nodes = 0;
0515          size_type total_free_blocks = 0u;
0516          for(; it != itend; ++it){
0517             if(it != itbeg){
0518                //Check order invariant
0519                const_block_iterator prev(it);
0520                --prev;
0521                BOOST_ASSERT(!(m_block_container.key_comp()(*it, *prev)));
0522                (void)prev;   (void)it;
0523             }
0524
0525             //free_nodes invariant
0526             const size_type free_nodes = it->free_nodes.size();
0527             BOOST_ASSERT(free_nodes <= real_num_node);
0528             BOOST_ASSERT(free_nodes != 0);
0529
0530             //Acummulate total_free_nodes and total_free_blocks
0531             total_free_nodes += free_nodes;
0532             total_free_blocks += it->free_nodes.size() == real_num_node;
0533
0534             if (!AlignOnly) {
0535                //Check that header offsets are correct
0536                hdr_offset_holder *hdr_off_holder = this->priv_first_subblock_from_block(const_cast<block_info_t *>(&*it), num_subblocks, real_block_alignment);
0537                for (size_type i = 0, max = num_subblocks; i < max; ++i) {
0538                   const size_type offset = size_type(reinterpret_cast<char*>(const_cast<block_info_t *>(&*it)) - reinterpret_cast<char*>(hdr_off_holder));
0539                   (void)offset;
0540                   BOOST_ASSERT(hdr_off_holder->hdr_offset == offset);
0541                   BOOST_ASSERT(0 == (reinterpret_cast<std::size_t>(hdr_off_holder) & (real_block_alignment - 1)));
0542                   BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (real_block_alignment - 1)));
0543                   hdr_off_holder = move_detail::force_ptr<hdr_offset_holder *>(reinterpret_cast<char*>(hdr_off_holder) + real_block_alignment);
0544                }
0545             }
0546          }
0547          BOOST_ASSERT(total_free_blocks == m_totally_free_blocks);
0548          BOOST_ASSERT(total_free_nodes >= m_totally_free_blocks*real_num_node);
0549       }
0550    #endif
0551    }
0552
0553    void priv_deallocate_free_blocks( const size_type max_free_blocks, const size_type real_num_node
0554                                    , const size_type num_subblocks, const size_type real_block_alignment)
0555    {  //Trampoline function to ease inlining
0556       if(m_totally_free_blocks > max_free_blocks){
0557          this->priv_deallocate_free_blocks_impl(max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
0558       }
0559    }
0560
0561    hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block, const size_type num_subblocks, const size_type real_block_alignment) const
0562    {  return this->priv_first_subblock_from_block(block, num_subblocks, real_block_alignment, IsAlignOnly());   }
0563
0564    hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block, const size_type num_subblocks, const size_type real_block_alignment, AlignOnlyFalse) const
0565    {
0566       hdr_offset_holder *const hdr_off_holder = move_detail::force_ptr<hdr_offset_holder*>
0567             (reinterpret_cast<char*>(block) - (num_subblocks-1)*real_block_alignment);
0568       BOOST_ASSERT(hdr_off_holder->hdr_offset == size_type(reinterpret_cast<char*>(block) - reinterpret_cast<char*>(hdr_off_holder)));
0569       BOOST_ASSERT(0 == ((std::size_t)hdr_off_holder & (real_block_alignment - 1)));
0570       BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (real_block_alignment - 1)));
0571       return hdr_off_holder;
0572    }
0573
0574    hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block, const size_type num_subblocks, const size_type real_block_alignment, AlignOnlyTrue) const
0575    {
0576       (void)num_subblocks; (void)real_block_alignment;
0577       return move_detail::force_ptr<hdr_offset_holder*>(block);
0578    }
0579
0580    void priv_deallocate_free_blocks_impl( const size_type max_free_blocks, const size_type real_num_node
0581                                         , const size_type num_subblocks, const size_type real_block_alignment)
0582    {
0583       this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0584       //Now check if we've reached the free nodes limit
0585       //and check if we have free blocks. If so, deallocate as much
0586       //as we can to stay below the limit
0587       multiallocation_chain chain;
0588       {
0589          if(Flags & adaptive_pool_flag::size_ordered){
0590             const_block_iterator it = m_block_container.cend();
0591             --it;
0592             size_type totally_free_blocks = m_totally_free_blocks;
0593
0594             for( ; totally_free_blocks > max_free_blocks; --totally_free_blocks){
0595                BOOST_ASSERT(it->free_nodes.size() == real_num_node);
0596                void *addr = priv_first_subblock_from_block(const_cast<block_info_t*>(&*it), num_subblocks, real_block_alignment);
0597                --it;
0598                block_container_traits_t::erase_last(m_block_container);
0599                chain.push_front(void_pointer(addr));
0600             }
0601          }
0602          else{
0603             const_block_iterator it = m_block_container.cend();
0604             size_type totally_free_blocks = m_totally_free_blocks;
0605
0606             while(totally_free_blocks > max_free_blocks){
0607                --it;
0608                if(it->free_nodes.size() == real_num_node){
0609                   void *addr = priv_first_subblock_from_block(const_cast<block_info_t*>(&*it), num_subblocks, real_block_alignment);
0610                   it = m_block_container.erase(it);
0611                   chain.push_front(void_pointer(addr));
0612                   --totally_free_blocks;
0613                }
0614             }
0615          }
0616          BOOST_ASSERT((m_totally_free_blocks - max_free_blocks) == chain.size());
0617          m_totally_free_blocks = max_free_blocks;
0618       }
0619       this->mp_segment_mngr_base->deallocate_many(chain);
0620       this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0621    }
0622
0623    void priv_fill_chain_remaining_to_block
0624       ( multiallocation_chain &chain, size_type target_elem_in_chain, block_info_t &c_info
0625       , char *mem_address, size_type max_node_in_mem
0626       , const size_type real_node_size)
0627    {
0628       BOOST_ASSERT(chain.size() <= target_elem_in_chain);
0629
0630       //First add all possible nodes to the chain
0631       const size_type left = target_elem_in_chain - chain.size();
0632       const size_type add_to_chain = (max_node_in_mem < left) ? max_node_in_mem : left;
0633       char *free_mem_address = static_cast<char *>(boost::movelib::to_raw_pointer
0634          (chain.incorporate_after(chain.last(), void_pointer(mem_address), real_node_size, add_to_chain)));
0635       //Now store remaining nodes in the free list
0636       if(const size_type free = max_node_in_mem - add_to_chain){
0637          free_nodes_t & free_nodes = c_info.free_nodes;
0638          free_nodes.incorporate_after(free_nodes.last(), void_pointer(free_mem_address), real_node_size, free);
0639       }
0640    }
0641
0642    //!Allocates a several blocks of nodes. Can throw
0643    void priv_append_from_new_blocks( size_type min_elements, multiallocation_chain &chain
0644                                    , const size_type max_free_blocks
0645                                    , const size_type real_block_alignment, const size_type real_node_size
0646                                    , const size_type real_num_node, const size_type num_subblocks
0647                                    , AlignOnlyTrue)
0648    {
0649       (void)num_subblocks;
0650       BOOST_ASSERT(m_block_container.empty());
0651       BOOST_ASSERT(min_elements > 0);
0652       const size_type n = (min_elements - 1)/real_num_node + 1;
0653       const size_type real_block_size = real_block_alignment - PayloadPerAllocation;
0654       const size_type target_elem_in_chain = chain.size() + min_elements;
0655       for(size_type i = 0; i != n; ++i){
0656          //We allocate a new NodeBlock and put it the last
0657          //element of the tree
0658          char *mem_address = static_cast<char*>
0659             (mp_segment_mngr_base->allocate_aligned(real_block_size, real_block_alignment));
0660          if(!mem_address){
0661             //In case of error, free memory deallocating all nodes (the new ones allocated
0662             //in this function plus previously stored nodes in chain).
0663             this->priv_deallocate_nodes(chain, max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
0664             throw_bad_alloc();
0665          }
0666          block_info_t &c_info = *new(mem_address, boost_container_new_t())block_info_t();
0667          mem_address += HdrSize;
0668          this->priv_fill_chain_remaining_to_block(chain, target_elem_in_chain, c_info, mem_address, real_num_node, real_node_size);
0669          const size_type free_nodes = c_info.free_nodes.size();
0670          if(free_nodes){
0671             const bool is_full = free_nodes == real_num_node;
0672             BOOST_ASSERT(free_nodes < real_num_node);
0673             m_totally_free_blocks += static_cast<size_type>(is_full);
0674             block_container_traits_t::insert_was_empty(m_block_container, c_info, is_full);
0675          }
0676       }
0677    }
0678
0679    void priv_append_from_new_blocks( size_type min_elements, multiallocation_chain &chain
0680                                    , const size_type max_free_blocks
0681                                    , const size_type real_block_alignment, const size_type real_node_size
0682                                    , const size_type real_num_node, const size_type num_subblocks
0683                                    , AlignOnlyFalse)
0684    {
0685       BOOST_ASSERT(m_block_container.empty());
0686       BOOST_ASSERT(min_elements > 0);
0687       const size_type n = (min_elements - 1)/real_num_node + 1;
0688       const size_type real_block_size = real_block_alignment*num_subblocks - PayloadPerAllocation;
0689       const size_type elements_per_subblock_mid = (real_block_alignment - HdrOffsetSize)/real_node_size;
0690       const size_type elements_per_subblock_end = (real_block_alignment - HdrOffsetSize - PayloadPerAllocation) / real_node_size;
0691       const size_type hdr_subblock_elements = (real_block_alignment - HdrSize - PayloadPerAllocation)/real_node_size;
0692       const size_type target_elem_in_chain = chain.size() + min_elements;
0693
0694       for(size_type i = 0; i != n; ++i){
0695          //We allocate a new NodeBlock and put it the last
0696          //element of the tree
0697          char *mem_address = static_cast<char*>
0698             (mp_segment_mngr_base->allocate_aligned(real_block_size, real_block_alignment));
0699          if(!mem_address){
0700             //In case of error, free memory deallocating all nodes (the new ones allocated
0701             //in this function plus previously stored nodes in chain).
0702             this->priv_deallocate_nodes(chain, max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
0703             throw_bad_alloc();
0704          }
0705          //First initialize header information on the last subblock
0706          char *hdr_addr = mem_address + real_block_alignment*(num_subblocks-1);
0707          block_info_t &c_info = *new(hdr_addr, boost_container_new_t())block_info_t();
0708          //Some structural checks
0709          BOOST_ASSERT(static_cast<void*>(&static_cast<hdr_offset_holder&>(c_info).hdr_offset) ==
0710                       static_cast<void*>(&c_info));   (void)c_info;
0711          for( size_type subblock = 0, maxsubblock = num_subblocks - 1
0712             ; subblock < maxsubblock
0713             ; ++subblock, mem_address += real_block_alignment){
0714             //Initialize header offset mark
0715             new(mem_address, boost_container_new_t()) hdr_offset_holder(size_type(hdr_addr - mem_address));
0716             const size_type elements_per_subblock = (subblock != (maxsubblock - 1)) ? elements_per_subblock_mid : elements_per_subblock_end;
0717             this->priv_fill_chain_remaining_to_block
0718                (chain, target_elem_in_chain, c_info, mem_address + HdrOffsetSize, elements_per_subblock, real_node_size);
0719          }
0720          this->priv_fill_chain_remaining_to_block
0721             (chain, target_elem_in_chain, c_info, hdr_addr + HdrSize, hdr_subblock_elements, real_node_size);
0722          m_totally_free_blocks += static_cast<size_type>(c_info.free_nodes.size() == real_num_node);
0723          if (c_info.free_nodes.size())
0724             m_block_container.push_front(c_info);
0725       }
0726    }
0727
0728    //!Allocates array of count elements. Can throw
0729    void *priv_allocate_node( const size_type max_free_blocks, const size_type real_block_alignment, const size_type real_node_size
0730                            , const size_type real_num_node, const size_type num_subblocks)
0731    {
0732       this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0733       //If there are no free nodes we allocate a new block
0734       if(!m_block_container.empty()){
0735          //We take the first free node the multiset can't be empty
0736          free_nodes_t &free_nodes = m_block_container.begin()->free_nodes;
0737          BOOST_ASSERT(!free_nodes.empty());
0738          const size_type free_nodes_count = free_nodes.size();
0739          void *first_node = boost::movelib::to_raw_pointer(free_nodes.pop_front());
0740          if(free_nodes.empty()){
0741             block_container_traits_t::erase_first(m_block_container);
0742          }
0743          m_totally_free_blocks -= static_cast<size_type>(free_nodes_count == real_num_node);
0744          this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0745          return first_node;
0746       }
0747       else{
0748          multiallocation_chain chain;
0749          this->priv_append_from_new_blocks
0750             (1, chain, max_free_blocks, real_block_alignment, real_node_size, real_num_node, num_subblocks, IsAlignOnly());
0751          void *node = boost::movelib::to_raw_pointer(chain.pop_front());
0752          this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0753          return node;
0754       }
0755    }
0756
0757    void priv_allocate_nodes( const size_type n, multiallocation_chain &chain
0758                            , const size_type max_free_blocks, const size_type real_block_alignment, const size_type real_node_size
0759                            , const size_type real_num_node, const size_type num_subblocks)
0760    {
0761       size_type i = 0;
0762       BOOST_CONTAINER_TRY{
0763          this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0764          while(i != n){
0765             //If there are no free nodes we allocate all needed blocks
0766             if (m_block_container.empty()){
0767                this->priv_append_from_new_blocks
0768                   (n - i, chain, max_free_blocks, real_block_alignment, real_node_size, real_num_node, num_subblocks, IsAlignOnly());
0769                BOOST_ASSERT(m_block_container.empty() || (++m_block_container.cbegin() == m_block_container.cend()));
0770                BOOST_ASSERT(chain.size() == n);
0771                break;
0772             }
0773             free_nodes_t &free_nodes = m_block_container.begin()->free_nodes;
0774             const size_type free_nodes_count_before = free_nodes.size();
0775             m_totally_free_blocks -= static_cast<size_type>(free_nodes_count_before == real_num_node);
0776             const size_type num_left  = n-i;
0777             const size_type num_elems = (num_left < free_nodes_count_before) ? num_left : free_nodes_count_before;
0778             typedef typename free_nodes_t::iterator free_nodes_iterator;
0779
0780             if(num_left < free_nodes_count_before){
0781                const free_nodes_iterator it_bbeg(free_nodes.before_begin());
0782                free_nodes_iterator it_bend(it_bbeg);
0783                for(size_type j = 0; j != num_elems; ++j){
0784                   ++it_bend;
0785                }
0786                free_nodes_iterator it_end = it_bend; ++it_end;
0787                free_nodes_iterator it_beg = it_bbeg; ++it_beg;
0788                free_nodes.erase_after(it_bbeg, it_end, num_elems);
0789                chain.incorporate_after(chain.last(), &*it_beg, &*it_bend, num_elems);
0790                //chain.splice_after(chain.last(), free_nodes, it_bbeg, it_bend, num_elems);
0791                BOOST_ASSERT(!free_nodes.empty());
0792             }
0793             else{
0794                const free_nodes_iterator it_beg(free_nodes.begin()), it_bend(free_nodes.last());
0795                free_nodes.clear();
0796                chain.incorporate_after(chain.last(), &*it_beg, &*it_bend, num_elems);
0797                block_container_traits_t::erase_first(m_block_container);
0798             }
0799             i += num_elems;
0800          }
0801       }
0802       BOOST_CONTAINER_CATCH(...){
0803          this->priv_deallocate_nodes(chain, max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
0804          this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0805          BOOST_CONTAINER_RETHROW
0806       }
0807       BOOST_CONTAINER_CATCH_END
0808       this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0809    }
0810
0811    //!Deallocates an array pointed by ptr. Never throws
0812    void priv_deallocate_node( void *pElem
0813                             , const size_type max_free_blocks, const size_type real_num_node
0814                             , const size_type num_subblocks, const size_type real_block_alignment)
0815    {
0816       this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0817       block_info_t &block_info = *this->priv_block_from_node(pElem, real_block_alignment);
0818       const size_type prev_free_nodes = block_info.free_nodes.size();
0819       BOOST_ASSERT(block_info.free_nodes.size() < real_num_node);
0820
0821       //We put the node at the beginning of the free node list
0822       block_info.free_nodes.push_back(void_pointer(pElem));
0823
0824       //The loop reinserts all blocks except the last one
0825       this->priv_reinsert_block(block_info, prev_free_nodes == 0, real_num_node);
0826       this->priv_deallocate_free_blocks(max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
0827       this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0828    }
0829
0830    void priv_deallocate_nodes( multiallocation_chain &nodes
0831                              , const size_type max_free_blocks, const size_type real_num_node
0832                              , const size_type num_subblocks, const size_type real_block_alignment)
0833    {
0834       this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0835       //To take advantage of node locality, wait until two
0836       //nodes belong to different blocks. Only then reinsert
0837       //the block of the first node in the block tree.
0838       //Cache of the previous block
0839       block_info_t *prev_block_info = 0;
0840
0841       //If block was empty before this call, it's not already
0842       //inserted in the block tree.
0843       bool prev_block_was_empty     = false;
0844       typedef typename free_nodes_t::iterator free_nodes_iterator;
0845       {
0846          const free_nodes_iterator itbb(nodes.before_begin()), ite(nodes.end());
0847          free_nodes_iterator itf(nodes.begin()), itbf(itbb);
0848          size_type splice_node_count = size_type(-1);
0849          while(itf != ite){
0850             void *pElem = boost::movelib::to_raw_pointer(boost::movelib::iterator_to_raw_pointer(itf));
0851             block_info_t &block_info = *this->priv_block_from_node(pElem, real_block_alignment);
0852             BOOST_ASSERT(block_info.free_nodes.size() < real_num_node);
0853             ++splice_node_count;
0854
0855             //If block change is detected calculate the cached block position in the tree
0856             if(&block_info != prev_block_info){
0857                if(prev_block_info){ //Make sure we skip the initial "dummy" cache
0858                   free_nodes_iterator it(itbb); ++it;
0859                   nodes.erase_after(itbb, itf, splice_node_count);
0860                   prev_block_info->free_nodes.incorporate_after(prev_block_info->free_nodes.last(), &*it, &*itbf, splice_node_count);
0861                   this->priv_reinsert_block(*prev_block_info, prev_block_was_empty, real_num_node);
0862                   splice_node_count = 0;
0863                }
0864                //Update cache with new data
0865                prev_block_was_empty = block_info.free_nodes.empty();
0866                prev_block_info = &block_info;
0867             }
0868             itbf = itf;
0869             ++itf;
0870          }
0871       }
0872       if(prev_block_info){
0873          //The loop reinserts all blocks except the last one
0874          const free_nodes_iterator itfirst(nodes.begin()), itlast(nodes.last());
0875          const size_type splice_node_count = nodes.size();
0876          nodes.clear();
0877          prev_block_info->free_nodes.incorporate_after(prev_block_info->free_nodes.last(), &*itfirst, &*itlast, splice_node_count);
0878          this->priv_reinsert_block(*prev_block_info, prev_block_was_empty, real_num_node);
0879          this->priv_deallocate_free_blocks(max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
0880       }
0881       this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0882    }
0883
0884    void priv_reinsert_block(block_info_t &prev_block_info, const bool prev_block_was_empty, const size_type real_num_node)
0885    {
0886       //Cache the free nodes from the block
0887       const size_type this_block_free_nodes = prev_block_info.free_nodes.size();
0888       const bool is_full = this_block_free_nodes == real_num_node;
0889
0890       //Update free block count
0891       m_totally_free_blocks += static_cast<size_type>(is_full);
0892       if(prev_block_was_empty){
0893          block_container_traits_t::insert_was_empty(m_block_container, prev_block_info, is_full);
0894       }
0895       else{
0896          block_container_traits_t::reinsert_was_used(m_block_container, prev_block_info, is_full);
0897       }
0898    }
0899
0900    block_info_t *priv_block_from_node(void *node, const size_type real_block_alignment, AlignOnlyFalse) const
0901    {
0902       hdr_offset_holder *hdr_off_holder =
0903          reinterpret_cast<hdr_offset_holder*>((std::size_t)node & size_type(~(real_block_alignment - 1)));
0904       BOOST_ASSERT(0 == ((std::size_t)hdr_off_holder & (real_block_alignment - 1)));
0905       BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (real_block_alignment - 1)));
0906       block_info_t *block = move_detail::force_ptr<block_info_t *>
0907          (reinterpret_cast<char*>(hdr_off_holder) + hdr_off_holder->hdr_offset);
0908       BOOST_ASSERT(block->hdr_offset == 0);
0909       return block;
0910    }
0911
0912    block_info_t *priv_block_from_node(void *node, const size_type real_block_alignment, AlignOnlyTrue) const
0913    {
0914       return (block_info_t *)((std::size_t)node & std::size_t(~(real_block_alignment - 1)));
0915    }
0916
0917    block_info_t *priv_block_from_node(void *node, const size_type real_block_alignment) const
0918    {  return this->priv_block_from_node(node, real_block_alignment, IsAlignOnly());   }
0919
0920    //!Deallocates all used memory. Never throws
0921    void priv_clear(const size_type num_subblocks, const size_type real_block_alignment, const size_type real_num_node)
0922    {
0923       #ifndef NDEBUG
0924       block_iterator it    = m_block_container.begin();
0925       block_iterator itend = m_block_container.end();
0926       size_type n_free_nodes = 0;
0927       for(; it != itend; ++it){
0928          //Check for memory leak
0929          BOOST_ASSERT(it->free_nodes.size() == real_num_node);
0930          ++n_free_nodes;
0931       }
0932       BOOST_ASSERT(n_free_nodes == m_totally_free_blocks);
0933       #endif
0934       //Check for memory leaks
0935       this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0936       multiallocation_chain chain;
0937       m_block_container.clear_and_dispose(block_destroyer(this, chain, num_subblocks, real_block_alignment, real_num_node));
0938       this->mp_segment_mngr_base->deallocate_many(chain);
0939       m_totally_free_blocks = 0;
0940       this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
0941    }
0942
0943    public:
0944    private_adaptive_node_pool_impl_common(segment_manager_base_type *segment_mngr_base)
0945       //General purpose allocator
0946    :  mp_segment_mngr_base(segment_mngr_base)
0947    ,  m_block_container()
0948    ,  m_totally_free_blocks(0)
0949    {}
0950
0951    size_type num_free_nodes()
0952    {
0953       typedef typename block_container_t::const_iterator citerator;
0954       size_type count = 0;
0955       citerator it (m_block_container.begin()), itend(m_block_container.end());
0956       for(; it != itend; ++it){
0957          count += it->free_nodes.size();
0958       }
0959       return count;
0960    }
0961
0962    void swap(private_adaptive_node_pool_impl_common &other)
0963    {
0964       std::swap(mp_segment_mngr_base, other.mp_segment_mngr_base);
0965       std::swap(m_totally_free_blocks, other.m_totally_free_blocks);
0966       m_block_container.swap(other.m_block_container);
0967    }
0968
0969    //!Returns the segment manager. Never throws
0970    segment_manager_base_type* get_segment_manager_base()const
0971    {  return boost::movelib::to_raw_pointer(mp_segment_mngr_base);  }
0972 };
0973
0974 template< class SizeType
0975         , std::size_t HdrSize
0976         , std::size_t PayloadPerAllocation
0977         , std::size_t RealNodeSize
0978         , std::size_t NodesPerBlock
0979         , std::size_t HdrOffsetSize
0980         , std::size_t OverheadPercent
0981         , bool AlignOnly>
0982 struct calculate_alignment_ct
0983 {
0984    static const std::size_t alignment     = upper_power_of_2_ct<SizeType, HdrSize + RealNodeSize*NodesPerBlock>::value;
0985    static const std::size_t num_subblocks = 0;
0986    static const std::size_t real_num_node = (alignment - PayloadPerAllocation - HdrSize)/RealNodeSize;
0987 };
0988
0989 template< class SizeType
0990         , std::size_t HdrSize
0991         , std::size_t PayloadPerAllocation
0992         , std::size_t RealNodeSize
0993         , std::size_t NodesPerBlock
0994         , std::size_t HdrOffsetSize
0995         , std::size_t OverheadPercent>
0996 struct calculate_alignment_ct
0997    < SizeType
0998    , HdrSize
0999    , PayloadPerAllocation
1000    , RealNodeSize
1001    , NodesPerBlock
1002    , HdrOffsetSize
1003    , OverheadPercent
1004    , false>
1005 {
1006    typedef typename candidate_power_of_2_ct
1007       < upper_power_of_2_ct<SizeType, HdrSize + PayloadPerAllocation + RealNodeSize>::value
1008       , RealNodeSize
1009       , PayloadPerAllocation
1010       , NodesPerBlock
1011       , HdrSize
1012       , HdrOffsetSize
1013       , OverheadPercent
1014       >::type type;
1015
1016    static const std::size_t alignment     = type::alignment;
1017    static const std::size_t num_subblocks = type::num_subblocks;
1018    static const std::size_t real_num_node = type::real_num_node;
1019 };
1020
1021
1022 /////////////////////////////////////////////
1023 //
1024 //    private_adaptive_node_pool_impl_ct
1025 //
1026 /////////////////////////////////////////////
1027 template< class SegmentManagerBase
1028         , std::size_t MaxFreeBlocks
1029         , std::size_t NodeSize
1030         , std::size_t NodesPerBlock
1031         , std::size_t OverheadPercent
1032         , unsigned int Flags>
1033 class private_adaptive_node_pool_impl_ct
1034    : public private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags>
1035 {
1036    typedef private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags> base_t;
1037
1038    //Non-copyable
1039    private_adaptive_node_pool_impl_ct();
1040    private_adaptive_node_pool_impl_ct(const private_adaptive_node_pool_impl_ct &);
1041    private_adaptive_node_pool_impl_ct &operator=(const private_adaptive_node_pool_impl_ct &);
1042
1043    public:
1044    typedef typename base_t::void_pointer              void_pointer;
1045    typedef typename base_t::size_type                 size_type;
1046    typedef typename base_t::multiallocation_chain     multiallocation_chain;
1047    typedef typename base_t::segment_manager_base_type segment_manager_base_type;
1048
1049    static const typename base_t::size_type PayloadPerAllocation = base_t::PayloadPerAllocation;
1050
1051    //align_only
1052    static const bool AlignOnly      = base_t::AlignOnly;
1053
1054    private:
1055    static const size_type MaxAlign = base_t::MaxAlign;
1056    static const size_type HdrSize  = base_t::HdrSize;
1057    static const size_type HdrOffsetSize = base_t::HdrOffsetSize;
1058
1059    static const size_type RealNodeSize = lcm_ct<NodeSize, alignment_of<void_pointer>::value>::value;
1060
1061    typedef calculate_alignment_ct
1062       < size_type, HdrSize, PayloadPerAllocation
1063       , RealNodeSize, NodesPerBlock, HdrOffsetSize, OverheadPercent, AlignOnly> data_t;
1064
1065    //Round the size to a power of two value.
1066    //This is the total memory size (including payload) that we want to
1067    //allocate from the general-purpose allocator
1068    static const size_type NumSubBlocks       = data_t::num_subblocks;
1069    static const size_type RealNumNode        = data_t::real_num_node;
1070    static const size_type RealBlockAlignment = data_t::alignment;
1071
1072    public:
1073
1074    //!Constructor from a segment manager. Never throws
1075    private_adaptive_node_pool_impl_ct(typename base_t::segment_manager_base_type *segment_mngr_base)
1076       //General purpose allocator
1077    :  base_t(segment_mngr_base)
1078    {}
1079
1080    //!Destructor. Deallocates all allocated blocks. Never throws
1081    ~private_adaptive_node_pool_impl_ct()
1082    {  this->priv_clear(NumSubBlocks, data_t::alignment, RealNumNode);  }
1083
1084    size_type get_real_num_node() const
1085    {  return RealNumNode; }
1086
1087    //!Allocates array of count elements. Can throw
1088    void *allocate_node()
1089    {
1090       return this->priv_allocate_node
1091          (MaxFreeBlocks, data_t::alignment, RealNodeSize, RealNumNode, NumSubBlocks);
1092    }
1093
1094    //!Allocates n nodes.
1095    //!Can throw
1096    void allocate_nodes(const size_type n, multiallocation_chain &chain)
1097    {
1098       this->priv_allocate_nodes
1099          (n, chain, MaxFreeBlocks, data_t::alignment, RealNodeSize, RealNumNode, NumSubBlocks);
1100    }
1101
1102    //!Deallocates an array pointed by ptr. Never throws
1103    void deallocate_node(void *pElem)
1104    {
1105       this->priv_deallocate_node(pElem, MaxFreeBlocks, RealNumNode, NumSubBlocks, RealBlockAlignment);
1106    }
1107
1108    //!Deallocates a linked list of nodes. Never throws
1109    void deallocate_nodes(multiallocation_chain &nodes)
1110    {
1111       this->priv_deallocate_nodes(nodes, MaxFreeBlocks, RealNumNode, NumSubBlocks, data_t::alignment);
1112    }
1113
1114    void deallocate_free_blocks()
1115    {  this->priv_deallocate_free_blocks(0, RealNumNode, NumSubBlocks, data_t::alignment);  }
1116
1117    //Deprecated, use deallocate_free_blocks
1118    void deallocate_free_chunks()
1119    {  this->priv_deallocate_free_blocks(0, RealNumNode, NumSubBlocks, data_t::alignment);   }
1120 };
1121
1122 /////////////////////////////////////////////
1123 //
1124 //    private_adaptive_node_pool_impl_rt
1125 //
1126 /////////////////////////////////////////////
1127 template<class SizeType>
1128 struct private_adaptive_node_pool_impl_rt_data
1129 {
1130    typedef SizeType size_type;
1131
1132    private_adaptive_node_pool_impl_rt_data(size_type max_free_blocks, size_type real_node_size)
1133       : m_max_free_blocks(max_free_blocks), m_real_node_size(real_node_size)
1134       , m_real_block_alignment(), m_num_subblocks(), m_real_num_node()
1135    {}
1136
1137    const size_type m_max_free_blocks;
1138    const size_type m_real_node_size;
1139    //Round the size to a power of two value.
1140    //This is the total memory size (including payload) that we want to
1141    //allocate from the general-purpose allocator
1142    size_type m_real_block_alignment;
1143    size_type m_num_subblocks;
1144    //This is the real number of nodes per block
1145    size_type m_real_num_node;
1146 };
1147
1148
1149 template<class SegmentManagerBase, unsigned int Flags>
1150 class private_adaptive_node_pool_impl_rt
1151    : private private_adaptive_node_pool_impl_rt_data<typename SegmentManagerBase::size_type>
1152    , public  private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags>
1153 {
1154    typedef private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags> impl_t;
1155    typedef private_adaptive_node_pool_impl_rt_data<typename SegmentManagerBase::size_type> data_t;
1156
1157    //Non-copyable
1158    private_adaptive_node_pool_impl_rt();
1159    private_adaptive_node_pool_impl_rt(const private_adaptive_node_pool_impl_rt &);
1160    private_adaptive_node_pool_impl_rt &operator=(const private_adaptive_node_pool_impl_rt &);
1161
1162    protected:
1163
1164    typedef typename impl_t::void_pointer           void_pointer;
1165    typedef typename impl_t::size_type              size_type;
1166    typedef typename impl_t::multiallocation_chain  multiallocation_chain;
1167
1168    static const typename impl_t::size_type PayloadPerAllocation = impl_t::PayloadPerAllocation;
1169
1170    //Flags
1171    //align_only
1172    static const bool AlignOnly      = impl_t::AlignOnly;
1173
1174    static const size_type HdrSize  = impl_t::HdrSize;
1175    static const size_type HdrOffsetSize = impl_t::HdrOffsetSize;
1176
1177    public:
1178
1179    //!Segment manager typedef
1180    typedef SegmentManagerBase                 segment_manager_base_type;
1181
1182    //!Constructor from a segment manager. Never throws
1183    private_adaptive_node_pool_impl_rt
1184       ( segment_manager_base_type *segment_mngr_base
1185       , size_type node_size
1186       , size_type nodes_per_block
1187       , size_type max_free_blocks
1188       , unsigned char overhead_percent
1189       )
1190    :  data_t(max_free_blocks, lcm(node_size, size_type(alignment_of<void_pointer>::value)))
1191    ,  impl_t(segment_mngr_base)
1192    {
1193       if(AlignOnly){
1194          this->m_real_block_alignment = upper_power_of_2(HdrSize + this->m_real_node_size*nodes_per_block);
1195          this->m_real_num_node = (this->m_real_block_alignment - PayloadPerAllocation - HdrSize)/this->m_real_node_size;
1196       }
1197       else{
1198          candidate_power_of_2_rt ( upper_power_of_2(HdrSize + PayloadPerAllocation + this->m_real_node_size)
1199                                  , this->m_real_node_size
1200                                  , PayloadPerAllocation
1201                                  , nodes_per_block
1202                                  , HdrSize
1203                                  , HdrOffsetSize
1204                                  , overhead_percent
1205                                  , this->m_real_block_alignment
1206                                  , this->m_num_subblocks
1207                                  , this->m_real_num_node);
1208       }
1209    }
1210
1211    //!Destructor. Deallocates all allocated blocks. Never throws
1212    ~private_adaptive_node_pool_impl_rt()
1213    {  this->priv_clear(this->m_num_subblocks, this->m_real_block_alignment, this->m_real_num_node);  }
1214
1215    size_type get_real_num_node() const
1216    {  return this->m_real_num_node; }
1217
1218    //!Allocates array of count elements. Can throw
1219    void *allocate_node()
1220    {
1221       return this->priv_allocate_node
1222          (this->m_max_free_blocks, this->m_real_block_alignment, this->m_real_node_size, this->m_real_num_node, this->m_num_subblocks);
1223    }
1224
1225    //!Allocates n nodes.
1226    //!Can throw
1227    void allocate_nodes(const size_type n, multiallocation_chain &chain)
1228    {
1229
1230       this->priv_allocate_nodes
1231          (n, chain, this->m_max_free_blocks, this->m_real_block_alignment, this->m_real_node_size, this->m_real_num_node, this->m_num_subblocks);
1232    }
1233
1234    //!Deallocates an array pointed by ptr. Never throws
1235    void deallocate_node(void *pElem)
1236    {
1237       this->priv_deallocate_node(pElem, this->m_max_free_blocks, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment);
1238    }
1239
1240    //!Deallocates a linked list of nodes. Never throws
1241    void deallocate_nodes(multiallocation_chain &nodes)
1242    {
1243       this->priv_deallocate_nodes(nodes, this->m_max_free_blocks, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment);
1244    }
1245
1246    void deallocate_free_blocks()
1247    {  this->priv_deallocate_free_blocks(0, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment);  }
1248
1249    //Deprecated, use deallocate_free_blocks
1250    void deallocate_free_chunks()
1251    {  this->priv_deallocate_free_blocks(0, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment);   }
1252 };
1253
1254 }  //namespace dtl {
1255 }  //namespace container {
1256 }  //namespace boost {
1257
1258 #include <boost/container/detail/config_end.hpp>
1259
1260 #endif   //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP