| ////////////////////////////////////////////////////////////////////////////// |
| // |
| // (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_NODE_POOL_IMPL_HPP |
| #define BOOST_CONTAINER_DETAIL_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> |
| #include <functional> //std::unary_function |
| |
| namespace boost { |
| namespace container { |
| namespace containers_detail { |
| |
| template<class SegmentManagerBase> |
| class private_node_pool_impl |
| { |
| //Non-copyable |
| private_node_pool_impl(); |
| private_node_pool_impl(const private_node_pool_impl &); |
| private_node_pool_impl &operator=(const private_node_pool_impl &); |
| |
| //A node object will hold node_t when it's not allocated |
| public: |
| typedef typename SegmentManagerBase::void_pointer void_pointer; |
| typedef typename node_slist<void_pointer>::slist_hook_t slist_hook_t; |
| 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 bi::make_slist |
| < node_t, bi::base_hook<slist_hook_t> |
| , bi::linear<true> |
| , bi::constant_time_size<false> >::type blockslist_t; |
| public: |
| |
| //!Segment manager typedef |
| typedef SegmentManagerBase segment_manager_base_type; |
| |
| //!Constructor from a segment manager. Never throws |
| private_node_pool_impl(segment_manager_base_type *segment_mngr_base, std::size_t node_size, std::size_t nodes_per_block) |
| : m_nodes_per_block(nodes_per_block) |
| , m_real_node_size(lcm(node_size, std::size_t(alignment_of<node_t>::value))) |
| //General purpose allocator |
| , mp_segment_mngr_base(segment_mngr_base) |
| , m_blocklist() |
| , m_freelist() |
| //Debug node count |
| , m_allocated(0) |
| {} |
| |
| //!Destructor. Deallocates all allocated blocks. Never throws |
| ~private_node_pool_impl() |
| { this->purge_blocks(); } |
| |
| std::size_t get_real_num_node() const |
| { return m_nodes_per_block; } |
| |
| //!Returns the segment manager. Never throws |
| segment_manager_base_type* get_segment_manager_base()const |
| { return containers_detail::get_pointer(mp_segment_mngr_base); } |
| |
| void *allocate_node() |
| { return priv_alloc_node(); } |
| |
| //!Deallocates an array pointed by ptr. Never throws |
| void deallocate_node(void *ptr) |
| { priv_dealloc_node(ptr); } |
| |
| //!Allocates a singly linked list of n nodes ending in null pointer. |
| multiallocation_chain allocate_nodes(const std::size_t n) |
| { |
| //Preallocate all needed blocks to fulfill the request |
| std::size_t cur_nodes = m_freelist.size(); |
| if(cur_nodes < n){ |
| priv_alloc_block(((n - cur_nodes) - 1)/m_nodes_per_block + 1); |
| } |
| |
| //We just iterate the needed nodes to get the last we'll erase |
| typedef typename free_nodes_t::iterator free_iterator; |
| free_iterator before_last_new_it = m_freelist.before_begin(); |
| for(std::size_t j = 0; j != n; ++j){ |
| ++before_last_new_it; |
| } |
| |
| //Cache the first node of the allocated range before erasing |
| free_iterator first_node(m_freelist.begin()); |
| free_iterator last_node (before_last_new_it); |
| |
| //Erase the range. Since we already have the distance, this is O(1) |
| m_freelist.erase_after( m_freelist.before_begin() |
| , ++free_iterator(before_last_new_it) |
| , n); |
| |
| //Now take the last erased node and just splice it in the end |
| //of the intrusive list that will be traversed by the multialloc iterator. |
| multiallocation_chain chain; |
| chain.incorporate_after(chain.before_begin(), &*first_node, &*last_node, n); |
| m_allocated += n; |
| return BOOST_CONTAINER_MOVE_NAMESPACE::move(chain); |
| } |
| |
| void deallocate_nodes(multiallocation_chain chain) |
| { |
| typedef typename multiallocation_chain::iterator iterator; |
| iterator it(chain.begin()), itend(chain.end()); |
| while(it != itend){ |
| void *pElem = &*it; |
| ++it; |
| priv_dealloc_node(pElem); |
| } |
| } |
| |
| //!Deallocates all the free blocks of memory. Never throws |
| void deallocate_free_blocks() |
| { |
| typedef typename free_nodes_t::iterator nodelist_iterator; |
| typename blockslist_t::iterator bit(m_blocklist.before_begin()), |
| it(m_blocklist.begin()), |
| itend(m_blocklist.end()); |
| free_nodes_t backup_list; |
| nodelist_iterator backup_list_last = backup_list.before_begin(); |
| |
| //Execute the algorithm and get an iterator to the last value |
| std::size_t blocksize = get_rounded_size |
| (m_real_node_size*m_nodes_per_block, alignment_of<node_t>::value); |
| |
| while(it != itend){ |
| //Collect all the nodes from the block pointed by it |
| //and push them in the list |
| free_nodes_t free_nodes; |
| nodelist_iterator last_it = free_nodes.before_begin(); |
| const void *addr = get_block_from_hook(&*it, blocksize); |
| |
| m_freelist.remove_and_dispose_if |
| (is_between(addr, blocksize), push_in_list(free_nodes, last_it)); |
| |
| //If the number of nodes is equal to m_nodes_per_block |
| //this means that the block can be deallocated |
| if(free_nodes.size() == m_nodes_per_block){ |
| //Unlink the nodes |
| free_nodes.clear(); |
| it = m_blocklist.erase_after(bit); |
| mp_segment_mngr_base->deallocate((void*)addr); |
| } |
| //Otherwise, insert them in the backup list, since the |
| //next "remove_if" does not need to check them again. |
| else{ |
| //Assign the iterator to the last value if necessary |
| if(backup_list.empty() && !m_freelist.empty()){ |
| backup_list_last = last_it; |
| } |
| //Transfer nodes. This is constant time. |
| backup_list.splice_after |
| ( backup_list.before_begin() |
| , free_nodes |
| , free_nodes.before_begin() |
| , last_it |
| , free_nodes.size()); |
| bit = it; |
| ++it; |
| } |
| } |
| //We should have removed all the nodes from the free list |
| BOOST_ASSERT(m_freelist.empty()); |
| |
| //Now pass all the node to the free list again |
| m_freelist.splice_after |
| ( m_freelist.before_begin() |
| , backup_list |
| , backup_list.before_begin() |
| , backup_list_last |
| , backup_list.size()); |
| } |
| |
| std::size_t num_free_nodes() |
| { return m_freelist.size(); } |
| |
| //!Deallocates all used memory. Precondition: all nodes allocated from this pool should |
| //!already be deallocated. Otherwise, undefined behaviour. Never throws |
| void purge_blocks() |
| { |
| //check for memory leaks |
| BOOST_ASSERT(m_allocated==0); |
| std::size_t blocksize = get_rounded_size |
| (m_real_node_size*m_nodes_per_block, alignment_of<node_t>::value); |
| typename blockslist_t::iterator |
| it(m_blocklist.begin()), itend(m_blocklist.end()), aux; |
| |
| //We iterate though the NodeBlock list to free the memory |
| while(!m_blocklist.empty()){ |
| void *addr = get_block_from_hook(&m_blocklist.front(), blocksize); |
| m_blocklist.pop_front(); |
| mp_segment_mngr_base->deallocate((void*)addr); |
| } |
| //Just clear free node list |
| m_freelist.clear(); |
| } |
| |
| void swap(private_node_pool_impl &other) |
| { |
| BOOST_ASSERT(m_nodes_per_block == other.m_nodes_per_block); |
| BOOST_ASSERT(m_real_node_size == other.m_real_node_size); |
| std::swap(mp_segment_mngr_base, other.mp_segment_mngr_base); |
| m_blocklist.swap(other.m_blocklist); |
| m_freelist.swap(other.m_freelist); |
| std::swap(m_allocated, other.m_allocated); |
| } |
| |
| private: |
| |
| struct push_in_list |
| { |
| push_in_list(free_nodes_t &l, typename free_nodes_t::iterator &it) |
| : slist_(l), last_it_(it) |
| {} |
| |
| void operator()(typename free_nodes_t::pointer p) const |
| { |
| slist_.push_front(*p); |
| if(slist_.size() == 1){ //Cache last element |
| ++last_it_ = slist_.begin(); |
| } |
| } |
| |
| private: |
| free_nodes_t &slist_; |
| typename free_nodes_t::iterator &last_it_; |
| }; |
| |
| struct is_between |
| : std::unary_function<typename free_nodes_t::value_type, bool> |
| { |
| is_between(const void *addr, std::size_t size) |
| : beg_(static_cast<const char *>(addr)), end_(beg_+size) |
| {} |
| |
| bool operator()(typename free_nodes_t::const_reference v) const |
| { |
| return (beg_ <= reinterpret_cast<const char *>(&v) && |
| end_ > reinterpret_cast<const char *>(&v)); |
| } |
| private: |
| const char * beg_; |
| const char * end_; |
| }; |
| |
| //!Allocates one node, using single segregated storage algorithm. |
| //!Never throws |
| node_t *priv_alloc_node() |
| { |
| //If there are no free nodes we allocate a new block |
| if (m_freelist.empty()) |
| priv_alloc_block(); |
| //We take the first free node |
| node_t *n = (node_t*)&m_freelist.front(); |
| m_freelist.pop_front(); |
| ++m_allocated; |
| return n; |
| } |
| |
| //!Deallocates one node, using single segregated storage algorithm. |
| //!Never throws |
| void priv_dealloc_node(void *pElem) |
| { |
| //We put the node at the beginning of the free node list |
| node_t * to_deallocate = static_cast<node_t*>(pElem); |
| m_freelist.push_front(*to_deallocate); |
| BOOST_ASSERT(m_allocated>0); |
| --m_allocated; |
| } |
| |
| //!Allocates several blocks of nodes. Can throw |
| void priv_alloc_block(std::size_t num_blocks = 1) |
| { |
| if(!num_blocks) |
| return; |
| std::size_t blocksize = |
| get_rounded_size(m_real_node_size*m_nodes_per_block, alignment_of<node_t>::value); |
| |
| try{ |
| for(std::size_t i = 0; i != num_blocks; ++i){ |
| //We allocate a new NodeBlock and put it as first |
| //element in the free Node list |
| char *pNode = reinterpret_cast<char*> |
| (mp_segment_mngr_base->allocate(blocksize + sizeof(node_t))); |
| char *pBlock = pNode; |
| m_blocklist.push_front(get_block_hook(pBlock, blocksize)); |
| |
| //We initialize all Nodes in Node Block to insert |
| //them in the free Node list |
| for(std::size_t i = 0; i < m_nodes_per_block; ++i, pNode += m_real_node_size){ |
| m_freelist.push_front(*new (pNode) node_t); |
| } |
| } |
| } |
| catch(...){ |
| //to-do: if possible, an efficient way to deallocate allocated blocks |
| throw; |
| } |
| } |
| |
| //!Deprecated, use deallocate_free_blocks |
| void deallocate_free_chunks() |
| { this->deallocate_free_blocks(); } |
| |
| //!Deprecated, use purge_blocks |
| void purge_chunks() |
| { this->purge_blocks(); } |
| |
| private: |
| //!Returns a reference to the block hook placed in the end of the block |
| static node_t & get_block_hook (void *block, std::size_t blocksize) |
| { |
| return *reinterpret_cast<node_t*>(reinterpret_cast<char*>(block) + blocksize); |
| } |
| |
| //!Returns the starting address of the block reference to the block hook placed in the end of the block |
| void *get_block_from_hook (node_t *hook, std::size_t blocksize) |
| { |
| return (reinterpret_cast<char*>(hook) - blocksize); |
| } |
| |
| private: |
| typedef typename boost::pointer_to_other |
| <void_pointer, segment_manager_base_type>::type segment_mngr_base_ptr_t; |
| |
| const std::size_t m_nodes_per_block; |
| const std::size_t m_real_node_size; |
| segment_mngr_base_ptr_t mp_segment_mngr_base; //Segment manager |
| blockslist_t m_blocklist; //Intrusive container of blocks |
| free_nodes_t m_freelist; //Intrusive container of free nods |
| std::size_t m_allocated; //Used nodes for debugging |
| }; |
| |
| |
| } //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 |