Alien-boost-mini
view release on metacpan or search on metacpan
include/boost/container/detail/adaptive_node_pool_impl.hpp view on Meta::CPAN
< 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
include/boost/container/detail/adaptive_node_pool_impl.hpp view on Meta::CPAN
//
/////////////////////////////////////////////
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);
include/boost/container/detail/adaptive_node_pool_impl.hpp view on Meta::CPAN
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);
( run in 0.657 second using v1.01-cache-2.11-cpan-cdf2f3d4e48 )