From a41950ddfb82aed98b3faa7addf6c2b82f2a3c8b Mon Sep 17 00:00:00 2001 From: Gedare Bloom Date: Wed, 2 May 2012 15:23:30 -0400 Subject: PR2061: RBTree: updating min and max on insert with duplicates When inserting to a red-black tree with duplicates the min and max pointers are not updated properly. We need to check the key of the min/max node against the insert node since the insert point could be the child of a node with an identical key to the min/max node. --- cpukit/score/src/rbtreeinsert.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c index 3ea6b354b4..d2d544299b 100644 --- a/cpukit/score/src/rbtreeinsert.c +++ b/cpukit/score/src/rbtreeinsert.c @@ -106,7 +106,12 @@ RBTree_Node *_RBTree_Insert_unprotected( iter_node->child[dir] = the_node; the_node->parent = iter_node; /* update min/max */ - if (_RBTree_Is_first(the_rbtree, iter_node, dir)) { + compare_result = the_rbtree->compare_function( + the_node, + _RBTree_First(the_rbtree, dir) + ); + if ( (!dir && _RBTree_Is_lesser(compare_result)) || + (dir && _RBTree_Is_greater(compare_result)) ) { the_rbtree->first[dir] = the_node; } break; -- cgit v1.2.3