18 #ifndef _RTEMS_SCORE_RBTREE_H 19 #define _RTEMS_SCORE_RBTREE_H 23 #include <rtems/score/assert.h> 42 struct RBTree_Control;
65 #define RBTREE_INITIALIZER_EMPTY( name ) \ 66 RB_INITIALIZER( name ) 71 #define RBTREE_DEFINE_EMPTY( name ) \ 72 RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name ) 85 RB_COLOR( the_node, Node ) = -1;
103 return RB_COLOR( the_node, Node ) == -1;
113 RBTree_Control *the_rbtree,
127 #if defined(RTEMS_DEBUG) 148 RB_SET( child, parent, Node );
203 RBTree_Control *the_rbtree,
226 RBTree_Control *the_rbtree,
243 const RBTree_Control *the_rbtree
246 return RB_ROOT( the_rbtree );
253 RBTree_Control *the_rbtree
256 return &RB_ROOT( the_rbtree );
263 const RBTree_Control *the_rbtree
266 return &RB_ROOT( the_rbtree );
285 return RB_PARENT( the_node, Node );
301 return RB_LEFT( the_node, Node );
312 return &RB_LEFT( the_node, Node );
328 return RB_RIGHT( the_node, Node );
339 return &RB_RIGHT( the_node, Node );
354 const RBTree_Control *the_rbtree
357 return RB_EMPTY( the_rbtree );
388 RBTree_Control *the_rbtree
391 RB_INIT( the_rbtree );
402 RBTree_Control *the_rbtree,
407 RB_ROOT( the_rbtree ) = the_node;
408 RB_PARENT( the_node, Node ) =
NULL;
409 RB_LEFT( the_node, Node ) =
NULL;
410 RB_RIGHT( the_node, Node ) =
NULL;
411 RB_COLOR( the_node, Node ) = RB_BLACK;
461 RBTree_Control *the_rbtree,
484 RBTree_Control *the_rbtree,
487 bool ( *less )(
const void *,
const RBTree_Node * )
496 is_new_minimum =
true;
498 while ( *link !=
NULL ) {
501 if ( ( *less )( key, parent ) ) {
505 is_new_minimum =
false;
511 return is_new_minimum;
533 const RBTree_Control *the_rbtree,
535 bool ( *equal )(
const void *,
const RBTree_Node * ),
536 bool ( *less )(
const void *,
const RBTree_Node * ),
546 while ( *link !=
NULL ) {
549 if ( ( *equal )( key, parent ) ) {
550 return ( *
map )( parent );
551 }
else if ( ( *less )( key, parent ) ) {
607 const RBTree_Control *the_rbtree,
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.
Definition: rbtree.h:483
RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(const RBTree_Control *the_rbtree)
Is the RBTree empty.
Definition: rbtree.h:353
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.
Definition: rbtree.h:401
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 RBTree_Node ** _RBTree_Left_reference(RBTree_Node *the_node)
Returns a reference to the left child pointer of the red-black tree node.
Definition: rbtree.h:308
struct RBTree_Node RBTree_Node
Red-black tree node.
#define RTEMS_INLINE_ROUTINE
Definition: basedefs.h:65
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
RBTree_Node * _RBTree_Successor(const RBTree_Node *node)
Returns the successor of a node.
Definition: rbtreenext.c:46
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.
Definition: rbtreereplace.c:29
Red-black tree node.
Definition: rbtree.h:50
RTEMS_INLINE_ROUTINE void _RBTree_Initialize_node(RBTree_Node *the_node)
Initializes a red-black tree node.
Definition: rbtree.h:125
RTEMS_INLINE_ROUTINE RBTree_Node ** _RBTree_Root_reference(RBTree_Control *the_rbtree)
Returns a reference to the root pointer of the red-black tree.
Definition: rbtree.h:252
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.
Definition: rbtree.h:532
void _RBTree_Insert_color(RBTree_Control *the_rbtree, RBTree_Node *the_node)
Rebalances the red-black tree after insertion of the node.
Definition: rbtreeinsert.c:17
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.
Definition: rbtree.h:262
RTEMS_INLINE_ROUTINE RBTree_Node * _RBTree_Right(const RBTree_Node *the_node)
Return pointer to the right of this node.
Definition: rbtree.h:324
int link(const char *path1, const char *path2)
Definition: link.c:28
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
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.
Definition: rbtreepostorder.c:68
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
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 void _RBTree_Add_child(RBTree_Node *child, RBTree_Node *parent, RBTree_Node **link)
Adds a child node to a parent node.
Definition: rbtree.h:141
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.
Definition: rbtree.h:335
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 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.
Definition: rbtree.h:202
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
void * _RBTree_Postorder_next(const RBTree_Node *the_node, size_t offset)
Returns the container of the next node in postorder.
Definition: rbtreepostorder.c:46
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
typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control
Red-black tree control.
#define NULL
Requests a GPIO pin group configuration.
Definition: bestcomm_api.h:77