RTEMS  5.0.0
rbtree.h
Go to the documentation of this file.
1 
10 /*
11  * Copyright (c) 2010 Gedare Bloom.
12  *
13  * The license and distribution terms for this file may be
14  * found in the file LICENSE in this distribution or at
15  * http://www.rtems.org/license/LICENSE.
16  */
17 
18 #ifndef _RTEMS_SCORE_RBTREE_H
19 #define _RTEMS_SCORE_RBTREE_H
20 
21 #include <sys/tree.h>
22 #include <rtems/score/basedefs.h>
23 #include <rtems/score/assert.h>
24 
25 #ifdef __cplusplus
26 extern "C" {
27 #endif
28 
42 struct RBTree_Control;
43 
50 typedef struct RBTree_Node {
51  RB_ENTRY(RBTree_Node) Node;
52 } RBTree_Node;
53 
60 typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control;
61 
65 #define RBTREE_INITIALIZER_EMPTY( name ) \
66  RB_INITIALIZER( name )
67 
71 #define RBTREE_DEFINE_EMPTY( name ) \
72  RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
73 
84 {
85  RB_COLOR( the_node, Node ) = -1;
86 }
87 
100  const RBTree_Node *the_node
101 )
102 {
103  return RB_COLOR( the_node, Node ) == -1;
104 }
105 
113  RBTree_Control *the_rbtree,
114  RBTree_Node *the_node
115 );
116 
126 {
127 #if defined(RTEMS_DEBUG)
128  _RBTree_Set_off_tree( the_node );
129 #else
130  (void) the_node;
131 #endif
132 }
133 
142  RBTree_Node *child,
143  RBTree_Node *parent,
144  RBTree_Node **link
145 )
146 {
147  _Assert( _RBTree_Is_node_off_tree( child ) );
148  RB_SET( child, parent, Node );
149  *link = child;
150 }
151 
203  RBTree_Control *the_rbtree,
204  RBTree_Node *the_node,
205  RBTree_Node *parent,
206  RBTree_Node **link
207 )
208 {
209  _RBTree_Add_child( the_node, parent, link );
210  _RBTree_Insert_color( the_rbtree, the_node );
211 }
212 
225 void _RBTree_Extract(
226  RBTree_Control *the_rbtree,
227  RBTree_Node *the_node
228 );
229 
243  const RBTree_Control *the_rbtree
244 )
245 {
246  return RB_ROOT( the_rbtree );
247 }
248 
253  RBTree_Control *the_rbtree
254 )
255 {
256  return &RB_ROOT( the_rbtree );
257 }
258 
263  const RBTree_Control *the_rbtree
264 )
265 {
266  return &RB_ROOT( the_rbtree );
267 }
268 
282  const RBTree_Node *the_node
283 )
284 {
285  return RB_PARENT( the_node, Node );
286 }
287 
298  const RBTree_Node *the_node
299 )
300 {
301  return RB_LEFT( the_node, Node );
302 }
303 
309  RBTree_Node *the_node
310 )
311 {
312  return &RB_LEFT( the_node, Node );
313 }
314 
325  const RBTree_Node *the_node
326 )
327 {
328  return RB_RIGHT( the_node, Node );
329 }
330 
336  RBTree_Node *the_node
337 )
338 {
339  return &RB_RIGHT( the_node, Node );
340 }
341 
354  const RBTree_Control *the_rbtree
355 )
356 {
357  return RB_EMPTY( the_rbtree );
358 }
359 
376  const RBTree_Node *the_node
377 )
378 {
379  return _RBTree_Parent( the_node ) == NULL;
380 }
381 
388  RBTree_Control *the_rbtree
389 )
390 {
391  RB_INIT( the_rbtree );
392 }
393 
402  RBTree_Control *the_rbtree,
403  RBTree_Node *the_node
404 )
405 {
406  _Assert( _RBTree_Is_node_off_tree( the_node ) );
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;
412 }
413 
422 RBTree_Node *_RBTree_Minimum( const RBTree_Control *the_rbtree );
423 
432 RBTree_Node *_RBTree_Maximum( const RBTree_Control *the_rbtree );
433 
443 
452 
461  RBTree_Control *the_rbtree,
462  RBTree_Node *victim,
463  RBTree_Node *replacement
464 );
465 
484  RBTree_Control *the_rbtree,
485  RBTree_Node *the_node,
486  const void *key,
487  bool ( *less )( const void *, const RBTree_Node * )
488 )
489 {
490  RBTree_Node **link;
491  RBTree_Node *parent;
492  bool is_new_minimum;
493 
494  link = _RBTree_Root_reference( the_rbtree );
495  parent = NULL;
496  is_new_minimum = true;
497 
498  while ( *link != NULL ) {
499  parent = *link;
500 
501  if ( ( *less )( key, parent ) ) {
502  link = _RBTree_Left_reference( parent );
503  } else {
504  link = _RBTree_Right_reference( parent );
505  is_new_minimum = false;
506  }
507  }
508 
509  _RBTree_Add_child( the_node, parent, link );
510  _RBTree_Insert_color( the_rbtree, the_node );
511  return is_new_minimum;
512 }
513 
533  const RBTree_Control *the_rbtree,
534  const void *key,
535  bool ( *equal )( const void *, const RBTree_Node * ),
536  bool ( *less )( const void *, const RBTree_Node * ),
537  void *( *map )( RBTree_Node * )
538 )
539 {
540  RBTree_Node * const *link;
541  RBTree_Node *parent;
542 
543  link = _RBTree_Root_const_reference( the_rbtree );
544  parent = NULL;
545 
546  while ( *link != NULL ) {
547  parent = *link;
548 
549  if ( ( *equal )( key, parent ) ) {
550  return ( *map )( parent );
551  } else if ( ( *less )( key, parent ) ) {
552  link = _RBTree_Left_reference( parent );
553  } else {
554  link = _RBTree_Right_reference( parent );
555  }
556  }
557 
558  return NULL;
559 }
560 
607  const RBTree_Control *the_rbtree,
608  size_t offset
609 );
610 
623  const RBTree_Node *the_node,
624  size_t offset
625 );
626 
629 #ifdef __cplusplus
630 }
631 #endif
632 
633 #endif
634 /* end of include file */
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
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
Basic Definitions.
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
Definition: mm.c:60
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