| ////////////////////////////////////////////////////////////////////////////// |
| // |
| // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost |
| // Software License, Version 1.0. (See accompanying file |
| // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| // |
| // See http://www.boost.org/libs/container for documentation. |
| // |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| #ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP |
| #define BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP |
| |
| #ifndef BOOST_CONFIG_HPP |
| # include <boost/config.hpp> |
| #endif |
| |
| #if defined(BOOST_HAS_PRAGMA_ONCE) |
| # pragma once |
| #endif |
| |
| #include <boost/container/detail/config_begin.hpp> |
| #include <boost/container/detail/workaround.hpp> |
| |
| // container |
| #include <boost/container/container_fwd.hpp> |
| #include <boost/container/throw_exception.hpp> |
| // container/detail |
| #include <boost/container/detail/pool_common.hpp> |
| #include <boost/container/detail/iterator.hpp> |
| #include <boost/move/detail/iterator_to_raw_pointer.hpp> |
| #include <boost/container/detail/math_functions.hpp> |
| #include <boost/container/detail/placement_new.hpp> |
| #include <boost/container/detail/mpl.hpp> |
| #include <boost/move/detail/to_raw_pointer.hpp> |
| #include <boost/container/detail/type_traits.hpp> |
| // intrusive |
| #include <boost/intrusive/pointer_traits.hpp> |
| #include <boost/intrusive/set.hpp> |
| #include <boost/intrusive/list.hpp> |
| #include <boost/intrusive/slist.hpp> |
| // other |
| #include <boost/assert.hpp> |
| #include <boost/core/no_exceptions_support.hpp> |
| #include <cstddef> |
| |
| namespace boost { |
| namespace container { |
| |
| namespace adaptive_pool_flag { |
| |
| static const unsigned int none = 0u; |
| static const unsigned int align_only = 1u << 0u; |
| static const unsigned int size_ordered = 1u << 1u; |
| static const unsigned int address_ordered = 1u << 2u; |
| |
| } //namespace adaptive_pool_flag{ |
| |
| namespace dtl { |
| |
| template<class size_type> |
| struct hdr_offset_holder_t |
| { |
| hdr_offset_holder_t(size_type offset = 0) |
| : hdr_offset(offset) |
| {} |
| size_type hdr_offset; |
| }; |
| |
| template<class SizeType, unsigned int Flags> |
| struct less_func; |
| |
| template<class SizeType> |
| struct less_func<SizeType, adaptive_pool_flag::none> |
| { |
| static bool less(SizeType, SizeType, const void *, const void *) |
| { return true; } |
| }; |
| |
| template<class SizeType> |
| struct less_func<SizeType, adaptive_pool_flag::size_ordered> |
| { |
| static bool less(SizeType ls, SizeType rs, const void *, const void *) |
| { return ls < rs; } |
| }; |
| |
| template<class SizeType> |
| struct less_func<SizeType, adaptive_pool_flag::address_ordered> |
| { |
| static bool less(SizeType, SizeType, const void *la, const void *ra) |
| { return la < ra; } |
| }; |
| |
| template<class SizeType> |
| struct less_func<SizeType, adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered> |
| { |
| static bool less(SizeType ls, SizeType rs, const void *la, const void *ra) |
| { return (ls < rs) || ((ls == rs) && (la < ra)); } |
| }; |
| |
| template<class VoidPointer, class SizeType, unsigned OrderFlags> |
| struct block_container_traits |
| { |
| typedef typename bi::make_set_base_hook |
| < bi::void_pointer<VoidPointer> |
| , bi::optimize_size<true> |
| , bi::link_mode<bi::normal_link> >::type hook_t; |
| |
| template<class T> |
| struct container |
| { |
| typedef typename bi::make_multiset |
| <T, bi::base_hook<hook_t>, bi::size_type<SizeType> >::type type; |
| }; |
| |
| template<class Container> |
| static void reinsert_was_used(Container &container, typename Container::reference v, bool) |
| { |
| typedef typename Container::const_iterator const_block_iterator; |
| typedef typename Container::iterator block_iterator; |
| typedef typename Container::value_compare value_compare; |
| |
| const block_iterator this_block(Container::s_iterator_to(v)); |
| const const_block_iterator cendit(container.cend()); |
| block_iterator next_block(this_block); |
| |
| if(++next_block != cendit && value_compare()(*next_block, v)){ |
| const_block_iterator next2_block(next_block); |
| //Test if v should be swapped with next (optimization) |
| if(++next2_block == cendit || !value_compare()(*next2_block, v)){ |
| v.swap_nodes(*next_block); |
| BOOST_ASSERT(++next_block == this_block); |
| } |
| else{ |
| container.erase(this_block); |
| container.insert(v); |
| } |
| } |
| } |
| |
| template<class Container> |
| static void insert_was_empty(Container &container, typename Container::value_type &v, bool) |
| { |
| container.insert(v); |
| } |
| |
| template<class Container> |
| static void erase_first(Container &container) |
| { |
| container.erase(container.cbegin()); |
| } |
| |
| template<class Container> |
| static void erase_last(Container &container) |
| { |
| container.erase(--container.cend()); |
| } |
| }; |
| |
| template<class VoidPointer, class SizeType> |
| struct block_container_traits<VoidPointer, SizeType, 0u> |
| { |
| typedef typename bi::make_list_base_hook |
| < bi::void_pointer<VoidPointer> |
| , bi::link_mode<bi::normal_link> >::type hook_t; |
| |
| template<class T> |
| struct container |
| { |
| typedef typename bi::make_list |
| <T, bi::base_hook<hook_t>, bi::size_type<SizeType>, bi::constant_time_size<false> >::type type; |
| }; |
| |
| template<class Container> |
| static void reinsert_was_used(Container &container, typename Container::value_type &v, bool is_full) |
| { |
| if(is_full){ |
| container.erase(Container::s_iterator_to(v)); |
| container.push_back(v); |
| } |
| } |
| |
| template<class Container> |
| static void insert_was_empty(Container &container, typename Container::value_type &v, bool is_full) |
| { |
| if(is_full){ |
| container.push_back(v); |
| } |
| else{ |
| container.push_front(v); |
| } |
| } |
| |
| template<class Container> |
| static void erase_first(Container &container) |
| { |
| container.pop_front(); |
| } |
| |
| template<class Container> |
| static void erase_last(Container &container) |
| { |
| container.pop_back(); |
| } |
| }; |
| |
| ///////////////////////////// |
| // |
| // adaptive_pool_types |
| // |
| ///////////////////////////// |
| template<class MultiallocationChain, class VoidPointer, class SizeType, unsigned int Flags> |
| struct adaptive_pool_types |
| { |
| typedef VoidPointer void_pointer; |
| static const unsigned ordered = (Flags & (adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered)); |
| typedef block_container_traits<VoidPointer, SizeType, ordered> block_container_traits_t; |
| typedef typename block_container_traits_t::hook_t hook_t; |
| typedef hdr_offset_holder_t<SizeType> hdr_offset_holder; |
| static const unsigned int order_flags = Flags & (adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered); |
| typedef MultiallocationChain free_nodes_t; |
| |
| struct block_info_t |
| : public hdr_offset_holder, |
| public hook_t |
| { |
| //An intrusive list of free node from this block |
| free_nodes_t free_nodes; |
| friend bool operator <(const block_info_t &l, const block_info_t &r) |
| { |
| return less_func<SizeType, order_flags>:: |
| less(l.free_nodes.size(), r.free_nodes.size(), &l , &r); |
| } |
| |
| friend bool operator ==(const block_info_t &l, const block_info_t &r) |
| { return &l == &r; } |
| }; |
| typedef typename block_container_traits_t:: template container<block_info_t>::type block_container_t; |
| }; |
| |
| |
| ///////////////////////////////////////////// |
| // |
| // candidate_power_of_2_ct |
| // |
| ///////////////////////////////////////////// |
| template< std::size_t alignment |
| , std::size_t real_node_size |
| , std::size_t payload_per_allocation |
| , std::size_t min_elements_per_block |
| , std::size_t hdr_size |
| , std::size_t hdr_offset_size |
| , std::size_t overhead_percent> |
| struct candidate_power_of_2_ct_helper |
| { |
| static const std::size_t hdr_subblock_elements_alone = (alignment - hdr_size - payload_per_allocation)/real_node_size; |
| static const std::size_t hdr_subblock_elements_first = (alignment - hdr_size - payload_per_allocation)/real_node_size; |
| static const std::size_t elements_per_b_subblock_mid = (alignment - hdr_offset_size)/real_node_size; |
| static const std::size_t elements_per_b_subblock_end = (alignment - hdr_offset_size - payload_per_allocation)/real_node_size; |
| static const std::size_t num_b_subblock = |
| hdr_subblock_elements_alone >= min_elements_per_block |
| ? 0 |
| : ( ((hdr_subblock_elements_first + elements_per_b_subblock_end) >= min_elements_per_block) |
| ? 1 |
| : 2 + (min_elements_per_block - hdr_subblock_elements_first - elements_per_b_subblock_end - 1)/elements_per_b_subblock_mid |
| ) |
| ; |
| |
| static const std::size_t num_b_subblock_mid = (num_b_subblock > 1) ? (num_b_subblock - 1) : 0; |
| |
| static const std::size_t total_nodes = (num_b_subblock == 0) |
| ? hdr_subblock_elements_alone |
| : ( (num_b_subblock == 1) |
| ? (hdr_subblock_elements_first + elements_per_b_subblock_end) |
| : (hdr_subblock_elements_first + num_b_subblock_mid*elements_per_b_subblock_mid + elements_per_b_subblock_end) |
| ) |
| ; |
| static const std::size_t total_data = total_nodes*real_node_size; |
| static const std::size_t total_size = alignment*(num_b_subblock+1); |
| static const bool overhead_satisfied = (total_size - total_data)*100/total_size < overhead_percent; |
| }; |
| |
| template< std::size_t initial_alignment |
| , std::size_t real_node_size |
| , std::size_t payload_per_allocation |
| , std::size_t min_elements_per_block |
| , std::size_t hdr_size |
| , std::size_t hdr_offset_size |
| , std::size_t overhead_percent |
| , bool Loop = true> |
| struct candidate_power_of_2_ct |
| { |
| typedef candidate_power_of_2_ct_helper |
| < initial_alignment |
| , real_node_size |
| , payload_per_allocation |
| , min_elements_per_block |
| , hdr_size |
| , hdr_offset_size |
| , overhead_percent> helper_t; |
| |
| static const std::size_t candidate_power_of_2 = initial_alignment << std::size_t(!helper_t::overhead_satisfied); |
| |
| typedef typename candidate_power_of_2_ct |
| < candidate_power_of_2 |
| , real_node_size |
| , payload_per_allocation |
| , min_elements_per_block |
| , hdr_size |
| , hdr_offset_size |
| , overhead_percent |
| , !helper_t::overhead_satisfied |
| >::type type; |
| |
| static const std::size_t alignment = type::alignment; |
| static const std::size_t num_subblocks = type::num_subblocks; |
| static const std::size_t real_num_node = type::real_num_node; |
| }; |
| |
| template< std::size_t initial_alignment |
| , std::size_t real_node_size |
| , std::size_t payload_per_allocation |
| , std::size_t min_elements_per_block |
| , std::size_t hdr_size |
| , std::size_t hdr_offset_size |
| , std::size_t overhead_percent |
| > |
| struct candidate_power_of_2_ct |
| < initial_alignment |
| , real_node_size |
| , payload_per_allocation |
| , min_elements_per_block |
| , hdr_size |
| , hdr_offset_size |
| , overhead_percent |
| , false> |
| { |
| typedef candidate_power_of_2_ct |
| < initial_alignment |
| , real_node_size |
| , payload_per_allocation |
| , min_elements_per_block |
| , hdr_size |
| , hdr_offset_size |
| , overhead_percent |
| , false> type; |
| |
| typedef candidate_power_of_2_ct_helper |
| < initial_alignment |
| , real_node_size |
| , payload_per_allocation |
| , min_elements_per_block |
| , hdr_size |
| , hdr_offset_size |
| , overhead_percent> helper_t; |
| |
| static const std::size_t alignment = initial_alignment; |
| static const std::size_t num_subblocks = helper_t::num_b_subblock+1; |
| static const std::size_t real_num_node = helper_t::total_nodes; |
| }; |
| |
| ///////////////////////////////////////////// |
| // |
| // candidate_power_of_2_rt |
| // |
| ///////////////////////////////////////////// |
| inline void candidate_power_of_2_rt ( std::size_t initial_alignment |
| , std::size_t real_node_size |
| , std::size_t payload_per_allocation |
| , std::size_t min_elements_per_block |
| , std::size_t hdr_size |
| , std::size_t hdr_offset_size |
| , std::size_t overhead_percent |
| , std::size_t &alignment |
| , std::size_t &num_subblocks |
| , std::size_t &real_num_node) |
| { |
| bool overhead_satisfied = false; |
| std::size_t num_b_subblock = 0; |
| std::size_t total_nodes = 0; |
| |
| while(!overhead_satisfied) |
| { |
| std::size_t hdr_subblock_elements_alone = (initial_alignment - hdr_size - payload_per_allocation)/real_node_size; |
| std::size_t hdr_subblock_elements_first = (initial_alignment - hdr_size - payload_per_allocation)/real_node_size; |
| std::size_t elements_per_b_subblock_mid = (initial_alignment - hdr_offset_size)/real_node_size; |
| std::size_t elements_per_b_subblock_end = (initial_alignment - hdr_offset_size - payload_per_allocation)/real_node_size; |
| |
| num_b_subblock = |
| hdr_subblock_elements_alone >= min_elements_per_block |
| ? 0 |
| : ( ((hdr_subblock_elements_first + elements_per_b_subblock_end) >= min_elements_per_block) |
| ? 1 |
| : 2 + (min_elements_per_block - hdr_subblock_elements_first - elements_per_b_subblock_end - 1)/elements_per_b_subblock_mid |
| ) |
| ; |
| |
| std::size_t num_b_subblock_mid = (num_b_subblock > 1) ? (num_b_subblock - 1) : 0; |
| |
| total_nodes = (num_b_subblock == 0) |
| ? hdr_subblock_elements_alone |
| : ( (num_b_subblock == 1) |
| ? (hdr_subblock_elements_first + elements_per_b_subblock_end) |
| : (hdr_subblock_elements_first + num_b_subblock_mid*elements_per_b_subblock_mid + elements_per_b_subblock_end) |
| ) |
| ; |
| std::size_t total_data = total_nodes*real_node_size; |
| std::size_t total_size = initial_alignment*(num_b_subblock+1); |
| overhead_satisfied = (total_size - total_data)*100/total_size < overhead_percent; |
| initial_alignment = initial_alignment << std::size_t(!overhead_satisfied); |
| } |
| alignment = initial_alignment; |
| num_subblocks = num_b_subblock+1; |
| real_num_node = total_nodes; |
| } |
| |
| ///////////////////////////////////////////// |
| // |
| // private_adaptive_node_pool_impl_common |
| // |
| ///////////////////////////////////////////// |
| template< class SegmentManagerBase, unsigned int Flags> |
| class private_adaptive_node_pool_impl_common |
| { |
| public: |
| //!Segment manager typedef |
| typedef SegmentManagerBase segment_manager_base_type; |
| typedef typename SegmentManagerBase::multiallocation_chain multiallocation_chain; |
| typedef typename SegmentManagerBase::size_type size_type; |
| //Flags |
| //align_only |
| static const bool AlignOnly = (Flags & adaptive_pool_flag::align_only) != 0; |
| typedef bool_<AlignOnly> IsAlignOnly; |
| typedef true_ AlignOnlyTrue; |
| typedef false_ AlignOnlyFalse; |
| |
| typedef typename SegmentManagerBase::void_pointer void_pointer; |
| static const typename SegmentManagerBase:: |
| size_type PayloadPerAllocation = SegmentManagerBase::PayloadPerAllocation; |
| |
| typedef typename boost::intrusive::pointer_traits |
| <void_pointer>::template rebind_pointer<segment_manager_base_type>::type segment_mngr_base_ptr_t; |
| |
| protected: |
| typedef adaptive_pool_types |
| <multiallocation_chain, void_pointer, size_type, Flags> adaptive_pool_types_t; |
| typedef typename adaptive_pool_types_t::free_nodes_t free_nodes_t; |
| typedef typename adaptive_pool_types_t::block_info_t block_info_t; |
| typedef typename adaptive_pool_types_t::block_container_t block_container_t; |
| typedef typename adaptive_pool_types_t::block_container_traits_t block_container_traits_t; |
| typedef typename block_container_t::iterator block_iterator; |
| typedef typename block_container_t::const_iterator const_block_iterator; |
| typedef typename adaptive_pool_types_t::hdr_offset_holder hdr_offset_holder; |
| typedef private_adaptive_node_pool_impl_common this_type; |
| |
| static const size_type MaxAlign = alignment_of<void_pointer>::value; |
| static const size_type HdrSize = ((sizeof(block_info_t)-1)/MaxAlign+1)*MaxAlign; |
| static const size_type HdrOffsetSize = ((sizeof(hdr_offset_holder)-1)/MaxAlign+1)*MaxAlign; |
| |
| segment_mngr_base_ptr_t mp_segment_mngr_base; //Segment manager |
| block_container_t m_block_container; //Intrusive block list |
| size_type m_totally_free_blocks; //Free blocks |
| |
| class block_destroyer; |
| friend class block_destroyer; |
| |
| class block_destroyer |
| { |
| public: |
| 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) |
| : 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) |
| {} |
| |
| void operator()(typename block_container_t::pointer to_deallocate) |
| { return this->do_destroy(to_deallocate, IsAlignOnly()); } |
| |
| private: |
| void do_destroy(typename block_container_t::pointer to_deallocate, AlignOnlyTrue) |
| { |
| BOOST_ASSERT(to_deallocate->free_nodes.size() == m_real_num_node); |
| m_chain.push_back(to_deallocate); |
| } |
| |
| void do_destroy(typename block_container_t::pointer to_deallocate, AlignOnlyFalse) |
| { |
| BOOST_ASSERT(to_deallocate->free_nodes.size() == m_real_num_node); |
| BOOST_ASSERT(0 == to_deallocate->hdr_offset); |
| hdr_offset_holder *hdr_off_holder = |
| mp_impl->priv_first_subblock_from_block(boost::movelib::to_raw_pointer(to_deallocate), m_num_subblocks, m_real_block_alignment); |
| m_chain.push_back(hdr_off_holder); |
| } |
| |
| const this_type *mp_impl; |
| multiallocation_chain &m_chain; |
| const size_type m_num_subblocks; |
| const size_type m_real_block_alignment; |
| const size_type m_real_num_node; |
| }; |
| |
| //This macro will activate invariant checking. Slow, but helpful for debugging the code. |
| //#define BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS |
| void priv_invariants(const size_type real_num_node, const size_type num_subblocks, const size_type real_block_alignment) const |
| { |
| (void)real_num_node; (void)num_subblocks; (void)real_block_alignment; |
| #ifdef BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS |
| //Check that the total totally free blocks are correct |
| BOOST_ASSERT(m_block_container.size() >= m_totally_free_blocks); |
| |
| const const_block_iterator itend(m_block_container.cend()); |
| const const_block_iterator itbeg(m_block_container.cbegin()); |
| |
| { //Try to do checks in a single iteration |
| const_block_iterator it(itbeg); |
| size_type total_free_nodes = 0; |
| size_type total_free_blocks = 0u; |
| for(; it != itend; ++it){ |
| if(it != itbeg){ |
| //Check order invariant |
| const_block_iterator prev(it); |
| --prev; |
| BOOST_ASSERT(!(m_block_container.key_comp()(*it, *prev))); |
| (void)prev; (void)it; |
| } |
| |
| //free_nodes invariant |
| const size_type free_nodes = it->free_nodes.size(); |
| BOOST_ASSERT(free_nodes <= real_num_node); |
| BOOST_ASSERT(free_nodes != 0); |
| |
| //Acummulate total_free_nodes and total_free_blocks |
| total_free_nodes += free_nodes; |
| total_free_blocks += it->free_nodes.size() == real_num_node; |
| |
| if (!AlignOnly) { |
| //Check that header offsets are correct |
| hdr_offset_holder *hdr_off_holder = this->priv_first_subblock_from_block(const_cast<block_info_t *>(&*it), num_subblocks, real_block_alignment); |
| for (size_type i = 0, max = num_subblocks; i < max; ++i) { |
| const size_type offset = reinterpret_cast<char*>(const_cast<block_info_t *>(&*it)) - reinterpret_cast<char*>(hdr_off_holder); |
| (void)offset; |
| BOOST_ASSERT(hdr_off_holder->hdr_offset == offset); |
| BOOST_ASSERT(0 == (reinterpret_cast<std::size_t>(hdr_off_holder) & (real_block_alignment - 1))); |
| BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (real_block_alignment - 1))); |
| hdr_off_holder = reinterpret_cast<hdr_offset_holder *>(reinterpret_cast<char*>(hdr_off_holder) + real_block_alignment); |
| } |
| } |
| } |
| BOOST_ASSERT(total_free_blocks == m_totally_free_blocks); |
| BOOST_ASSERT(total_free_nodes >= m_totally_free_blocks*real_num_node); |
| } |
| #endif |
| } |
| |
| void priv_deallocate_free_blocks( const size_type max_free_blocks, const size_type real_num_node |
| , const size_type num_subblocks, const size_type real_block_alignment) |
| { //Trampoline function to ease inlining |
| if(m_totally_free_blocks > max_free_blocks){ |
| this->priv_deallocate_free_blocks_impl(max_free_blocks, real_num_node, num_subblocks, real_block_alignment); |
| } |
| } |
| |
| hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block, const size_type num_subblocks, const size_type real_block_alignment) const |
| { return this->priv_first_subblock_from_block(block, num_subblocks, real_block_alignment, IsAlignOnly()); } |
| |
| 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 |
| { |
| hdr_offset_holder *const hdr_off_holder = reinterpret_cast<hdr_offset_holder*> |
| (reinterpret_cast<char*>(block) - (num_subblocks-1)*real_block_alignment); |
| BOOST_ASSERT(hdr_off_holder->hdr_offset == size_type(reinterpret_cast<char*>(block) - reinterpret_cast<char*>(hdr_off_holder))); |
| BOOST_ASSERT(0 == ((std::size_t)hdr_off_holder & (real_block_alignment - 1))); |
| BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (real_block_alignment - 1))); |
| return hdr_off_holder; |
| } |
| |
| 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 |
| { |
| (void)num_subblocks; (void)real_block_alignment; |
| return reinterpret_cast<hdr_offset_holder*>(block); |
| } |
| |
| void priv_deallocate_free_blocks_impl( const size_type max_free_blocks, const size_type real_num_node |
| , const size_type num_subblocks, const size_type real_block_alignment) |
| { |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| //Now check if we've reached the free nodes limit |
| //and check if we have free blocks. If so, deallocate as much |
| //as we can to stay below the limit |
| multiallocation_chain chain; |
| { |
| if(Flags & adaptive_pool_flag::size_ordered){ |
| const_block_iterator it = m_block_container.cend(); |
| --it; |
| size_type totally_free_blocks = m_totally_free_blocks; |
| |
| for( ; totally_free_blocks > max_free_blocks; --totally_free_blocks){ |
| BOOST_ASSERT(it->free_nodes.size() == real_num_node); |
| void *addr = priv_first_subblock_from_block(const_cast<block_info_t*>(&*it), num_subblocks, real_block_alignment); |
| --it; |
| block_container_traits_t::erase_last(m_block_container); |
| chain.push_front(void_pointer(addr)); |
| } |
| } |
| else{ |
| const_block_iterator it = m_block_container.cend(); |
| size_type totally_free_blocks = m_totally_free_blocks; |
| |
| while(totally_free_blocks > max_free_blocks){ |
| --it; |
| if(it->free_nodes.size() == real_num_node){ |
| void *addr = priv_first_subblock_from_block(const_cast<block_info_t*>(&*it), num_subblocks, real_block_alignment); |
| it = m_block_container.erase(it); |
| chain.push_front(void_pointer(addr)); |
| --totally_free_blocks; |
| } |
| } |
| } |
| BOOST_ASSERT((m_totally_free_blocks - max_free_blocks) == chain.size()); |
| m_totally_free_blocks = max_free_blocks; |
| } |
| this->mp_segment_mngr_base->deallocate_many(chain); |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| } |
| |
| void priv_fill_chain_remaining_to_block |
| ( multiallocation_chain &chain, size_type target_elem_in_chain, block_info_t &c_info |
| , char *mem_address, size_type max_node_in_mem |
| , const size_type real_node_size) |
| { |
| BOOST_ASSERT(chain.size() <= target_elem_in_chain); |
| |
| //First add all possible nodes to the chain |
| const size_type left = target_elem_in_chain - chain.size(); |
| const size_type add_to_chain = (max_node_in_mem < left) ? max_node_in_mem : left; |
| char *free_mem_address = static_cast<char *>(boost::movelib::to_raw_pointer |
| (chain.incorporate_after(chain.last(), void_pointer(mem_address), real_node_size, add_to_chain))); |
| //Now store remaining nodes in the free list |
| if(const size_type free = max_node_in_mem - add_to_chain){ |
| free_nodes_t & free_nodes = c_info.free_nodes; |
| free_nodes.incorporate_after(free_nodes.last(), void_pointer(free_mem_address), real_node_size, free); |
| } |
| } |
| |
| //!Allocates a several blocks of nodes. Can throw |
| void priv_append_from_new_blocks( size_type min_elements, multiallocation_chain &chain |
| , const size_type max_free_blocks |
| , const size_type real_block_alignment, const size_type real_node_size |
| , const size_type real_num_node, const size_type num_subblocks |
| , AlignOnlyTrue) |
| { |
| (void)num_subblocks; |
| BOOST_ASSERT(m_block_container.empty()); |
| BOOST_ASSERT(min_elements > 0); |
| const size_type n = (min_elements - 1)/real_num_node + 1; |
| const size_type real_block_size = real_block_alignment - PayloadPerAllocation; |
| const size_type target_elem_in_chain = chain.size() + min_elements; |
| for(size_type i = 0; i != n; ++i){ |
| //We allocate a new NodeBlock and put it the last |
| //element of the tree |
| char *mem_address = static_cast<char*> |
| (mp_segment_mngr_base->allocate_aligned(real_block_size, real_block_alignment)); |
| if(!mem_address){ |
| //In case of error, free memory deallocating all nodes (the new ones allocated |
| //in this function plus previously stored nodes in chain). |
| this->priv_deallocate_nodes(chain, max_free_blocks, real_num_node, num_subblocks, real_block_alignment); |
| throw_bad_alloc(); |
| } |
| block_info_t &c_info = *new(mem_address, boost_container_new_t())block_info_t(); |
| mem_address += HdrSize; |
| this->priv_fill_chain_remaining_to_block(chain, target_elem_in_chain, c_info, mem_address, real_num_node, real_node_size); |
| const size_type free_nodes = c_info.free_nodes.size(); |
| if(free_nodes){ |
| const bool is_full = free_nodes == real_num_node; |
| BOOST_ASSERT(free_nodes < real_num_node); |
| m_totally_free_blocks += static_cast<size_type>(is_full); |
| block_container_traits_t::insert_was_empty(m_block_container, c_info, is_full); |
| } |
| } |
| } |
| |
| void priv_append_from_new_blocks( size_type min_elements, multiallocation_chain &chain |
| , const size_type max_free_blocks |
| , const size_type real_block_alignment, const size_type real_node_size |
| , const size_type real_num_node, const size_type num_subblocks |
| , AlignOnlyFalse) |
| { |
| BOOST_ASSERT(m_block_container.empty()); |
| BOOST_ASSERT(min_elements > 0); |
| const size_type n = (min_elements - 1)/real_num_node + 1; |
| const size_type real_block_size = real_block_alignment*num_subblocks - PayloadPerAllocation; |
| const size_type elements_per_subblock_mid = (real_block_alignment - HdrOffsetSize)/real_node_size; |
| const size_type elements_per_subblock_end = (real_block_alignment - HdrOffsetSize - PayloadPerAllocation) / real_node_size; |
| const size_type hdr_subblock_elements = (real_block_alignment - HdrSize - PayloadPerAllocation)/real_node_size; |
| const size_type target_elem_in_chain = chain.size() + min_elements; |
| |
| for(size_type i = 0; i != n; ++i){ |
| //We allocate a new NodeBlock and put it the last |
| //element of the tree |
| char *mem_address = static_cast<char*> |
| (mp_segment_mngr_base->allocate_aligned(real_block_size, real_block_alignment)); |
| if(!mem_address){ |
| //In case of error, free memory deallocating all nodes (the new ones allocated |
| //in this function plus previously stored nodes in chain). |
| this->priv_deallocate_nodes(chain, max_free_blocks, real_num_node, num_subblocks, real_block_alignment); |
| throw_bad_alloc(); |
| } |
| //First initialize header information on the last subblock |
| char *hdr_addr = mem_address + real_block_alignment*(num_subblocks-1); |
| block_info_t &c_info = *new(hdr_addr, boost_container_new_t())block_info_t(); |
| //Some structural checks |
| BOOST_ASSERT(static_cast<void*>(&static_cast<hdr_offset_holder&>(c_info).hdr_offset) == |
| static_cast<void*>(&c_info)); (void)c_info; |
| for( size_type subblock = 0, maxsubblock = num_subblocks - 1 |
| ; subblock < maxsubblock |
| ; ++subblock, mem_address += real_block_alignment){ |
| //Initialize header offset mark |
| new(mem_address, boost_container_new_t()) hdr_offset_holder(size_type(hdr_addr - mem_address)); |
| const size_type elements_per_subblock = (subblock != (maxsubblock - 1)) ? elements_per_subblock_mid : elements_per_subblock_end; |
| this->priv_fill_chain_remaining_to_block |
| (chain, target_elem_in_chain, c_info, mem_address + HdrOffsetSize, elements_per_subblock, real_node_size); |
| } |
| this->priv_fill_chain_remaining_to_block |
| (chain, target_elem_in_chain, c_info, hdr_addr + HdrSize, hdr_subblock_elements, real_node_size); |
| m_totally_free_blocks += static_cast<size_type>(c_info.free_nodes.size() == real_num_node); |
| if (c_info.free_nodes.size()) |
| m_block_container.push_front(c_info); |
| } |
| } |
| |
| //!Allocates array of count elements. Can throw |
| void *priv_allocate_node( const size_type max_free_blocks, const size_type real_block_alignment, const size_type real_node_size |
| , const size_type real_num_node, const size_type num_subblocks) |
| { |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| //If there are no free nodes we allocate a new block |
| if(!m_block_container.empty()){ |
| //We take the first free node the multiset can't be empty |
| free_nodes_t &free_nodes = m_block_container.begin()->free_nodes; |
| BOOST_ASSERT(!free_nodes.empty()); |
| const size_type free_nodes_count = free_nodes.size(); |
| void *first_node = boost::movelib::to_raw_pointer(free_nodes.pop_front()); |
| if(free_nodes.empty()){ |
| block_container_traits_t::erase_first(m_block_container); |
| } |
| m_totally_free_blocks -= static_cast<size_type>(free_nodes_count == real_num_node); |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| return first_node; |
| } |
| else{ |
| multiallocation_chain chain; |
| this->priv_append_from_new_blocks |
| (1, chain, max_free_blocks, real_block_alignment, real_node_size, real_num_node, num_subblocks, IsAlignOnly()); |
| void *node = boost::movelib::to_raw_pointer(chain.pop_front()); |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| return node; |
| } |
| } |
| |
| void priv_allocate_nodes( const size_type n, multiallocation_chain &chain |
| , const size_type max_free_blocks, const size_type real_block_alignment, const size_type real_node_size |
| , const size_type real_num_node, const size_type num_subblocks) |
| { |
| size_type i = 0; |
| BOOST_TRY{ |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| while(i != n){ |
| //If there are no free nodes we allocate all needed blocks |
| if (m_block_container.empty()){ |
| this->priv_append_from_new_blocks |
| (n - i, chain, max_free_blocks, real_block_alignment, real_node_size, real_num_node, num_subblocks, IsAlignOnly()); |
| BOOST_ASSERT(m_block_container.empty() || (++m_block_container.cbegin() == m_block_container.cend())); |
| BOOST_ASSERT(chain.size() == n); |
| break; |
| } |
| free_nodes_t &free_nodes = m_block_container.begin()->free_nodes; |
| const size_type free_nodes_count_before = free_nodes.size(); |
| m_totally_free_blocks -= static_cast<size_type>(free_nodes_count_before == real_num_node); |
| const size_type num_left = n-i; |
| const size_type num_elems = (num_left < free_nodes_count_before) ? num_left : free_nodes_count_before; |
| typedef typename free_nodes_t::iterator free_nodes_iterator; |
| |
| if(num_left < free_nodes_count_before){ |
| const free_nodes_iterator it_bbeg(free_nodes.before_begin()); |
| free_nodes_iterator it_bend(it_bbeg); |
| for(size_type j = 0; j != num_elems; ++j){ |
| ++it_bend; |
| } |
| free_nodes_iterator it_end = it_bend; ++it_end; |
| free_nodes_iterator it_beg = it_bbeg; ++it_beg; |
| free_nodes.erase_after(it_bbeg, it_end, num_elems); |
| chain.incorporate_after(chain.last(), &*it_beg, &*it_bend, num_elems); |
| //chain.splice_after(chain.last(), free_nodes, it_bbeg, it_bend, num_elems); |
| BOOST_ASSERT(!free_nodes.empty()); |
| } |
| else{ |
| const free_nodes_iterator it_beg(free_nodes.begin()), it_bend(free_nodes.last()); |
| free_nodes.clear(); |
| chain.incorporate_after(chain.last(), &*it_beg, &*it_bend, num_elems); |
| block_container_traits_t::erase_first(m_block_container); |
| } |
| i += num_elems; |
| } |
| } |
| BOOST_CATCH(...){ |
| this->priv_deallocate_nodes(chain, max_free_blocks, real_num_node, num_subblocks, real_block_alignment); |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| BOOST_RETHROW |
| } |
| BOOST_CATCH_END |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| } |
| |
| //!Deallocates an array pointed by ptr. Never throws |
| void priv_deallocate_node( void *pElem |
| , const size_type max_free_blocks, const size_type real_num_node |
| , const size_type num_subblocks, const size_type real_block_alignment) |
| { |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| block_info_t &block_info = *this->priv_block_from_node(pElem, real_block_alignment); |
| const size_type prev_free_nodes = block_info.free_nodes.size(); |
| BOOST_ASSERT(block_info.free_nodes.size() < real_num_node); |
| |
| //We put the node at the beginning of the free node list |
| block_info.free_nodes.push_back(void_pointer(pElem)); |
| |
| //The loop reinserts all blocks except the last one |
| this->priv_reinsert_block(block_info, prev_free_nodes == 0, real_num_node); |
| this->priv_deallocate_free_blocks(max_free_blocks, real_num_node, num_subblocks, real_block_alignment); |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| } |
| |
| void priv_deallocate_nodes( multiallocation_chain &nodes |
| , const size_type max_free_blocks, const size_type real_num_node |
| , const size_type num_subblocks, const size_type real_block_alignment) |
| { |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| //To take advantage of node locality, wait until two |
| //nodes belong to different blocks. Only then reinsert |
| //the block of the first node in the block tree. |
| //Cache of the previous block |
| block_info_t *prev_block_info = 0; |
| |
| //If block was empty before this call, it's not already |
| //inserted in the block tree. |
| bool prev_block_was_empty = false; |
| typedef typename free_nodes_t::iterator free_nodes_iterator; |
| { |
| const free_nodes_iterator itbb(nodes.before_begin()), ite(nodes.end()); |
| free_nodes_iterator itf(nodes.begin()), itbf(itbb); |
| size_type splice_node_count = size_type(-1); |
| while(itf != ite){ |
| void *pElem = boost::movelib::to_raw_pointer(boost::movelib::iterator_to_raw_pointer(itf)); |
| block_info_t &block_info = *this->priv_block_from_node(pElem, real_block_alignment); |
| BOOST_ASSERT(block_info.free_nodes.size() < real_num_node); |
| ++splice_node_count; |
| |
| //If block change is detected calculate the cached block position in the tree |
| if(&block_info != prev_block_info){ |
| if(prev_block_info){ //Make sure we skip the initial "dummy" cache |
| free_nodes_iterator it(itbb); ++it; |
| nodes.erase_after(itbb, itf, splice_node_count); |
| prev_block_info->free_nodes.incorporate_after(prev_block_info->free_nodes.last(), &*it, &*itbf, splice_node_count); |
| this->priv_reinsert_block(*prev_block_info, prev_block_was_empty, real_num_node); |
| splice_node_count = 0; |
| } |
| //Update cache with new data |
| prev_block_was_empty = block_info.free_nodes.empty(); |
| prev_block_info = &block_info; |
| } |
| itbf = itf; |
| ++itf; |
| } |
| } |
| if(prev_block_info){ |
| //The loop reinserts all blocks except the last one |
| const free_nodes_iterator itfirst(nodes.begin()), itlast(nodes.last()); |
| const size_type splice_node_count = nodes.size(); |
| nodes.clear(); |
| prev_block_info->free_nodes.incorporate_after(prev_block_info->free_nodes.last(), &*itfirst, &*itlast, splice_node_count); |
| this->priv_reinsert_block(*prev_block_info, prev_block_was_empty, real_num_node); |
| this->priv_deallocate_free_blocks(max_free_blocks, real_num_node, num_subblocks, real_block_alignment); |
| } |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| } |
| |
| void priv_reinsert_block(block_info_t &prev_block_info, const bool prev_block_was_empty, const size_type real_num_node) |
| { |
| //Cache the free nodes from the block |
| const size_type this_block_free_nodes = prev_block_info.free_nodes.size(); |
| const bool is_full = this_block_free_nodes == real_num_node; |
| |
| //Update free block count |
| m_totally_free_blocks += static_cast<size_type>(is_full); |
| if(prev_block_was_empty){ |
| block_container_traits_t::insert_was_empty(m_block_container, prev_block_info, is_full); |
| } |
| else{ |
| block_container_traits_t::reinsert_was_used(m_block_container, prev_block_info, is_full); |
| } |
| } |
| |
| block_info_t *priv_block_from_node(void *node, const size_type real_block_alignment, AlignOnlyFalse) const |
| { |
| hdr_offset_holder *hdr_off_holder = |
| reinterpret_cast<hdr_offset_holder*>((std::size_t)node & size_type(~(real_block_alignment - 1))); |
| BOOST_ASSERT(0 == ((std::size_t)hdr_off_holder & (real_block_alignment - 1))); |
| BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (real_block_alignment - 1))); |
| block_info_t *block = reinterpret_cast<block_info_t *> |
| (reinterpret_cast<char*>(hdr_off_holder) + hdr_off_holder->hdr_offset); |
| BOOST_ASSERT(block->hdr_offset == 0); |
| return block; |
| } |
| |
| block_info_t *priv_block_from_node(void *node, const size_type real_block_alignment, AlignOnlyTrue) const |
| { |
| return (block_info_t *)((std::size_t)node & std::size_t(~(real_block_alignment - 1))); |
| } |
| |
| block_info_t *priv_block_from_node(void *node, const size_type real_block_alignment) const |
| { return this->priv_block_from_node(node, real_block_alignment, IsAlignOnly()); } |
| |
| //!Deallocates all used memory. Never throws |
| void priv_clear(const size_type num_subblocks, const size_type real_block_alignment, const size_type real_num_node) |
| { |
| #ifndef NDEBUG |
| block_iterator it = m_block_container.begin(); |
| block_iterator itend = m_block_container.end(); |
| size_type n_free_nodes = 0; |
| for(; it != itend; ++it){ |
| //Check for memory leak |
| BOOST_ASSERT(it->free_nodes.size() == real_num_node); |
| ++n_free_nodes; |
| } |
| BOOST_ASSERT(n_free_nodes == m_totally_free_blocks); |
| #endif |
| //Check for memory leaks |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| multiallocation_chain chain; |
| m_block_container.clear_and_dispose(block_destroyer(this, chain, num_subblocks, real_block_alignment, real_num_node)); |
| this->mp_segment_mngr_base->deallocate_many(chain); |
| m_totally_free_blocks = 0; |
| this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
| } |
| |
| public: |
| private_adaptive_node_pool_impl_common(segment_manager_base_type *segment_mngr_base) |
| //General purpose allocator |
| : mp_segment_mngr_base(segment_mngr_base) |
| , m_block_container() |
| , m_totally_free_blocks(0) |
| {} |
| |
| size_type num_free_nodes() |
| { |
| typedef typename block_container_t::const_iterator citerator; |
| size_type count = 0; |
| citerator it (m_block_container.begin()), itend(m_block_container.end()); |
| for(; it != itend; ++it){ |
| count += it->free_nodes.size(); |
| } |
| return count; |
| } |
| |
| void swap(private_adaptive_node_pool_impl_common &other) |
| { |
| std::swap(mp_segment_mngr_base, other.mp_segment_mngr_base); |
| std::swap(m_totally_free_blocks, other.m_totally_free_blocks); |
| m_block_container.swap(other.m_block_container); |
| } |
| |
| //!Returns the segment manager. Never throws |
| segment_manager_base_type* get_segment_manager_base()const |
| { return boost::movelib::to_raw_pointer(mp_segment_mngr_base); } |
| }; |
| |
| template< class SizeType |
| , std::size_t HdrSize |
| , std::size_t PayloadPerAllocation |
| , std::size_t RealNodeSize |
| , std::size_t NodesPerBlock |
| , std::size_t HdrOffsetSize |
| , std::size_t OverheadPercent |
| , bool AlignOnly> |
| struct calculate_alignment_ct |
| { |
| static const std::size_t alignment = upper_power_of_2_ct<SizeType, HdrSize + RealNodeSize*NodesPerBlock>::value; |
| static const std::size_t num_subblocks = 0; |
| static const std::size_t real_num_node = (alignment - PayloadPerAllocation - HdrSize)/RealNodeSize; |
| }; |
| |
| template< class SizeType |
| , std::size_t HdrSize |
| , std::size_t PayloadPerAllocation |
| , std::size_t RealNodeSize |
| , std::size_t NodesPerBlock |
| , std::size_t HdrOffsetSize |
| , std::size_t OverheadPercent> |
| struct calculate_alignment_ct |
| < SizeType |
| , HdrSize |
| , PayloadPerAllocation |
| , RealNodeSize |
| , NodesPerBlock |
| , HdrOffsetSize |
| , OverheadPercent |
| , false> |
| { |
| typedef typename candidate_power_of_2_ct |
| < upper_power_of_2_ct<SizeType, HdrSize + PayloadPerAllocation + RealNodeSize>::value |
| , RealNodeSize |
| , PayloadPerAllocation |
| , NodesPerBlock |
| , HdrSize |
| , HdrOffsetSize |
| , OverheadPercent |
| >::type type; |
| |
| static const std::size_t alignment = type::alignment; |
| static const std::size_t num_subblocks = type::num_subblocks; |
| static const std::size_t real_num_node = type::real_num_node; |
| }; |
| |
| |
| ///////////////////////////////////////////// |
| // |
| // private_adaptive_node_pool_impl_ct |
| // |
| ///////////////////////////////////////////// |
| template< class SegmentManagerBase |
| , std::size_t MaxFreeBlocks |
| , std::size_t NodeSize |
| , std::size_t NodesPerBlock |
| , std::size_t OverheadPercent |
| , unsigned int Flags> |
| class private_adaptive_node_pool_impl_ct |
| : public private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags> |
| { |
| typedef private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags> base_t; |
| |
| //Non-copyable |
| private_adaptive_node_pool_impl_ct(); |
| private_adaptive_node_pool_impl_ct(const private_adaptive_node_pool_impl_ct &); |
| private_adaptive_node_pool_impl_ct &operator=(const private_adaptive_node_pool_impl_ct &); |
| |
| public: |
| typedef typename base_t::void_pointer void_pointer; |
| typedef typename base_t::size_type size_type; |
| typedef typename base_t::multiallocation_chain multiallocation_chain; |
| typedef typename base_t::segment_manager_base_type segment_manager_base_type; |
| |
| static const typename base_t::size_type PayloadPerAllocation = base_t::PayloadPerAllocation; |
| |
| //align_only |
| static const bool AlignOnly = base_t::AlignOnly; |
| |
| private: |
| static const size_type MaxAlign = base_t::MaxAlign; |
| static const size_type HdrSize = base_t::HdrSize; |
| static const size_type HdrOffsetSize = base_t::HdrOffsetSize; |
| |
| static const size_type RealNodeSize = lcm_ct<NodeSize, alignment_of<void_pointer>::value>::value; |
| |
| typedef calculate_alignment_ct |
| < size_type, HdrSize, PayloadPerAllocation |
| , RealNodeSize, NodesPerBlock, HdrOffsetSize, OverheadPercent, AlignOnly> data_t; |
| |
| //Round the size to a power of two value. |
| //This is the total memory size (including payload) that we want to |
| //allocate from the general-purpose allocator |
| static const size_type NumSubBlocks = data_t::num_subblocks; |
| static const size_type RealNumNode = data_t::real_num_node; |
| static const size_type RealBlockAlignment = data_t::alignment; |
| |
| public: |
| |
| //!Constructor from a segment manager. Never throws |
| private_adaptive_node_pool_impl_ct(typename base_t::segment_manager_base_type *segment_mngr_base) |
| //General purpose allocator |
| : base_t(segment_mngr_base) |
| {} |
| |
| //!Destructor. Deallocates all allocated blocks. Never throws |
| ~private_adaptive_node_pool_impl_ct() |
| { this->priv_clear(NumSubBlocks, data_t::alignment, RealNumNode); } |
| |
| size_type get_real_num_node() const |
| { return RealNumNode; } |
| |
| //!Allocates array of count elements. Can throw |
| void *allocate_node() |
| { |
| return this->priv_allocate_node |
| (MaxFreeBlocks, data_t::alignment, RealNodeSize, RealNumNode, NumSubBlocks); |
| } |
| |
| //!Allocates n nodes. |
| //!Can throw |
| void allocate_nodes(const size_type n, multiallocation_chain &chain) |
| { |
| this->priv_allocate_nodes |
| (n, chain, MaxFreeBlocks, data_t::alignment, RealNodeSize, RealNumNode, NumSubBlocks); |
| } |
| |
| //!Deallocates an array pointed by ptr. Never throws |
| void deallocate_node(void *pElem) |
| { |
| this->priv_deallocate_node(pElem, MaxFreeBlocks, RealNumNode, NumSubBlocks, RealBlockAlignment); |
| } |
| |
| //!Deallocates a linked list of nodes. Never throws |
| void deallocate_nodes(multiallocation_chain &nodes) |
| { |
| this->priv_deallocate_nodes(nodes, MaxFreeBlocks, RealNumNode, NumSubBlocks, data_t::alignment); |
| } |
| |
| void deallocate_free_blocks() |
| { this->priv_deallocate_free_blocks(0, RealNumNode, NumSubBlocks, data_t::alignment); } |
| |
| //Deprecated, use deallocate_free_blocks |
| void deallocate_free_chunks() |
| { this->priv_deallocate_free_blocks(0, RealNumNode, NumSubBlocks, data_t::alignment); } |
| }; |
| |
| ///////////////////////////////////////////// |
| // |
| // private_adaptive_node_pool_impl_rt |
| // |
| ///////////////////////////////////////////// |
| template<class SizeType> |
| struct private_adaptive_node_pool_impl_rt_data |
| { |
| typedef SizeType size_type; |
| |
| private_adaptive_node_pool_impl_rt_data(size_type max_free_blocks, size_type real_node_size) |
| : m_max_free_blocks(max_free_blocks), m_real_node_size(real_node_size) |
| , m_real_block_alignment(), m_num_subblocks(), m_real_num_node() |
| {} |
| |
| const size_type m_max_free_blocks; |
| const size_type m_real_node_size; |
| //Round the size to a power of two value. |
| //This is the total memory size (including payload) that we want to |
| //allocate from the general-purpose allocator |
| size_type m_real_block_alignment; |
| size_type m_num_subblocks; |
| //This is the real number of nodes per block |
| size_type m_real_num_node; |
| }; |
| |
| |
| template<class SegmentManagerBase, unsigned int Flags> |
| class private_adaptive_node_pool_impl_rt |
| : private private_adaptive_node_pool_impl_rt_data<typename SegmentManagerBase::size_type> |
| , public private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags> |
| { |
| typedef private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags> impl_t; |
| typedef private_adaptive_node_pool_impl_rt_data<typename SegmentManagerBase::size_type> data_t; |
| |
| //Non-copyable |
| private_adaptive_node_pool_impl_rt(); |
| private_adaptive_node_pool_impl_rt(const private_adaptive_node_pool_impl_rt &); |
| private_adaptive_node_pool_impl_rt &operator=(const private_adaptive_node_pool_impl_rt &); |
| |
| protected: |
| |
| typedef typename impl_t::void_pointer void_pointer; |
| typedef typename impl_t::size_type size_type; |
| typedef typename impl_t::multiallocation_chain multiallocation_chain; |
| |
| static const typename impl_t::size_type PayloadPerAllocation = impl_t::PayloadPerAllocation; |
| |
| //Flags |
| //align_only |
| static const bool AlignOnly = impl_t::AlignOnly; |
| |
| static const size_type HdrSize = impl_t::HdrSize; |
| static const size_type HdrOffsetSize = impl_t::HdrOffsetSize; |
| |
| public: |
| |
| //!Segment manager typedef |
| typedef SegmentManagerBase segment_manager_base_type; |
| |
| //!Constructor from a segment manager. Never throws |
| private_adaptive_node_pool_impl_rt |
| ( segment_manager_base_type *segment_mngr_base |
| , size_type node_size |
| , size_type nodes_per_block |
| , size_type max_free_blocks |
| , unsigned char overhead_percent |
| ) |
| : data_t(max_free_blocks, lcm(node_size, size_type(alignment_of<void_pointer>::value))) |
| , impl_t(segment_mngr_base) |
| { |
| if(AlignOnly){ |
| this->m_real_block_alignment = upper_power_of_2(HdrSize + this->m_real_node_size*nodes_per_block); |
| this->m_real_num_node = (this->m_real_block_alignment - PayloadPerAllocation - HdrSize)/this->m_real_node_size; |
| } |
| else{ |
| candidate_power_of_2_rt ( upper_power_of_2(HdrSize + PayloadPerAllocation + this->m_real_node_size) |
| , this->m_real_node_size |
| , PayloadPerAllocation |
| , nodes_per_block |
| , HdrSize |
| , HdrOffsetSize |
| , overhead_percent |
| , this->m_real_block_alignment |
| , this->m_num_subblocks |
| , this->m_real_num_node); |
| } |
| } |
| |
| //!Destructor. Deallocates all allocated blocks. Never throws |
| ~private_adaptive_node_pool_impl_rt() |
| { this->priv_clear(this->m_num_subblocks, this->m_real_block_alignment, this->m_real_num_node); } |
| |
| size_type get_real_num_node() const |
| { return this->m_real_num_node; } |
| |
| //!Allocates array of count elements. Can throw |
| void *allocate_node() |
| { |
| return this->priv_allocate_node |
| (this->m_max_free_blocks, this->m_real_block_alignment, this->m_real_node_size, this->m_real_num_node, this->m_num_subblocks); |
| } |
| |
| //!Allocates n nodes. |
| //!Can throw |
| void allocate_nodes(const size_type n, multiallocation_chain &chain) |
| { |
| |
| this->priv_allocate_nodes |
| (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); |
| } |
| |
| //!Deallocates an array pointed by ptr. Never throws |
| void deallocate_node(void *pElem) |
| { |
| this->priv_deallocate_node(pElem, this->m_max_free_blocks, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment); |
| } |
| |
| //!Deallocates a linked list of nodes. Never throws |
| void deallocate_nodes(multiallocation_chain &nodes) |
| { |
| this->priv_deallocate_nodes(nodes, this->m_max_free_blocks, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment); |
| } |
| |
| void deallocate_free_blocks() |
| { this->priv_deallocate_free_blocks(0, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment); } |
| |
| //Deprecated, use deallocate_free_blocks |
| void deallocate_free_chunks() |
| { this->priv_deallocate_free_blocks(0, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment); } |
| }; |
| |
| } //namespace dtl { |
| } //namespace container { |
| } //namespace boost { |
| |
| #include <boost/container/detail/config_end.hpp> |
| |
| #endif //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP |
