Changeset 3d74da6 in rtems


Ignore:
Timestamp:
May 2, 2012, 7:04:58 PM (7 years ago)
Author:
Gedare Bloom <gedare@…>
Branches:
4.11, master
Children:
a41950dd
Parents:
0f31ec5d
git-author:
Gedare Bloom <gedare@…> (05/02/12 19:04:58)
git-committer:
Gedare Bloom <gedare@…> (05/08/12 22:40:44)
Message:

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.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • cpukit/score/src/rbtreeextract.c

    r0f31ec5d r3d74da6  
    109109  /* check if min needs to be updated */
    110110  if (the_node == the_rbtree->first[RBT_LEFT]) {
    111     if (the_node->child[RBT_RIGHT])
    112       the_rbtree->first[RBT_LEFT] = the_node->child[RBT_RIGHT];
    113     else {
    114       the_rbtree->first[RBT_LEFT] = the_node->parent;
    115       if(_RBTree_Are_nodes_equal((RBTree_Node *)the_rbtree,
    116             the_rbtree->first[RBT_LEFT]))
    117         the_rbtree->first[RBT_LEFT] = NULL;
    118     }
    119   }
    120   /* check if max needs to be updated: note, min can equal max (1 element) */
     111    RBTree_Node *next;
     112    next = _RBTree_Successor_unprotected(the_rbtree, the_node);
     113    the_rbtree->first[RBT_LEFT] = next;
     114  }
     115
     116  /* Check if max needs to be updated. min=max for 1 element trees so
     117   * do not use else if here. */
    121118  if (the_node == the_rbtree->first[RBT_RIGHT]) {
    122     if (the_node->child[RBT_LEFT])
    123       the_rbtree->first[RBT_RIGHT] = the_node->child[RBT_LEFT];
    124     else {
    125       the_rbtree->first[RBT_RIGHT] = the_node->parent;
    126       if(_RBTree_Are_nodes_equal((RBTree_Node *)the_rbtree,
    127             the_rbtree->first[RBT_RIGHT]))
    128         the_rbtree->first[RBT_RIGHT] = NULL;
    129     }
     119    RBTree_Node *previous;
     120    previous = _RBTree_Predecessor_unprotected(the_rbtree, the_node);
     121    the_rbtree->first[RBT_RIGHT] = previous;
    130122  }
    131123
Note: See TracChangeset for help on using the changeset viewer.