rbtree.h File Reference

Constants and Structures Associated with the Red-Black Tree Handler. More...

#include <sys/tree.h>
#include <rtems/score/basedefs.h>
#include <rtems/score/assert.h>

Go to the source code of this file.

Data Structures
struct	RBTree_Node
	Red-black tree node. More...

Macros
#define	RBTREE_INITIALIZER_EMPTY(name)   RB_INITIALIZER( name )
	Initializer for an empty red-black tree with designator name.
#define	RBTREE_DEFINE_EMPTY(name)   RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
	Definition for an empty red-black tree with designator name.

Typedefs
typedef struct RBTree_Node	RBTree_Node
	Red-black tree node. More...

Functions
typedef	RB_HEAD (RBTree_Control, RBTree_Node) RBTree_Control
	Red-black tree control. 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)
	Checks if this red-black tree node is off-tree. More...
void	_RBTree_Insert_color (RBTree_Control *the_rbtree, RBTree_Node *the_node)
	Rebalances the red-black tree after insertion of the node. More...
RTEMS_INLINE_ROUTINE void	_RBTree_Initialize_node (RBTree_Node *the_node)
	Initializes a red-black tree node. More...
RTEMS_INLINE_ROUTINE void	_RBTree_Add_child (RBTree_Node *child, RBTree_Node *parent, RBTree_Node **link)
	Adds a child node to a parent node. More...
RTEMS_INLINE_ROUTINE void	_RBTree_Insert_with_parent (RBTree_Control *the_rbtree, RBTree_Node *the_node, RBTree_Node *parent, RBTree_Node **link)
	Inserts the node into the red-black tree using the specified parent node and link. More...
void	_RBTree_Extract (RBTree_Control *the_rbtree, RBTree_Node *the_node)
	Extracts (removes) the node from the red-black tree. 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_Root_reference (RBTree_Control *the_rbtree)
	Returns a reference to the root pointer of the red-black tree. More...
RTEMS_INLINE_ROUTINE RBTree_Node *const *	_RBTree_Root_const_reference (const RBTree_Control *the_rbtree)
	Returns a constant reference to the root pointer of the red-black tree. 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)
	Returns pointer to the left of this node. More...
RTEMS_INLINE_ROUTINE RBTree_Node **	_RBTree_Left_reference (RBTree_Node *the_node)
	Returns a reference to the left child pointer of the red-black tree node. More...
RTEMS_INLINE_ROUTINE RBTree_Node *	_RBTree_Right (const RBTree_Node *the_node)
	Returns pointer to the right of this node. More...
RTEMS_INLINE_ROUTINE RBTree_Node **	_RBTree_Right_reference (RBTree_Node *the_node)
	Returns a reference to the right child pointer of the red-black tree node. More...
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_empty (const RBTree_Control *the_rbtree)
	Checks if the RBTree is empty. More...
RTEMS_INLINE_ROUTINE bool	_RBTree_Is_root (const RBTree_Node *the_node)
	Checks if this node is the root node of a red-black tree. More...
RTEMS_INLINE_ROUTINE void	_RBTree_Initialize_empty (RBTree_Control *the_rbtree)
	Initializes this RBTree as empty. More...
RTEMS_INLINE_ROUTINE void	_RBTree_Initialize_one (RBTree_Control *the_rbtree, RBTree_Node *the_node)
	Initializes this red-black tree to contain exactly the specified node. More...
RBTree_Node *	_RBTree_Minimum (const RBTree_Control *the_rbtree)
	Returns the minimum node of the red-black tree. More...
RBTree_Node *	_RBTree_Maximum (const RBTree_Control *the_rbtree)
	Returns the maximum node of the red-black tree. More...
RBTree_Node *	_RBTree_Predecessor (const RBTree_Node *node)
	Returns the predecessor of a node. More...
RBTree_Node *	_RBTree_Successor (const RBTree_Node *node)
	Returns the successor of a node. More...
void	_RBTree_Replace_node (RBTree_Control *the_rbtree, RBTree_Node *victim, RBTree_Node *replacement)
	Replaces a node in the red-black tree without a rebalance. More...
RTEMS_INLINE_ROUTINE bool	_RBTree_Insert_inline (RBTree_Control *the_rbtree, RBTree_Node *the_node, const void *key, bool(*less)(const void *, const RBTree_Node *))
	Inserts the node into the red-black tree. More...
RTEMS_INLINE_ROUTINE void *	_RBTree_Find_inline (const RBTree_Control *the_rbtree, const void *key, bool(*equal)(const void *, const RBTree_Node *), bool(*less)(const void *, const RBTree_Node *), void *(*map)(RBTree_Node *))
	Finds an object in the red-black tree with the specified key. More...
void *	_RBTree_Postorder_first (const RBTree_Control *the_rbtree, size_t offset)
	Returns the container of the first node of the specified red-black tree in postorder. More...
void *	_RBTree_Postorder_next (const RBTree_Node *the_node, size_t offset)
	Returns the container of the next node in postorder. More...

Detailed Description

Constants and Structures Associated with the Red-Black Tree Handler.

This include file contains all the constants and structures associated with the Red-Black Tree Handler.