Class template rbtree_best_fit

boost::interprocess::rbtree_best_fit

Synopsis

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

template<typename MutexFamily, typename VoidPointer, std::size_t MemAlignment> 
class rbtree_best_fit {
public:
  // 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
    block_ctrl();
  };

  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();
  rbtree_best_fit(const rbtree_best_fit &);
  rbtree_best_fit(std::size_t, std::size_t);
  rbtree_best_fit& operator=(const rbtree_best_fit &);
  ~rbtree_best_fit();

  // private member functions
   BOOST_STATIC_ASSERT((Alignment >=4));
   BOOST_STATIC_ASSERT(unspecified);
   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);
  multiallocation_chain 
  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;
};

Description

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

typedef MutexFamily mutex_family;

Shared interprocess_mutex family used for the rest of the Interprocess framework

`rbtree_best_fit` public construct/copy/destruct

```
rbtree_best_fit();
```
@ //Non-copyable

rbtree_best_fit(const rbtree_best_fit &);

```
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.

rbtree_best_fit& operator=(const rbtree_best_fit &);

```
~rbtree_best_fit();
```
Destructor.

`rbtree_best_fit` private member functions

```
 BOOST_STATIC_ASSERT((Alignment >=4));
```
```
 BOOST_STATIC_ASSERT(unspecified);
```

 BOOST_STATIC_ASSERT((0==(Alignment &(Alignment-std::size_t(1u)))));

`rbtree_best_fit` public member functions

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

multiallocation_chain 
allocate_many(std::size_t elem_bytes, std::size_t num_elements);

Multiple element allocation, same size

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.

void deallocate_many(multiallocation_chain chain);

Multiple element allocation, different size.

```
void deallocate(void * addr);
```
Deallocates previously allocated bytes
```
std::size_t get_size() const;
```
Returns the size of the memory segment.
```
std::size_t get_free_memory() const;
```
Returns the number of free bytes of the segment.
```
void zero_free_memory();
```
Initializes to zero all the memory that's not in use. This function is normally used for security reasons.
```
void grow(std::size_t extra_size);
```
Increases managed memory in extra_size bytes more
```
void shrink_to_fit();
```
Decreases managed memory as much as possible.
```
bool all_memory_deallocated();
```
Returns true if all allocated memory has been deallocated.
```
bool check_sanity();
```
Makes an internal sanity check and returns true if success

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);

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);

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

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);

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.

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.

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.

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

bool priv_is_prev_allocated(block_ctrl * ptr);

Returns true if the previous block is allocated.

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

block_ctrl * priv_next_block(block_ctrl * ptr);

Get the size in the tail of the previous block.

bool priv_is_allocated_block(block_ctrl * ptr);

Check if this block is free (not allocated)

void priv_mark_as_allocated_block(block_ctrl * ptr);

Marks the block as allocated.

void priv_mark_as_free_block(block_ctrl * ptr);

Marks the block as allocated.

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

```
void priv_deallocate(void * addr);
```
Real deallocation algorithm.

void priv_add_segment(void * addr, std::size_t size);

Makes a new memory portion available for allocation.

void priv_mark_new_allocated_block(block_ctrl * block);

`rbtree_best_fit` public static functions

static std::size_t get_min_size(std::size_t extra_hdr_bytes);

Obtains the minimum size needed by the algorithm.

static std::size_t 
priv_first_block_offset(const void * this_ptr, std::size_t extra_hdr_bytes);

@ private:

static block_ctrl * priv_get_block(const void * ptr);

Obtains the block control structure of the user buffer.

static void * priv_get_user_buffer(const block_ctrl * block);

Obtains the pointer returned to the user from the block control.

```
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)

Boost C++ Libraries