rbtree: Update maximum node in LIFO order

The test sptests/sp35 showed a NULL pointer access due to an invalid
maximum node field (e.g. a tree with one element and NULL as the maximum
node).

2 files changed, 11 insertions, 9 deletions

diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index b3f2ed4c0d..2ec77ead4f 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -219,15 +219,16 @@ RBTree_Node *_RBTree_Find(
 );
 
 /**
- *  @brief Insert @a the_node on the Red-Black Tree @a the_rbtree.
+ * @brief Inserts the node into the red-black tree.
  *
- *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
+ * In case the node is already a node of a tree, then this function yields
+ * unpredictable results.
  *
  * @param[in] the_rbtree The red-black tree control.
  * @param[in] the_node The node to insert.
  * @param[in] compare The node compare function.
  * @param[in] is_unique If true, then reject nodes with a duplicate key, else
- *   otherwise.
+ *   insert nodes in FIFO order in case the key value is equal to existing nodes.
  *
  * @retval NULL Successfully inserted.
  * @retval existing_node This is a unique insert and there exists a node with
@@ -487,19 +488,20 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
 }
 
 /**
- * @brief Gets a node with an extremal key value.
+ * @brief Gets a node with an extremal key value from the red-black tree.
  *
  * This function extracts a node with the minimum or maximum key value from
  * tree and returns a pointer to that node if it exists.  In case multiple
- * nodes with an extremal key value exist, then they are extracted in FIFO
- * order.
+ * nodes with a minimum key value exist, then they are extracted in FIFO order.
+ * In case multiple nodes with a maximum key value exist, then they are
+ * extracted in LIFO order.
  *
  * @param[in] the_rbtree The red-black tree control.
  * @param[in] dir Specifies whether to get a node with the minimum (RBT_LEFT)
  *   or maximum (RBT_RIGHT) key value.
  *
  * @retval NULL The tree is empty.
- * @retval extremal_node A node with the minimal or maximal key value on the
+ * @retval extremal_node A node with a minimal or maximal key value on the
  *   tree.
  */
 RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get(
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index b31c8e7bb7..afff1ef5f9 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -96,8 +96,8 @@ RBTree_Node *_RBTree_Insert(
         );
 
         if (
-          ( !dir && _RBTree_Is_lesser( compare_result ) )
-            || ( dir && _RBTree_Is_greater( compare_result ) )
+          ( dir == RBT_LEFT && _RBTree_Is_lesser( compare_result ) )
+            || ( dir == RBT_RIGHT && !_RBTree_Is_lesser( compare_result ) )
         ) {
           the_rbtree->first[ dir ] = the_node;
         }