mem_algo_common.hpp

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

//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2005-2008. 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/interprocess for documentation.
//
//////////////////////////////////////////////////////////////////////////////

#ifndef BOOST_INTERPROCESS_DETAIL_MEM_ALGO_COMMON_HPP
#define BOOST_INTERPROCESS_DETAIL_MEM_ALGO_COMMON_HPP

#if (defined _MSC_VER) && (_MSC_VER >= 1200)
#  pragma once
#endif

#include <boost/interprocess/detail/config_begin.hpp>
#include <boost/interprocess/detail/workaround.hpp>

#include <boost/interprocess/interprocess_fwd.hpp>
#include <boost/interprocess/allocators/allocation_type.hpp>
#include <boost/interprocess/detail/utilities.hpp>
#include <boost/interprocess/detail/type_traits.hpp>
#include <boost/interprocess/detail/iterators.hpp>
#include <boost/interprocess/detail/math_functions.hpp>
#include <boost/interprocess/detail/utilities.hpp>
#include <boost/assert.hpp>
#include <boost/static_assert.hpp>

//!\file
//!Implements common operations for memory algorithms.

namespace boost {
namespace interprocess {
namespace detail {

template<class VoidPointer>
struct multi_allocation_next
{
   typedef typename detail::
      pointer_to_other<VoidPointer, multi_allocation_next>::type
         multi_allocation_next_ptr;

   multi_allocation_next(multi_allocation_next_ptr n)
      :  next_(n)
   {}
   multi_allocation_next_ptr next_;
};

//!This iterator is returned by "allocate_many" functions so that
//!the user can access the multiple buffers allocated in a single call
template<class VoidPointer>
class basic_multiallocation_iterator
   :  public std::iterator<std::input_iterator_tag, char>
{
   void unspecified_bool_type_func() const {}
   typedef void (basic_multiallocation_iterator::*unspecified_bool_type)() const;
   typedef typename detail::
      pointer_to_other
         <VoidPointer, multi_allocation_next<VoidPointer> >::type
            multi_allocation_next_ptr;

   public:
   typedef char         value_type;
   typedef value_type & reference;
   typedef value_type * pointer;

   basic_multiallocation_iterator()
      : next_alloc_(0)
   {}

   basic_multiallocation_iterator(multi_allocation_next_ptr next)
      : next_alloc_(next)
   {}

   basic_multiallocation_iterator &operator=(const basic_multiallocation_iterator &other)
   {  next_alloc_ = other.next_alloc_;  return *this;  }

   public:
   basic_multiallocation_iterator& operator++() 
   {  next_alloc_.next_ = detail::get_pointer(next_alloc_.next_->next_); return *this;  }
   
   basic_multiallocation_iterator operator++(int)
   {
      basic_multiallocation_iterator result(next_alloc_.next_);
      ++*this;
      return result;
   }

   bool operator== (const basic_multiallocation_iterator& other) const
   { return next_alloc_.next_ == other.next_alloc_.next_; }

   bool operator!= (const basic_multiallocation_iterator& other) const
   { return !operator== (other); }

   reference operator*() const
   {  return *reinterpret_cast<char*>(detail::get_pointer(next_alloc_.next_)); }

   operator unspecified_bool_type() const  
   {  return next_alloc_.next_? &basic_multiallocation_iterator::unspecified_bool_type_func : 0;   }

   pointer operator->() const
   { return &(*(*this)); }

   static basic_multiallocation_iterator create_simple_range(void *mem)
   {
      basic_multiallocation_iterator it;
      typedef multi_allocation_next<VoidPointer> next_impl_t;
      next_impl_t * tmp_mem = static_cast<next_impl_t*>(mem);
      it = basic_multiallocation_iterator<VoidPointer>(tmp_mem);
      tmp_mem->next_ = 0;
      return it;
   }

   multi_allocation_next<VoidPointer> &get_multi_allocation_next()
   {  return *next_alloc_.next_;  }

   private:
   multi_allocation_next<VoidPointer> next_alloc_;
};

template<class VoidPointer>
class basic_multiallocation_chain
{
   private:
   basic_multiallocation_iterator<VoidPointer> it_;
   VoidPointer last_mem_;
   std::size_t num_mem_;

   basic_multiallocation_chain(const basic_multiallocation_chain &);
   basic_multiallocation_chain &operator=(const basic_multiallocation_chain &);

   public:
   typedef basic_multiallocation_iterator<VoidPointer> multiallocation_iterator;

   basic_multiallocation_chain()
      :  it_(0), last_mem_(0), num_mem_(0)
   {}

   void reset()
   {
      this->it_ = multiallocation_iterator();
      this->last_mem_ = 0;
      this->num_mem_ = 0;
   }

   void push_back(void *mem)
   {
      typedef multi_allocation_next<VoidPointer> next_impl_t;
      next_impl_t * tmp_mem = static_cast<next_impl_t*>(mem);
      
      if(!this->last_mem_){
         this->it_ = basic_multiallocation_iterator<VoidPointer>(tmp_mem);
      }
      else{
         static_cast<next_impl_t*>(detail::get_pointer(this->last_mem_))->next_ = tmp_mem;
      }
      tmp_mem->next_ = 0;
      this->last_mem_ = tmp_mem;
      ++num_mem_;
   }

   void push_front(void *mem)
   {
      typedef multi_allocation_next<VoidPointer> next_impl_t;
      next_impl_t * tmp_mem   = static_cast<next_impl_t*>(mem);      
      ++num_mem_;

      if(!this->last_mem_){
         this->it_ = basic_multiallocation_iterator<VoidPointer>(tmp_mem);
         tmp_mem->next_ = 0;
         this->last_mem_ = tmp_mem;
      }
      else{
         next_impl_t * old_first = &this->it_.get_multi_allocation_next();
         tmp_mem->next_          = old_first;
         this->it_ = basic_multiallocation_iterator<VoidPointer>(tmp_mem);
      }
   }

   void swap(basic_multiallocation_chain &other_chain)
   {
      std::swap(this->it_, other_chain.it_);
      std::swap(this->last_mem_, other_chain.last_mem_);
      std::swap(this->num_mem_, other_chain.num_mem_);
   }

   void splice_back(basic_multiallocation_chain &other_chain)
   {
      typedef multi_allocation_next<VoidPointer> next_impl_t;
      multiallocation_iterator end_it;
      multiallocation_iterator other_it = other_chain.get_it();
      multiallocation_iterator this_it  = this->get_it();
      if(end_it == other_it){
         return;
      }
      else if(end_it == this_it){
         this->swap(other_chain);
      }
      else{
         static_cast<next_impl_t*>(detail::get_pointer(this->last_mem_))->next_
            = &other_chain.it_.get_multi_allocation_next();
         this->last_mem_ = other_chain.last_mem_;
         this->num_mem_ += other_chain.num_mem_;
      }
   }

   void *pop_front()
   {
      multiallocation_iterator itend;
      if(this->it_ == itend){
         this->last_mem_= 0;
         this->num_mem_ = 0;
         return 0;
      }
      else{
         void *addr = &*it_;
         ++it_;
         --num_mem_;
         if(!num_mem_){
            this->last_mem_ = 0;
            this->it_ = multiallocation_iterator();
         }
         return addr;
      }
   }

   bool empty() const
   {  return !num_mem_; }

   multiallocation_iterator get_it() const
   {  return it_;  }

   std::size_t size() const
   {  return num_mem_;  }
};


//!This class implements several allocation functions shared by different algorithms
//!(aligned allocation, multiple allocation...).
template<class MemoryAlgorithm>
class memory_algorithm_common
{
   public:
   typedef typename MemoryAlgorithm::void_pointer              void_pointer;
   typedef typename MemoryAlgorithm::block_ctrl                block_ctrl;
   typedef typename MemoryAlgorithm::multiallocation_iterator  multiallocation_iterator;
   typedef multi_allocation_next<void_pointer>                 multi_allocation_next_t;
   typedef typename multi_allocation_next_t::
      multi_allocation_next_ptr                                multi_allocation_next_ptr;
   typedef memory_algorithm_common<MemoryAlgorithm>            this_type;

   static const std::size_t Alignment           = MemoryAlgorithm::Alignment;
   static const std::size_t MinBlockUnits       = MemoryAlgorithm::MinBlockUnits;
   static const std::size_t AllocatedCtrlBytes  = MemoryAlgorithm::AllocatedCtrlBytes;
   static const std::size_t AllocatedCtrlUnits  = MemoryAlgorithm::AllocatedCtrlUnits;
   static const std::size_t BlockCtrlBytes      = MemoryAlgorithm::BlockCtrlBytes;
   static const std::size_t BlockCtrlUnits      = MemoryAlgorithm::BlockCtrlUnits;
   static const std::size_t UsableByPreviousChunk   = MemoryAlgorithm::UsableByPreviousChunk;

   static void assert_alignment(const void *ptr)
   {  assert_alignment((std::size_t)ptr); }

   static void assert_alignment(std::size_t uint_ptr)
   {
      (void)uint_ptr;
      BOOST_ASSERT(uint_ptr % Alignment == 0);
   }

   static bool check_alignment(const void *ptr)
   {  return (((std::size_t)ptr) % Alignment == 0);   }

   static std::size_t ceil_units(std::size_t size)
   {  return detail::get_rounded_size(size, Alignment)/Alignment; }

   static std::size_t floor_units(std::size_t size)
   {  return size/Alignment;  }

   static std::size_t multiple_of_units(std::size_t size)
   {  return detail::get_rounded_size(size, Alignment);  }

   static multiallocation_iterator allocate_many
      (MemoryAlgorithm *memory_algo, std::size_t elem_bytes, std::size_t n_elements)
   {
      return this_type::priv_allocate_many(memory_algo, &elem_bytes, n_elements, 0);
   }

   static bool calculate_lcm_and_needs_backwards_lcmed
      (std::size_t backwards_multiple, std::size_t received_size, std::size_t size_to_achieve,
      std::size_t &lcm_out, std::size_t &needs_backwards_lcmed_out)
   {
      // Now calculate lcm
      std::size_t max = backwards_multiple;
      std::size_t min = Alignment;
      std::size_t needs_backwards;
      std::size_t needs_backwards_lcmed;
      std::size_t lcm;
      std::size_t current_forward;
      //Swap if necessary
      if(max < min){
         std::size_t tmp = min;
         min = max;
         max = tmp;
      }
      //Check if it's power of two
      if((backwards_multiple & (backwards_multiple-1)) == 0){
         if(0 != (size_to_achieve & ((backwards_multiple-1)))){
            return false;
         }

         lcm = max;
         //If we want to use minbytes data to get a buffer between maxbytes
         //and minbytes if maxbytes can't be achieved, calculate the 
         //biggest of all possibilities
         current_forward = detail::get_truncated_size_po2(received_size, backwards_multiple);
         needs_backwards = size_to_achieve - current_forward;
         assert((needs_backwards % backwards_multiple) == 0);
         needs_backwards_lcmed = detail::get_rounded_size_po2(needs_backwards, lcm);
         lcm_out = lcm;
         needs_backwards_lcmed_out = needs_backwards_lcmed;
         return true;
      }
      //Check if it's multiple of alignment
      else if((backwards_multiple & (Alignment - 1u)) == 0){
         lcm = backwards_multiple;
         current_forward = detail::get_truncated_size(received_size, backwards_multiple);
         //No need to round needs_backwards because backwards_multiple == lcm
         needs_backwards_lcmed = needs_backwards = size_to_achieve - current_forward;
         assert((needs_backwards_lcmed & (Alignment - 1u)) == 0);
         lcm_out = lcm;
         needs_backwards_lcmed_out = needs_backwards_lcmed;
         return true;
      }
      //Check if it's multiple of the half of the alignmment
      else if((backwards_multiple & ((Alignment/2u) - 1u)) == 0){
         lcm = backwards_multiple*2u;
         current_forward = detail::get_truncated_size(received_size, backwards_multiple);
         needs_backwards_lcmed = needs_backwards = size_to_achieve - current_forward;
         if(0 != (needs_backwards_lcmed & (Alignment-1)))
         //while(0 != (needs_backwards_lcmed & (Alignment-1)))
            needs_backwards_lcmed += backwards_multiple;
         assert((needs_backwards_lcmed % lcm) == 0);
         lcm_out = lcm;
         needs_backwards_lcmed_out = needs_backwards_lcmed;
         return true;
      }
      //Check if it's multiple of the half of the alignmment
      else if((backwards_multiple & ((Alignment/4u) - 1u)) == 0){
         std::size_t remainder;
         lcm = backwards_multiple*4u;
         current_forward = detail::get_truncated_size(received_size, backwards_multiple);
         needs_backwards_lcmed = needs_backwards = size_to_achieve - current_forward;
         //while(0 != (needs_backwards_lcmed & (Alignment-1)))
            //needs_backwards_lcmed += backwards_multiple;
         if(0 != (remainder = ((needs_backwards_lcmed & (Alignment-1))>>(Alignment/8u)))){
            if(backwards_multiple & Alignment/2u){
               needs_backwards_lcmed += (remainder)*backwards_multiple;
            }
            else{
               needs_backwards_lcmed += (4-remainder)*backwards_multiple;
            }
         }
         assert((needs_backwards_lcmed % lcm) == 0);
         lcm_out = lcm;
         needs_backwards_lcmed_out = needs_backwards_lcmed;
         return true;
      }
      else{
         lcm = detail::lcm(max, min);
      }
      //If we want to use minbytes data to get a buffer between maxbytes
      //and minbytes if maxbytes can't be achieved, calculate the 
      //biggest of all possibilities
      current_forward = detail::get_truncated_size(received_size, backwards_multiple);
      needs_backwards = size_to_achieve - current_forward;