//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2005-2009. 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/pointer_to_other.hpp>

#include <boost/interprocess/interprocess_fwd.hpp>
#include <boost/interprocess/mem_algo/detail/mem_algo_common.hpp>
#include <boost/interprocess/containers/allocation_type.hpp>
#include <boost/interprocess/containers/container/detail/multiallocation_chain.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 <boost/assert.hpp>
#include <cstring>
#include <iterator>

#include <boost/assert.hpp>
#include <new>

#include <boost/intrusive/set.hpp>

//!\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 boost::container::containers_detail::
      basic_multiallocation_chain<VoidPointer>  multiallocation_chain;

   /// @cond

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

   typedef typename bi::make_set_base_hook
      < bi::void_pointer<VoidPointer>
      , bi::optimize_size<true>
      , bi::link_mode<bi::normal_link> >::type           TreeHook;

   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;
   typedef typename bi::make_multiset
      <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::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_chain allocate_many(std::size_t elem_bytes, std::size_t num_elements)
   {

      //-----------------------
      boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
      //-----------------------
      return algo_impl_t::allocate_many(this, elem_bytes, num_elements);
   }

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

      //-----------------------
      boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
      //-----------------------
      return algo_impl_t::allocate_many(this, elem_sizes, n_elements, sizeof_element);
   }

   //!Multiple element allocation, different size
   void deallocate_many(multiallocation_chain chain);

   /// @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  (boost::interprocess::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  (boost::interprocess::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(boost::interprocess::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(boost::interprocess::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(boost::interprocess::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));
   static const std::size_t AlignmentMask = (Alignment - 1);
   static const std::size_t BlockCtrlBytes = detail::ct_rounded_size<sizeof(block_ctrl), Alignment>::value;
   static const std::size_t BlockCtrlUnits = BlockCtrlBytes/Alignment;
   static const std::size_t AllocatedCtrlBytes  = detail::ct_rounded_size<sizeof(SizeHolder), Alignment>::value;
   static const std::size_t AllocatedCtrlUnits  = AllocatedCtrlBytes/Alignment;
   static const std::size_t EndCtrlBlockBytes   = detail::ct_rounded_size<sizeof(SizeHolder), Alignment>::value;
   static const std::size_t EndCtrlBlockUnits   = EndCtrlBlockBytes/Alignment;
   static const std::size_t MinBlockUnits       = BlockCtrlUnits;
   static const std::size_t UsableByPreviousChunk   = sizeof(std::size_t);

   //Make sure the maximum alignment is power of two
   BOOST_STATIC_ASSERT((0 == (Alignment & (Alignment - std::size_t(1u)))));
   /// @endcond
   public:
   static const std::size_t PayloadPerAllocation = AllocatedCtrlBytes - UsableByPreviousChunk;
};

/// @cond

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline std::size_t rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>
   ::priv_first_block_offset(const void *this_ptr, std::size_t extra_hdr_bytes)
{
   std::size_t uint_this      = (std::size_t)this_ptr;
   std::size_t main_hdr_end   = uint_this + sizeof(rbtree_best_fit) + extra_hdr_bytes;
   std::size_t aligned_main_hdr_end = detail::get_rounded_size(main_hdr_end, Alignment);
   std::size_t block1_off = aligned_main_hdr_end -  uint_this;
   algo_impl_t::assert_alignment(aligned_main_hdr_end);
   algo_impl_t::assert_alignment(uint_this + block1_off);
   return block1_off;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   rbtree_best_fit(std::size_t size, std::size_t extra_hdr_bytes)
{
   //Initialize the header
   m_header.m_allocated       = 0;
   m_header.m_size            = size;
   m_header.m_extra_hdr_bytes = extra_hdr_bytes;

   //Now write calculate the offset of the first big block that will
   //cover the whole segment
   BOOST_ASSERT(get_min_size(extra_hdr_bytes) <= size);
   std::size_t block1_off  = priv_first_block_offset(this, extra_hdr_bytes);
   priv_add_segment(reinterpret_cast<char*>(this) + block1_off, size - block1_off);
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::~rbtree_best_fit()
{
   //There is a memory leak!
//   BOOST_ASSERT(m_header.m_allocated == 0);
//   BOOST_ASSERT(m_header.m_root.m_next->m_next == block_ctrl_ptr(&m_header.m_root));
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
void rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::grow(std::size_t extra_size)
{
   //Get the address of the first block
   std::size_t block1_off =
      priv_first_block_offset(this, m_header.m_extra_hdr_bytes);

   block_ctrl *first_block = reinterpret_cast<block_ctrl *>
                                 (reinterpret_cast<char*>(this) + block1_off);
   block_ctrl *old_end_block   = priv_end_block(first_block);
   BOOST_ASSERT(priv_is_allocated_block(old_end_block));
   std::size_t old_border_offset = (reinterpret_cast<char*>(old_end_block) - 
                                    reinterpret_cast<char*>(this)) + EndCtrlBlockBytes;

   //Update managed buffer's size
   m_header.m_size += extra_size;

   //We need at least MinBlockUnits blocks to create a new block
//   BOOST_ASSERT((m_header.m_size - old_end) >= MinBlockUnits);
   if((m_header.m_size - old_border_offset) < MinBlockUnits){
      return;
   }

   //Now create a new block between the old end and the new end
   std::size_t align_offset = (m_header.m_size - old_border_offset)/Alignment;
   block_ctrl *new_end_block = reinterpret_cast<block_ctrl*>
      (reinterpret_cast<char*>(old_end_block) + align_offset*Alignment);
   new_end_block->m_size      = (reinterpret_cast<char*>(first_block) - 
                                 reinterpret_cast<char*>(new_end_block))/Alignment;
   first_block->m_prev_size = new_end_block->m_size;
   BOOST_ASSERT(first_block == priv_next_block(new_end_block));
   priv_mark_new_allocated_block(new_end_block);
   
   BOOST_ASSERT(new_end_block == priv_end_block(first_block));

   //The old end block is the new block
   block_ctrl *new_block = old_end_block;
   new_block->m_size = (reinterpret_cast<char*>(new_end_block) - 
                        reinterpret_cast<char*>(new_block))/Alignment;
   BOOST_ASSERT(new_block->m_size >= BlockCtrlUnits);
   priv_mark_new_allocated_block(new_block);
   BOOST_ASSERT(priv_next_block(new_block) == new_end_block);

   m_header.m_allocated += new_block->m_size*Alignment;

   //Now deallocate the newly created block
   this->priv_deallocate(priv_get_user_buffer(new_block));
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
void rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::shrink_to_fit()
{  
   //Get the address of the first block
   std::size_t block1_off =
      priv_first_block_offset(this, m_header.m_extra_hdr_bytes);

   block_ctrl *first_block = reinterpret_cast<block_ctrl*>
                                 (reinterpret_cast<char*>(this) + block1_off);
   algo_impl_t::assert_alignment(first_block);

   block_ctrl *old_end_block = priv_end_block(first_block);
   algo_impl_t::assert_alignment(old_end_block);
   BOOST_ASSERT(priv_is_allocated_block(old_end_block));

   algo_impl_t::assert_alignment(old_end_block);

   std::size_t old_end_block_size = old_end_block->m_size;

   void *unique_buffer = 0;
   block_ctrl *last_block;
   if(priv_next_block(first_block) == old_end_block){
      std::size_t ignore;
      unique_buffer = priv_allocate(boost::interprocess::allocate_new, 0, 0, ignore).first;
      if(!unique_buffer)
         return;
      algo_impl_t::assert_alignment(unique_buffer);
      block_ctrl *unique_block = priv_get_block(unique_buffer);
      BOOST_ASSERT(priv_is_allocated_block(unique_block));
      algo_impl_t::assert_alignment(unique_block);
      last_block = priv_next_block(unique_block);
      BOOST_ASSERT(!priv_is_allocated_block(last_block));
      algo_impl_t::assert_alignment(last_block);
   }
   else{
      if(priv_is_prev_allocated(old_end_block))
         return;
      last_block = priv_prev_block(old_end_block);
   }

   std::size_t last_block_size = last_block->m_size;

   //Erase block from the free tree, since we will erase it
   m_header.m_imultiset.erase(Imultiset::s_iterator_to(*last_block));

   std::size_t shrunk_border_offset = (reinterpret_cast<char*>(last_block) - 
                                       reinterpret_cast<char*>(this)) + EndCtrlBlockBytes;
   
   block_ctrl *new_end_block = last_block;
   algo_impl_t::assert_alignment(new_end_block);
   new_end_block->m_size = old_end_block_size + last_block_size;
   priv_mark_as_allocated_block(new_end_block);

   //Although the first block might be allocated, we'll
   //store the offset to the end block since in the previous
   //offset can't be overwritten by a previous block
   first_block->m_prev_size = new_end_block->m_size;
   BOOST_ASSERT(priv_end_block(first_block) == new_end_block);

   //Update managed buffer's size
   m_header.m_size = shrunk_border_offset;
   if(unique_buffer)
      priv_deallocate(unique_buffer);
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
void rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   priv_add_segment(void *addr, std::size_t size)
{  
   //Check alignment
   algo_impl_t::check_alignment(addr);
   //Check size
   BOOST_ASSERT(size >= (BlockCtrlBytes + EndCtrlBlockBytes));

   //Initialize the first big block and the "end" node
   block_ctrl *first_big_block = new(addr)block_ctrl;
   first_big_block->m_size = size/Alignment - EndCtrlBlockUnits;
   BOOST_ASSERT(first_big_block->m_size >= BlockCtrlUnits);

   //The "end" node is just a node of size 0 with the "end" bit set
   block_ctrl *end_block = static_cast<block_ctrl*> 
      (new (reinterpret_cast<char*>(addr) + first_big_block->m_size*Alignment)SizeHolder);

   //This will overwrite the prev part of the "end" node
   priv_mark_as_free_block (first_big_block);
   first_big_block->m_prev_size = end_block->m_size =
      (reinterpret_cast<char*>(first_big_block) - reinterpret_cast<char*>(end_block))/Alignment;
   priv_mark_as_allocated_block(end_block);

   BOOST_ASSERT(priv_next_block(first_big_block) == end_block);
   BOOST_ASSERT(priv_next_block(end_block) == first_big_block);
   BOOST_ASSERT(priv_end_block(first_big_block) == end_block);
   BOOST_ASSERT(priv_prev_block(end_block) == first_big_block);

   //Some check to validate the algorithm, since it makes some assumptions
   //to optimize the space wasted in bookkeeping:

   //Check that the sizes of the header are placed before the rbtree
   BOOST_ASSERT(static_cast<void*>(static_cast<SizeHolder*>(first_big_block))
          < static_cast<void*>(static_cast<TreeHook*>(first_big_block)));

   //Check that the alignment is power of two (we use some optimizations based on this)
   //BOOST_ASSERT((Alignment % 2) == 0);
   //Insert it in the intrusive containers
   m_header.m_imultiset.insert(*first_big_block);
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline void rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   priv_mark_new_allocated_block(block_ctrl *new_block)
{  priv_mark_as_allocated_block(new_block);  }

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline std::size_t rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::get_size()  const
{  return m_header.m_size;  }

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline std::size_t rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::get_free_memory()  const
{
   return m_header.m_size - m_header.m_allocated - 
      priv_first_block_offset(this, m_header.m_extra_hdr_bytes);
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline std::size_t rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   get_min_size (std::size_t extra_hdr_bytes)
{
   return (algo_impl_t::ceil_units(sizeof(rbtree_best_fit)) +
           algo_impl_t::ceil_units(extra_hdr_bytes) + 
           MinBlockUnits + EndCtrlBlockUnits)*Alignment;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline bool rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
    all_memory_deallocated()
{
   //-----------------------
   boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
   //-----------------------
   std::size_t block1_off  = 
      priv_first_block_offset(this, m_header.m_extra_hdr_bytes);

   return m_header.m_allocated == 0 && 
      m_header.m_imultiset.begin() != m_header.m_imultiset.end() &&
       (++m_header.m_imultiset.begin()) == m_header.m_imultiset.end()
       && m_header.m_imultiset.begin()->m_size == 
         (m_header.m_size - block1_off - EndCtrlBlockBytes)/Alignment;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
bool rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
    check_sanity()
{
   //-----------------------
   boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
   //-----------------------
   imultiset_iterator ib(m_header.m_imultiset.begin()), ie(m_header.m_imultiset.end());

   std::size_t free_memory = 0;

   //Iterate through all blocks obtaining their size
   for(; ib != ie; ++ib){
      free_memory += ib->m_size*Alignment;
      algo_impl_t::assert_alignment(&*ib);
      if(!algo_impl_t::check_alignment(&*ib))
         return false;
   }

   //Check allocated bytes are less than size
   if(m_header.m_allocated > m_header.m_size){
      return false;
   }

   std::size_t block1_off  = 
      priv_first_block_offset(this, m_header.m_extra_hdr_bytes);

   //Check free bytes are less than size
   if(free_memory > (m_header.m_size - block1_off)){
      return false;
   }
   return true;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline void* rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   allocate(std::size_t nbytes)
{  
   //-----------------------
   boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
   //-----------------------
   std::size_t ignore;
   void * ret = priv_allocate(boost::interprocess::allocate_new, nbytes, nbytes, ignore).first;
   return ret;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline void* rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   allocate_aligned(std::size_t nbytes, std::size_t alignment)
{ 
   //-----------------------
   boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
   //-----------------------
   return algo_impl_t::allocate_aligned(this, nbytes, alignment); 
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
template<class T>
inline std::pair<T*, bool> rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   allocation_command  (boost::interprocess::allocation_type command,   std::size_t limit_size,
                        std::size_t preferred_size,std::size_t &received_size, 
                        T *reuse_ptr)
{
   std::pair<void*, bool> ret = priv_allocation_command
      (command, limit_size, preferred_size, received_size, static_cast<void*>(reuse_ptr), sizeof(T));

   BOOST_ASSERT(0 == ((std::size_t)ret.first % detail::alignment_of<T>::value));
   return std::pair<T *, bool>(static_cast<T*>(ret.first), ret.second);
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline std::pair<void*, bool> rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   raw_allocation_command  (boost::interprocess::allocation_type command,   std::size_t limit_objects,
                        std::size_t preferred_objects,std::size_t &received_objects, 
                        void *reuse_ptr, std::size_t sizeof_object)
{
   if(!sizeof_object)
      return std::pair<void *, bool>(static_cast<void*>(0), false);
   if(command & boost::interprocess::try_shrink_in_place){
      bool success = algo_impl_t::try_shrink
         ( this, reuse_ptr, limit_objects*sizeof_object
         , preferred_objects*sizeof_object, received_objects);
      received_objects /= sizeof_object;
      return std::pair<void *, bool> ((success ? reuse_ptr : 0), true);
   }
   return priv_allocation_command
      (command, limit_objects, preferred_objects, received_objects, reuse_ptr, sizeof_object);
}


template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline std::pair<void*, bool> rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   priv_allocation_command (boost::interprocess::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)
{
   std::pair<void*, bool> ret;
   std::size_t max_count = m_header.m_size/sizeof_object;
   if(limit_size > max_count || preferred_size > max_count){
      ret.first = 0; return ret;
   }
   std::size_t l_size = limit_size*sizeof_object;
   std::size_t p_size = preferred_size*sizeof_object;
   std::size_t r_size;
   {
      //-----------------------
      boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
      //-----------------------
      ret = priv_allocate(command, l_size, p_size, r_size, reuse_ptr, sizeof_object);
   }
   received_size = r_size/sizeof_object;
   return ret;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline std::size_t rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   size(const void *ptr) const
{
   //We need no synchronization since this block's size is not going
   //to be modified by anyone else
   //Obtain the real size of the block
   return (priv_get_block(ptr)->m_size - AllocatedCtrlUnits)*Alignment + UsableByPreviousChunk;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline void rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::zero_free_memory()
{
   //-----------------------
   boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
   //-----------------------
   imultiset_iterator ib(m_header.m_imultiset.begin()), ie(m_header.m_imultiset.end());

   //Iterate through all blocks obtaining their size
   while(ib != ie){
      //Just clear user the memory part reserved for the user
      volatile char *ptr = reinterpret_cast<char*>(&*ib) + BlockCtrlBytes;
      std::size_t s = ib->m_size*Alignment - BlockCtrlBytes;
      while(s--){
         *ptr++ = 0;
      }

      //This surprisingly is optimized out by Visual C++ 7.1 in release mode!
      //std::memset( reinterpret_cast<char*>(&*ib) + BlockCtrlBytes
      //           , 0
      //           , ib->m_size*Alignment - BlockCtrlBytes);
      ++ib;
   }
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
void* rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   priv_expand_both_sides(boost::interprocess::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)
{
   algo_impl_t::assert_alignment(reuse_ptr);
   if(command & boost::interprocess::expand_fwd){
      if(priv_expand(reuse_ptr, min_size, preferred_size, received_size))
         return reuse_ptr;
   }
   else{
      received_size = this->size(reuse_ptr);
      if(received_size >= preferred_size || received_size >= min_size)
         return reuse_ptr;
   }

   if(backwards_multiple){
      BOOST_ASSERT(0 == (min_size       % backwards_multiple));
      BOOST_ASSERT(0 == (preferred_size % backwards_multiple));
   }

   if(command & boost::interprocess::expand_bwd){
      //Obtain the real size of the block
      block_ctrl *reuse = priv_get_block(reuse_ptr);

      //Sanity check 
      //BOOST_ASSERT(reuse->m_size == priv_tail_size(reuse));
      algo_impl_t::assert_alignment(reuse);

      block_ctrl *prev_block;

      //If the previous block is not free, there is nothing to do
      if(priv_is_prev_allocated(reuse)){
         return 0;
      }

      prev_block = priv_prev_block(reuse);
      BOOST_ASSERT(!priv_is_allocated_block(prev_block));

      //Some sanity checks
      BOOST_ASSERT(prev_block->m_size == reuse->m_prev_size);
      algo_impl_t::assert_alignment(prev_block);

      std::size_t needs_backwards_aligned;
      std::size_t lcm;
      if(!algo_impl_t::calculate_lcm_and_needs_backwards_lcmed
         ( backwards_multiple
         , received_size
         , only_preferred_backwards ? preferred_size : min_size
         , lcm, needs_backwards_aligned)){
         return 0;
      }

      //Check if previous block has enough size
      if(std::size_t(prev_block->m_size*Alignment) >= needs_backwards_aligned){
         //Now take all next space. This will succeed
         if(command & boost::interprocess::expand_fwd){
            std::size_t received_size2;
            if(!priv_expand(reuse_ptr, received_size, received_size, received_size2)){
               BOOST_ASSERT(0);
            }
            BOOST_ASSERT(received_size = received_size2);
         }
         //We need a minimum size to split the previous one
         if(prev_block->m_size >= (needs_backwards_aligned/Alignment + BlockCtrlUnits)){
            block_ctrl *new_block = reinterpret_cast<block_ctrl *>
               (reinterpret_cast<char*>(reuse) - needs_backwards_aligned);

            //Free old previous buffer
            new_block->m_size = 
               AllocatedCtrlUnits + (needs_backwards_aligned + (received_size - UsableByPreviousChunk))/Alignment;
            BOOST_ASSERT(new_block->m_size >= BlockCtrlUnits);
            priv_mark_new_allocated_block(new_block);

            prev_block->m_size = (reinterpret_cast<char*>(new_block) - 
                                  reinterpret_cast<char*>(prev_block))/Alignment;
            BOOST_ASSERT(prev_block->m_size >= BlockCtrlUnits);
            priv_mark_as_free_block(prev_block);

            //Update the old previous block in the free blocks tree
            //If the new size fulfills tree invariants do nothing,
            //otherwise erase() + insert()
            {
               imultiset_iterator prev_block_it(Imultiset::s_iterator_to(*prev_block));
               imultiset_iterator was_smaller_it(prev_block_it);
               if(prev_block_it != m_header.m_imultiset.begin() && 
                  (--(was_smaller_it = prev_block_it))->m_size > prev_block->m_size){
                  m_header.m_imultiset.erase(prev_block_it);
                  m_header.m_imultiset.insert(m_header.m_imultiset.begin(), *prev_block);
               }
            }

            received_size = needs_backwards_aligned + received_size;
            m_header.m_allocated += needs_backwards_aligned;
         
            //Check alignment
            algo_impl_t::assert_alignment(new_block);

            //If the backwards expansion has remaining bytes in the
            //first bytes, fill them with a pattern
            void *p = priv_get_user_buffer(new_block);
            void *user_ptr = reinterpret_cast<char*>(p);
            BOOST_ASSERT((static_cast<char*>(reuse_ptr) - static_cast<char*>(user_ptr)) % backwards_multiple == 0);
            algo_impl_t::assert_alignment(user_ptr);
            return user_ptr;
         }
         //Check if there is no place to create a new block and
         //the whole new block is multiple of the backwards expansion multiple
         else if(prev_block->m_size >= needs_backwards_aligned/Alignment &&
                 0 == ((prev_block->m_size*Alignment) % lcm)) {
            //Erase old previous block, since we will change it
            m_header.m_imultiset.erase(Imultiset::s_iterator_to(*prev_block));

            //Just merge the whole previous block
            //prev_block->m_size*Alignment is multiple of lcm (and backwards_multiple)
            received_size = received_size + prev_block->m_size*Alignment;

            m_header.m_allocated += prev_block->m_size*Alignment;
            //Now update sizes
            prev_block->m_size = prev_block->m_size + reuse->m_size;
            BOOST_ASSERT(prev_block->m_size >= BlockCtrlUnits);
            priv_mark_new_allocated_block(prev_block);

            //If the backwards expansion has remaining bytes in the
            //first bytes, fill them with a pattern
            void *user_ptr = priv_get_user_buffer(prev_block);
            BOOST_ASSERT((static_cast<char*>(reuse_ptr) - static_cast<char*>(user_ptr)) % backwards_multiple == 0);
            algo_impl_t::assert_alignment(user_ptr);
            return user_ptr;
         }
         else{
            //Alignment issues
         }
      }
   }
   return 0;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline void rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   deallocate_many(typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::multiallocation_chain chain)
{
   //-----------------------
   boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
   //-----------------------
   algo_impl_t::deallocate_many(this, boost::interprocess::move(chain));
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
std::pair<void *, bool> rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   priv_allocate(boost::interprocess::allocation_type command
                ,std::size_t limit_size
                ,std::size_t preferred_size
                ,std::size_t &received_size
                ,void *reuse_ptr
               ,std::size_t backwards_multiple)
{
   //Remove me. Forbid backwards allocation
   //command &= (~boost::interprocess::expand_bwd);

   if(command & boost::interprocess::shrink_in_place){
      bool success = 
         algo_impl_t::shrink(this, reuse_ptr, limit_size, preferred_size, received_size);
      return std::pair<void *, bool> ((success ? reuse_ptr : 0), true);
   }

   typedef std::pair<void *, bool> return_type;
   received_size = 0;

   if(limit_size > preferred_size)
      return return_type(static_cast<void*>(0), false);

   //Number of units to request (including block_ctrl header)
   std::size_t preferred_units = priv_get_total_units(preferred_size);

   //Number of units to request (including block_ctrl header)
   std::size_t limit_units = priv_get_total_units(limit_size);

   //Expand in place
   if(reuse_ptr && (command & (boost::interprocess::expand_fwd | boost::interprocess::expand_bwd))){
      void *ret = priv_expand_both_sides
         (command, limit_size, preferred_size, received_size, reuse_ptr, true, backwards_multiple);
      if(ret)
         return return_type(ret, true);
   }

   if(command & boost::interprocess::allocate_new){
      size_block_ctrl_compare comp;
      imultiset_iterator it(m_header.m_imultiset.lower_bound(preferred_units, comp));

      if(it != m_header.m_imultiset.end()){
         return return_type(this->priv_check_and_allocate
            (preferred_units, detail::get_pointer(&*it), received_size), false);
      }

      if(it != m_header.m_imultiset.begin()&&
              (--it)->m_size >= limit_units){
         return return_type(this->priv_check_and_allocate
            (it->m_size, detail::get_pointer(&*it), received_size), false);
      }
   }


   //Now try to expand both sides with min size
   if(reuse_ptr && (command & (boost::interprocess::expand_fwd | boost::interprocess::expand_bwd))){
      return return_type(priv_expand_both_sides
         (command, limit_size, preferred_size, received_size, reuse_ptr, false, backwards_multiple), true);
   }

   return return_type(static_cast<void*>(0), false);
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline
typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *
   rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::priv_get_block(const void *ptr)
{
   return const_cast<block_ctrl*>
      (reinterpret_cast<const block_ctrl*>
         (reinterpret_cast<const char*>(ptr) - AllocatedCtrlBytes));
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline
void *rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
      priv_get_user_buffer(const typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *block)
{  return const_cast<char*>(reinterpret_cast<const char*>(block) + AllocatedCtrlBytes);   }

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
inline
std::size_t rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   priv_get_total_units(std::size_t userbytes)
{
   if(userbytes < UsableByPreviousChunk)
      userbytes = UsableByPreviousChunk;
   std::size_t units = detail::get_rounded_size(userbytes - UsableByPreviousChunk, Alignment)/Alignment + AllocatedCtrlUnits;
   if(units < BlockCtrlUnits) units = BlockCtrlUnits;
   return units;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
bool rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::
   priv_expand (void *ptr
               ,const std::size_t min_size
               ,const std::size_t preferred_size
               ,std::size_t &received_size)
{
   //Obtain the real size of the block
   block_ctrl *block = priv_get_block(ptr);
   std::size_t old_block_units = block->m_size;

   //The block must be marked as allocated and the sizes must be equal
   BOOST_ASSERT(priv_is_allocated_block(block));
   //BOOST_ASSERT(old_block_units == priv_tail_size(block));
   
   //Put this to a safe value
   received_size = (old_block_units - AllocatedCtrlUnits)*Alignment + UsableByPreviousChunk;
   if(received_size >= preferred_size || received_size >= min_size)
      return true;

   //Now translate it to Alignment units
   const std::size_t min_user_units = algo_impl_t::ceil_units(min_size - UsableByPreviousChunk);
   const std::size_t preferred_user_units = algo_impl_t::ceil_units(preferred_size - UsableByPreviousChunk);

   //Some parameter checks
   BOOST_ASSERT(min_user_units <= preferred_user_units);

   block_ctrl *next_block;

   if(priv_is_allocated_block(next_block = priv_next_block(block))){
      return received_size >= min_size ? true : false;
   }
   algo_impl_t::assert_alignment(next_block);

   //Is "block" + "next_block" big enough?
   const std::size_t merged_units = old_block_units + next_block->m_size;

   //Now get the expansion size
   const std::size_t merged_user_units = merged_units - AllocatedCtrlUnits;

   if(merged_user_units < min_user_units){
      received_size = merged_units*Alignment - UsableByPreviousChunk;
      return false;
   }

   //Now get the maximum size the user can allocate
   std::size_t intended_user_units = (merged_user_units < preferred_user_units) ?
      merged_user_units : preferred_user_units;

   //These are total units of the merged block (supposing the next block can be split)
   const std::size_t intended_units = AllocatedCtrlUnits + intended_user_units;

   //Check if we can split the next one in two parts
   if((merged_units - intended_units) >=  BlockCtrlUnits){
      //This block is bigger than needed, split it in 
      //two blocks, the first one will be merged and
      //the second's size will be the remaining space
      BOOST_ASSERT(next_block->m_size == priv_next_block(next_block)->m_prev_size);
      const std::size_t rem_units = merged_units - intended_units;

      //Check if we we need to update the old next block in the free blocks tree
      //If the new size fulfills tree invariants, we just need to replace the node
      //(the block start has been displaced), otherwise erase() + insert().
      //
      //This fixup must be done in two parts, because the new next block might
      //overwrite the tree hook of the old next block. So we first erase the
      //old if needed and we'll insert the new one after creating the new next
      imultiset_iterator old_next_block_it(Imultiset::s_iterator_to(*next_block));
      const bool size_invariants_broken = 
            (next_block->m_size - rem_units ) < BlockCtrlUnits ||
            (old_next_block_it != m_header.m_imultiset.begin() && 
            (--imultiset_iterator(old_next_block_it))->m_size > rem_units);
      if(size_invariants_broken){
         m_header.m_imultiset.erase(old_next_block_it);
      }
      //This is the remaining block
      block_ctrl *rem_block = new(reinterpret_cast<block_ctrl*>
                     (reinterpret_cast<char*>(block) + intended_units*Alignment))block_ctrl;
      rem_block->m_size  = rem_units;
      algo_impl_t::assert_alignment(rem_block);
      BOOST_ASSERT(rem_block->m_size >= BlockCtrlUnits);
      priv_mark_as_free_block(rem_block);

      //Now the second part of the fixup
      if(size_invariants_broken)
         m_header.m_imultiset.insert(m_header.m_imultiset.begin(), *rem_block);
      else
         m_header.m_imultiset.replace_node(old_next_block_it, *rem_block);

      //Write the new length
      block->m_size = intended_user_units + AllocatedCtrlUnits;
      BOOST_ASSERT(block->m_size >= BlockCtrlUnits);
      m_header.m_allocated += (intended_units - old_block_units)*Alignment;
   }
   //There is no free space to create a new node: just merge both blocks
   else{
      //Now we have to update the data in the tree
      m_header.m_imultiset.erase(Imultiset::s_iterator_to(*next_block));

      //Write the new length
      block->m_size = merged_units;
      BOOST_ASSERT(block->m_size >= BlockCtrlUnits);
      m_header.m_allocated += (merged_units - old_block_units)*Alignment;
   }
   priv_mark_as_allocated_block(block);
   received_size = (block->m_size - AllocatedCtrlUnits)*Alignment + UsableByPreviousChunk;
   return true;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment> inline
typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *
   rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::priv_prev_block
      (typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *ptr)
{
   BOOST_ASSERT(!ptr->m_prev_allocated);
   return reinterpret_cast<block_ctrl *>
      (reinterpret_cast<char*>(ptr) - ptr->m_prev_size*Alignment);
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment> inline
bool rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::priv_is_prev_allocated
      (typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *ptr)
{
   if(ptr->m_prev_allocated){
      return true;
   }
   else{
      block_ctrl *prev = priv_prev_block(ptr);
      (void)prev;
      BOOST_ASSERT(!priv_is_allocated_block(prev));
      return false;
   }
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment> inline
typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *
   rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::priv_end_block
      (typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *first_segment_block)
{
   BOOST_ASSERT(first_segment_block->m_prev_allocated);
   block_ctrl *end_block = reinterpret_cast<block_ctrl *>
      (reinterpret_cast<char*>(first_segment_block) - first_segment_block->m_prev_size*Alignment);
   (void)end_block;
   BOOST_ASSERT(priv_is_allocated_block(end_block));
   BOOST_ASSERT(end_block > first_segment_block);
   return end_block;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment> inline
typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *
   rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::priv_next_block
      (typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *ptr)
{
   return reinterpret_cast<block_ctrl *>
      (reinterpret_cast<char*>(ptr) + ptr->m_size*Alignment);
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment> inline
bool rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::priv_is_allocated_block
      (typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *block)
{
   bool allocated = block->m_allocated != 0;
   block_ctrl *next_block = reinterpret_cast<block_ctrl *>
      (reinterpret_cast<char*>(block) + block->m_size*Alignment);
   bool next_block_prev_allocated = next_block->m_prev_allocated != 0;
   (void)next_block_prev_allocated;
   BOOST_ASSERT(allocated == next_block_prev_allocated);
   return allocated;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment> inline
void rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::priv_mark_as_allocated_block
      (typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *block)
{
   //BOOST_ASSERT(!priv_is_allocated_block(block));
   block->m_allocated = 1;
   reinterpret_cast<block_ctrl *>
      (reinterpret_cast<char*>(block)+ block->m_size*Alignment)->m_prev_allocated = 1;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment> inline
void rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::priv_mark_as_free_block
      (typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl *block)
{
   block->m_allocated = 0;
   reinterpret_cast<block_ctrl *>
      (reinterpret_cast<char*>(block) + block->m_size*Alignment)->m_prev_allocated = 0;
   //BOOST_ASSERT(!priv_is_allocated_block(ptr));
   priv_next_block(block)->m_prev_size = block->m_size;
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment> inline
void* rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::priv_check_and_allocate
   (std::size_t nunits
   ,typename rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::block_ctrl* block
   ,std::size_t &received_size)
{
   std::size_t upper_nunits = nunits + BlockCtrlUnits;
   imultiset_iterator it_old = Imultiset::s_iterator_to(*block);
   algo_impl_t::assert_alignment(block);

   if (block->m_size >= upper_nunits){
      //This block is bigger than needed, split it in 
      //two blocks, the first's size will be "units" and
      //the second's size "block->m_size-units"
      std::size_t block_old_size = block->m_size;
      block->m_size = nunits;
      BOOST_ASSERT(block->m_size >= BlockCtrlUnits);

      //This is the remaining block
      block_ctrl *rem_block = new(reinterpret_cast<block_ctrl*>
                     (reinterpret_cast<char*>(block) + Alignment*nunits))block_ctrl;
      algo_impl_t::assert_alignment(rem_block);
      rem_block->m_size  = block_old_size - nunits;
      BOOST_ASSERT(rem_block->m_size >= BlockCtrlUnits);
      priv_mark_as_free_block(rem_block);

      imultiset_iterator it_hint;
      if(it_old == m_header.m_imultiset.begin()
         || (--imultiset_iterator(it_old))->m_size < rem_block->m_size){
         //option a: slow but secure
         //m_header.m_imultiset.insert(m_header.m_imultiset.erase(it_old), *rem_block);
         //option b: Construct an empty node and swap
         //Imultiset::init_node(*rem_block);
         //block->swap_nodes(*rem_block);
         //option c: replace the node directly
         m_header.m_imultiset.replace_node(Imultiset::s_iterator_to(*it_old), *rem_block);
      }
      else{
         //Now we have to update the data in the tree
         m_header.m_imultiset.erase(it_old);
         m_header.m_imultiset.insert(m_header.m_imultiset.begin(), *rem_block);
      }
         
   }
   else if (block->m_size >= nunits){
      m_header.m_imultiset.erase(it_old);
   }
   else{
      BOOST_ASSERT(0);
      return 0;
   }
   //We need block_ctrl for deallocation stuff, so
   //return memory user can overwrite
   m_header.m_allocated += block->m_size*Alignment;
   received_size =  (block->m_size - AllocatedCtrlUnits)*Alignment + UsableByPreviousChunk;

   //Mark the block as allocated
   priv_mark_as_allocated_block(block);

   //Clear the memory occupied by the tree hook, since this won't be
   //cleared with zero_free_memory
   TreeHook *t = static_cast<TreeHook*>(block);
   //Just clear the memory part reserved for the user      
   std::size_t tree_hook_offset_in_block = (char*)t - (char*)block;
   //volatile char *ptr = 
   char *ptr = reinterpret_cast<char*>(block)+tree_hook_offset_in_block;
   const std::size_t s = BlockCtrlBytes - tree_hook_offset_in_block;
   /*
   while(s--){
      *ptr++ = 0;
   }*/
   std::memset(ptr, 0, s);
   this->priv_next_block(block)->m_prev_size = 0;
   return priv_get_user_buffer(block);
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
void rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::deallocate(void* addr)
{
   if(!addr)   return;
   //-----------------------
   boost::interprocess::scoped_lock<interprocess_mutex> guard(m_header);
   //-----------------------
   return this->priv_deallocate(addr);
}

template<class MutexFamily, class VoidPointer, std::size_t MemAlignment>
void rbtree_best_fit<MutexFamily, VoidPointer, MemAlignment>::priv_deallocate(void* addr)
{
   if(!addr)   return;

   block_ctrl *block = priv_get_block(addr);
  
   //The blocks must be marked as allocated and the sizes must be equal
   BOOST_ASSERT(priv_is_allocated_block(block));
//   BOOST_ASSERT(block->m_size == priv_tail_size(block));

   //Check if alignment and block size are right
   algo_impl_t::assert_alignment(addr);

   std::size_t block_old_size = Alignment*block->m_size;
   BOOST_ASSERT(m_header.m_allocated >= block_old_size);

   //Update used memory count
   m_header.m_allocated -= block_old_size;

   //The block to insert in the tree
   block_ctrl *block_to_insert = block;

   //Get the next block
   block_ctrl *next_block  = priv_next_block(block);
   bool merge_with_prev    = !priv_is_prev_allocated(block);
   bool merge_with_next    = !priv_is_allocated_block(next_block);

   //Merge logic. First just update block sizes, then fix free blocks tree
   if(merge_with_prev || merge_with_next){
      //Merge if the previous is free
      if(merge_with_prev){
         //Get the previous block
         block_ctrl *prev_block = priv_prev_block(block);
         prev_block->m_size += block->m_size;
         BOOST_ASSERT(prev_block->m_size >= BlockCtrlUnits);
         block_to_insert = prev_block;
      }
      //Merge if the next is free
      if(merge_with_next){
         block_to_insert->m_size += next_block->m_size;
         BOOST_ASSERT(block_to_insert->m_size >= BlockCtrlUnits);
         if(merge_with_prev)
            m_header.m_imultiset.erase(Imultiset::s_iterator_to(*next_block));
      }

      bool only_merge_next = !merge_with_prev && merge_with_next;
      imultiset_iterator free_block_to_check_it
         (Imultiset::s_iterator_to(only_merge_next ? *next_block : *block_to_insert));
      imultiset_iterator was_bigger_it(free_block_to_check_it);

      //Now try to shortcut erasure + insertion (O(log(N))) with
      //a O(1) operation if merging does not alter tree positions
      if(++was_bigger_it != m_header.m_imultiset.end()   &&
         block_to_insert->m_size > was_bigger_it->m_size ){
         m_header.m_imultiset.erase(free_block_to_check_it);
         m_header.m_imultiset.insert(m_header.m_imultiset.begin(), *block_to_insert);
      }
      else if(only_merge_next){
         m_header.m_imultiset.replace_node(free_block_to_check_it, *block_to_insert);
      }
   }
   else{
      m_header.m_imultiset.insert(m_header.m_imultiset.begin(), *block_to_insert);
   }
   priv_mark_as_free_block(block_to_insert);
}

/// @endcond

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

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

#endif   //#ifndef BOOST_INTERPROCESS_MEM_ALGO_RBTREE_BEST_FIT_HPP