[rtems commit] PR2061: RBTree: updating min and max on insert with duplicates

[Gedare Bloom]

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

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

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 files changed, 6 insertions(+), 1 deletions(-)

diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index 3ea6b35..d2d5442 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;