CLASS TEMPLAT(3)

NAME
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

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

        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();
        Destructor. .RE

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

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

            4.

            void deallocate_many(multiallocation_chain chain);
            Multiple element allocation, different size. .RE

                5.

                void deallocate(void * addr);

                Deallocates previously allocated bytes

                6.

                std::size_t get_size() const;
                Returns the size of the memory segment. .RE

                    7.

                    std::size_t get_free_memory() const;
                    Returns the number of free bytes of the segment. .RE

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

                            11.

                            bool all_memory_deallocated();
                            Returns true if all allocated memory has been deallocated. .RE

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

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

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

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

                                                21.

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

                                                    22.

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

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

                                                            24.

                                                            block_ctrl * priv_next_block(block_ctrl * ptr);
                                                            Get the size in the tail of the previous block. .RE

                                                                25.

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

                                                                    26.

                                                                    void priv_mark_as_allocated_block(block_ctrl * ptr);
                                                                    Marks the block as allocated. .RE

                                                                        27.

                                                                        void priv_mark_as_free_block(block_ctrl * ptr);
                                                                        Marks the block as allocated. .RE

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

                                                                                30.

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

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

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

            4.

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

                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)