20 #ifndef _RTEMS_RBTREE_H 21 #define _RTEMS_RBTREE_H 87 #define RTEMS_RBTREE_INITIALIZER_EMPTY(name) \ 88 RBTREE_INITIALIZER_EMPTY(name) 93 #define RTEMS_RBTREE_DEFINE_EMPTY(name) \ 94 RBTREE_DEFINE_EMPTY(name) 112 rtems_rbtree_control *the_rbtree,
114 void *starting_address,
126 rtems_rbtree_control *the_rbtree
139 rtems_rbtree_node *node
152 const rtems_rbtree_node *node
164 const rtems_rbtree_control *the_rbtree
174 const rtems_rbtree_control *the_rbtree
184 const rtems_rbtree_control *the_rbtree
196 const rtems_rbtree_node *the_node
208 const rtems_rbtree_node *the_node
218 const rtems_rbtree_node *the_node
231 const rtems_rbtree_control *the_rbtree
244 const rtems_rbtree_control *the_rbtree,
245 const rtems_rbtree_node *the_node
258 const rtems_rbtree_control *the_rbtree,
259 const rtems_rbtree_node *the_node
269 const rtems_rbtree_node *the_node
276 rtems_rbtree_compare_result compare_result
279 return compare_result == 0;
283 rtems_rbtree_compare_result compare_result
286 return compare_result > 0;
290 rtems_rbtree_compare_result compare_result
293 return compare_result < 0;
311 const rtems_rbtree_control *the_rbtree,
312 const rtems_rbtree_node *the_node,
321 const rtems_rbtree_node *node
331 const rtems_rbtree_node *node
341 rtems_rbtree_control *the_rbtree,
342 rtems_rbtree_node *the_node
361 rtems_rbtree_control *the_rbtree
366 if ( the_node !=
NULL ) {
386 rtems_rbtree_control *the_rbtree
391 if ( the_node !=
NULL ) {
406 const rtems_rbtree_control *the_rbtree
420 const rtems_rbtree_control *the_rbtree
443 RBTree_Control *the_rbtree,
RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(const RBTree_Control *the_rbtree)
Is the RBTree empty.
Definition: rbtree.h:353
RBTree_Node rtems_rbtree_node
Definition: rbtree.h:48
RBTree_Node * _RBTree_Maximum(const RBTree_Control *the_rbtree)
Returns the maximum node of the red-black tree.
Definition: rbtreenext.c:41
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_tree(const rtems_rbtree_node *node)
Is the Node off RBTree.
Definition: rbtree.h:151
#define RTEMS_INLINE_ROUTINE
Definition: basedefs.h:65
rtems_rbtree_compare_result(* rtems_rbtree_compare)(const RBTree_Node *first, const RBTree_Node *second)
Compares two red-black tree nodes.
Definition: rbtree.h:79
RTEMS_INLINE_ROUTINE RBTree_Node * _RBTree_Root(const RBTree_Control *the_rbtree)
Returns a pointer to root node of the red-black tree.
Definition: rbtree.h:242
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_predecessor(const rtems_rbtree_node *node)
Returns the predecessor of a node.
Definition: rbtree.h:320
RBTree_Node * _RBTree_Successor(const RBTree_Node *node)
Returns the successor of a node.
Definition: rbtreenext.c:46
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_parent(const rtems_rbtree_node *the_node)
Returns a pointer to the parent of this node.
Definition: rbtree.h:217
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_get_min(rtems_rbtree_control *the_rbtree)
Gets a node with the minimum key value from the red-black tree.
Definition: rbtree.h:360
RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(rtems_rbtree_control *the_rbtree)
Initialize this RBTree as Empty.
Definition: rbtree.h:125
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_successor(const rtems_rbtree_node *node)
Returns the successor of a node.
Definition: rbtree.h:330
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_root(const rtems_rbtree_control *the_rbtree)
Return pointer to RBTree root.
Definition: rbtree.h:163
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_min(const rtems_rbtree_control *the_rbtree)
Returns the minimum node of the red-black tree.
Definition: rbtree.h:173
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_get_max(rtems_rbtree_control *the_rbtree)
Gets a node with the maximal key value from the red-black tree.
Definition: rbtree.h:385
Red-black tree node.
Definition: rbtree.h:50
RBTree_Control rtems_rbtree_control
Definition: rbtree.h:55
RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_tree(rtems_rbtree_node *node)
Set off RBtree.
Definition: rbtree.h:138
rtems_rbtree_node * rtems_rbtree_insert(RBTree_Control *the_rbtree, RBTree_Node *the_node, rtems_rbtree_compare compare, bool is_unique)
Inserts the node into the red-black tree.
Definition: sapirbtreeinsert.c:26
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_peek_min(const rtems_rbtree_control *the_rbtree)
Peek at the min node on a rbtree.
Definition: rbtree.h:405
RTEMS_INLINE_ROUTINE void rtems_rbtree_extract(rtems_rbtree_control *the_rbtree, rtems_rbtree_node *the_node)
Extracts (removes) the node from the red-black tree.
Definition: rbtree.h:340
RTEMS_INLINE_ROUTINE RBTree_Node * _RBTree_Right(const RBTree_Node *the_node)
Return pointer to the right of this node.
Definition: rbtree.h:324
void rtems_rbtree_initialize(rtems_rbtree_control *the_rbtree, rtems_rbtree_compare compare, void *starting_address, size_t number_nodes, size_t node_size, bool is_unique)
Initialize a RBTree header.
Definition: rbtree.c:23
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_empty(const rtems_rbtree_control *the_rbtree)
Is the RBTree empty.
Definition: rbtree.h:230
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(const rtems_rbtree_node *the_node)
Returns true if this node is the root node of a red-black tree, and false otherwise.
Definition: rbtree.h:268
RTEMS_INLINE_ROUTINE RBTree_Node * _RBTree_Parent(const RBTree_Node *the_node)
Returns a pointer to the parent of this node.
Definition: rbtree.h:281
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max(const rtems_rbtree_control *the_rbtree, const rtems_rbtree_node *the_node)
Is this the maximum node on the RBTree.
Definition: rbtree.h:257
Constants and Structures Associated with the Red-Black Tree Handler.
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.
Definition: rbtree.h:99
RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree(RBTree_Node *the_node)
Sets a red-black tree node as off-tree.
Definition: rbtree.h:83
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_peek_max(const rtems_rbtree_control *the_rbtree)
Peek at the max node on a rbtree.
Definition: rbtree.h:419
rtems_rbtree_node * rtems_rbtree_find(const rtems_rbtree_control *the_rbtree, const rtems_rbtree_node *the_node, rtems_rbtree_compare compare, bool is_unique)
Tries to find a node for the specified key in the tree.
Definition: rbtreefind.c:22
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_left(const rtems_rbtree_node *the_node)
Return pointer to the left child node from this node.
Definition: rbtree.h:195
long rtems_rbtree_compare_result
Integer type for compare results.
Definition: rbtree.h:64
RBTree_Node * _RBTree_Minimum(const RBTree_Control *the_rbtree)
Returns the minimum node of the red-black tree.
Definition: rbtreenext.c:36
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_min(const rtems_rbtree_control *the_rbtree, const rtems_rbtree_node *the_node)
Is this the minimum node on the RBTree.
Definition: rbtree.h:243
RTEMS_INLINE_ROUTINE RBTree_Node * _RBTree_Left(const RBTree_Node *the_node)
Return pointer to the left of this node.
Definition: rbtree.h:297
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_right(const rtems_rbtree_node *the_node)
Return pointer to the right child node from this node.
Definition: rbtree.h:207
void _RBTree_Extract(RBTree_Control *the_rbtree, RBTree_Node *the_node)
Extracts (removes) the node from the red-black tree.
Definition: rbtreeextract.c:35
RBTree_Node * _RBTree_Predecessor(const RBTree_Node *node)
Returns the predecessor of a node.
Definition: rbtreenext.c:51
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.
Definition: rbtree.h:375
RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(RBTree_Control *the_rbtree)
Initialize this RBTree as empty.
Definition: rbtree.h:387
RTEMS_INLINE_ROUTINE rtems_rbtree_node * rtems_rbtree_max(const rtems_rbtree_control *the_rbtree)
Returns the maximum node of the red-black tree.
Definition: rbtree.h:183
#define NULL
Requests a GPIO pin group configuration.
Definition: bestcomm_api.h:77