RTEMS  5.0.0
Files | Data Structures | Typedefs | Functions
Red-Black Tree Heap

Red-Black Tree Heap API. More...

Files

file  rbheap.c
 Red-Black Tree Heap implementation.
 

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

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

◆ rtems_rbheap_extend_descriptors

typedef void(* rtems_rbheap_extend_descriptors) (rtems_rbheap_control *control)

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

◆ rtems_rbheap_allocate()

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_rbheap_free()

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_rbheap_initialize()

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.