From 993f5acd25cc3d140689c7a0f2c1912da7b2f0f3 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Wed, 23 Jul 2014 13:03:54 +0200 Subject: rbtree: Simplify insert and extract Simplify _RBTree_Insert() and _RBTree_Extract(). Remove more superfluous NULL pointer checks. Change _RBTree_Is_root() to use only the node. Add parent parameter to _RBTree_Sibling(). Delete _RBTree_Grandparent() and _RBTree_Parent_sibling(). --- cpukit/sapi/include/rtems/rbtree.h | 12 ++---- cpukit/score/include/rtems/score/rbtree.h | 44 +++++++++++++++------ cpukit/score/include/rtems/score/rbtreeimpl.h | 53 +++++-------------------- cpukit/score/src/rbtreeextract.c | 7 ++-- cpukit/score/src/rbtreeinsert.c | 57 +++++++++++++++++---------- testsuites/sptests/sprbtree01/init.c | 14 ++----- 6 files changed, 87 insertions(+), 100 deletions(-) diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h index 0e2ea2c743..900506fdc7 100644 --- a/cpukit/sapi/include/rtems/rbtree.h +++ b/cpukit/sapi/include/rtems/rbtree.h @@ -195,9 +195,7 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_right( } /** - * @brief Return pointer to the parent child node from this node. - * - * This function returns a pointer to the parent node of @a the_node. + * @copydoc _RBTree_Parent() */ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_parent( const rtems_rbtree_node *the_node @@ -248,17 +246,13 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max( } /** - * @brief Is this node the RBTree root. - * - * This function returns true if @a the_node is the root of @a the_rbtree and - * false otherwise. + * @copydoc _RBTree_Is_root() */ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root( - const rtems_rbtree_control *the_rbtree, const rtems_rbtree_node *the_node ) { - return _RBTree_Is_root( the_rbtree, the_node ); + return _RBTree_Is_root( the_node ); } /** diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h index aa84558721..299b75ad2c 100644 --- a/cpukit/score/include/rtems/score/rbtree.h +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -300,9 +300,16 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree( } /** - * @brief Return pointer to RBTree's root node. + * @brief Returns a pointer to root node of the red-black tree. * - * This function returns a pointer to the root node of @a the_rbtree. + * The root node may change after insert or extract operations. + * + * @param[in] the_rbtree The red-black tree control. + * + * @retval NULL The tree is empty. + * @retval root The root node. + * + * @see _RBTree_Is_root(). */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root( const RBTree_Control *the_rbtree @@ -326,15 +333,21 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First( } /** - * @brief Return pointer to the parent of this node. + * @brief Returns a pointer to the parent of this node. + * + * The node must have a parent, thus it is invalid to use this function for the + * root node or a node that is not part of a tree. To test for the root node + * compare with _RBTree_Root() or use _RBTree_Is_root(). + * + * @param[in] the_node The node of interest. * - * This function returns a pointer to the parent node of @a the_node. + * @retval parent The parent of this node. + * @retval undefined The node is the root node or not part of a tree. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent( const RBTree_Node *the_node ) { - if (!the_node->parent->parent) return NULL; return the_node->parent; } @@ -409,20 +422,25 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_first( } /** - * @brief Is this node the RBTree root. - * - * This function returns true if @a the_node is the root of @a the_rbtree and + * @brief Returns true if this node is the root node of a red-black tree, and * false otherwise. * - * @retval true @a the_node is the root of @a the_rbtree. - * @retval false @a the_node is not the root of @a the_rbtree. + * The root node may change after insert or extract operations. In case the + * node is not a node of a tree, then this function yields unpredictable + * results. + * + * @param[in] the_node The node of interest. + * + * @retval true The node is the root node. + * @retval false Otherwise. + * + * @see _RBTree_Root(). */ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root( - const RBTree_Control *the_rbtree, - const RBTree_Node *the_node + const RBTree_Node *the_node ) { - return (the_node == _RBTree_Root(the_rbtree)); + return _RBTree_Parent( _RBTree_Parent( the_node ) ) == NULL; } /** diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h b/cpukit/score/include/rtems/score/rbtreeimpl.h index 5f5e78367a..ed4cbd558a 100644 --- a/cpukit/score/include/rtems/score/rbtreeimpl.h +++ b/cpukit/score/include/rtems/score/rbtreeimpl.h @@ -107,56 +107,23 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_red( } /** - * @brief Return a pointer to node's grandparent. + * @brief Returns the sibling of the node. * - * This function returns a pointer to the grandparent of @a the_node if it - * exists, and NULL if not. - */ -RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent( - const RBTree_Node *the_node -) -{ - if(!the_node) return NULL; - if(!(the_node->parent)) return NULL; - if(!(the_node->parent->parent)) return NULL; - if(!(the_node->parent->parent->parent)) return NULL; - return(the_node->parent->parent); -} - -/** - * @brief Return a pointer to node's sibling. + * @param[in] the_node The node of interest. + * @param[in] parent The parent of the node. The parent must exist, thus it is + * invalid to use this function for the root node. * - * This function returns a pointer to the sibling of @a the_node if it - * exists, and NULL if not. + * @retval NULL No sibling exists. + * @retval sibling The sibling of the node. */ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling( - const RBTree_Node *the_node -) -{ - if(!the_node) return NULL; - if(!(the_node->parent)) return NULL; - if(!(the_node->parent->parent)) return NULL; - - if(the_node == the_node->parent->child[RBT_LEFT]) - return the_node->parent->child[RBT_RIGHT]; - else - return the_node->parent->child[RBT_LEFT]; -} - -/** - * @brief Return a pointer to node's parent's sibling. - * - * This function returns a pointer to the sibling of the parent of - * @a the_node if it exists, and NULL if not. - */ -RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling( - const RBTree_Node *the_node + const RBTree_Node *the_node, + const RBTree_Node *parent ) { - if(!the_node) return NULL; - if(_RBTree_Grandparent(the_node) == NULL) return NULL; + RBTree_Node *left_child = parent->child[ RBT_LEFT ]; - return _RBTree_Sibling(the_node->parent); + return the_node == left_child ? parent->child[ RBT_RIGHT ] : left_child; } RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal( diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c index a1896a960e..f3a7328e8d 100644 --- a/cpukit/score/src/rbtreeextract.c +++ b/cpukit/score/src/rbtreeextract.c @@ -22,7 +22,7 @@ */ static void _RBTree_Extract_validate( RBTree_Node *the_node ) { - RBTree_Node *parent, *sibling; + RBTree_Node *parent; RBTree_Direction dir; parent = the_node->parent; @@ -30,10 +30,10 @@ static void _RBTree_Extract_validate( RBTree_Node *the_node ) if ( !parent->parent ) return; - sibling = _RBTree_Sibling( the_node ); - /* continue to correct tree as long as the_node is black and not the root */ while ( !_RBTree_Is_red( the_node ) && parent->parent ) { + RBTree_Node *sibling = _RBTree_Sibling( the_node, parent ); + /* if sibling is red, switch parent (black) and sibling colors, * then rotate parent left, making the sibling be the_node's grandparent. * Now the_node has a black sibling and red parent. After rotation, @@ -59,7 +59,6 @@ static void _RBTree_Extract_validate( RBTree_Node *the_node ) the_node = parent; /* done if parent is red */ parent = the_node->parent; - sibling = _RBTree_Sibling( the_node ); } else { /* at least one of sibling's children is red. we now proceed in two * cases, either the_node is to the left or the right of the parent. diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c index 3bccba5aaa..a7be449420 100644 --- a/cpukit/score/src/rbtreeinsert.c +++ b/cpukit/score/src/rbtreeinsert.c @@ -32,40 +32,55 @@ RTEMS_STATIC_ASSERT( */ static void _RBTree_Validate_insert( RBTree_Node *the_node ) { - RBTree_Node *u, *g; + RBTree_Node *parent = _RBTree_Parent( the_node ); + RBTree_Node *grandparent = _RBTree_Parent( parent ); /* note: the insert root case is handled already */ /* if the parent is black, nothing needs to be done * otherwise may need to loop a few times */ - while ( _RBTree_Is_red( _RBTree_Parent( the_node ) ) ) { - u = _RBTree_Parent_sibling( the_node ); - g = the_node->parent->parent; - - /* if uncle is red, repaint uncle/parent black and grandparent red */ - if ( _RBTree_Is_red( u ) ) { - the_node->parent->color = RBT_BLACK; - u->color = RBT_BLACK; - g->color = RBT_RED; - the_node = g; - } else { /* if uncle is black */ - RBTree_Direction dir = the_node != the_node->parent->child[ 0 ]; - RBTree_Direction pdir = the_node->parent != g->child[ 0 ]; + while ( parent->color == RBT_RED ) { + /* The root is black, so the grandparent must exist */ + RBTree_Node *uncle = _RBTree_Sibling( parent, grandparent ); + + /* + * If uncle exists and is red, repaint uncle/parent black and grandparent + * red. + */ + if ( uncle != NULL && uncle->color == RBT_RED ) { + parent->color = RBT_BLACK; + uncle->color = RBT_BLACK; + grandparent->color = RBT_RED; + the_node = grandparent; + parent = _RBTree_Parent( the_node ); + grandparent = _RBTree_Parent( parent ); + + if ( grandparent == NULL ) + break; + } else { /* If uncle does not exist or is black */ + RBTree_Direction dir = _RBTree_Direction( the_node, parent ); + RBTree_Direction parentdir = _RBTree_Direction( parent, grandparent ); /* ensure node is on the same branch direction as parent */ - if ( dir != pdir ) { - _RBTree_Rotate( the_node->parent, pdir ); - the_node = the_node->child[ pdir ]; + if ( dir != parentdir ) { + RBTree_Node *oldparent = parent; + + parent = the_node; + the_node = oldparent; + _RBTree_Rotate( oldparent, parentdir ); } - the_node->parent->color = RBT_BLACK; - g->color = RBT_RED; + parent->color = RBT_BLACK; + grandparent->color = RBT_RED; /* now rotate grandparent in the other branch direction (toward uncle) */ - _RBTree_Rotate( g, ( 1 - pdir ) ); + _RBTree_Rotate( grandparent, _RBTree_Opposite_direction( parentdir ) ); + + grandparent = _RBTree_Parent( parent ); + break; } } - if ( !the_node->parent->parent ) + if ( grandparent == NULL ) the_node->color = RBT_BLACK; } diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c index 734530e6bd..6a02a53413 100644 --- a/testsuites/sptests/sprbtree01/init.c +++ b/testsuites/sptests/sprbtree01/init.c @@ -816,13 +816,13 @@ static bool visit_nodes( rtems_test_assert( td->key == tn->key ); if ( td->parent == NULL ) { - rtems_test_assert( td->parent == tn->Node.parent->parent ); + rtems_test_assert( rtems_rbtree_is_root( &tn->Node ) ); } else { - rtems_test_assert( td->parent == tn->Node.parent ); + rtems_test_assert( td->parent == rtems_rbtree_parent( &tn->Node ) ); } - rtems_test_assert( td->left == tn->Node.child[ RBT_LEFT ] ); - rtems_test_assert( td->right == tn->Node.child[ RBT_RIGHT ] ); + rtems_test_assert( td->left == rtems_rbtree_left( &tn->Node ) ); + rtems_test_assert( td->right == rtems_rbtree_right( &tn->Node ) ); rtems_test_assert( td->color == tn->Node.color ); ++ctx->current; @@ -1194,12 +1194,6 @@ rtems_task Init( rtems_task_argument ignored ) rtems_test_exit(0); } - if ( _RBTree_Sibling( NULL ) != NULL ) - puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" ); - if ( _RBTree_Sibling( rbtree1.root ) != NULL ) - puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" ); - if ( _RBTree_Grandparent( NULL ) != NULL ) - puts ( "INIT - ERROR ON RBTREE NULL GRANDPARENT MISMATCH" ); if ( _RBTree_Is_red( NULL ) != 0 ) puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" ); if ( _RBTree_Is_red( rbtree1.root ) != 0 ) -- cgit v1.2.3