[PATCH 1/3] rbtree: Simplify insert and extract
Sebastian Huber
sebastian.huber at embedded-brains.de
Tue Aug 5 14:27:57 UTC 2014
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 | 44 ++++++++++++----------
testsuites/sptests/sprbtree01/init.c | 14 ++-----
6 files changed, 76 insertions(+), 98 deletions(-)
diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h
index 0e2ea2c..900506f 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 aa84558..299b75a 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 451b5f4..e7d5630 100644
--- a/cpukit/score/include/rtems/score/rbtreeimpl.h
+++ b/cpukit/score/include/rtems/score/rbtreeimpl.h
@@ -92,56 +92,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 a1896a9..f3a7328 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 3bccba5..05fc9cb 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -32,40 +32,46 @@ RTEMS_STATIC_ASSERT(
*/
static void _RBTree_Validate_insert( RBTree_Node *the_node )
{
- RBTree_Node *u, *g;
+ RBTree_Node *parent = _RBTree_Parent( the_node );
/* 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 *grandparent = _RBTree_Parent( parent );
+ 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 );
+ } else { /* If uncle does not exist or is black */
+ RBTree_Direction dir = the_node != parent->child[ 0 ];
+ RBTree_Direction pdir = parent != grandparent->child[ 0 ];
/* ensure node is on the same branch direction as parent */
if ( dir != pdir ) {
- _RBTree_Rotate( the_node->parent, pdir );
+ _RBTree_Rotate( parent, pdir );
the_node = the_node->child[ pdir ];
+ parent = _RBTree_Parent( the_node );
}
- 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( pdir ) );
}
}
- if ( !the_node->parent->parent )
+ if ( _RBTree_Parent( parent ) == NULL )
the_node->color = RBT_BLACK;
}
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index ffb91b1..89abdd3 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;
@@ -1195,12 +1195,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 )
--
1.8.1.4
More information about the devel
mailing list