Constants and Structures Associated with the Red-Black Tree Handler. More...
Include dependency graph for rbtree.h:
This graph shows which files directly or indirectly include this file:
Go to the source code of this file.
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... | |
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... | |
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.
