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.

2 files changed, 7 insertions, 12 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);