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;

  // construct/copy/destruct
  rbtree_best_fit(std::size_t, std::size_t);

  // public member functions
  void * allocate(std::size_t) ;
  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) ;

  // public static functions
  static std::size_t get_min_size(std::size_t) ;
  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(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.

  2. ~rbtree_best_fit();

rbtree_best_fit public member functions

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

    Deallocates previously allocated bytes

  3. std::size_t get_size() const;
    Returns the size of the memory segment.
  4. std::size_t get_free_memory() const;
    Returns the number of free bytes of the segment.
  5. void zero_free_memory() ;

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

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

    Increases managed memory in extra_size bytes more

  7. void shrink_to_fit() ;
    Decreases managed memory as much as possible.
  8. bool all_memory_deallocated() ;
    Returns true if all allocated memory has been deallocated.
  9. bool check_sanity() ;

    Makes an internal sanity check and returns true if success

  10. 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) ;
  11. 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) ;
  12. std::size_t size(const void * ptr) const;
    Returns the size of the buffer previously allocated pointed by ptr.
  13. 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

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.