diff options
author | Chanho Park <chanho61.park@samsung.com> | 2014-12-11 18:55:56 +0900 |
---|---|---|
committer | Chanho Park <chanho61.park@samsung.com> | 2014-12-11 18:55:56 +0900 |
commit | 08c1e93fa36a49f49325a07fe91ff92c964c2b6c (patch) | |
tree | 7a7053ceb8874b28ec4b868d4c49b500008a102e /boost/container/detail/adaptive_node_pool_impl.hpp | |
parent | bb4dd8289b351fae6b55e303f189127a394a1edd (diff) | |
download | boost-08c1e93fa36a49f49325a07fe91ff92c964c2b6c.tar.gz boost-08c1e93fa36a49f49325a07fe91ff92c964c2b6c.tar.bz2 boost-08c1e93fa36a49f49325a07fe91ff92c964c2b6c.zip |
Imported Upstream version 1.57.0upstream/1.57.0
Diffstat (limited to 'boost/container/detail/adaptive_node_pool_impl.hpp')
-rw-r--r-- | boost/container/detail/adaptive_node_pool_impl.hpp | 725 |
1 files changed, 476 insertions, 249 deletions
diff --git a/boost/container/detail/adaptive_node_pool_impl.hpp b/boost/container/detail/adaptive_node_pool_impl.hpp index afba6b5f1b..dc1a7f102e 100644 --- a/boost/container/detail/adaptive_node_pool_impl.hpp +++ b/boost/container/detail/adaptive_node_pool_impl.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost +// (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) // @@ -11,26 +11,40 @@ #ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP #define BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP -#if (defined _MSC_VER) && (_MSC_VER >= 1200) +#if defined(_MSC_VER) # pragma once #endif -#include "config_begin.hpp" -#include <boost/container/container_fwd.hpp> +#include <boost/container/detail/config_begin.hpp> #include <boost/container/detail/workaround.hpp> + +#include <boost/container/container_fwd.hpp> #include <boost/container/detail/utilities.hpp> #include <boost/intrusive/pointer_traits.hpp> #include <boost/intrusive/set.hpp> +#include <boost/intrusive/list.hpp> #include <boost/intrusive/slist.hpp> #include <boost/container/detail/type_traits.hpp> #include <boost/container/detail/math_functions.hpp> #include <boost/container/detail/mpl.hpp> #include <boost/container/detail/pool_common.hpp> +#include <boost/container/throw_exception.hpp> #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 container_detail { template<class size_type> @@ -42,42 +56,160 @@ struct hdr_offset_holder_t 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, bool ordered> +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; + const const_block_iterator this_block + (Container::s_iterator_to(const_cast<typename Container::const_reference>(v))); + const_block_iterator next_block(this_block); + if(++next_block != container.cend()){ + if(this_block->free_nodes.size() > next_block->free_nodes.size()){ + 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, false> +{ + 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(); + } +}; + +template<class MultiallocationChain, class VoidPointer, class SizeType, unsigned int Flags> struct adaptive_pool_types { typedef VoidPointer void_pointer; - typedef typename bi::make_set_base_hook - < bi::void_pointer<void_pointer> - , bi::optimize_size<true> - , bi::constant_time_size<false> - , bi::link_mode<bi::normal_link> >::type multiset_hook_t; - + static const bool ordered = (Flags & (adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered)) != 0; + 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 multiset_hook_t + : public hdr_offset_holder, + public hook_t { - typedef typename node_slist<void_pointer>::node_slist_t free_nodes_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 l.free_nodes.size() < r.free_nodes.size(); } - //Let's order blocks first by free nodes and then by address - //so that highest address fully free blocks are deallocated. - //This improves returning memory to the OS (trimming). - const bool is_less = l.free_nodes.size() < r.free_nodes.size(); - const bool is_equal = l.free_nodes.size() == r.free_nodes.size(); - return is_less || (is_equal && (&l < &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 bi::make_multiset - <block_info_t, bi::base_hook<multiset_hook_t> >::type block_multiset_t; + typedef typename block_container_traits_t:: template container<block_info_t>::type block_container_t; }; template<class size_type> @@ -113,9 +245,9 @@ inline void calculate_num_subblocks , size_type &num_subblocks, size_type &real_num_node, size_type overhead_percent , size_type hdr_size, size_type hdr_offset_size, size_type payload_per_allocation) { + const size_type hdr_subblock_elements = (alignment - hdr_size - payload_per_allocation)/real_node_size; size_type elements_per_subblock = (alignment - hdr_offset_size)/real_node_size; size_type possible_num_subblock = (elements_per_block - 1)/elements_per_subblock + 1; - size_type hdr_subblock_elements = (alignment - hdr_size - payload_per_allocation)/real_node_size; while(((possible_num_subblock-1)*elements_per_subblock + hdr_subblock_elements) < elements_per_block){ ++possible_num_subblock; } @@ -135,7 +267,7 @@ inline void calculate_num_subblocks real_num_node = (possible_num_subblock-1)*elements_per_subblock + hdr_subblock_elements; } -template<class SegmentManagerBase, bool AlignOnly = false> +template<class SegmentManagerBase, unsigned int Flags> class private_adaptive_node_pool_impl { //Non-copyable @@ -147,27 +279,42 @@ class private_adaptive_node_pool_impl typedef typename SegmentManagerBase::void_pointer void_pointer; static const typename SegmentManagerBase:: size_type PayloadPerAllocation = SegmentManagerBase::PayloadPerAllocation; + //Flags + //align_only + static const bool AlignOnly = (Flags & adaptive_pool_flag::align_only) != 0; typedef bool_<AlignOnly> IsAlignOnly; typedef true_ AlignOnlyTrue; typedef false_ AlignOnlyFalse; + //size_ordered + static const bool SizeOrdered = (Flags & adaptive_pool_flag::size_ordered) != 0; + typedef bool_<SizeOrdered> IsSizeOrdered; + typedef true_ SizeOrderedTrue; + typedef false_ SizeOrderedFalse; + //address_ordered + static const bool AddressOrdered = (Flags & adaptive_pool_flag::address_ordered) != 0; + typedef bool_<AddressOrdered> IsAddressOrdered; + typedef true_ AddressOrderedTrue; + typedef false_ AddressOrderedFalse; public: - typedef typename node_slist<void_pointer>::node_t node_t; - typedef typename node_slist<void_pointer>::node_slist_t free_nodes_t; - typedef typename SegmentManagerBase::multiallocation_chain multiallocation_chain; - typedef typename SegmentManagerBase::size_type size_type; + typedef typename SegmentManagerBase::multiallocation_chain multiallocation_chain; + typedef typename SegmentManagerBase::size_type size_type; private: - typedef typename adaptive_pool_types<void_pointer, size_type>::block_info_t block_info_t; - typedef typename adaptive_pool_types<void_pointer, size_type>::block_multiset_t block_multiset_t; - typedef typename block_multiset_t::iterator block_iterator; - typedef typename adaptive_pool_types<void_pointer, size_type>::hdr_offset_holder hdr_offset_holder; - - static const size_type MaxAlign = alignment_of<node_t>::value; + 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; + + 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; - public: //!Segment manager typedef typedef SegmentManagerBase segment_manager_base_type; @@ -181,7 +328,7 @@ class private_adaptive_node_pool_impl , unsigned char overhead_percent ) : m_max_free_blocks(max_free_blocks) - , m_real_node_size(lcm(node_size, size_type(alignment_of<node_t>::value))) + , m_real_node_size(lcm(node_size, size_type(alignment_of<void_pointer>::value))) //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 @@ -195,7 +342,7 @@ class private_adaptive_node_pool_impl , m_real_num_node(AlignOnly ? (m_real_block_alignment - PayloadPerAllocation - HdrSize)/m_real_node_size : 0) //General purpose allocator , mp_segment_mngr_base(segment_mngr_base) - , m_block_multiset() + , m_block_container() , m_totally_free_blocks(0) { if(!AlignOnly){ @@ -214,7 +361,7 @@ class private_adaptive_node_pool_impl //!Destructor. Deallocates all allocated blocks. Never throws ~private_adaptive_node_pool_impl() - { priv_clear(); } + { this->priv_clear(); } size_type get_real_num_node() const { return m_real_num_node; } @@ -226,84 +373,157 @@ class private_adaptive_node_pool_impl //!Allocates array of count elements. Can throw void *allocate_node() { - priv_invariants(); + this->priv_invariants(); //If there are no free nodes we allocate a new block - if (m_block_multiset.empty()){ - priv_alloc_block(1); + 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 = container_detail::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 == m_real_num_node); + this->priv_invariants(); + return first_node; + } + else{ + multiallocation_chain chain; + this->priv_append_from_new_blocks(1, chain, IsAlignOnly()); + return container_detail::to_raw_pointer(chain.pop_front()); } - //We take the first free node the multiset can't be empty - return priv_take_first_node(); } //!Deallocates an array pointed by ptr. Never throws void deallocate_node(void *pElem) { - multiallocation_chain chain; - chain.push_front(void_pointer(pElem)); - this->priv_reinsert_nodes_in_block(chain, 1); - //Update free block count< - if(m_totally_free_blocks > m_max_free_blocks){ - this->priv_deallocate_free_blocks(m_max_free_blocks); - } - priv_invariants(); + this->priv_invariants(); + block_info_t &block_info = *this->priv_block_from_node(pElem); + BOOST_ASSERT(block_info.free_nodes.size() < m_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, block_info.free_nodes.size() == 1); + this->priv_deallocate_free_blocks(m_max_free_blocks); + this->priv_invariants(); } //!Allocates n nodes. //!Can throw - multiallocation_chain allocate_nodes(const size_type n) + void allocate_nodes(const size_type n, multiallocation_chain &chain) { - multiallocation_chain chain; size_type i = 0; - try{ - priv_invariants(); + BOOST_TRY{ + this->priv_invariants(); while(i != n){ //If there are no free nodes we allocate all needed blocks - if (m_block_multiset.empty()){ - priv_alloc_block(((n - i) - 1)/m_real_num_node + 1); + if (m_block_container.empty()){ + this->priv_append_from_new_blocks(n - i, chain, 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_multiset.begin()->free_nodes; + free_nodes_t &free_nodes = m_block_container.begin()->free_nodes; const size_type free_nodes_count_before = free_nodes.size(); - if(free_nodes_count_before == m_real_num_node){ - --m_totally_free_blocks; - } - const size_type num_elems = ((n-i) < free_nodes_count_before) ? (n-i) : free_nodes_count_before; - for(size_type j = 0; j != num_elems; ++j){ - void *new_node = &free_nodes.front(); - free_nodes.pop_front(); - chain.push_back(new_node); + m_totally_free_blocks -= static_cast<size_type>(free_nodes_count_before == m_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()); } - - if(free_nodes.empty()){ - m_block_multiset.erase(m_block_multiset.begin()); + 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; } } - catch(...){ - this->deallocate_nodes(boost::move(chain)); - throw; + BOOST_CATCH(...){ + this->deallocate_nodes(chain); + BOOST_RETHROW } - priv_invariants(); - return boost::move(chain); + BOOST_CATCH_END + this->priv_invariants(); } //!Deallocates a linked list of nodes. Never throws - void deallocate_nodes(multiallocation_chain nodes) + void deallocate_nodes(multiallocation_chain &nodes) { - this->priv_reinsert_nodes_in_block(nodes, nodes.size()); - if(m_totally_free_blocks > m_max_free_blocks){ + this->priv_invariants(); + //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 = container_detail::to_raw_pointer(container_detail::iterator_to_pointer(itf)); + block_info_t &block_info = *this->priv_block_from_node(pElem); + BOOST_ASSERT(block_info.free_nodes.size() < m_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); + 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); + this->priv_invariants(); this->priv_deallocate_free_blocks(m_max_free_blocks); } } void deallocate_free_blocks() - { this->priv_deallocate_free_blocks(0); } + { this->priv_deallocate_free_blocks(0); } size_type num_free_nodes() { - typedef typename block_multiset_t::const_iterator citerator; + typedef typename block_container_t::const_iterator citerator; size_type count = 0; - citerator it (m_block_multiset.begin()), itend(m_block_multiset.end()); + citerator it (m_block_container.begin()), itend(m_block_container.end()); for(; it != itend; ++it){ count += it->free_nodes.size(); } @@ -318,7 +538,7 @@ class private_adaptive_node_pool_impl BOOST_ASSERT(m_real_num_node == other.m_real_num_node); std::swap(mp_segment_mngr_base, other.mp_segment_mngr_base); std::swap(m_totally_free_blocks, other.m_totally_free_blocks); - m_block_multiset.swap(other.m_block_multiset); + m_block_container.swap(other.m_block_container); } //Deprecated, use deallocate_free_blocks @@ -326,84 +546,54 @@ class private_adaptive_node_pool_impl { this->priv_deallocate_free_blocks(0); } private: + void priv_deallocate_free_blocks(size_type max_free_blocks) + { //Trampoline function to ease inlining + if(m_totally_free_blocks > max_free_blocks){ + this->priv_deallocate_free_blocks_impl(max_free_blocks); + } + } + + void priv_deallocate_free_blocks_impl(size_type max_free_blocks) { - priv_invariants(); + this->priv_invariants(); //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 - for( block_iterator itend = m_block_multiset.end() - ; m_totally_free_blocks > max_free_blocks - ; --m_totally_free_blocks - ){ - BOOST_ASSERT(!m_block_multiset.empty()); - block_iterator it = itend; + multiallocation_chain chain; + { + const const_block_iterator itend = m_block_container.cend(); + const_block_iterator it = itend; --it; - BOOST_ASSERT(it->free_nodes.size() == m_real_num_node); - m_block_multiset.erase_and_dispose(it, block_destroyer(this)); - } - } - - void priv_reinsert_nodes_in_block(multiallocation_chain &chain, size_type n) - { - block_iterator block_it(m_block_multiset.end()); - while(n--){ - void *pElem = container_detail::to_raw_pointer(chain.front()); - chain.pop_front(); - priv_invariants(); - block_info_t *block_info = this->priv_block_from_node(pElem); - BOOST_ASSERT(block_info->free_nodes.size() < m_real_num_node); - //We put the node at the beginning of the free node list - node_t * to_deallocate = static_cast<node_t*>(pElem); - block_info->free_nodes.push_front(*to_deallocate); - - block_iterator this_block(block_multiset_t::s_iterator_to(*block_info)); - block_iterator next_block(this_block); - ++next_block; - - //Cache the free nodes from the block - size_type this_block_free_nodes = this_block->free_nodes.size(); - - if(this_block_free_nodes == 1){ - m_block_multiset.insert(m_block_multiset.begin(), *block_info); + 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() == m_real_num_node); + void *addr = priv_first_subblock_from_block(const_cast<block_info_t*>(&*it)); + --it; + block_container_traits_t::erase_last(m_block_container); + chain.push_front(void_pointer(addr)); } - else{ - block_iterator next_block(this_block); - ++next_block; - if(next_block != block_it){ - size_type next_free_nodes = next_block->free_nodes.size(); - if(this_block_free_nodes > next_free_nodes){ - //Now move the block to the new position - m_block_multiset.erase(this_block); - m_block_multiset.insert(*block_info); - } - } - } - //Update free block count - if(this_block_free_nodes == m_real_num_node){ - ++m_totally_free_blocks; - } - priv_invariants(); + 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); } - node_t *priv_take_first_node() + void priv_reinsert_block(block_info_t &prev_block_info, const bool prev_block_was_empty) { - BOOST_ASSERT(m_block_multiset.begin() != m_block_multiset.end()); - //We take the first free node the multiset can't be empty - free_nodes_t &free_nodes = m_block_multiset.begin()->free_nodes; - node_t *first_node = &free_nodes.front(); - const size_type free_nodes_count = free_nodes.size(); - BOOST_ASSERT(0 != free_nodes_count); - free_nodes.pop_front(); - if(free_nodes_count == 1){ - m_block_multiset.erase(m_block_multiset.begin()); + //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 == m_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 if(free_nodes_count == m_real_num_node){ - --m_totally_free_blocks; + else{ + block_container_traits_t::reinsert_was_used(m_block_container, prev_block_info, is_full); } - priv_invariants(); - return first_node; } class block_destroyer; @@ -412,33 +602,31 @@ class private_adaptive_node_pool_impl class block_destroyer { public: - block_destroyer(const this_type *impl) - : mp_impl(impl) + block_destroyer(const this_type *impl, multiallocation_chain &chain) + : mp_impl(impl), m_chain(chain) {} - void operator()(typename block_multiset_t::pointer to_deallocate) + void operator()(typename block_container_t::pointer to_deallocate) { return this->do_destroy(to_deallocate, IsAlignOnly()); } private: - void do_destroy(typename block_multiset_t::pointer to_deallocate, AlignOnlyTrue) + void do_destroy(typename block_container_t::pointer to_deallocate, AlignOnlyTrue) { - size_type free_nodes = to_deallocate->free_nodes.size(); - (void)free_nodes; - BOOST_ASSERT(free_nodes == mp_impl->m_real_num_node); - mp_impl->mp_segment_mngr_base->deallocate(to_deallocate); + BOOST_ASSERT(to_deallocate->free_nodes.size() == mp_impl->m_real_num_node); + m_chain.push_back(to_deallocate); } - void do_destroy(typename block_multiset_t::pointer to_deallocate, AlignOnlyFalse) + void do_destroy(typename block_container_t::pointer to_deallocate, AlignOnlyFalse) { - size_type free_nodes = to_deallocate->free_nodes.size(); - (void)free_nodes; - BOOST_ASSERT(free_nodes == mp_impl->m_real_num_node); + BOOST_ASSERT(to_deallocate->free_nodes.size() == mp_impl->m_real_num_node); BOOST_ASSERT(0 == to_deallocate->hdr_offset); - hdr_offset_holder *hdr_off_holder = mp_impl->priv_first_subblock_from_block(container_detail::to_raw_pointer(to_deallocate)); - mp_impl->mp_segment_mngr_base->deallocate(hdr_off_holder); + hdr_offset_holder *hdr_off_holder = + mp_impl->priv_first_subblock_from_block(container_detail::to_raw_pointer(to_deallocate)); + m_chain.push_back(hdr_off_holder); } const this_type *mp_impl; + multiallocation_chain &m_chain; }; //This macro will activate invariant checking. Slow, but helpful for debugging the code. @@ -447,44 +635,45 @@ class private_adaptive_node_pool_impl #ifdef BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS #undef BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS { - //We iterate through the block tree to free the memory - block_iterator it(m_block_multiset.begin()), - itend(m_block_multiset.end()), to_deallocate; - if(it != itend){ - for(++it; it != itend; ++it){ - block_iterator prev(it); - --prev; - size_type sp = prev->free_nodes.size(), - si = it->free_nodes.size(); - BOOST_ASSERT(sp <= si); - (void)sp; (void)si; + const const_block_iterator itend(m_block_container.end()); + + { //We iterate through the block tree to free the memory + const_block_iterator it(m_block_container.begin()); + + if(it != itend){ + for(++it; it != itend; ++it){ + const_block_iterator prev(it); + --prev; + BOOST_ASSERT(*prev < *it); + (void)prev; (void)it; + } } } - //Check that the total free nodes are correct - it = m_block_multiset.begin(); - itend = m_block_multiset.end(); - size_type total_free_nodes = 0; - for(; it != itend; ++it){ - total_free_nodes += it->free_nodes.size(); + { //Check that the total free nodes are correct + const_block_iterator it(m_block_container.cbegin()); + size_type total_free_nodes = 0; + for(; it != itend; ++it){ + total_free_nodes += it->free_nodes.size(); + } + BOOST_ASSERT(total_free_nodes >= m_totally_free_blocks*m_real_num_node); } - BOOST_ASSERT(total_free_nodes >= m_totally_free_blocks*m_real_num_node); - - //Check that the total totally free blocks are correct - it = m_block_multiset.begin(); - itend = m_block_multiset.end(); - total_free = 0; - for(; it != itend; ++it){ - total_free += it->free_nodes.size() == m_real_num_node; + { //Check that the total totally free blocks are correct + BOOST_ASSERT(m_block_container.size() >= m_totally_free_blocks); + const_block_iterator it = m_block_container.cend(); + size_type total_free_blocks = m_totally_free_blocks; + while(total_free_blocks--){ + BOOST_ASSERT((--it)->free_nodes.size() == m_real_num_node); + } } - BOOST_ASSERT(total_free >= m_totally_free_blocks); if(!AlignOnly){ //Check that header offsets are correct - it = m_block_multiset.begin(); + const_block_iterator it = m_block_container.begin(); for(; it != itend; ++it){ - hdr_offset_holder *hdr_off_holder = priv_first_subblock_from_block(&*it); + hdr_offset_holder *hdr_off_holder = this->priv_first_subblock_from_block(const_cast<block_info_t *>(&*it)); for(size_type i = 0, max = m_num_subblocks; i < max; ++i){ - BOOST_ASSERT(hdr_off_holder->hdr_offset == size_type(reinterpret_cast<char*>(&*it)- reinterpret_cast<char*>(hdr_off_holder))); + const size_type offset = reinterpret_cast<char*>(const_cast<block_info_t *>(&*it)) - reinterpret_cast<char*>(hdr_off_holder); + BOOST_ASSERT(hdr_off_holder->hdr_offset == offset); BOOST_ASSERT(0 == ((size_type)hdr_off_holder & (m_real_block_alignment - 1))); BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (m_real_block_alignment - 1))); hdr_off_holder = reinterpret_cast<hdr_offset_holder *>(reinterpret_cast<char*>(hdr_off_holder) + m_real_block_alignment); @@ -500,19 +689,21 @@ class private_adaptive_node_pool_impl void priv_clear() { #ifndef NDEBUG - block_iterator it = m_block_multiset.begin(); - block_iterator itend = m_block_multiset.end(); - size_type num_free_nodes = 0; + 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() == m_real_num_node); - ++num_free_nodes; + ++n_free_nodes; } - BOOST_ASSERT(num_free_nodes == m_totally_free_blocks); + BOOST_ASSERT(n_free_nodes == m_totally_free_blocks); #endif //Check for memory leaks - priv_invariants(); - m_block_multiset.clear_and_dispose(block_destroyer(this)); + this->priv_invariants(); + multiallocation_chain chain; + m_block_container.clear_and_dispose(block_destroyer(this, chain)); + this->mp_segment_mngr_base->deallocate_many(chain); m_totally_free_blocks = 0; } @@ -534,93 +725,129 @@ class private_adaptive_node_pool_impl } block_info_t *priv_block_from_node(void *node) const - { return priv_block_from_node(node, IsAlignOnly()); } + { return this->priv_block_from_node(node, IsAlignOnly()); } hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block) const + { return this->priv_first_subblock_from_block(block, IsAlignOnly()); } + + hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block, AlignOnlyFalse) const { - hdr_offset_holder *hdr_off_holder = reinterpret_cast<hdr_offset_holder*> + hdr_offset_holder *const hdr_off_holder = reinterpret_cast<hdr_offset_holder*> (reinterpret_cast<char*>(block) - (m_num_subblocks-1)*m_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 & (m_real_block_alignment - 1))); + BOOST_ASSERT(0 == ((std::size_t)hdr_off_holder & (m_real_block_alignment - 1))); BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (m_real_block_alignment - 1))); return hdr_off_holder; } + hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block, AlignOnlyTrue) const + { + return reinterpret_cast<hdr_offset_holder*>(block); + } + + void priv_dispatch_block_chain_or_free + ( multiallocation_chain &chain, block_info_t &c_info, size_type num_node + , char *mem_address, size_type total_elements, bool insert_block_if_free) + { + BOOST_ASSERT(chain.size() <= total_elements); + //First add all possible nodes to the chain + const size_type left = total_elements - chain.size(); + const size_type max_chain = (num_node < left) ? num_node : left; + mem_address = static_cast<char *>(container_detail::to_raw_pointer + (chain.incorporate_after(chain.last(), void_pointer(mem_address), m_real_node_size, max_chain))); + //Now store remaining nodes in the free list + if(const size_type max_free = num_node - max_chain){ + free_nodes_t & free_nodes = c_info.free_nodes; + free_nodes.incorporate_after(free_nodes.last(), void_pointer(mem_address), m_real_node_size, max_free); + if(insert_block_if_free){ + m_block_container.push_front(c_info); + } + } + } + //!Allocates a several blocks of nodes. Can throw - void priv_alloc_block(size_type n, AlignOnlyTrue) + void priv_append_from_new_blocks(size_type min_elements, multiallocation_chain &chain, AlignOnlyTrue) { - size_type real_block_size = m_real_block_alignment - PayloadPerAllocation; + BOOST_ASSERT(m_block_container.empty()); + BOOST_ASSERT(min_elements > 0); + const size_type n = (min_elements - 1)/m_real_num_node + 1; + const size_type real_block_size = m_real_block_alignment - PayloadPerAllocation; + const size_type total_elements = 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, m_real_block_alignment)); - if(!mem_address) throw std::bad_alloc(); - ++m_totally_free_blocks; - block_info_t *c_info = new(mem_address)block_info_t(); - m_block_multiset.insert(m_block_multiset.end(), *c_info); - + 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->deallocate_nodes(chain); + throw_bad_alloc(); + } + block_info_t &c_info = *new(mem_address)block_info_t(); mem_address += HdrSize; - //We initialize all Nodes in Node Block to insert - //them in the free Node list - typename free_nodes_t::iterator prev_insert_pos = c_info->free_nodes.before_begin(); - for(size_type i = 0; i < m_real_num_node; ++i){ - prev_insert_pos = c_info->free_nodes.insert_after(prev_insert_pos, *(node_t*)mem_address); - mem_address += m_real_node_size; + if(i != (n-1)){ + chain.incorporate_after(chain.last(), void_pointer(mem_address), m_real_node_size, m_real_num_node); + } + else{ + this->priv_dispatch_block_chain_or_free(chain, c_info, m_real_num_node, mem_address, total_elements, true); } } } - void priv_alloc_block(size_type n, AlignOnlyFalse) + void priv_append_from_new_blocks(size_type min_elements, multiallocation_chain &chain, AlignOnlyFalse) { - size_type real_block_size = m_real_block_alignment*m_num_subblocks - PayloadPerAllocation; - size_type elements_per_subblock = (m_real_block_alignment - HdrOffsetSize)/m_real_node_size; - size_type hdr_subblock_elements = (m_real_block_alignment - HdrSize - PayloadPerAllocation)/m_real_node_size; + BOOST_ASSERT(m_block_container.empty()); + BOOST_ASSERT(min_elements > 0); + const size_type n = (min_elements - 1)/m_real_num_node + 1; + const size_type real_block_size = m_real_block_alignment*m_num_subblocks - PayloadPerAllocation; + const size_type elements_per_subblock = (m_real_block_alignment - HdrOffsetSize)/m_real_node_size; + const size_type hdr_subblock_elements = (m_real_block_alignment - HdrSize - PayloadPerAllocation)/m_real_node_size; + const size_type total_elements = 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, m_real_block_alignment)); - if(!mem_address) throw std::bad_alloc(); - ++m_totally_free_blocks; - + 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->deallocate_nodes(chain); + throw_bad_alloc(); + } //First initialize header information on the last subblock char *hdr_addr = mem_address + m_real_block_alignment*(m_num_subblocks-1); - block_info_t *c_info = new(hdr_addr)block_info_t(); + block_info_t &c_info = *new(hdr_addr)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)); - typename free_nodes_t::iterator prev_insert_pos = c_info->free_nodes.before_begin(); - for( size_type subblock = 0, maxsubblock = m_num_subblocks - 1 - ; subblock < maxsubblock - ; ++subblock, mem_address += m_real_block_alignment){ - //Initialize header offset mark - new(mem_address) hdr_offset_holder(size_type(hdr_addr - mem_address)); - char *pNode = mem_address + HdrOffsetSize; - for(size_type i = 0; i < elements_per_subblock; ++i){ - prev_insert_pos = c_info->free_nodes.insert_after(prev_insert_pos, *new (pNode) node_t); - pNode += m_real_node_size; + BOOST_ASSERT(static_cast<void*>(&static_cast<hdr_offset_holder&>(c_info).hdr_offset) == + static_cast<void*>(&c_info)); (void)c_info; + if(i != (n-1)){ + for( size_type subblock = 0, maxsubblock = m_num_subblocks - 1 + ; subblock < maxsubblock + ; ++subblock, mem_address += m_real_block_alignment){ + //Initialize header offset mark + new(mem_address) hdr_offset_holder(size_type(hdr_addr - mem_address)); + chain.incorporate_after + (chain.last(), void_pointer(mem_address + HdrOffsetSize), m_real_node_size, elements_per_subblock); } + chain.incorporate_after(chain.last(), void_pointer(hdr_addr + HdrSize), m_real_node_size, hdr_subblock_elements); } - { - char *pNode = hdr_addr + HdrSize; - //We initialize all Nodes in Node Block to insert - //them in the free Node list - for(size_type i = 0; i < hdr_subblock_elements; ++i){ - prev_insert_pos = c_info->free_nodes.insert_after(prev_insert_pos, *new (pNode) node_t); - pNode += m_real_node_size; + else{ + for( size_type subblock = 0, maxsubblock = m_num_subblocks - 1 + ; subblock < maxsubblock + ; ++subblock, mem_address += m_real_block_alignment){ + //Initialize header offset mark + new(mem_address) hdr_offset_holder(size_type(hdr_addr - mem_address)); + this->priv_dispatch_block_chain_or_free + (chain, c_info, elements_per_subblock, mem_address + HdrOffsetSize, total_elements, false); } + this->priv_dispatch_block_chain_or_free + (chain, c_info, hdr_subblock_elements, hdr_addr + HdrSize, total_elements, true); } - //Insert the block after the free node list is full - m_block_multiset.insert(m_block_multiset.end(), *c_info); } } - //!Allocates a block of nodes. Can throw std::bad_alloc - void priv_alloc_block(size_type n) - { return priv_alloc_block(n, IsAlignOnly()); } - private: typedef typename boost::intrusive::pointer_traits <void_pointer>::template rebind_pointer<segment_manager_base_type>::type segment_mngr_base_ptr_t; @@ -634,9 +861,9 @@ class private_adaptive_node_pool_impl //This is the real number of nodes per block //const size_type m_real_num_node; - segment_mngr_base_ptr_t mp_segment_mngr_base; //Segment manager - block_multiset_t m_block_multiset; //Intrusive block list - size_type m_totally_free_blocks; //Free blocks + 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 }; } //namespace container_detail { |