RTEMS CPU Kit with SuperCore  4.10.99.0
Data Structures | Typedefs | Functions
Red-Black Tree Heap
RTEMS Classic API

Red-Black Tree Heap API. More...

Collaboration diagram for Red-Black Tree Heap:

Data Structures

struct  rtems_rbheap_chunk
 Red-black heap chunk descriptor. More...
struct  rtems_rbheap_control
 Red-black heap control. More...

Typedefs

typedef struct rtems_rbheap_control rtems_rbheap_control
typedef void(* rtems_rbheap_extend_descriptors )(rtems_rbheap_control *control)
 Handler to extend the available chunk descriptors.

Functions

rtems_status_code rtems_rbheap_initialize (rtems_rbheap_control *control, void *area_begin, uintptr_t area_size, uintptr_t alignment, rtems_rbheap_extend_descriptors extend_descriptors, void *handler_arg)
 Initializes the red-black tree heap control.
void * rtems_rbheap_allocate (rtems_rbheap_control *control, size_t size)
 Allocates a chunk of memory of at least size bytes from the red-black tree heap control.
rtems_status_code rtems_rbheap_free (rtems_rbheap_control *control, void *ptr)
 Frees a chunk of memory ptr allocated from the red-black tree heap control.
void rtems_rbheap_extend_descriptors_never (rtems_rbheap_control *control)
 Chunk descriptor extend handler that does nothing.
void rtems_rbheap_extend_descriptors_with_malloc (rtems_rbheap_control *control)
 Chunk descriptor extend handler that uses malloc().

Detailed Description

Red-Black Tree Heap API.

The red-black tree heap provides a memory allocator suitable to implement the malloc() and free() interface. It uses a first-fit allocation strategy. In the red-black tree heap the administration data structures are not contained in the managed memory area. Thus writing beyond the boundaries of a chunk does not damage the data to maintain the heap. This can be used for example in a task stack allocator which protects the task stacks from access by other tasks. The allocated and free memory parts of the managed area are called chunks. Each chunk needs a descriptor which is stored outside of the managed area.


Typedef Documentation

Handler to extend the available chunk descriptors.

This handler is called when no more chunk descriptors are available. An example implementation is this:

 void extend_descriptors_with_malloc(rtems_rbheap_control *control)
 {
   rtems_rbheap_chunk *chunk = malloc(sizeof(*chunk));

   if (chunk != NULL) {
     rtems_rbheap_add_to_spare_descriptor_chain(control, chunk);
   }
 }
See also:
rtems_rbheap_extend_descriptors_never() and rtems_rbheap_extend_descriptors_with_malloc().

Function Documentation

void* rtems_rbheap_allocate ( rtems_rbheap_control control,
size_t  size 
)

Allocates a chunk of memory of at least size bytes from the red-black tree heap control.

The chunk begin is aligned by the value specified in rtems_rbheap_initialize().

Parameters:
[in,out]controlThe red-black tree heap.
[in]sizeThe requested chunk size in bytes.
Return values:
NULLNot enough free space in the heap.
otherwisePointer to allocated chunk of memory.
rtems_status_code rtems_rbheap_free ( rtems_rbheap_control control,
void *  ptr 
)

Frees a chunk of memory ptr allocated from the red-black tree heap control.

Parameters:
[in,out]controlThe red-black tree heap.
[in]ptrThe pointer to the chunk of memory.
Return values:
RTEMS_SUCCESSFULSuccessful operation.
RTEMS_INVALID_IDThe chunk of memory is not a valid chunk in the red-black tree heap.
RTEMS_INCORRECT_STATEThe chunk of memory is not in the right state.
rtems_status_code rtems_rbheap_initialize ( rtems_rbheap_control control,
void *  area_begin,
uintptr_t  area_size,
uintptr_t  alignment,
rtems_rbheap_extend_descriptors  extend_descriptors,
void *  handler_arg 
)

Initializes the red-black tree heap control.

Parameters:
[in,out]controlThe red-black tree heap.
[in]area_beginThe managed memory area begin.
[in]area_sizeThe managed memory area size.
[in]alignmentThe minimum chunk alignment.
[in]extend_descriptorsThe handler to extend the available chunk descriptors.
[in]handler_argThe handler argument.
Return values:
RTEMS_SUCCESSFULSuccessful operation.
RTEMS_INVALID_ADDRESSThe memory area is invalid.
RTEMS_NO_MEMORYNot enough chunk descriptors.