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

Collaboration diagram for Red-Black Tree Handler:

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...
Defines
#define	_RBTree_Container_of(node, container_type, node_field_name)
	Macro to return the structure containing the node.
#define	RBTREE_INITIALIZER_EMPTY(name)
	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)
	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.
typedef int(*	RBTree_Compare_function )(const RBTree_Node node1, const RBTree_Node node2)
	This type defines function pointers for user-provided comparison function.
typedef bool(*	RBTree_Visitor )(const RBTree_Node node, RBTree_Direction dir, void visitor_arg)
	Red-black tree visitor.
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_function compare_function, void starting_address, size_t number_nodes, size_t node_size, bool is_unique)
	Initialize a RBTree Header.
RBTree_Node *	_RBTree_Get (RBTree_Control *the_rbtree, RBTree_Direction dir)
	Obtain the min or max node of a rbtree.
RBTree_Node *	_RBTree_Find_unprotected (const RBTree_Control the_rbtree, const RBTree_Node the_node)
	Find the node with given key in the tree.
RBTree_Node *	_RBTree_Find (const RBTree_Control the_rbtree, const RBTree_Node the_node)
	Find the node with given key in the tree.
RBTree_Control *	_RBTree_Find_header (RBTree_Node *the_node)
	Find the control structure of the tree containing the given node.
RBTree_Node *	_RBTree_Insert_unprotected (RBTree_Control the_rbtree, RBTree_Node the_node)
	Insert the_node on the Red-Black Tree the_rbtree (unprotected).
RBTree_Node *	_RBTree_Insert (RBTree_Control the_rbtree, RBTree_Node the_node)
	Insert a node on a rbtree.
void	_RBTree_Extract_unprotected (RBTree_Control the_rbtree, RBTree_Node the_node)
	Extracts (removes) the_node from the_rbtree (unprotected).
void	_RBTree_Extract (RBTree_Control the_rbtree, RBTree_Node the_node)
	Delete a node from the rbtree.
RBTree_Node *	_RBTree_Next_unprotected (const RBTree_Node *node, RBTree_Direction dir)
	Returns the in-order next node of a node.
RBTree_Node *	_RBTree_Next (const RBTree_Node *node, RBTree_Direction dir)
void	_RBTree_Iterate_unprotected (const RBTree_Control rbtree, RBTree_Direction dir, RBTree_Visitor visitor, void visitor_arg)
	Red-black tree iteration.
RTEMS_INLINE_ROUTINE RBTree_Direction	_RBTree_Opposite_direction (RBTree_Direction the_dir)
	Get the direction opposite to the_dir.
RTEMS_INLINE_ROUTINE void	_RBTree_Set_off_rbtree (RBTree_Node *node)
	Set off RBtree.
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_node_off_rbtree (const RBTree_Node *node)
	Is the node off RBTree.
RTEMS_INLINE_ROUTINE bool	_RBTree_Are_nodes_equal (const RBTree_Node left, const RBTree_Node right)
	Are two Nodes equal.
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_null (const RBTree_Control *the_rbtree)
	Is this RBTree control pointer NULL.
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_null_node (const RBTree_Node *the_node)
	Is the RBTree node pointer NUL.
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Root (const RBTree_Control *the_rbtree)
	Return pointer to RBTree's root node.
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_First (const RBTree_Control *the_rbtree, RBTree_Direction dir)
	Return pointer to RBTree's first node.
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Parent (const RBTree_Node *the_node)
	Return pointer to the parent of this node.
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Left (const RBTree_Node *the_node)
	Return pointer to the left of this node.
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Right (const RBTree_Node *the_node)
	Return pointer to the right of this node.
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_empty (const RBTree_Control *the_rbtree)
	Is the RBTree empty.
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.
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_red (const RBTree_Node *the_node)
	Is this node red.
RTEMS_INLINE_ROUTINE bool	_RBTree_Has_only_one_node (const RBTree_Control *the_rbtree)
	Does this RBTree have only one node.
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_root (const RBTree_Control the_rbtree, const RBTree_Node the_node)
	Is this node the RBTree root.
RTEMS_INLINE_ROUTINE void	_RBTree_Initialize_empty (RBTree_Control *the_rbtree, RBTree_Compare_function compare_function, bool is_unique)
	Initialize this RBTree as empty.
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Grandparent (const RBTree_Node *the_node)
	Return a pointer to node's grandparent.
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Sibling (const RBTree_Node *the_node)
	Return a pointer to node's sibling.
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Parent_sibling (const RBTree_Node *the_node)
	Return a pointer to node's parent's sibling.
RTEMS_INLINE_ROUTINE RBTree_Control *	_RBTree_Find_header_unprotected (RBTree_Node *the_node)
	Find the RBTree_Control header given a node in the tree.
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_equal (int compare_result)
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_greater (int compare_result)
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_lesser (int compare_result)
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Predecessor_unprotected (const RBTree_Node *node)
	Returns the predecessor of a node.
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Predecessor (const RBTree_Node *node)
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Successor_unprotected (const RBTree_Node *node)
	Returns the successor of a node.
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Successor (const RBTree_Node *node)
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Get_unprotected (RBTree_Control *the_rbtree, RBTree_Direction dir)
	Get the first node (unprotected).
RTEMS_INLINE_ROUTINE void	_RBTree_Rotate (RBTree_Node *the_node, RBTree_Direction dir)
	Rotate the_node in the direction passed as second argument.
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_unique (const RBTree_Control *the_rbtree)
	Determines whether the tree is unique.

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.

Define Documentation

#define _RBTree_Container_of	(	node,
		container_type,
		node_field_name
	)

Value:

( \
  (container_type*) \
    ( (uintptr_t)(node) - offsetof(container_type, node_field_name) ) \
)

Macro to return the structure containing the node.

This macro returns a pointer of type container_type that points to the structure containing node, where node_field_name is the field name of the RBTree_Node structure in container_type.

#define RBTREE_INITIALIZER_EMPTY ( name )

Value:

{ \
  .permanent_null = NULL, \
  .root = NULL, \
  .first[0] = NULL, \
  .first[1] = NULL, \
  .compare_function = NULL, \
  .is_unique = 0 \
}

RBTree initializer for an empty rbtree with designator name.

#define RBTREE_NODE_INITIALIZER_EMPTY ( name )

Value:

{ \
  .parent = NULL, \
  .child[0] = NULL, \
  .child[1] = NULL, \
  RBT_RED \
}

RBTree_Node initializer for an empty node with designator name.

Typedef Documentation

typedef int(* RBTree_Compare_function)(const RBTree_Node *node1, const RBTree_Node *node2)

This type defines function pointers for user-provided comparison function.

The function compares two nodes in order to determine the order in a red-black tree.

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.

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_unprotected().

Function Documentation

RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal	(	const RBTree_Node *	left,
		const RBTree_Node *	right
	)

Are two Nodes equal.

This function returns true if left and right are equal, and false otherwise.

Return values:

true	left and right are equal.
false	left and right are not equal.

Referenced by rtems_rbtree_are_nodes_equal().

void _RBTree_Extract	(	RBTree_Control *	the_rbtree,
		RBTree_Node *	the_node
	)

Delete a node from the rbtree.

This routine deletes the_node from the_rbtree.

Note:: It disables interrupts to ensure the atomicity of the append operation.

Referenced by rtems_rbtree_extract().

void _RBTree_Extract_unprotected	(	RBTree_Control *	the_rbtree,
		RBTree_Node *	the_node
	)

Extracts (removes) the_node from the_rbtree (unprotected).

This routine extracts (removes) the_node from the_rbtree.

Note:: It does NOT disable interrupts to ensure the atomicity of the extract operation.

Referenced by rtems_rbtree_extract_unprotected(), and _RBTree_Get_unprotected().

RBTree_Node* _RBTree_Find	(	const RBTree_Control *	the_rbtree,
		const RBTree_Node *	the_node
	)

Find the node with given key in the tree.

This function returns a pointer to the node with key equal to a key of the_node if it exists in the Red-Black Tree the_rbtree, and NULL if not.

Parameters:

[in]	the_rbtree	pointer to rbtree control
[in]	the_node	node with the key to search for

Return values:

This	method returns pointer to control header of rbtree. * If there is no control header available (the node is not part of a tree), then NULL is returned. *

INTERRUPT LATENCY: + single case

Referenced by rtems_rbtree_find().

RBTree_Control* _RBTree_Find_header ( RBTree_Node * the_node )

Find the control structure of the tree containing the given node.

This function returns a pointer called return_header to the control structure of the tree containing the_node, if it exists, and NULL if not.

Parameters:

[in] the_node is the pointer to the rbtree node.

-INTERRUPT LATENCY: + single case

Referenced by rtems_rbtree_find_header().

RTEMS_INLINE_ROUTINE RBTree_Control* _RBTree_Find_header_unprotected ( RBTree_Node * the_node )

Find the RBTree_Control header given a node in the tree.

This function returns a pointer to the header of the Red Black Tree containing the_node if it exists, and NULL if not.

References RBTree_Node_struct::parent.

Referenced by rtems_rbtree_find_header_unprotected().

RBTree_Node* _RBTree_Find_unprotected	(	const RBTree_Control *	the_rbtree,
		const RBTree_Node *	the_node
	)

Find the node with given key in the tree.

This function returns a pointer to the node in the_rbtree having key equal to key of the_node if it exists, and NULL if not. the_node has to be made up before a search.

Note:: If the tree is not unique and contains duplicate keys, the set of duplicate keys acts as FIFO.

Referenced by rtems_rbtree_find_unprotected().

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 rtems_rbtree_min(), rtems_rbtree_max(), rtems_rbtree_peek_min(), rtems_rbtree_peek_max(), and _RBTree_Is_first().

RBTree_Node* _RBTree_Get	(	RBTree_Control *	the_rbtree,
		RBTree_Direction	dir
	)

Obtain the min or max node of a rbtree.

This function removes the min or max node from the_rbtree and returns a pointer to that node. If the_rbtree is empty, then NULL is returned. dir specifies whether to return the min (0) or max (1).

Return values:

This	method returns a pointer to a node. If a node was removed, then a pointer to that node is returned. If the_rbtree was empty, then NULL is returned.

Note:: It disables interrupts to ensure the atomicity of the get operation.

Referenced by rtems_rbtree_get_min(), and rtems_rbtree_get_max().

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

Get the first node (unprotected).

This function removes the minimum or maximum node from the_rbtree and returns a pointer to that node. It does NOT disable interrupts to ensure the atomicity of the get operation.

Parameters:

[in]	the_rbtree	is the rbtree to attempt to get the min node from.
[in]	dir	specifies whether to get minimum (0) or maximum (1)

Returns:: This method returns the min or max node on the rbtree, or NULL.

Note:: This routine may return NULL if the RBTree is empty.

References RBTree_Control::first, and _RBTree_Extract_unprotected().

Referenced by rtems_rbtree_get_min_unprotected(), and rtems_rbtree_get_max_unprotected().

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Grandparent ( const RBTree_Node * the_node )

Return a pointer to node's grandparent.

This function returns a pointer to the grandparent of the_node if it exists, and NULL if not.

References RBTree_Node_struct::parent.

Referenced by _RBTree_Parent_sibling().

RTEMS_INLINE_ROUTINE bool _RBTree_Has_only_one_node ( const RBTree_Control * the_rbtree )

Does this RBTree have only one node.

This function returns true if there is only one node on the_rbtree and false otherwise.

Return values:

true	the_rbtree has only one node.
false	the_rbtree has more than one nodes.

References RBTree_Control::root, and RBTree_Node_struct::child.

Referenced by rtems_rbtree_has_only_one_node().

void _RBTree_Initialize	(	RBTree_Control *	the_rbtree,
		RBTree_Compare_function	compare_function,
		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]	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

Referenced by rtems_rbtree_initialize().

RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty	(	RBTree_Control *	the_rbtree,
		RBTree_Compare_function	compare_function,
		bool	is_unique
	)

Initialize this RBTree as empty.

This routine initializes the_rbtree to contain zero nodes.

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

Referenced by rtems_rbtree_initialize_empty().

RBTree_Node* _RBTree_Insert	(	RBTree_Control *	the_rbtree,
		RBTree_Node *	the_node
	)

Insert a node on a rbtree.

This routine inserts the_node on the tree the_rbtree.

Return values:

0	Successfully inserted.
-1	NULL the_node.
RBTree_Node*	if one with equal value to the_node 's key exists in an unique the_rbtree.

Note:: It disables interrupts to ensure the atomicity of the extract operation.

Referenced by rtems_rbtree_insert().

RBTree_Node* _RBTree_Insert_unprotected	(	RBTree_Control *	the_rbtree,
		RBTree_Node *	the_node
	)

Insert the_node on the Red-Black Tree the_rbtree (unprotected).

This routine inserts the_node on the Red-Black Tree the_rbtree.

Return values:

0	Successfully inserted.
-1	NULL the_node.
RBTree_Node*	if one with equal value to the_node 's key exists in an unique the_rbtree.

Note:: It does NOT disable interrupts to ensure the atomicity of the extract operation.

Referenced by rtems_rbtree_insert_unprotected().

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

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_min(), and rtems_rbtree_is_max().

RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree ( const RBTree_Node * node )

Is the node off RBTree.

This function returns true if the node is not on a rbtree. A node is off rbtree if the parent and child fields are set to NULL.

References RBTree_Node_struct::parent, and RBTree_Node_struct::child.

Referenced by rtems_rbtree_is_node_off_rbtree().

RTEMS_INLINE_ROUTINE bool _RBTree_Is_null ( const RBTree_Control * the_rbtree )

Is this RBTree control pointer NULL.

This function returns true if the_rbtree is NULL and false otherwise.

Return values:

true	the_rbtree is `NULL`.
false	the_rbtree is not `NULL`.

RTEMS_INLINE_ROUTINE bool _RBTree_Is_null_node ( const RBTree_Node * the_node )

Is the RBTree node pointer NUL.

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

Return values:

true	the_node is `NULL`.
false	the_node is not `NULL`.

Referenced by rtems_rbtree_is_null_node().

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.

RTEMS_INLINE_ROUTINE bool _RBTree_Is_root	(	const RBTree_Control *	the_rbtree,
		const RBTree_Node *	the_node
	)

Is this node the RBTree root.

This function returns true if the_node is the root of the_rbtree and false otherwise.

Return values:

true	the_node is the root of the_rbtree.
false	the_node is not the root of the_rbtree.

References _RBTree_Root().

Referenced by rtems_rbtree_is_root().

void _RBTree_Iterate_unprotected	(	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.

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

The function disables the interrupts protect the operation.

Referenced by _RBTree_Predecessor(), and _RBTree_Successor().

RBTree_Node* _RBTree_Next_unprotected	(	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.

Referenced by _RBTree_Predecessor_unprotected(), and _RBTree_Successor_unprotected().

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Parent ( const RBTree_Node * the_node )

Return pointer to the parent of this node.

This function returns a pointer to the parent node of the_node.

References RBTree_Node_struct::parent.

Referenced by rtems_rbtree_parent().

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Parent_sibling ( const RBTree_Node * the_node )

Return a pointer to node's parent's sibling.

This function returns a pointer to the sibling of the parent of the_node if it exists, and NULL if not.

References _RBTree_Grandparent(), _RBTree_Sibling(), and RBTree_Node_struct::parent.

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Predecessor ( const RBTree_Node * node )

Returns the predecessor of a node.

Parameters:

[in] node is the node.

Return values:

NULL	The predecessor does not exist. Otherwise it returns the predecessor node.

The function disables the interrupts protect the operation.

References _RBTree_Next().

Referenced by rtems_rbtree_predecessor().

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Predecessor_unprotected ( const RBTree_Node * node )

Returns the predecessor of a node.

Parameters:

[in] node is the node.

Return values:

NULL	The predecessor does not exist. Otherwise it returns the predecessor node.

References _RBTree_Next_unprotected().

Referenced by rtems_rbtree_predecessor_unprotected().

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Right ( const RBTree_Node * the_node )

Return pointer to the right of this node.

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

Parameters:

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

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

References RBTree_Node_struct::child.

Referenced by rtems_rbtree_right().

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Root ( const RBTree_Control * the_rbtree )

Return pointer to RBTree's root node.

This function returns a pointer to the root node of the_rbtree.

References RBTree_Control::root.

Referenced by rtems_rbtree_root(), and _RBTree_Is_root().

RTEMS_INLINE_ROUTINE void _RBTree_Rotate	(	RBTree_Node *	the_node,
		RBTree_Direction	dir
	)

Rotate the_node in the direction passed as second argument.

This routine rotates the_node to the direction dir, swapping the_node with its child\[dir\].

References RBTree_Node_struct::child, _RBTree_Opposite_direction(), and RBTree_Node_struct::parent.

RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree ( RBTree_Node * node )

Set off RBtree.

This function sets the parent and child fields of the node to NULL indicating the node is not part of a rbtree.

References RBTree_Node_struct::parent, and RBTree_Node_struct::child.

Referenced by rtems_rbtree_set_off_rbtree().

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Sibling ( const RBTree_Node * the_node )

Return a pointer to node's sibling.

This function returns a pointer to the sibling of the_node if it exists, and NULL if not.

References RBTree_Node_struct::parent, and RBTree_Node_struct::child.

Referenced by _RBTree_Parent_sibling().

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Successor ( const RBTree_Node * node )

Returns the successor of a node.

Parameters:

[in] node is the node.

Return values:

NULL	The successor does not exist. Otherwise the successor node.

The function disables the interrupts protect the operation.

References _RBTree_Next().

Referenced by rtems_rbtree_successor().

RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Successor_unprotected ( const RBTree_Node * node )

Returns the successor of a node.

Parameters:

[in] node is the node.

Return values:

NULL	The successor does not exist. Otherwise the successor node.

References _RBTree_Next_unprotected().

Referenced by rtems_rbtree_successor_unprotected().

Data Structures

Defines

Typedefs

Enumerations

Functions

Detailed Description

Define Documentation

Typedef Documentation

Function Documentation