view release on metacpan or  search on metacpan

include/boost/container/detail/adaptive_node_pool_impl.hpp  view on Meta::CPAN

   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
        , std::size_t min_elements_per_block
        , std::size_t hdr_size
        , std::size_t hdr_offset_size
        , std::size_t overhead_percent
        , bool Loop = true>
struct candidate_power_of_2_ct
{
   typedef candidate_power_of_2_ct_helper
        < initial_alignment
        , real_node_size
        , payload_per_allocation
        , min_elements_per_block
        , hdr_size
        , hdr_offset_size
        , overhead_percent> helper_t;

   static const std::size_t candidate_power_of_2 = initial_alignment << std::size_t(!helper_t::overhead_satisfied);

   typedef typename candidate_power_of_2_ct
      < candidate_power_of_2
      , real_node_size
      , payload_per_allocation
      , min_elements_per_block
      , hdr_size
      , hdr_offset_size
      , overhead_percent
      , !helper_t::overhead_satisfied
      >::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;
};

template< 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
        >
struct candidate_power_of_2_ct
      < initial_alignment
      , real_node_size
      , payload_per_allocation
      , min_elements_per_block
      , hdr_size
      , hdr_offset_size
      , overhead_percent
      , false>
{
   typedef candidate_power_of_2_ct
      < initial_alignment
      , real_node_size
      , payload_per_allocation
      , min_elements_per_block
      , hdr_size
      , hdr_offset_size
      , overhead_percent
      , false> type;

   typedef candidate_power_of_2_ct_helper
        < initial_alignment
        , real_node_size
        , payload_per_allocation
        , min_elements_per_block
        , hdr_size
        , hdr_offset_size
        , overhead_percent> helper_t;

   static const std::size_t alignment = initial_alignment;
   static const std::size_t num_subblocks = helper_t::num_b_subblock+1;
   static const std::size_t real_num_node = helper_t::total_nodes;
};

/////////////////////////////////////////////
//
//       candidate_power_of_2_rt
//
/////////////////////////////////////////////
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:

include/boost/container/detail/adaptive_node_pool_impl.hpp  view on Meta::CPAN

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);
   }

   //!Deallocates a linked list of nodes. Never throws
   void deallocate_nodes(multiallocation_chain &nodes)
   {
      this->priv_deallocate_nodes(nodes, this->m_max_free_blocks, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment);
   }

   void deallocate_free_blocks()
   {  this->priv_deallocate_free_blocks(0, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment);  }

   //Deprecated, use deallocate_free_blocks
   void deallocate_free_chunks()
   {  this->priv_deallocate_free_blocks(0, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment);   }
};

}  //namespace dtl {
}  //namespace container {
}  //namespace boost {

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

#endif   //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP