Red-Black Tree Heap

The red-black tree heap provides a memory allocator using a red-black tree to maintain blocks of memory. More...

Files
file	rbheap.h
	This header file provides the Red-Black Tree Heap API.
file	rbheap.c
	This source file contains the implementation of rtems_rbheap_allocate(), rtems_rbheap_extend_descriptors_never(), rtems_rbheap_extend_descriptors_with_malloc(), rtems_rbheap_free(), and rtems_rbheap_initialize().

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

The red-black tree heap provides a memory allocator using a red-black tree to maintain blocks of memory.

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]	control	The red-black tree heap.
[in]	size	The requested chunk size in bytes.

Return values

NULL	Not enough free space in the heap.
otherwise	Pointer 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]	control	The red-black tree heap.
[in]	ptr	The pointer to the chunk of memory.

Return values

RTEMS_SUCCESSFUL	Successful operation.
RTEMS_INVALID_ID	The chunk of memory is not a valid chunk in the red-black tree heap.
RTEMS_INCORRECT_STATE	The 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]	control	The red-black tree heap.
[in]	area_begin	The managed memory area begin.
[in]	area_size	The managed memory area size.
[in]	alignment	The minimum chunk alignment.
[in]	extend_descriptors	The handler to extend the available chunk descriptors.
[in]	handler_arg	The handler argument.

Return values

RTEMS_SUCCESSFUL	Successful operation.
RTEMS_INVALID_ADDRESS	The memory area is invalid.
RTEMS_NO_MEMORY	Not enough chunk descriptors.