[rtems commit] PR2060: RBTree: updating min and max on extract path

[Gedare Bloom]

Module:    rtems
Branch:    master
Commit:    3d74da6e2359977de4924fc3ce7a2519843058dd
Changeset: http://git.rtems.org/rtems/commit/?id=3d74da6e2359977de4924fc3ce7a2519843058dd

Author:    Gedare Bloom <gedare at rtems.org>
Date:      Wed May  2 15:04:58 2012 -0400

PR2060: RBTree: updating min and max on extract path

During node extraction from a red-black tree the min and max values are updated
incorrectly. We need to use the successor/predecessor functions to find the
next/previous node when we remove the min/max from the tree.

---

 cpukit/score/src/rbtreeextract.c |   26 +++++++++-----------------
 1 files changed, 9 insertions(+), 17 deletions(-)

diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index 4071361..9a0a18b 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -108,25 +108,17 @@ void _RBTree_Extract_unprotected(
 
   /* check if min needs to be updated */
   if (the_node == the_rbtree->first[RBT_LEFT]) {
-    if (the_node->child[RBT_RIGHT])
-      the_rbtree->first[RBT_LEFT] = the_node->child[RBT_RIGHT];
-    else {
-      the_rbtree->first[RBT_LEFT] = the_node->parent;
-      if(_RBTree_Are_nodes_equal((RBTree_Node *)the_rbtree,
-            the_rbtree->first[RBT_LEFT]))
-        the_rbtree->first[RBT_LEFT] = NULL;
-    }
+    RBTree_Node *next;
+    next = _RBTree_Successor_unprotected(the_rbtree, the_node);
+    the_rbtree->first[RBT_LEFT] = next;
   }
-  /* check if max needs to be updated: note, min can equal max (1 element) */
+
+  /* Check if max needs to be updated. min=max for 1 element trees so
+   * do not use else if here. */
   if (the_node == the_rbtree->first[RBT_RIGHT]) {
-    if (the_node->child[RBT_LEFT])
-      the_rbtree->first[RBT_RIGHT] = the_node->child[RBT_LEFT];
-    else {
-      the_rbtree->first[RBT_RIGHT] = the_node->parent;
-      if(_RBTree_Are_nodes_equal((RBTree_Node *)the_rbtree,
-            the_rbtree->first[RBT_RIGHT]))
-        the_rbtree->first[RBT_RIGHT] = NULL;
-    }
+    RBTree_Node *previous;
+    previous = _RBTree_Predecessor_unprotected(the_rbtree, the_node);
+    the_rbtree->first[RBT_RIGHT] = previous;
   }
 
   /* if the_node has at most one non-null child then it is safe to proceed