diff options
| author | Gedare Bloom <gedare@rtems.org> | 2012-05-02 15:23:30 -0400 |
|---|---|---|
| committer | Gedare Bloom <gedare@rtems.org> | 2012-05-08 18:40:44 -0400 |
| commit | a41950ddfb82aed98b3faa7addf6c2b82f2a3c8b (patch) | |
| tree | 92852b9beb89db10918236bf46ec5e38d7d9e015 | |
| parent | PR2060: RBTree: updating min and max on extract path (diff) | |
| download | rtems-a41950ddfb82aed98b3faa7addf6c2b82f2a3c8b.tar.bz2 | |
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.
| -rw-r--r-- | 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 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; |