adaptive_node_pool.hpp

来自「Boost provides free peer-reviewed portab」· HPP 代码 · 共 655 行 · 第 1/2 页

         m_block_multiset.erase_and_dispose
            (it, block_destroyer(this));
      }
   }

   void priv_reinsert_nodes_in_block(multiallocation_iterator it)
   {
      multiallocation_iterator itend;
      block_iterator block_it(m_block_multiset.end());
      while(it != itend){
         void *pElem = &*it;
         ++it;
         priv_invariants();
         block_info_t *block_info = this->priv_block_from_node(pElem);
         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()
   {
      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();
      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 private_adaptive_node_pool_impl *impl)
         :  mp_impl(impl)
      {}

      void operator()(typename block_multiset_t::pointer to_deallocate)
      {
         std::size_t free_nodes = to_deallocate->free_nodes.size();
         (void)free_nodes;
         assert(free_nodes == mp_impl->m_real_num_node);
         assert(0 == to_deallocate->hdr_offset);
         hdr_offset_holder *hdr_off_holder = mp_impl->priv_first_subblock_from_block(detail::get_pointer(to_deallocate));
         mp_impl->mp_segment_mngr_base->deallocate(hdr_off_holder);
      }
      const private_adaptive_node_pool_impl *mp_impl;
   };

   //This macro will activate invariant checking. Slow, but helpful for debugging the code.
   //#define BOOST_INTERPROCESS_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
   void priv_invariants()
   #ifdef BOOST_INTERPROCESS_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
   #undef BOOST_INTERPROCESS_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
   {
      //We iterate through the block list 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();
            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();
         }
         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();
         std::size_t total_free_blocks = 0;
         for(; it != itend; ++it){
            total_free_blocks += (it->free_nodes.size() == m_real_num_node);
         }
         assert(total_free_blocks == m_totally_free_blocks);
      }
      {
      //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){
            assert(hdr_off_holder->hdr_offset == std::size_t(reinterpret_cast<char*>(&*it)- reinterpret_cast<char*>(hdr_off_holder)));
            assert(0 == ((std::size_t)hdr_off_holder & (m_real_block_alignment - 1)));
            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
         assert(it->free_nodes.size() == m_real_num_node);
         ++num_free_nodes;
      }
      assert(num_free_nodes == m_totally_free_blocks);
      #endif
      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) const
   {
      hdr_offset_holder *hdr_off_holder =
         reinterpret_cast<hdr_offset_holder*>((std::size_t)node & std::size_t(~(m_real_block_alignment - 1)));
      assert(0 == ((std::size_t)hdr_off_holder & (m_real_block_alignment - 1)));
      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);
      assert(block->hdr_offset == 0);
      return block;
   }

   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);
      assert(hdr_off_holder->hdr_offset == std::size_t(reinterpret_cast<char*>(block) - reinterpret_cast<char*>(hdr_off_holder)));
      assert(0 == ((std::size_t)hdr_off_holder & (m_real_block_alignment - 1)));
      assert(0 == (hdr_off_holder->hdr_offset & (m_real_block_alignment - 1)));
      return hdr_off_holder;
   }

   //!Allocates a several blocks of nodes. Can throw boost::interprocess::bad_alloc
   void priv_alloc_block(std::size_t n)
   {
      std::size_t real_block_size = m_real_block_alignment*m_num_subblocks - SegmentManagerBase::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 - SegmentManagerBase::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
         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);
      }
   }

   private:
   typedef typename 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
};

template< class SegmentManager
        , std::size_t NodeSize
        , std::size_t NodesPerBlock
        , std::size_t MaxFreeBlocks
        , unsigned char OverheadPercent
        >
class private_adaptive_node_pool
   :  public private_adaptive_node_pool_impl
         <typename SegmentManager::segment_manager_base_type>
{
   typedef private_adaptive_node_pool_impl
      <typename SegmentManager::segment_manager_base_type> base_t;
   //Non-copyable
   private_adaptive_node_pool();
   private_adaptive_node_pool(const private_adaptive_node_pool &);
   private_adaptive_node_pool &operator=(const private_adaptive_node_pool &);

   public:
   typedef SegmentManager segment_manager;

   static const std::size_t nodes_per_block = NodesPerBlock;

   //Deprecated, use node_per_block
   static const std::size_t nodes_per_chunk = NodesPerBlock;

   //!Constructor from a segment manager. Never throws
   private_adaptive_node_pool(segment_manager *segment_mngr)
      :  base_t(segment_mngr, NodeSize, NodesPerBlock, MaxFreeBlocks, OverheadPercent)
   {}

   //!Returns the segment manager. Never throws
   segment_manager* get_segment_manager() const
   {  return static_cast<segment_manager*>(base_t::get_segment_manager_base()); }
};

//!Pooled shared memory allocator using adaptive pool. Includes
//!a reference count but the class does not delete itself, this is  
//!responsibility of user classes. Node size (NodeSize) and the number of
//!nodes allocated per block (NodesPerBlock) are known at compile time
template< class SegmentManager
        , std::size_t NodeSize
        , std::size_t NodesPerBlock
        , std::size_t MaxFreeBlocks
        , unsigned char OverheadPercent
        >
class shared_adaptive_node_pool 
   :  public detail::shared_pool_impl
      < private_adaptive_node_pool
         <SegmentManager, NodeSize, NodesPerBlock, MaxFreeBlocks, OverheadPercent>
      >
{
   typedef detail::shared_pool_impl
      < private_adaptive_node_pool
         <SegmentManager, NodeSize, NodesPerBlock, MaxFreeBlocks, OverheadPercent>
      > base_t;
   public:
   shared_adaptive_node_pool(SegmentManager *segment_mgnr)
      : base_t(segment_mgnr)
   {}
};

}  //namespace detail {
}  //namespace interprocess {
}  //namespace boost {

#include <boost/interprocess/detail/config_end.hpp>

#endif   //#ifndef BOOST_INTERPROCESS_DETAIL_ADAPTIVE_NODE_POOL_HPP