////////////////////////////////////////////////////////////////////////////// | |
// | |
// (C) Copyright Ion Gaztanaga 2005-2009. Distributed under the Boost | |
// Software License, Version 1.0. (See accompanying file | |
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
// | |
// See http://www.boost.org/libs/container for documentation. | |
// | |
////////////////////////////////////////////////////////////////////////////// | |
#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP | |
#define BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP | |
#if (defined _MSC_VER) && (_MSC_VER >= 1200) | |
# pragma once | |
#endif | |
#include "config_begin.hpp" | |
#include INCLUDE_BOOST_CONTAINER_CONTAINER_FWD_HPP | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_WORKAROUND_HPP | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_UTILITIES_HPP | |
#include <boost/pointer_to_other.hpp> | |
#include <boost/intrusive/set.hpp> | |
#include <boost/intrusive/slist.hpp> | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_TYPE_TRAITS_HPP | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_MATH_FUNCTIONS_HPP | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_MPL_HPP | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_POOL_COMMON_HPP | |
#include <boost/assert.hpp> | |
#include <cstddef> | |
namespace boost { | |
namespace container { | |
namespace containers_detail { | |
struct hdr_offset_holder | |
{ | |
hdr_offset_holder(std::size_t offset = 0) | |
: hdr_offset(offset) | |
{} | |
std::size_t hdr_offset; | |
}; | |
template<class VoidPointer> | |
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; | |
struct block_info_t | |
: | |
public hdr_offset_holder, | |
public multiset_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)); | |
} | |
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; | |
}; | |
inline std::size_t calculate_alignment | |
( std::size_t overhead_percent, std::size_t real_node_size | |
, std::size_t hdr_size, std::size_t hdr_offset_size, std::size_t payload_per_allocation) | |
{ | |
//to-do: handle real_node_size != node_size | |
const std::size_t divisor = overhead_percent*real_node_size; | |
const std::size_t dividend = hdr_offset_size*100; | |
std::size_t elements_per_subblock = (dividend - 1)/divisor + 1; | |
std::size_t candidate_power_of_2 = | |
upper_power_of_2(elements_per_subblock*real_node_size + hdr_offset_size); | |
bool overhead_satisfied = false; | |
//Now calculate the wors-case overhead for a subblock | |
const std::size_t max_subblock_overhead = hdr_size + payload_per_allocation; | |
while(!overhead_satisfied){ | |
elements_per_subblock = (candidate_power_of_2 - max_subblock_overhead)/real_node_size; | |
const std::size_t overhead_size = candidate_power_of_2 - elements_per_subblock*real_node_size; | |
if(overhead_size*100/candidate_power_of_2 < overhead_percent){ | |
overhead_satisfied = true; | |
} | |
else{ | |
candidate_power_of_2 <<= 1; | |
} | |
} | |
return candidate_power_of_2; | |
} | |
inline void calculate_num_subblocks | |
(std::size_t alignment, std::size_t real_node_size, std::size_t elements_per_block | |
, std::size_t &num_subblocks, std::size_t &real_num_node, std::size_t overhead_percent | |
, std::size_t hdr_size, std::size_t hdr_offset_size, std::size_t payload_per_allocation) | |
{ | |
std::size_t elements_per_subblock = (alignment - hdr_offset_size)/real_node_size; | |
std::size_t possible_num_subblock = (elements_per_block - 1)/elements_per_subblock + 1; | |
std::size_t 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; | |
} | |
elements_per_subblock = (alignment - hdr_offset_size)/real_node_size; | |
bool overhead_satisfied = false; | |
while(!overhead_satisfied){ | |
const std::size_t total_data = (elements_per_subblock*(possible_num_subblock-1) + hdr_subblock_elements)*real_node_size; | |
const std::size_t total_size = alignment*possible_num_subblock; | |
if((total_size - total_data)*100/total_size < overhead_percent){ | |
overhead_satisfied = true; | |
} | |
else{ | |
++possible_num_subblock; | |
} | |
} | |
num_subblocks = possible_num_subblock; | |
real_num_node = (possible_num_subblock-1)*elements_per_subblock + hdr_subblock_elements; | |
} | |
template<class SegmentManagerBase, bool AlignOnly = false> | |
class private_adaptive_node_pool_impl | |
{ | |
//Non-copyable | |
private_adaptive_node_pool_impl(); | |
private_adaptive_node_pool_impl(const private_adaptive_node_pool_impl &); | |
private_adaptive_node_pool_impl &operator=(const private_adaptive_node_pool_impl &); | |
typedef private_adaptive_node_pool_impl this_type; | |
typedef typename SegmentManagerBase::void_pointer void_pointer; | |
static const std::size_t PayloadPerAllocation = SegmentManagerBase::PayloadPerAllocation; | |
typedef bool_<AlignOnly> IsAlignOnly; | |
typedef true_ AlignOnlyTrue; | |
typedef false_ AlignOnlyFalse; | |
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; | |
private: | |
typedef typename adaptive_pool_types<void_pointer>::block_info_t block_info_t; | |
typedef typename adaptive_pool_types<void_pointer>::block_multiset_t block_multiset_t; | |
typedef typename block_multiset_t::iterator block_iterator; | |
static const std::size_t MaxAlign = alignment_of<node_t>::value; | |
static const std::size_t HdrSize = ((sizeof(block_info_t)-1)/MaxAlign+1)*MaxAlign; | |
static const std::size_t HdrOffsetSize = ((sizeof(hdr_offset_holder)-1)/MaxAlign+1)*MaxAlign; | |
public: | |
//!Segment manager typedef | |
typedef SegmentManagerBase segment_manager_base_type; | |
//!Constructor from a segment manager. Never throws | |
private_adaptive_node_pool_impl | |
( segment_manager_base_type *segment_mngr_base | |
, std::size_t node_size | |
, std::size_t nodes_per_block | |
, std::size_t max_free_blocks | |
, unsigned char overhead_percent | |
) | |
: m_max_free_blocks(max_free_blocks) | |
, m_real_node_size(lcm(node_size, std::size_t(alignment_of<node_t>::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 | |
, m_real_block_alignment | |
(AlignOnly ? | |
upper_power_of_2(HdrSize + m_real_node_size*nodes_per_block) : | |
calculate_alignment( overhead_percent, m_real_node_size | |
, HdrSize, HdrOffsetSize, PayloadPerAllocation)) | |
//This is the real number of nodes per block | |
, m_num_subblocks(0) | |
, 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_totally_free_blocks(0) | |
{ | |
if(!AlignOnly){ | |
calculate_num_subblocks | |
( m_real_block_alignment | |
, m_real_node_size | |
, nodes_per_block | |
, m_num_subblocks | |
, m_real_num_node | |
, overhead_percent | |
, HdrSize | |
, HdrOffsetSize | |
, PayloadPerAllocation); | |
} | |
} | |
//!Destructor. Deallocates all allocated blocks. Never throws | |
~private_adaptive_node_pool_impl() | |
{ priv_clear(); } | |
std::size_t get_real_num_node() const | |
{ return m_real_num_node; } | |
//!Returns the segment manager. Never throws | |
segment_manager_base_type* get_segment_manager_base()const | |
{ return containers_detail::get_pointer(mp_segment_mngr_base); } | |
//!Allocates array of count elements. Can throw | |
void *allocate_node() | |
{ | |
priv_invariants(); | |
//If there are no free nodes we allocate a new block | |
if (m_block_multiset.empty()){ | |
priv_alloc_block(1); | |
} | |
//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(); | |
} | |
//!Allocates n nodes. | |
//!Can throw | |
multiallocation_chain allocate_nodes(const std::size_t n) | |
{ | |
multiallocation_chain chain; | |
std::size_t i = 0; | |
try{ | |
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); | |
} | |
free_nodes_t &free_nodes = m_block_multiset.begin()->free_nodes; | |
const std::size_t free_nodes_count_before = free_nodes.size(); | |
if(free_nodes_count_before == m_real_num_node){ | |
--m_totally_free_blocks; | |
} | |
const std::size_t num_elems = ((n-i) < free_nodes_count_before) ? (n-i) : free_nodes_count_before; | |
for(std::size_t j = 0; j != num_elems; ++j){ | |
void *new_node = &free_nodes.front(); | |
free_nodes.pop_front(); | |
chain.push_back(new_node); | |
} | |
if(free_nodes.empty()){ | |
m_block_multiset.erase(m_block_multiset.begin()); | |
} | |
i += num_elems; | |
} | |
} | |
catch(...){ | |
this->deallocate_nodes(BOOST_CONTAINER_MOVE_NAMESPACE::move(chain)); | |
throw; | |
} | |
priv_invariants(); | |
return BOOST_CONTAINER_MOVE_NAMESPACE::move(chain); | |
} | |
//!Deallocates a linked list of nodes. Never throws | |
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_deallocate_free_blocks(m_max_free_blocks); | |
} | |
} | |
void deallocate_free_blocks() | |
{ this->priv_deallocate_free_blocks(0); } | |
std::size_t num_free_nodes() | |
{ | |
typedef typename block_multiset_t::const_iterator citerator; | |
std::size_t count = 0; | |
citerator it (m_block_multiset.begin()), itend(m_block_multiset.end()); | |
for(; it != itend; ++it){ | |
count += it->free_nodes.size(); | |
} | |
return count; | |
} | |
void swap(private_adaptive_node_pool_impl &other) | |
{ | |
BOOST_ASSERT(m_max_free_blocks == other.m_max_free_blocks); | |
BOOST_ASSERT(m_real_node_size == other.m_real_node_size); | |
BOOST_ASSERT(m_real_block_alignment == other.m_real_block_alignment); | |
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); | |
} | |
//Deprecated, use deallocate_free_blocks | |
void deallocate_free_chunks() | |
{ this->priv_deallocate_free_blocks(0); } | |
private: | |
void priv_deallocate_free_blocks(std::size_t max_free_blocks) | |
{ | |
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; | |
--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, std::size_t n) | |
{ | |
block_iterator block_it(m_block_multiset.end()); | |
while(n--){ | |
void *pElem = containers_detail::get_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 | |
std::size_t 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); | |
} | |
else{ | |
block_iterator next_block(this_block); | |
++next_block; | |
if(next_block != block_it){ | |
std::size_t 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(); | |
} | |
} | |
node_t *priv_take_first_node() | |
{ | |
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 std::size_t 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()); | |
} | |
else if(free_nodes_count == m_real_num_node){ | |
--m_totally_free_blocks; | |
} | |
priv_invariants(); | |
return first_node; | |
} | |
class block_destroyer; | |
friend class block_destroyer; | |
class block_destroyer | |
{ | |
public: | |
block_destroyer(const this_type *impl) | |
: mp_impl(impl) | |
{} | |
void operator()(typename block_multiset_t::pointer to_deallocate) | |
{ return this->do_destroy(to_deallocate, IsAlignOnly()); } | |
private: | |
void do_destroy(typename block_multiset_t::pointer to_deallocate, AlignOnlyTrue) | |
{ | |
std::size_t 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); | |
} | |
void do_destroy(typename block_multiset_t::pointer to_deallocate, AlignOnlyFalse) | |
{ | |
std::size_t free_nodes = to_deallocate->free_nodes.size(); | |
(void)free_nodes; | |
BOOST_ASSERT(free_nodes == 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(containers_detail::get_pointer(to_deallocate)); | |
mp_impl->mp_segment_mngr_base->deallocate(hdr_off_holder); | |
} | |
const this_type *mp_impl; | |
}; | |
//This macro will activate invariant checking. Slow, but helpful for debugging the code. | |
//#define BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS | |
void priv_invariants() | |
#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; | |
std::size_t sp = prev->free_nodes.size(), | |
si = it->free_nodes.size(); | |
BOOST_ASSERT(sp <= si); | |
(void)sp; (void)si; | |
} | |
} | |
//Check that the total free nodes are correct | |
it = m_block_multiset.begin(); | |
itend = m_block_multiset.end(); | |
std::size_t 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); | |
//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; | |
} | |
BOOST_ASSERT(total_free >= m_totally_free_blocks); | |
if(!AlignOnly){ | |
//Check that header offsets are correct | |
it = m_block_multiset.begin(); | |
for(; it != itend; ++it){ | |
hdr_offset_holder *hdr_off_holder = priv_first_subblock_from_block(&*it); | |
for(std::size_t i = 0, max = m_num_subblocks; i < max; ++i){ | |
BOOST_ASSERT(hdr_off_holder->hdr_offset == std::size_t(reinterpret_cast<char*>(&*it)- reinterpret_cast<char*>(hdr_off_holder))); | |
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))); | |
hdr_off_holder = reinterpret_cast<hdr_offset_holder *>(reinterpret_cast<char*>(hdr_off_holder) + m_real_block_alignment); | |
} | |
} | |
} | |
} | |
#else | |
{} //empty | |
#endif | |
//!Deallocates all used memory. Never throws | |
void priv_clear() | |
{ | |
#ifndef NDEBUG | |
block_iterator it = m_block_multiset.begin(); | |
block_iterator itend = m_block_multiset.end(); | |
std::size_t num_free_nodes = 0; | |
for(; it != itend; ++it){ | |
//Check for memory leak | |
BOOST_ASSERT(it->free_nodes.size() == m_real_num_node); | |
++num_free_nodes; | |
} | |
BOOST_ASSERT(num_free_nodes == m_totally_free_blocks); | |
#endif | |
//Check for memory leaks | |
priv_invariants(); | |
m_block_multiset.clear_and_dispose(block_destroyer(this)); | |
m_totally_free_blocks = 0; | |
} | |
block_info_t *priv_block_from_node(void *node, AlignOnlyFalse) const | |
{ | |
hdr_offset_holder *hdr_off_holder = | |
reinterpret_cast<hdr_offset_holder*>((std::size_t)node & std::size_t(~(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))); | |
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, AlignOnlyTrue) const | |
{ | |
return (block_info_t *)((std::size_t)node & std::size_t(~(m_real_block_alignment - 1))); | |
} | |
block_info_t *priv_block_from_node(void *node) const | |
{ return priv_block_from_node(node, IsAlignOnly()); } | |
hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block) const | |
{ | |
hdr_offset_holder *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 == std::size_t(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 == (hdr_off_holder->hdr_offset & (m_real_block_alignment - 1))); | |
return hdr_off_holder; | |
} | |
//!Allocates a several blocks of nodes. Can throw | |
void priv_alloc_block(std::size_t n, AlignOnlyTrue) | |
{ | |
std::size_t real_block_size = m_real_block_alignment - PayloadPerAllocation; | |
for(std::size_t 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); | |
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(std::size_t 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; | |
} | |
} | |
} | |
void priv_alloc_block(std::size_t n, AlignOnlyFalse) | |
{ | |
std::size_t real_block_size = m_real_block_alignment*m_num_subblocks - PayloadPerAllocation; | |
std::size_t elements_per_subblock = (m_real_block_alignment - HdrOffsetSize)/m_real_node_size; | |
std::size_t hdr_subblock_elements = (m_real_block_alignment - HdrSize - PayloadPerAllocation)/m_real_node_size; | |
for(std::size_t 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; | |
//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; | |
//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( std::size_t 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(std::size_t(hdr_addr - mem_address)); | |
char *pNode = mem_address + HdrOffsetSize; | |
for(std::size_t 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; | |
} | |
} | |
{ | |
char *pNode = hdr_addr + HdrSize; | |
//We initialize all Nodes in Node Block to insert | |
//them in the free Node list | |
for(std::size_t 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; | |
} | |
} | |
//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(std::size_t n) | |
{ return priv_alloc_block(n, IsAlignOnly()); } | |
private: | |
typedef typename boost::pointer_to_other | |
<void_pointer, segment_manager_base_type>::type segment_mngr_base_ptr_t; | |
const std::size_t m_max_free_blocks; | |
const std::size_t 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 | |
const std::size_t m_real_block_alignment; | |
std::size_t m_num_subblocks; | |
//This is the real number of nodes per block | |
//const | |
std::size_t m_real_num_node; | |
segment_mngr_base_ptr_t mp_segment_mngr_base; //Segment manager | |
block_multiset_t m_block_multiset; //Intrusive block list | |
std::size_t m_totally_free_blocks; //Free blocks | |
}; | |
} //namespace containers_detail { | |
} //namespace container { | |
} //namespace boost { | |
#include INCLUDE_BOOST_CONTAINER_DETAIL_CONFIG_END_HPP | |
#endif //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP |