summaryrefslogtreecommitdiff
path: root/boost/container/detail/adaptive_node_pool_impl.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/container/detail/adaptive_node_pool_impl.hpp')
-rw-r--r--boost/container/detail/adaptive_node_pool_impl.hpp725
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 {