rbtree: API changes. Remove rbtree control node from RBTree_Next.

The implementation of RBTree_Next was using an awkward construction to detect
and avoid accessing the false root of the red-black tree. To deal with the
false root, RBTree_Next was comparing node parents with the control node.
Instead the false root can be detected by checking if the grandparent of a
node exists; the grandparent of the tree's true root is NULL by definition
so the root of the tree is found while walking up the tree by checking for
the non-existence of a grandparent.

This change propagates into the predecessor/successor and iterate functions.

8 files changed, 21 insertions, 36 deletions

diff --git a/cpukit/sapi/inline/rtems/rbtree.inl b/cpukit/sapi/inline/rtems/rbtree.inl
index 804cf382ca..dc53fa0381 100644
--- a/cpukit/sapi/inline/rtems/rbtree.inl
+++ b/cpukit/sapi/inline/rtems/rbtree.inl
@@ -283,44 +283,40 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
  * @copydoc _RBTree_Predecessor_unprotected()
  */
 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor_unprotected(
-  const rtems_rbtree_control *rbtree,
   const rtems_rbtree_node *node
 )
 {
-  return _RBTree_Predecessor_unprotected( rbtree, node );
+  return _RBTree_Predecessor_unprotected( node );
 }
 
 /**
  * @copydoc _RBTree_Predecessor()
  */
 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor(
-  const rtems_rbtree_control *rbtree,
   const rtems_rbtree_node *node
 )
 {
-  return _RBTree_Predecessor( rbtree, node );
+  return _RBTree_Predecessor( node );
 }
 
 /**
  * @copydoc _RBTree_Successor_unprotected()
  */
 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor_unprotected(
-  const rtems_rbtree_control *rbtree,
   const rtems_rbtree_node *node
 )
 {
-  return _RBTree_Successor_unprotected( rbtree, node );
+  return _RBTree_Successor_unprotected( node );
 }
 
 /**
  * @copydoc _RBTree_Successor()
  */
 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor(
-  const rtems_rbtree_control *rbtree,
   const rtems_rbtree_node *node
 )
 {
-  return _RBTree_Successor( rbtree, node );
+  return _RBTree_Successor( node );
 }
 
 /**
diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c
index 7facf4f9af..5233778171 100644
--- a/cpukit/sapi/src/rbheap.c
+++ b/cpukit/sapi/src/rbheap.c
@@ -203,13 +203,12 @@ static rtems_rbheap_chunk *find(rtems_rbtree_control *chunk_tree, uintptr_t key)
 }
 
 static rtems_rbheap_chunk *get_next(
-  const rtems_rbtree_control *chunk_tree,
   const rtems_rbheap_chunk *chunk,
   RBTree_Direction dir
 )
 {
   return rtems_rbheap_chunk_of_node(
-    _RBTree_Next_unprotected(chunk_tree, &chunk->tree_node, dir)
+    _RBTree_Next_unprotected(&chunk->tree_node, dir)
   );
 }
 
@@ -246,8 +245,8 @@ rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr)
 
     if (chunk != NULL_PAGE) {
       if (!rtems_rbheap_is_chunk_free(chunk)) {
-        rtems_rbheap_chunk *pred = get_next(chunk_tree, chunk, RBT_LEFT);
-        rtems_rbheap_chunk *succ = get_next(chunk_tree, chunk, RBT_RIGHT);
+        rtems_rbheap_chunk *pred = get_next(chunk, RBT_LEFT);
+        rtems_rbheap_chunk *succ = get_next(chunk, RBT_RIGHT);
 
         check_and_merge(free_chain, chunk_tree, chunk, succ);
         add_to_chain(free_chain, chunk);
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index d98392e872..b3cfc45fa3 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -307,7 +307,6 @@ void _RBTree_Extract(
 /**
  * @brief Returns the in-order next node of a node.
  *
- * @param[in] rbtree The red-black tree.
  * @param[in] node The node.
  * @param[in] dir The direction.
  *
@@ -315,7 +314,6 @@ void _RBTree_Extract(
  * @retval otherwise The next node.
  */
 RBTree_Node *_RBTree_Next_unprotected(
-  const RBTree_Control *rbtree,
   const RBTree_Node *node,
   RBTree_Direction dir
 );
@@ -326,7 +324,6 @@ RBTree_Node *_RBTree_Next_unprotected(
  * The function disables the interrupts protect the operation.
  */
 RBTree_Node *_RBTree_Next(
-  const RBTree_Control *rbtree,
   const RBTree_Node *node,
   RBTree_Direction dir
 );
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
index a079745290..c5187a02ae 100644
--- a/cpukit/score/inline/rtems/score/rbtree.inl
+++ b/cpukit/score/inline/rtems/score/rbtree.inl
@@ -384,11 +384,10 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected(
  * @retval otherwise The predecessor node.
  */
 RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
-  const RBTree_Control *rbtree,
   const RBTree_Node *node
 )
 {
-  return _RBTree_Next_unprotected( rbtree, node, RBT_LEFT );
+  return _RBTree_Next_unprotected( node, RBT_LEFT );
 }
 
 /**
@@ -397,11 +396,10 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
  * The function disables the interrupts protect the operation.
  */
 RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
-  const RBTree_Control *rbtree,
   const RBTree_Node *node
 )
 {
-  return _RBTree_Next( rbtree, node, RBT_LEFT );
+  return _RBTree_Next( node, RBT_LEFT );
 }
 
 /**
@@ -414,11 +412,10 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
  * @retval otherwise The successor node.
  */
 RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
-  const RBTree_Control *rbtree,
   const RBTree_Node *node
 )
 {
-  return _RBTree_Next_unprotected( rbtree, node, RBT_RIGHT );
+  return _RBTree_Next_unprotected( node, RBT_RIGHT );
 }
 
 /**
@@ -427,11 +424,10 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
  * The function disables the interrupts protect the operation.
  */
 RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
-  const RBTree_Control *rbtree,
   const RBTree_Node *node
 )
 {
-  return _RBTree_Next( rbtree, node, RBT_RIGHT );
+  return _RBTree_Next( node, RBT_RIGHT );
 }
 
 /** @brief Get the First Node (unprotected)
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index 9a0a18bea8..e3b27fc430 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -109,7 +109,7 @@ void _RBTree_Extract_unprotected(
   /* check if min needs to be updated */
   if (the_node == the_rbtree->first[RBT_LEFT]) {
     RBTree_Node *next;
-    next = _RBTree_Successor_unprotected(the_rbtree, the_node);
+    next = _RBTree_Successor_unprotected(the_node);
     the_rbtree->first[RBT_LEFT] = next;
   }
 
@@ -117,7 +117,7 @@ void _RBTree_Extract_unprotected(
    * do not use else if here. */
   if (the_node == the_rbtree->first[RBT_RIGHT]) {
     RBTree_Node *previous;
-    previous = _RBTree_Predecessor_unprotected(the_rbtree, the_node);
+    previous = _RBTree_Predecessor_unprotected(the_node);
     the_rbtree->first[RBT_RIGHT] = previous;
   }
 
diff --git a/cpukit/score/src/rbtreeiterate.c b/cpukit/score/src/rbtreeiterate.c
index 33f7e7d454..f6de82b576 100644
--- a/cpukit/score/src/rbtreeiterate.c
+++ b/cpukit/score/src/rbtreeiterate.c
@@ -40,6 +40,6 @@ void _RBTree_Iterate_unprotected(
   while ( !stop && current != NULL ) {
     stop = (*visitor)( current, dir, visitor_arg );
 
-    current = _RBTree_Next_unprotected( rbtree, current, dir );
+    current = _RBTree_Next_unprotected( current, dir );
   }
 }
diff --git a/cpukit/score/src/rbtreenext.c b/cpukit/score/src/rbtreenext.c
index e79f175f35..0aee0434f6 100644
--- a/cpukit/score/src/rbtreenext.c
+++ b/cpukit/score/src/rbtreenext.c
@@ -28,7 +28,6 @@
 #include <rtems/score/isr.h>
 
 RBTree_Node *_RBTree_Next_unprotected(
-  const RBTree_Control *rbtree,
   const RBTree_Node *node,
   RBTree_Direction dir
 )
@@ -43,18 +42,17 @@ RBTree_Node *_RBTree_Next_unprotected(
       next = current;
     }
   } else {
-    const RBTree_Node *null = (const RBTree_Node *) rbtree;
     RBTree_Node *parent = node->parent;
 
-    if ( parent != null && node == parent->child [opp_dir] ) {
+    if ( parent->parent && node == parent->child [opp_dir] ) {
       next = parent;
     } else {
-      while ( parent != null && node == parent->child [dir] ) {
+      while ( parent->parent && node == parent->child [dir] ) {
         node = parent;
-        parent = node->parent;
+        parent = parent->parent;
       }
 
-      if ( parent != null ) {
+      if ( parent->parent ) {
         next = parent;
       }
     }
@@ -64,7 +62,6 @@ RBTree_Node *_RBTree_Next_unprotected(
 }
 
 RBTree_Node *_RBTree_Next(
-  const RBTree_Control *rbtree,
   const RBTree_Node *node,
   RBTree_Direction dir
 )
@@ -73,7 +70,7 @@ RBTree_Node *_RBTree_Next(
   ISR_Level level;
 
   _ISR_Disable( level );
-  next = _RBTree_Next_unprotected( rbtree,  node, dir );
+  next = _RBTree_Next_unprotected( node, dir );
   _ISR_Enable( level );
 
   return next;
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index 7d0d3f60c7..76035f0bf4 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -439,13 +439,13 @@ rtems_task Init(
   }
 
   puts( "INIT - Verify rtems_rbtree_predecessor/successor");
-  p = rtems_rbtree_predecessor(&rbtree1, p);
+  p = rtems_rbtree_predecessor(p);
   if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 29) {
     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
     rtems_test_exit(0);
   }
   p = rtems_rbtree_find(&rbtree1, &search_node.Node);
-  p = rtems_rbtree_successor(&rbtree1, p);
+  p = rtems_rbtree_successor(p);
   if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 31) {
     puts ("INIT - ERROR ON RBTREE ID MISMATCH");
     rtems_test_exit(0);