RTEMS  5.0.0
Data Structures | Macros | Typedefs | Functions
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)
 Returns true, if this red-black tree node is off-tree, and false otherwise. 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.
 
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.
 
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_Left_reference (RBTree_Node *the_node)
 Returns a reference to the left child pointer of the red-black tree node.
 
RTEMS_INLINE_ROUTINE RBTree_Node_RBTree_Right (const RBTree_Node *the_node)
 Return 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.
 
RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty (const RBTree_Control *the_rbtree)
 Is the RBTree empty. 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 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.