rbtree_best_fit.hpp

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

//////////////////////////////////////////////////////////////////////////////
//
// (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_MEM_ALGO_RBTREE_BEST_FIT_HPP
#define BOOST_INTERPROCESS_MEM_ALGO_RBTREE_BEST_FIT_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/mem_algo/detail/mem_algo_common.hpp>
#include <boost/interprocess/allocators/allocation_type.hpp>
#include <boost/interprocess/offset_ptr.hpp>
#include <boost/interprocess/sync/interprocess_mutex.hpp>
#include <boost/interprocess/exceptions.hpp>
#include <boost/interprocess/detail/utilities.hpp>
#include <boost/interprocess/detail/min_max.hpp>
#include <boost/interprocess/detail/math_functions.hpp>
#include <boost/interprocess/detail/type_traits.hpp>
#include <boost/interprocess/sync/scoped_lock.hpp>
#include <boost/assert.hpp>
#include <boost/static_assert.hpp>
#include <algorithm>
#include <utility>
#include <climits>
#include <cstring>
#include <iterator>

#include <cassert>
#include <new>

//#define BOOST_INTERPROCESS_RBTREE_BEST_FIT_USE_SPLAY

#ifndef BOOST_INTERPROCESS_RBTREE_BEST_FIT_USE_SPLAY
#include <boost/intrusive/set.hpp>
#else
//#include <boost/intrusive/splay_set.hpp>
//#include <boost/intrusive/avl_set.hpp>
#include <boost/intrusive/sg_set.hpp>
#endif

//!\file
//!Describes a best-fit algorithm based in an intrusive red-black tree used to allocate
//!objects in shared memory. This class is intended as a base class for single segment
//!and multi-segment implementations.

namespace boost {
namespace interprocess {

//!This class implements an algorithm that stores the free nodes in a red-black tree
//!to have logarithmic search/insert times.
template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
class rbtree_best_fit
{
   /// @cond
   //Non-copyable
   rbtree_best_fit();
   rbtree_best_fit(const rbtree_best_fit &);
   rbtree_best_fit &operator=(const rbtree_best_fit &);
   /// @endcond

   public:
   //!Shared interprocess_mutex family used for the rest of the Interprocess framework
   typedef MutexFamily        mutex_family;
   //!Pointer type to be used with the rest of the Interprocess framework
   typedef VoidPointer        void_pointer;
   typedef detail::basic_multiallocation_iterator
      <void_pointer> multiallocation_iterator;
   typedef detail::basic_multiallocation_chain
      <void_pointer> multiallocation_chain;

   /// @cond

   private:
   struct block_ctrl;
   typedef typename detail::
      pointer_to_other<void_pointer, block_ctrl>::type   block_ctrl_ptr;
   typedef typename detail::
      pointer_to_other<void_pointer, char>::type         char_ptr;

#ifndef BOOST_INTERPROCESS_RBTREE_BEST_FIT_USE_SPLAY
   typedef typename bi::make_set_base_hook
#else
//   typedef typename bi::make_splay_set_base_hook
//   typedef typename bi::make_avl_set_base_hook
   typedef typename bi::make_sg_set_base_hook
#endif
      < bi::void_pointer<VoidPointer>
      , bi::optimize_size<true>
      , bi::link_mode<bi::normal_link> >::type           TreeHook;

   typedef detail::multi_allocation_next<void_pointer>   multi_allocation_next_t;
   typedef typename multi_allocation_next_t::
      multi_allocation_next_ptr                          multi_allocation_next_ptr;

   struct SizeHolder
   {
      //!This block's memory size (including block_ctrl 
      //!header) in Alignment units
      std::size_t m_prev_size :  sizeof(std::size_t)*CHAR_BIT;
      std::size_t m_size      :  sizeof(std::size_t)*CHAR_BIT - 2;
      std::size_t m_prev_allocated :  1;
      std::size_t m_allocated :  1;
   };

   //!Block control structure
   struct block_ctrl
      :  public SizeHolder, public TreeHook
   {
      block_ctrl()
      {  this->m_size = 0; this->m_allocated = 0, this->m_prev_allocated = 0;  }

      friend bool operator<(const block_ctrl &a, const block_ctrl &b)
      {  return a.m_size < b.m_size;  }
      friend bool operator==(const block_ctrl &a, const block_ctrl &b)
      {  return a.m_size == b.m_size;  }
   };

   struct size_block_ctrl_compare
   {
      bool operator()(std::size_t size, const block_ctrl &block) const
      {  return size < block.m_size;  }

      bool operator()(const block_ctrl &block, std::size_t size) const
      {  return block.m_size < size;  }      
   };

   //!Shared interprocess_mutex to protect memory allocate/deallocate
   typedef typename MutexFamily::mutex_type                       interprocess_mutex;
#ifndef BOOST_INTERPROCESS_RBTREE_BEST_FIT_USE_SPLAY
   typedef typename bi::make_multiset
#else
   //typedef typename bi::make_splay_multiset
   //typedef typename bi::make_avl_multiset
   typedef typename bi::make_sg_multiset
#endif
      <block_ctrl, bi::base_hook<TreeHook> >::type                Imultiset;

   typedef typename Imultiset::iterator                           imultiset_iterator;

   //!This struct includes needed data and derives from
   //!interprocess_mutex to allow EBO when using null interprocess_mutex
   struct header_t : public interprocess_mutex
   {
      Imultiset            m_imultiset;

      //!The extra size required by the segment
      std::size_t       m_extra_hdr_bytes;
      //!Allocated bytes for internal checking
      std::size_t       m_allocated;
      //!The size of the memory segment
      std::size_t       m_size;
   }  m_header;

   friend class detail::basic_multiallocation_iterator<void_pointer>;
   friend class detail::memory_algorithm_common<rbtree_best_fit>;
   
   typedef detail::memory_algorithm_common<rbtree_best_fit> algo_impl_t;

   public:
   /// @endcond

   //!Constructor. "size" is the total size of the managed memory segment, 
   //!"extra_hdr_bytes" indicates the extra bytes beginning in the sizeof(rbtree_best_fit)
   //!offset that the allocator should not use at all.
   rbtree_best_fit           (std::size_t size, std::size_t extra_hdr_bytes);

   //!Destructor.
   ~rbtree_best_fit();

   //!Obtains the minimum size needed by the algorithm
   static std::size_t get_min_size (std::size_t extra_hdr_bytes);

   //Functions for single segment management

   //!Allocates bytes, returns 0 if there is not more memory
   void* allocate             (std::size_t nbytes);

   /// @cond

   //Experimental. Dont' use

   //!Multiple element allocation, same size
   multiallocation_iterator allocate_many(std::size_t elem_bytes, std::size_t num_elements);

   //!Multiple element allocation, different size
   multiallocation_iterator allocate_many(const std::size_t *elem_sizes, std::size_t n_elements, std::size_t sizeof_element);

   //!Multiple element allocation, different size
   void deallocate_many(multiallocation_iterator it);

   /// @endcond

   //!Deallocates previously allocated bytes
   void   deallocate          (void *addr);

   //!Returns the size of the memory segment
   std::size_t get_size()  const;

   //!Returns the number of free bytes of the segment
   std::size_t get_free_memory()  const;

   //!Initializes to zero all the memory that's not in use.
   //!This function is normally used for security reasons.
   void zero_free_memory();

   //!Increases managed memory in
   //!extra_size bytes more
   void grow(std::size_t extra_size);

   //!Decreases managed memory as much as possible
   void shrink_to_fit();

   //!Returns true if all allocated memory has been deallocated
   bool all_memory_deallocated();

   //!Makes an internal sanity check
   //!and returns true if success
   bool check_sanity();

   template<class T>
   std::pair<T *, bool>
      allocation_command  (allocation_type command,   std::size_t limit_size,
                           std::size_t preferred_size,std::size_t &received_size, 
                           T *reuse_ptr = 0);

   std::pair<void *, bool>
     raw_allocation_command  (allocation_type command,   std::size_t limit_object,
                              std::size_t preferred_object,std::size_t &received_object, 
                              void *reuse_ptr = 0, std::size_t sizeof_object = 1);

   //!Returns the size of the buffer previously allocated pointed by ptr
   std::size_t size(const void *ptr) const;

   //!Allocates aligned bytes, returns 0 if there is not more memory.
   //!Alignment must be power of 2
   void* allocate_aligned     (std::size_t nbytes, std::size_t alignment);

   /// @cond
   private:
   static std::size_t priv_first_block_offset(const void *this_ptr, std::size_t extra_hdr_bytes);

   std::pair<void*, bool>
      priv_allocation_command(allocation_type command,   std::size_t limit_size,
                        std::size_t preferred_size,std::size_t &received_size, 
                        void *reuse_ptr, std::size_t sizeof_object);


   //!Real allocation algorithm with min allocation option
   std::pair<void *, bool> priv_allocate(allocation_type command
                                        ,std::size_t limit_size
                                        ,std::size_t preferred_size
                                        ,std::size_t &received_size
                                        ,void *reuse_ptr = 0
                                        ,std::size_t backwards_multiple = 1);

   //!Obtains the block control structure of the user buffer
   static block_ctrl *priv_get_block(const void *ptr);

   //!Obtains the pointer returned to the user from the block control
   static void *priv_get_user_buffer(const block_ctrl *block);

   //!Returns the number of total units that a user buffer
   //!of "userbytes" bytes really occupies (including header)
   static std::size_t priv_get_total_units(std::size_t userbytes);

   //!Real expand function implementation
   bool priv_expand(void *ptr
                   ,const std::size_t min_size, const std::size_t preferred_size
                   ,std::size_t &received_size);

   //!Real expand to both sides implementation
   void* priv_expand_both_sides(allocation_type command
                               ,std::size_t min_size
                               ,std::size_t preferred_size
                               ,std::size_t &received_size
                               ,void *reuse_ptr
                               ,bool only_preferred_backwards
                               ,std::size_t backwards_multiple);

   //!Get poitner of the previous block (previous block must be free)
   block_ctrl * priv_prev_block(block_ctrl *ptr);

   //!Returns true if the previous block is allocated
   bool priv_is_prev_allocated(block_ctrl *ptr);

   //!Get a pointer of the "end" block from the first block of the segment
   block_ctrl * priv_end_block(block_ctrl *first_segment_block);

   //!Get the size in the tail of the previous block
   block_ctrl * priv_next_block(block_ctrl *ptr);

   //!Check if this block is free (not allocated)
   bool priv_is_allocated_block(block_ctrl *ptr);

   //!Marks the block as allocated
   void priv_mark_as_allocated_block(block_ctrl *ptr);

   //!Marks the block as allocated
   void priv_mark_as_free_block(block_ctrl *ptr);

   //!Checks if block has enough memory and splits/unlinks the block
   //!returning the address to the users
   void* priv_check_and_allocate(std::size_t units
                                ,block_ctrl* block
                                ,std::size_t &received_size);
   //!Real deallocation algorithm
   void priv_deallocate(void *addr);

   //!Makes a new memory portion available for allocation
   void priv_add_segment(void *addr, std::size_t size);

   void priv_mark_new_allocated_block(block_ctrl *block);

   public:
   
   static const std::size_t Alignment = !MemAlignment
      ? detail::alignment_of<detail::max_align>::value
      : MemAlignment
      ;

   private:
   //Due to embedded bits in size, Alignment must be at least 4
   BOOST_STATIC_ASSERT((Alignment >= 4));
   //Due to rbtree size optimizations, Alignment must have at least pointer alignment
   BOOST_STATIC_ASSERT((Alignment >= detail::alignment_of<void_pointer>::value));