source: rtems/cpukit/score/src/rbtreeextract.c @ 993f5ac

4.115
Last change on this file since 993f5ac was 993f5ac, checked in by Sebastian Huber <sebastian.huber@…>, on 07/23/14 at 11:03:54

rbtree: Simplify insert and extract

Simplify _RBTree_Insert() and _RBTree_Extract(). Remove more
superfluous NULL pointer checks. Change _RBTree_Is_root() to use only
the node. Add parent parameter to _RBTree_Sibling(). Delete
_RBTree_Grandparent() and _RBTree_Parent_sibling().

  • Property mode set to 100644
File size: 7.0 KB
Line 
1/*
2 *  Copyright (c) 2010 Gedare Bloom.
3 *
4 *  The license and distribution terms for this file may be
5 *  found in the file LICENSE in this distribution or at
6 *  http://www.rtems.org/license/LICENSE.
7 */
8
9#if HAVE_CONFIG_H
10#include "config.h"
11#endif
12
13#include <rtems/score/rbtreeimpl.h>
14
15/** @brief  Validate and fix-up tree properties after deleting a node
16 *
17 *  This routine is called on a black node, @a the_node, after its deletion.
18 *  This function maintains the properties of the red-black tree.
19 *
20 *  @note It does NOT disable interrupts to ensure the atomicity
21 *        of the extract operation.
22 */
23static void _RBTree_Extract_validate( RBTree_Node *the_node )
24{
25  RBTree_Node     *parent;
26  RBTree_Direction dir;
27
28  parent = the_node->parent;
29
30  if ( !parent->parent )
31    return;
32
33  /* continue to correct tree as long as the_node is black and not the root */
34  while ( !_RBTree_Is_red( the_node ) && parent->parent ) {
35    RBTree_Node *sibling = _RBTree_Sibling( the_node, parent );
36
37    /* if sibling is red, switch parent (black) and sibling colors,
38     * then rotate parent left, making the sibling be the_node's grandparent.
39     * Now the_node has a black sibling and red parent. After rotation,
40     * update sibling pointer.
41     */
42    if ( _RBTree_Is_red( sibling ) ) {
43      parent->color = RBT_RED;
44      sibling->color = RBT_BLACK;
45      dir = the_node != parent->child[ 0 ];
46      _RBTree_Rotate( parent, dir );
47      sibling = parent->child[ _RBTree_Opposite_direction( dir ) ];
48    }
49
50    /* sibling is black, see if both of its children are also black. */
51    if ( !_RBTree_Is_red( sibling->child[ RBT_RIGHT ] ) &&
52         !_RBTree_Is_red( sibling->child[ RBT_LEFT ] ) ) {
53      sibling->color = RBT_RED;
54
55      if ( _RBTree_Is_red( parent ) ) {
56        parent->color = RBT_BLACK;
57        break;
58      }
59
60      the_node = parent;   /* done if parent is red */
61      parent = the_node->parent;
62    } else {
63      /* at least one of sibling's children is red. we now proceed in two
64       * cases, either the_node is to the left or the right of the parent.
65       * In both cases, first check if one of sibling's children is black,
66       * and if so rotate in the proper direction and update sibling pointer.
67       * Then switch the sibling and parent colors, and rotate through parent.
68       */
69      dir = the_node != parent->child[ 0 ];
70
71      if (
72        !_RBTree_Is_red( sibling->child[ _RBTree_Opposite_direction( dir ) ] )
73      ) {
74        sibling->color = RBT_RED;
75        sibling->child[ dir ]->color = RBT_BLACK;
76        _RBTree_Rotate( sibling, _RBTree_Opposite_direction( dir ) );
77        sibling = parent->child[ _RBTree_Opposite_direction( dir ) ];
78      }
79
80      sibling->color = parent->color;
81      parent->color = RBT_BLACK;
82      sibling->child[ _RBTree_Opposite_direction( dir ) ]->color = RBT_BLACK;
83      _RBTree_Rotate( parent, dir );
84      break; /* done */
85    }
86  } /* while */
87
88  if ( !the_node->parent->parent )
89    the_node->color = RBT_BLACK;
90}
91
92void _RBTree_Extract(
93  RBTree_Control *the_rbtree,
94  RBTree_Node    *the_node
95)
96{
97  RBTree_Node     *leaf, *target;
98  RBTree_Color     victim_color;
99  RBTree_Direction dir;
100
101  /* check if min needs to be updated */
102  if ( the_node == the_rbtree->first[ RBT_LEFT ] ) {
103    RBTree_Node *next;
104    next = _RBTree_Successor( the_node );
105    the_rbtree->first[ RBT_LEFT ] = next;
106  }
107
108  /* Check if max needs to be updated. min=max for 1 element trees so
109   * do not use else if here. */
110  if ( the_node == the_rbtree->first[ RBT_RIGHT ] ) {
111    RBTree_Node *previous;
112    previous = _RBTree_Predecessor( the_node );
113    the_rbtree->first[ RBT_RIGHT ] = previous;
114  }
115
116  /* if the_node has at most one non-null child then it is safe to proceed
117   * check if both children are non-null, if so then we must find a target node
118   * either max in node->child[RBT_LEFT] or min in node->child[RBT_RIGHT],
119   * and replace the_node with the target node. This maintains the binary
120   * search tree property, but may violate the red-black properties.
121   */
122
123  if ( the_node->child[ RBT_LEFT ] && the_node->child[ RBT_RIGHT ] ) {
124    target = the_node->child[ RBT_LEFT ]; /* find max in node->child[RBT_LEFT] */
125
126    while ( target->child[ RBT_RIGHT ] )
127      target = target->child[ RBT_RIGHT ];
128
129    /* if the target node has a child, need to move it up the tree into
130     * target's position (target is the right child of target->parent)
131     * when target vacates it. if there is no child, then target->parent
132     * should become NULL. This may cause the coloring to be violated.
133     * For now we store the color of the node being deleted in victim_color.
134     */
135    leaf = target->child[ RBT_LEFT ];
136
137    if ( leaf ) {
138      leaf->parent = target->parent;
139    } else {
140      /* fix the tree here if the child is a null leaf. */
141      _RBTree_Extract_validate( target );
142    }
143
144    victim_color = target->color;
145    dir = target != target->parent->child[ 0 ];
146    target->parent->child[ dir ] = leaf;
147
148    /* now replace the_node with target */
149    dir = the_node != the_node->parent->child[ 0 ];
150    the_node->parent->child[ dir ] = target;
151
152    /* set target's new children to the original node's children */
153    target->child[ RBT_RIGHT ] = the_node->child[ RBT_RIGHT ];
154
155    if ( the_node->child[ RBT_RIGHT ] )
156      the_node->child[ RBT_RIGHT ]->parent = target;
157
158    target->child[ RBT_LEFT ] = the_node->child[ RBT_LEFT ];
159
160    if ( the_node->child[ RBT_LEFT ] )
161      the_node->child[ RBT_LEFT ]->parent = target;
162
163    /* finally, update the parent node and recolor. target has completely
164     * replaced the_node, and target's child has moved up the tree if needed.
165     * the_node is no longer part of the tree, although it has valid pointers
166     * still.
167     */
168    target->parent = the_node->parent;
169    target->color = the_node->color;
170  } else {
171    /* the_node has at most 1 non-null child. Move the child in to
172     * the_node's location in the tree. This may cause the coloring to be
173     * violated. We will fix it later.
174     * For now we store the color of the node being deleted in victim_color.
175     */
176    leaf = the_node->child[ RBT_LEFT ] ?
177           the_node->child[ RBT_LEFT ] : the_node->child[ RBT_RIGHT ];
178
179    if ( leaf ) {
180      leaf->parent = the_node->parent;
181    } else {
182      /* fix the tree here if the child is a null leaf. */
183      _RBTree_Extract_validate( the_node );
184    }
185
186    victim_color = the_node->color;
187
188    /* remove the_node from the tree */
189    dir = the_node != the_node->parent->child[ 0 ];
190    the_node->parent->child[ dir ] = leaf;
191  }
192
193  /* fix coloring. leaf has moved up the tree. The color of the deleted
194   * node is in victim_color. There are two cases:
195   *   1. Deleted a red node, its child must be black. Nothing must be done.
196   *   2. Deleted a black node, its child must be red. Paint child black.
197   */
198  if ( victim_color == RBT_BLACK ) { /* eliminate case 1 */
199    if ( leaf ) {
200      leaf->color = RBT_BLACK; /* case 2 */
201    }
202  }
203
204  /* set root to black, if it exists */
205  if ( the_rbtree->root )
206    the_rbtree->root->color = RBT_BLACK;
207}
Note: See TracBrowser for help on using the repository browser.