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().

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 )