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