The Red-Black Tree Handler is used to manage sets of entities. More...

Collaboration diagram for Red-Black Tree Handler:

Files
file	rbtree.c
	Initialize a RBTree Header.

file	rbtreefind.c
	Find the control structure of the tree containing the given node.

file	rbtreeiterate.c
	_RBTree_Iterate() implementation.

file	rbtreenext.c
	_RBTree_Next() and _RBTree_Next() implementation.

Data Structures
struct	RBTree_Node_struct
	This is used to manage each element (node) which is placed on a RBT. More...

struct	RBTree_Control
	This is used to manage a RBT. More...

Macros
#define	RBTREE_INITIALIZER_EMPTY(name) { NULL, NULL, { NULL, NULL } }
	RBTree initializer for an empty rbtree with designator name.

#define	RBTREE_DEFINE_EMPTY(name) RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
	RBTree definition for an empty rbtree with designator name.

#define	RBTREE_NODE_INITIALIZER_EMPTY(name) { NULL, { NULL, NULL }, RBT_RED }
	RBTree_Node initializer for an empty node with designator name.

#define	RBTREE_NODE_DEFINE_EMPTY(name) RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY( name )
	RBTree definition for an empty rbtree with designator name.

Typedefs
typedef struct RBTree_Node_struct	RBTree_Node
	This type definition promotes the name for the RBTree Node used by all RTEMS code. More...

typedef long	RBTree_Compare_result
	Integer type for compare results. More...

typedef RBTree_Compare_result(*	RBTree_Compare) (const RBTree_Node first, const RBTree_Node second)
	Compares two red-black tree nodes. More...

typedef bool(*	RBTree_Visitor) (const RBTree_Node node, RBTree_Direction dir, void visitor_arg)
	Red-black tree visitor. More...

Enumerations
enum	RBTree_Color { RBT_BLACK, RBT_RED }
	This enum type defines the colors available for the RBTree Nodes.

enum	RBTree_Direction { RBT_LEFT =0, RBT_RIGHT =1 }
	This type indicates the direction.

Functions
void	_RBTree_Initialize (RBTree_Control the_rbtree, RBTree_Compare compare, void starting_address, size_t number_nodes, size_t node_size, bool is_unique)
	Initialize a RBTree Header. More...

RBTree_Node *	_RBTree_Find (const RBTree_Control the_rbtree, const RBTree_Node the_node, RBTree_Compare compare, bool is_unique)
	Tries to find a node for the specified key in the tree. More...

RBTree_Node *	_RBTree_Insert (RBTree_Control the_rbtree, RBTree_Node the_node, RBTree_Compare compare, bool is_unique)
	Inserts the node into the red-black tree. More...

void	_RBTree_Extract (RBTree_Control the_rbtree, RBTree_Node the_node)
	Extracts (removes) the node from the red-black tree. More...

RBTree_Node *	_RBTree_Next (const RBTree_Node *node, RBTree_Direction dir)
	Returns the in-order next node of a node. More...

RTEMS_INLINE_ROUTINE void	_RBTree_Set_off_tree (RBTree_Node *the_node)
	Sets a red-black tree node as off-tree. More...

RTEMS_INLINE_ROUTINE bool	_RBTree_Is_node_off_tree (const RBTree_Node *the_node)
	Returns true, if this red-black tree node is off-tree, and false otherwise. More...

RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Root (const RBTree_Control *the_rbtree)
	Returns a pointer to root node of the red-black tree. More...

RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_First (const RBTree_Control *the_rbtree, RBTree_Direction dir)
	Return pointer to RBTree's first node. More...

RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Parent (const RBTree_Node *the_node)
	Returns a pointer to the parent of this node. More...

RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Left (const RBTree_Node *the_node)
	Return pointer to the left of this node. More...

RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Right (const RBTree_Node *the_node)
	Return pointer to the right of this node. More...

RTEMS_INLINE_ROUTINE bool	_RBTree_Is_empty (const RBTree_Control *the_rbtree)
	Is the RBTree empty. More...

RTEMS_INLINE_ROUTINE bool	_RBTree_Is_first (const RBTree_Control the_rbtree, const RBTree_Node the_node, RBTree_Direction dir)
	Is this the first node on the RBTree. More...

RTEMS_INLINE_ROUTINE bool	_RBTree_Is_root (const RBTree_Node *the_node)
	Returns true if this node is the root node of a red-black tree, and false otherwise. More...

RTEMS_INLINE_ROUTINE void	_RBTree_Initialize_empty (RBTree_Control *the_rbtree)
	Initialize this RBTree as empty. More...

RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Predecessor (const RBTree_Node *node)
	Returns the predecessor of a node. More...

RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Successor (const RBTree_Node *node)
	Returns the successor of a node. More...

RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Get (RBTree_Control *the_rbtree, RBTree_Direction dir)
	Gets a node with an extremal key value from the red-black tree. More...

void	_RBTree_Iterate (const RBTree_Control rbtree, RBTree_Direction dir, RBTree_Visitor visitor, void visitor_arg)
	Red-black tree iteration. More...

RTEMS_INLINE_ROUTINE RBTree_Direction	_RBTree_Opposite_direction (RBTree_Direction the_dir)
	Get the direction opposite to the_dir.

RTEMS_INLINE_ROUTINE RBTree_Direction	_RBTree_Direction (const RBTree_Node the_node, const RBTree_Node parent)
	Returns the direction of the node. More...

RTEMS_INLINE_ROUTINE bool	_RBTree_Is_red (const RBTree_Node *the_node)
	Is this node red. More...

RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Sibling (const RBTree_Node the_node, const RBTree_Node parent)
	Returns the sibling of the node. More...

RTEMS_INLINE_ROUTINE bool	_RBTree_Is_equal (RBTree_Compare_result compare_result)

RTEMS_INLINE_ROUTINE bool	_RBTree_Is_greater (RBTree_Compare_result compare_result)

RTEMS_INLINE_ROUTINE bool	_RBTree_Is_lesser (RBTree_Compare_result compare_result)

RTEMS_INLINE_ROUTINE void	_RBTree_Rotate (RBTree_Node *the_node, RBTree_Direction dir)
	Rotates the node in the specified direction. More...

Detailed Description

The Red-Black Tree Handler is used to manage sets of entities.

This handler provides two data structures. The rbtree Node data structure is included as the first part of every data structure that will be placed on a RBTree. The second data structure is rbtree Control which is used to manage a set of rbtree Nodes.

Typedef Documentation

◆ RBTree_Compare

typedef RBTree_Compare_result( * RBTree_Compare) (const RBTree_Node *first, const RBTree_Node *second)

Compares two red-black tree nodes.

Parameters

[in]	first	The first node.
[in]	second	The second node.

Return values

positive	The key value of the first node is greater than the one of the second node.
0	The key value of the first node is equal to the one of the second node.
negative	The key value of the first node is less than the one of the second node.

◆ RBTree_Compare_result

typedef long RBTree_Compare_result

Integer type for compare results.

The type is large enough to represent pointers and 32-bit signed integers.

See also: RBTree_Compare.

◆ RBTree_Node

RBTree_Node

This type definition promotes the name for the RBTree Node used by all RTEMS code.

It is a separate type definition because a forward reference is required to define it. See RBTree_Node_struct for detailed information.

◆ RBTree_Visitor

typedef bool(* RBTree_Visitor) (const RBTree_Node *node, RBTree_Direction dir, void *visitor_arg)

Red-black tree visitor.

Parameters

[in]	node	The node.
[in]	dir	The direction.
[in]	visitor_arg	The visitor argument.

Return values

true	Stop the iteration.
false	Continue the iteration.

See also: _RBTree_Iterate().

Function Documentation

◆ _RBTree_Direction()

RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Direction	(	const RBTree_Node *	the_node,
		const RBTree_Node *	parent
	)

Returns the direction of the node.

Parameters

[in]	the_node	The node of interest.
[in]	parent	The parent of the node. The parent must exist, thus it is invalid to use this function for the root node.

References RBTree_Node_struct::child.

Referenced by _RBTree_Rotate().

◆ _RBTree_Extract()

void _RBTree_Extract	(	RBTree_Control *	the_rbtree,
		RBTree_Node *	the_node
	)

Extracts (removes) the node from the red-black tree.

This function does not set the node off-tree. In case this is desired, then call _RBTree_Set_off_tree() after the extraction.

In case the node to extract is not a node of the tree, then this function yields unpredictable results.

Parameters

[in]	the_rbtree	The red-black tree control.
[in]	the_node	The node to extract.

References RBTree_Control::first.

Referenced by _RBTree_Get(), and rtems_rbtree_extract().

◆ _RBTree_Find()

RBTree_Node* _RBTree_Find	(	const RBTree_Control *	the_rbtree,
		const RBTree_Node *	the_node,
		RBTree_Compare	compare,
		bool	is_unique
	)

Tries to find a node for the specified key in the tree.

Parameters

[in]	the_rbtree	The red-black tree control.
[in]	the_node	A node specifying the key.
[in]	compare	The node compare function.
[in]	is_unique	If true, then return the first node with a key equal to the one of the node specified if it exits, else return the last node if it exists.

Return values

node	A node corresponding to the key. If the tree is not unique and contains duplicate keys, the set of duplicate keys acts as FIFO.
NULL	No node exists in the tree for the key.

◆ _RBTree_First()

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_First	(	const RBTree_Control *	the_rbtree,
		RBTree_Direction	dir
	)

Return pointer to RBTree's first node.

This function returns a pointer to the first node on the_rbtree, where dir specifies whether to return the minimum (0) or maximum (1).

References RBTree_Control::first.

Referenced by _RBTree_Is_first(), _RBTree_Iterate(), rtems_rbtree_max(), rtems_rbtree_min(), rtems_rbtree_peek_max(), and rtems_rbtree_peek_min().

◆ _RBTree_Get()

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Get	(	RBTree_Control *	the_rbtree,
		RBTree_Direction	dir
	)

Gets a node with an extremal key value from the red-black tree.

This function extracts a node with the minimum or maximum key value from tree and returns a pointer to that node if it exists. In case multiple nodes with a minimum key value exist, then they are extracted in FIFO order. In case multiple nodes with a maximum key value exist, then they are extracted in LIFO order.

Parameters

[in]	the_rbtree	The red-black tree control.
[in]	dir	Specifies whether to get a node with the minimum (RBT_LEFT) or maximum (RBT_RIGHT) key value.

Return values

NULL	The tree is empty.
extremal_node	A node with a minimal or maximal key value on the tree.

References _RBTree_Extract(), and RBTree_Control::first.

Referenced by rtems_rbtree_get_max(), and rtems_rbtree_get_min().

◆ _RBTree_Initialize()

void _RBTree_Initialize	(	RBTree_Control *	the_rbtree,
		RBTree_Compare	compare,
		void *	starting_address,
		size_t	number_nodes,
		size_t	node_size,
		bool	is_unique
	)

Initialize a RBTree Header.

This routine initializes the_rbtree structure to manage the contiguous array of number_nodes nodes which starts at starting_address. Each node is of node_size bytes.

Parameters

[in]	the_rbtree	is the pointer to rbtree header
[in]	compare	The node compare function.
[in]	starting_address	is the starting address of first node
[in]	number_nodes	is the number of nodes in rbtree
[in]	node_size	is the size of node in bytes
[in]	is_unique	If true, then reject nodes with a duplicate key, else otherwise.

◆ _RBTree_Initialize_empty()

RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty ( RBTree_Control * the_rbtree )

Initialize this RBTree as empty.

This routine initializes the_rbtree to contain zero nodes.

References RBTree_Control::first, RBTree_Control::permanent_null, and RBTree_Control::root.

Referenced by rtems_rbtree_initialize_empty().

◆ _RBTree_Insert()

RBTree_Node* _RBTree_Insert	(	RBTree_Control *	the_rbtree,
		RBTree_Node *	the_node,
		RBTree_Compare	compare,
		bool	is_unique
	)

Inserts the node into the red-black tree.

In case the node is already a node of a tree, then this function yields unpredictable results.

Parameters

[in]	the_rbtree	The red-black tree control.
[in]	the_node	The node to insert.
[in]	compare	The node compare function.
[in]	is_unique	If true, then reject nodes with a duplicate key, else insert nodes in FIFO order in case the key value is equal to existing nodes.

Return values

NULL	Successfully inserted.
existing_node	This is a unique insert and there exists a node with an equal key in the tree already.

◆ _RBTree_Is_empty()

RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty ( const RBTree_Control * the_rbtree )

Is the RBTree empty.

This function returns true if there are no nodes on the_rbtree and false otherwise.

Parameters

[in] the_rbtree is the rbtree to be operated upon.

Return values

true	There are no nodes on the_rbtree.
false	There are nodes on the_rbtree.

References RBTree_Control::root.

Referenced by rtems_rbtree_is_empty().

◆ _RBTree_Is_first()

RTEMS_INLINE_ROUTINE bool _RBTree_Is_first	(	const RBTree_Control *	the_rbtree,
		const RBTree_Node *	the_node,
		RBTree_Direction	dir
	)

Is this the first node on the RBTree.

This function returns true if the_node is the first node on the_rbtree and false otherwise. dir specifies whether first means minimum (0) or maximum (1).

Return values

true	the_node is the first node on the_rbtree.
false	the_node is not the first node on the_rbtree.

References _RBTree_First().

Referenced by rtems_rbtree_is_max(), and rtems_rbtree_is_min().

◆ _RBTree_Is_node_off_tree()

RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree ( const RBTree_Node * the_node )

Returns true, if this red-black tree node is off-tree, and false otherwise.

Parameters

[in] the_node The node to test.

Return values

true	The node is not a part of a tree (off-tree).
false	Otherwise.

See also: _RBTree_Set_off_tree().

References RBTree_Node_struct::parent.

Referenced by rtems_rbtree_is_node_off_tree().

◆ _RBTree_Is_red()

RTEMS_INLINE_ROUTINE bool _RBTree_Is_red ( const RBTree_Node * the_node )

Is this node red.

This function returns true if the_node is red and false otherwise.

Return values

true	the_node is red.
false	the_node in not red.

References RBTree_Node_struct::color.

◆ _RBTree_Is_root()

RTEMS_INLINE_ROUTINE bool _RBTree_Is_root ( const RBTree_Node * the_node )

Returns true if this node is the root node of a red-black tree, and false otherwise.

The root node may change after insert or extract operations. In case the node is not a node of a tree, then this function yields unpredictable results.

Parameters

[in] the_node The node of interest.

Return values

true	The node is the root node.
false	Otherwise.

See also: _RBTree_Root().

References _RBTree_Parent().

Referenced by rtems_rbtree_is_root().

◆ _RBTree_Iterate()

void _RBTree_Iterate	(	const RBTree_Control *	rbtree,
		RBTree_Direction	dir,
		RBTree_Visitor	visitor,
		void *	visitor_arg
	)

Red-black tree iteration.

Parameters

[in]	rbtree	The red-black tree.
[in]	dir	The direction.
[in]	visitor	The visitor.
[in]	visitor_arg	The visitor argument.

References _RBTree_First(), _RBTree_Next(), and _RBTree_Opposite_direction().

◆ _RBTree_Left()

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Left ( const RBTree_Node * the_node )

Return pointer to the left of this node.

This function returns a pointer to the left node of this node.

Parameters

[in] the_node is the node to be operated upon.

Returns: This method returns the left node on the rbtree.

References RBTree_Node_struct::child.

Referenced by rtems_rbtree_left().

◆ _RBTree_Next()

RBTree_Node* _RBTree_Next	(	const RBTree_Node *	node,
		RBTree_Direction	dir
	)

Returns the in-order next node of a node.

Parameters

[in]	node	The node.
[in]	dir	The direction.

Return values

NULL	The in-order next node does not exist.
otherwise	The next node.

References _RBTree_Opposite_direction(), and RBTree_Node_struct::child.

Referenced by _RBTree_Iterate(), _RBTree_Predecessor(), and _RBTree_Successor().

◆ _RBTree_Parent()

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Parent ( const RBTree_Node * the_node )

Returns a pointer to the parent of this node.

The node must have a parent, thus it is invalid to use this function for the root node or a node that is not part of a tree. To test for the root node compare with _RBTree_Root() or use _RBTree_Is_root().

Parameters

[in] the_node The node of interest.

Return values