diff options
Diffstat (limited to 'cpukit/score/include/rtems/score/rbtree.h')
-rw-r--r-- | cpukit/score/include/rtems/score/rbtree.h | 277 |
1 files changed, 143 insertions, 134 deletions
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h index b44c09edb5..077f2b181d 100644 --- a/cpukit/score/include/rtems/score/rbtree.h +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -18,9 +18,8 @@ #ifndef _RTEMS_SCORE_RBTREE_H #define _RTEMS_SCORE_RBTREE_H -#include <stddef.h> - -#include <rtems/score/address.h> +#include <sys/tree.h> +#include <rtems/score/basedefs.h> #ifdef __cplusplus extern "C" { @@ -40,54 +39,22 @@ extern "C" { /**@{*/ /** - * @typedef RBTree_Node + * @brief Red-black tree node. * - * This type definition promotes the name for the RBTree Node used by - * all RTEMS code. It is a separate type definition because a forward - * reference is required to define it. See @ref RBTree_Node_struct for - * detailed information. + * This is used to manage each node (element) which is placed on a red-black + * tree. */ -typedef struct RBTree_Node_struct RBTree_Node; +typedef struct RBTree_Node { + RB_ENTRY(RBTree_Node) Node; +} RBTree_Node; /** - * This enum type defines the colors available for the RBTree Nodes - */ -typedef enum { - RBT_BLACK, - RBT_RED -} RBTree_Color; - -/** - * @struct RBTree_Node_struct - * - * This is used to manage each element (node) which is placed - * on a RBT. - * - * @note Typically, a more complicated structure will use the - * rbtree package. The more complicated structure will - * include a rbtree node as the first element in its - * control structure. It will then call the rbtree package - * with a pointer to that node element. The node pointer - * and the higher level structure start at the same address - * so the user can cast the pointers back and forth. + * @brief Red-black tree control. * + * This is used to manage a red-black tree. A red-black tree consists of a + * tree of zero or more nodes. */ -struct RBTree_Node_struct { - /** This points to the node's parent */ - RBTree_Node *parent; - /** child[0] points to the left child, child[1] points to the right child */ - RBTree_Node *child[2]; - /** The color of the node. Either red or black */ - RBTree_Color color; -}; - -/** - * This type indicates the direction. - */ -typedef enum { - RBT_LEFT=0, - RBT_RIGHT=1 -} RBTree_Direction; +typedef RB_HEAD(RBTree_Control, RBTree_Node) RBTree_Control; /** * @brief Integer type for compare results. @@ -117,41 +84,13 @@ typedef RBTree_Compare_result ( *RBTree_Compare )( ); /** - * @struct RBTree_Control - * - * This is used to manage a RBT. A rbtree consists of a tree of zero or more - * nodes. - * - * @note This implementation does not require special checks for - * manipulating the root element of the RBT. - * To accomplish this the @a RBTree_Control structure can be overlaid - * with a @ref RBTree_Node structure to act as a "dummy root", - * which has a NULL parent and its left child is the root. - */ - -/* the RBTree_Control is actually part of the RBTree structure as an - * RBTree_Node. The mapping of fields from RBTree_Control to RBTree_Node are: - * permanent_null == parent - * root == left - * first[0] == right - */ -typedef struct { - /** This points to a NULL. Useful for finding the root. */ - RBTree_Node *permanent_null; - /** This points to the root node of the RBT. */ - RBTree_Node *root; - /** This points to the min and max nodes of this RBT. */ - RBTree_Node *first[2]; -} RBTree_Control; - -/** - * @brief RBTree initializer for an empty rbtree with designator @a name. + * @brief Initializer for an empty red-black tree with designator @a name. */ #define RBTREE_INITIALIZER_EMPTY( name ) \ - { NULL, NULL, { NULL, NULL } } + RB_INITIALIZER( name ) /** - * @brief RBTree definition for an empty rbtree with designator @a name. + * @brief Definition for an empty red-black tree with designator @a name. */ #define RBTREE_DEFINE_EMPTY( name ) \ RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name ) @@ -201,6 +140,95 @@ RBTree_Node *_RBTree_Insert( ); /** + * @brief Rebalances the red-black tree after insertion of the node. + * + * @param[in] the_rbtree The red-black tree control. + * @param[in] the_node The most recently inserted node. + */ +void _RBTree_Insert_color( + RBTree_Control *the_rbtree, + RBTree_Node *the_node +); + +/** + * @brief Adds a child node to a parent node. + * + * @param[in] child The child node. + * @param[in] parent The parent node. + * @param[in] link The child node link of the parent node. + */ +RTEMS_INLINE_ROUTINE void _RBTree_Add_child( + RBTree_Node *child, + RBTree_Node *parent, + RBTree_Node **link +) +{ + RB_SET( child, parent, Node ); + *link = child; +} + +/** + * @brief Inserts the node into the red-black tree using the specified parent + * node and link. + * + * @param[in] the_rbtree The red-black tree control. + * @param[in] the_node The node to insert. + * @param[in] parent The parent node. + * @param[in] link The child node link of the parent node. + * + * @code + * #include <rtems/score/rbtree.h> + * + * typedef struct { + * int value; + * RBTree_Node Node; + * } Some_Node; + * + * bool _Some_Less( + * const RBTree_Node *a, + * const RBTree_Node *b + * ) + * { + * const Some_Node *aa = RTEMS_CONTAINER_OF( a, Some_Node, Node ); + * const Some_Node *bb = RTEMS_CONTAINER_OF( b, Some_Node, Node ); + * + * return aa->value < bb->value; + * } + * + * void _Some_Insert( + * RBTree_Control *the_rbtree, + * Some_Node *the_node + * ) + * { + * RBTree_Node **link = _RBTree_Root_reference( the_rbtree ); + * RBTree_Node *parent = NULL; + * + * while ( *link != NULL ) { + * parent = *link; + * + * if ( _Some_Less( &the_node->Node, parent ) ) { + * link = _RBTree_Left_reference( parent ); + * } else { + * link = _RBTree_Right_reference( parent ); + * } + * } + * + * _RBTree_Insert_with_parent( the_rbtree, &the_node->Node, parent, link ); + * } + * @endcode + */ +RTEMS_INLINE_ROUTINE void _RBTree_Insert_with_parent( + RBTree_Control *the_rbtree, + RBTree_Node *the_node, + RBTree_Node *parent, + RBTree_Node **link +) +{ + _RBTree_Add_child( the_node, parent, link ); + _RBTree_Insert_color( the_rbtree, the_node ); +} + +/** * @brief Extracts (removes) the node from the red-black tree. * * This function does not set the node off-tree. In case this is desired, then @@ -218,20 +246,6 @@ void _RBTree_Extract( ); /** - * @brief Returns the in-order next node of a node. - * - * @param[in] node The node. - * @param[in] dir The direction. - * - * @retval NULL The in-order next node does not exist. - * @retval otherwise The next node. - */ -RBTree_Node *_RBTree_Next( - const RBTree_Node *node, - RBTree_Direction dir -); - -/** * @brief Sets a red-black tree node as off-tree. * * Do not use this function on nodes which are a part of a tree. @@ -242,7 +256,7 @@ RBTree_Node *_RBTree_Next( */ RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node ) { - the_node->parent = NULL; + RB_COLOR( the_node, Node ) = -1; } /** @@ -260,7 +274,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree( const RBTree_Node *the_node ) { - return the_node->parent == NULL; + return RB_COLOR( the_node, Node ) == -1; } /** @@ -279,21 +293,17 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root( const RBTree_Control *the_rbtree ) { - return the_rbtree->root; + return RB_ROOT( the_rbtree ); } /** - * @brief Return pointer to RBTree's first node. - * - * This function returns a pointer to the first node on @a the_rbtree, - * where @a dir specifies whether to return the minimum (0) or maximum (1). + * @brief Returns a reference to the root pointer of the red-black tree. */ -RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First( - const RBTree_Control *the_rbtree, - RBTree_Direction dir +RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Root_reference( + RBTree_Control *the_rbtree ) { - return the_rbtree->first[dir]; + return &RB_ROOT( the_rbtree ); } /** @@ -312,7 +322,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent( const RBTree_Node *the_node ) { - return the_node->parent; + return RB_PARENT( the_node, Node ); } /** @@ -328,7 +338,18 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left( const RBTree_Node *the_node ) { - return the_node->child[RBT_LEFT]; + return RB_LEFT( the_node, Node ); +} + +/** + * @brief Returns a reference to the left child pointer of the red-black tree + * node. + */ +RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Left_reference( + RBTree_Node *the_node +) +{ + return &RB_LEFT( the_node, Node ); } /** @@ -344,7 +365,18 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right( const RBTree_Node *the_node ) { - return the_node->child[RBT_RIGHT]; + return RB_RIGHT( the_node, Node ); +} + +/** + * @brief Returns a reference to the right child pointer of the red-black tree + * node. + */ +RTEMS_INLINE_ROUTINE RBTree_Node **_RBTree_Right_reference( + RBTree_Node *the_node +) +{ + return &RB_RIGHT( the_node, Node ); } /** @@ -362,7 +394,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty( const RBTree_Control *the_rbtree ) { - return (the_rbtree->root == NULL); + return RB_EMPTY( the_rbtree ); } /** @@ -384,7 +416,7 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root( const RBTree_Node *the_node ) { - return _RBTree_Parent( _RBTree_Parent( the_node ) ) == NULL; + return _RBTree_Parent( the_node ) == NULL; } /** @@ -396,10 +428,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty( RBTree_Control *the_rbtree ) { - the_rbtree->permanent_null = NULL; - the_rbtree->root = NULL; - the_rbtree->first[RBT_LEFT] = NULL; - the_rbtree->first[RBT_RIGHT] = NULL; + RB_INIT( the_rbtree ); } /** @@ -410,12 +439,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty( * @retval NULL The red-black tree is empty. * @retval node The minimum node. */ -RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Minimum( - const RBTree_Control *the_rbtree -) -{ - return _RBTree_First( the_rbtree, RBT_LEFT ); -} +RBTree_Node *_RBTree_Minimum( const RBTree_Control *the_rbtree ); /** * @brief Returns the maximum node of the red-black tree. @@ -425,12 +449,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Minimum( * @retval NULL The red-black tree is empty. * @retval node The maximum node. */ -RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Maximum( - const RBTree_Control *the_rbtree -) -{ - return _RBTree_First( the_rbtree, RBT_RIGHT ); -} +RBTree_Node *_RBTree_Maximum( const RBTree_Control *the_rbtree ); /** * @brief Returns the predecessor of a node. @@ -440,12 +459,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Maximum( * @retval NULL The predecessor does not exist. Otherwise it returns * the predecessor node. */ -RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor( - const RBTree_Node *node -) -{ - return _RBTree_Next( node, RBT_LEFT ); -} +RBTree_Node *_RBTree_Predecessor( const RBTree_Node *node ); /** * @brief Returns the successor of a node. @@ -454,12 +468,7 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor( * * @retval NULL The successor does not exist. Otherwise the successor node. */ -RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor( - const RBTree_Node *node -) -{ - return _RBTree_Next( node, RBT_RIGHT ); -} +RBTree_Node *_RBTree_Successor( const RBTree_Node *node ); /**@}*/ |