RTEMS
5.0.0
|
Constants and Structures Associated with the Red-Black Tree Handler. More...
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... | |
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.