Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.

Class template rbtree_best_fit



// In header: <boost/interprocess/mem_algo/rbtree_best_fit.hpp>

template<typename MutexFamily, typename VoidPointer, std::size_t MemAlignment> 
class rbtree_best_fit {
  // types
  typedef MutexFamily mutex_family;
  typedef VoidPointer void_pointer;           // Pointer type to be used with the rest of the Interprocess framework. 
  typedef unspecified multiallocation_chain;

  // member classes/structs/unions

  // Block control structure.

  struct block_ctrl : public boost::interprocess::rbtree_best_fit< MutexFamily, VoidPointer, MemAlignment >::SizeHolder
    // construct/copy/destruct

  struct header_t : public boost::interprocess::interprocess_mutex {
    Imultiset m_imultiset;
    std::size_t m_extra_hdr_bytes;    // The extra size required by the segment. 
    std::size_t m_allocated;    // Allocated bytes for internal checking. 
    std::size_t m_size;    // The size of the memory segment. 

  struct size_block_ctrl_compare {

    // public member functions
    bool operator()(std::size_t, const block_ctrl &) const;
    bool operator()(const block_ctrl &, std::size_t) const;

  struct SizeHolder {
    std::size_t m_prev_size;
    std::size_t m_size;
    std::size_t m_prev_allocated;
    std::size_t m_allocated;

  // construct/copy/destruct
  rbtree_best_fit(const rbtree_best_fit &);
  rbtree_best_fit(std::size_t, std::size_t);
  rbtree_best_fit& operator=(const rbtree_best_fit &);

  // private member functions
   BOOST_STATIC_ASSERT((Alignment >=4));
   BOOST_STATIC_ASSERT((0==(Alignment &(Alignment-std::size_t(1u)))));

  // public member functions
  void * allocate(std::size_t);
  multiallocation_chain allocate_many(std::size_t, std::size_t);
  allocate_many(const std::size_t *, std::size_t, std::size_t);
  void deallocate_many(multiallocation_chain);
  void deallocate(void *);
  std::size_t get_size() const;
  std::size_t get_free_memory() const;
  void zero_free_memory();
  void grow(std::size_t);
  void shrink_to_fit();
  bool all_memory_deallocated();
  bool check_sanity();
  template<typename T> 
    std::pair< T *, bool > 
    allocation_command(boost::interprocess::allocation_type, std::size_t, 
                       std::size_t, std::size_t &, T * = 0);
  std::pair< void *, bool > 
  raw_allocation_command(boost::interprocess::allocation_type, std::size_t, 
                         std::size_t, std::size_t &, void * = 0, 
                         std::size_t = 1);
  std::size_t size(const void *) const;
  void * allocate_aligned(std::size_t, std::size_t);
  std::pair< void *, bool > 
  priv_allocation_command(boost::interprocess::allocation_type, std::size_t, 
                          std::size_t, std::size_t &, void *, std::size_t);
  std::pair< void *, bool > 
  priv_allocate(boost::interprocess::allocation_type, std::size_t, 
                std::size_t, std::size_t &, void * = 0, std::size_t = 1);
  bool priv_expand(void *, const std::size_t, const std::size_t, 
                   std::size_t &);
  void * priv_expand_both_sides(boost::interprocess::allocation_type, 
                                std::size_t, std::size_t, std::size_t &, 
                                void *, bool, std::size_t);
  block_ctrl * priv_prev_block(block_ctrl *);
  bool priv_is_prev_allocated(block_ctrl *);
  block_ctrl * priv_end_block(block_ctrl *);
  block_ctrl * priv_next_block(block_ctrl *);
  bool priv_is_allocated_block(block_ctrl *);
  void priv_mark_as_allocated_block(block_ctrl *);
  void priv_mark_as_free_block(block_ctrl *);
  void * priv_check_and_allocate(std::size_t, block_ctrl *, std::size_t &);
  void priv_deallocate(void *);
  void priv_add_segment(void *, std::size_t);
  void priv_mark_new_allocated_block(block_ctrl *);

  // public static functions
  static std::size_t get_min_size(std::size_t);
  static std::size_t priv_first_block_offset(const void *, std::size_t);
  static block_ctrl * priv_get_block(const void *);
  static void * priv_get_user_buffer(const block_ctrl *);
  static std::size_t priv_get_total_units(std::size_t);
  static const std::size_t Alignment;
  static const std::size_t PayloadPerAllocation;


This class implements an algorithm that stores the free nodes in a red-black tree to have logarithmic search/insert times.

rbtree_best_fit public types

  1. typedef MutexFamily mutex_family;

    Shared interprocess_mutex family used for the rest of the Interprocess framework

rbtree_best_fit public construct/copy/destruct

  1. rbtree_best_fit();
    @ //Non-copyable
  2. rbtree_best_fit(const rbtree_best_fit &);
  3. rbtree_best_fit(std::size_t size, std::size_t extra_hdr_bytes);

    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.

  4. rbtree_best_fit& operator=(const rbtree_best_fit &);
  5. ~rbtree_best_fit();

rbtree_best_fit private member functions

  1.  BOOST_STATIC_ASSERT((Alignment >=4));
  2.  BOOST_STATIC_ASSERT(unspecified);
  3.  BOOST_STATIC_ASSERT((0==(Alignment &(Alignment-std::size_t(1u)))));

rbtree_best_fit public member functions

  1. void * allocate(std::size_t nbytes);
    Allocates bytes, returns 0 if there is not more memory.
  2. multiallocation_chain 
    allocate_many(std::size_t elem_bytes, std::size_t num_elements);

    Multiple element allocation, same size

  3. multiallocation_chain 
    allocate_many(const std::size_t * elem_sizes, std::size_t n_elements, 
                  std::size_t sizeof_element);
    Multiple element allocation, different size.
  4. void deallocate_many(multiallocation_chain chain);
    Multiple element allocation, different size.
  5. void deallocate(void * addr);

    Deallocates previously allocated bytes

  6. std::size_t get_size() const;
    Returns the size of the memory segment.
  7. std::size_t get_free_memory() const;
    Returns the number of free bytes of the segment.
  8. void zero_free_memory();

    Initializes to zero all the memory that's not in use. This function is normally used for security reasons.

  9. void grow(std::size_t extra_size);

    Increases managed memory in extra_size bytes more

  10. void shrink_to_fit();
    Decreases managed memory as much as possible.
  11. bool all_memory_deallocated();
    Returns true if all allocated memory has been deallocated.
  12. bool check_sanity();

    Makes an internal sanity check and returns true if success

  13. template<typename 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);
  14. 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);
  15. std::size_t size(const void * ptr) const;
    Returns the size of the buffer previously allocated pointed by ptr.
  16. void * allocate_aligned(std::size_t nbytes, std::size_t alignment);

    Allocates aligned bytes, returns 0 if there is not more memory. Alignment must be power of 2

  17. 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);
  18. 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);
    Real allocation algorithm with min allocation option.
  19. bool priv_expand(void * ptr, const std::size_t min_size, 
                     const std::size_t preferred_size, 
                     std::size_t & received_size);
    Real expand function implementation.
  20. 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);
    Real expand to both sides implementation.
  21. block_ctrl * priv_prev_block(block_ctrl * ptr);
    Get poitner of the previous block (previous block must be free)
  22. bool priv_is_prev_allocated(block_ctrl * ptr);
    Returns true if the previous block is allocated.
  23. block_ctrl * priv_end_block(block_ctrl * first_segment_block);
    Get a pointer of the "end" block from the first block of the segment.
  24. block_ctrl * priv_next_block(block_ctrl * ptr);
    Get the size in the tail of the previous block.
  25. bool priv_is_allocated_block(block_ctrl * ptr);
    Check if this block is free (not allocated)
  26. void priv_mark_as_allocated_block(block_ctrl * ptr);
    Marks the block as allocated.
  27. void priv_mark_as_free_block(block_ctrl * ptr);
    Marks the block as allocated.
  28. void * priv_check_and_allocate(std::size_t units, block_ctrl * block, 
                                   std::size_t & received_size);

    Checks if block has enough memory and splits/unlinks the block returning the address to the users

  29. void priv_deallocate(void * addr);
    Real deallocation algorithm.
  30. void priv_add_segment(void * addr, std::size_t size);
    Makes a new memory portion available for allocation.
  31. void priv_mark_new_allocated_block(block_ctrl * block);

rbtree_best_fit public static functions

  1. static std::size_t get_min_size(std::size_t extra_hdr_bytes);
    Obtains the minimum size needed by the algorithm.
  2. static std::size_t 
    priv_first_block_offset(const void * this_ptr, std::size_t extra_hdr_bytes);
    @ private:


  3. static block_ctrl * priv_get_block(const void * ptr);
    Obtains the block control structure of the user buffer.
  4. static void * priv_get_user_buffer(const block_ctrl * block);
    Obtains the pointer returned to the user from the block control.
  5. static std::size_t priv_get_total_units(std::size_t userbytes);

    Returns the number of total units that a user buffer of "userbytes" bytes really occupies (including header)