From 3d74da6e2359977de4924fc3ce7a2519843058dd Mon Sep 17 00:00:00 2001 From: Gedare Bloom Date: Wed, 2 May 2012 15:04:58 -0400 Subject: 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 file changed, 9 insertions(+), 17 deletions(-) diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c index 407136164e..9a0a18bea8 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 -- cgit v1.2.3