From 6b0a7efc77bd0dec7acdd84b692e266f5183b2b6 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Mon, 21 Jul 2014 18:08:07 +0200 Subject: rbtree: Format --- cpukit/score/src/rbtreeextract.c | 154 ++++++++++++++++++++++----------------- 1 file changed, 86 insertions(+), 68 deletions(-) (limited to 'cpukit/score/src/rbtreeextract.c') diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c index 9e87868586..e4278a4f06 100644 --- a/cpukit/score/src/rbtreeextract.c +++ b/cpukit/score/src/rbtreeextract.c @@ -21,45 +21,46 @@ * @note It does NOT disable interrupts to ensure the atomicity * of the extract operation. */ -static void _RBTree_Extract_validate( - RBTree_Node *the_node - ) +static void _RBTree_Extract_validate( RBTree_Node *the_node ) { - RBTree_Node *parent, *sibling; + RBTree_Node *parent, *sibling; RBTree_Direction dir; parent = the_node->parent; - if(!parent->parent) return; - sibling = _RBTree_Sibling(the_node); + if ( !parent->parent ) + return; - /* continue to correct tree as long as the_node is black and not the root */ - while (!_RBTree_Is_red(the_node) && parent->parent) { + sibling = _RBTree_Sibling( the_node ); + /* continue to correct tree as long as the_node is black and not the root */ + while ( !_RBTree_Is_red( the_node ) && parent->parent ) { /* if sibling is red, switch parent (black) and sibling colors, * then rotate parent left, making the sibling be the_node's grandparent. * Now the_node has a black sibling and red parent. After rotation, * update sibling pointer. */ - if (_RBTree_Is_red(sibling)) { + if ( _RBTree_Is_red( sibling ) ) { parent->color = RBT_RED; sibling->color = RBT_BLACK; - dir = the_node != parent->child[0]; - _RBTree_Rotate(parent, dir); - sibling = parent->child[_RBTree_Opposite_direction(dir)]; + dir = the_node != parent->child[ 0 ]; + _RBTree_Rotate( parent, dir ); + sibling = parent->child[ _RBTree_Opposite_direction( dir ) ]; } /* sibling is black, see if both of its children are also black. */ - if (!_RBTree_Is_red(sibling->child[RBT_RIGHT]) && - !_RBTree_Is_red(sibling->child[RBT_LEFT])) { - sibling->color = RBT_RED; - if (_RBTree_Is_red(parent)) { - parent->color = RBT_BLACK; - break; - } - the_node = parent; /* done if parent is red */ - parent = the_node->parent; - sibling = _RBTree_Sibling(the_node); + if ( !_RBTree_Is_red( sibling->child[ RBT_RIGHT ] ) && + !_RBTree_Is_red( sibling->child[ RBT_LEFT ] ) ) { + sibling->color = RBT_RED; + + if ( _RBTree_Is_red( parent ) ) { + parent->color = RBT_BLACK; + break; + } + + the_node = parent; /* done if parent is red */ + parent = the_node->parent; + sibling = _RBTree_Sibling( the_node ); } else { /* at least one of sibling's children is red. we now proceed in two * cases, either the_node is to the left or the right of the parent. @@ -67,21 +68,27 @@ static void _RBTree_Extract_validate( * and if so rotate in the proper direction and update sibling pointer. * Then switch the sibling and parent colors, and rotate through parent. */ - dir = the_node != parent->child[0]; - if (!_RBTree_Is_red(sibling->child[_RBTree_Opposite_direction(dir)])) { + dir = the_node != parent->child[ 0 ]; + + if ( + !_RBTree_Is_red( sibling->child[ _RBTree_Opposite_direction( dir ) ] ) + ) { sibling->color = RBT_RED; - sibling->child[dir]->color = RBT_BLACK; - _RBTree_Rotate(sibling, _RBTree_Opposite_direction(dir)); - sibling = parent->child[_RBTree_Opposite_direction(dir)]; + sibling->child[ dir ]->color = RBT_BLACK; + _RBTree_Rotate( sibling, _RBTree_Opposite_direction( dir ) ); + sibling = parent->child[ _RBTree_Opposite_direction( dir ) ]; } + sibling->color = parent->color; parent->color = RBT_BLACK; - sibling->child[_RBTree_Opposite_direction(dir)]->color = RBT_BLACK; - _RBTree_Rotate(parent, dir); + sibling->child[ _RBTree_Opposite_direction( dir ) ]->color = RBT_BLACK; + _RBTree_Rotate( parent, dir ); break; /* done */ } } /* while */ - if(!the_node->parent->parent) the_node->color = RBT_BLACK; + + if ( !the_node->parent->parent ) + the_node->color = RBT_BLACK; } /** @brief Extract a Node (unprotected) @@ -92,29 +99,30 @@ static void _RBTree_Extract_validate( * of the extract operation. */ void _RBTree_Extract( - RBTree_Control *the_rbtree, - RBTree_Node *the_node - ) + RBTree_Control *the_rbtree, + RBTree_Node *the_node +) { - RBTree_Node *leaf, *target; - RBTree_Color victim_color; + RBTree_Node *leaf, *target; + RBTree_Color victim_color; RBTree_Direction dir; - if (!the_node) return; + if ( !the_node ) + return; /* check if min needs to be updated */ - if (the_node == the_rbtree->first[RBT_LEFT]) { + if ( the_node == the_rbtree->first[ RBT_LEFT ] ) { RBTree_Node *next; - next = _RBTree_Successor(the_node); - the_rbtree->first[RBT_LEFT] = next; + next = _RBTree_Successor( the_node ); + the_rbtree->first[ RBT_LEFT ] = next; } /* Check if max needs to be updated. min=max for 1 element trees so * do not use else if here. */ - if (the_node == the_rbtree->first[RBT_RIGHT]) { + if ( the_node == the_rbtree->first[ RBT_RIGHT ] ) { RBTree_Node *previous; - previous = _RBTree_Predecessor(the_node); - the_rbtree->first[RBT_RIGHT] = previous; + previous = _RBTree_Predecessor( the_node ); + the_rbtree->first[ RBT_RIGHT ] = previous; } /* if the_node has at most one non-null child then it is safe to proceed @@ -124,9 +132,11 @@ void _RBTree_Extract( * search tree property, but may violate the red-black properties. */ - if (the_node->child[RBT_LEFT] && the_node->child[RBT_RIGHT]) { - target = the_node->child[RBT_LEFT]; /* find max in node->child[RBT_LEFT] */ - while (target->child[RBT_RIGHT]) target = target->child[RBT_RIGHT]; + if ( the_node->child[ RBT_LEFT ] && the_node->child[ RBT_RIGHT ] ) { + target = the_node->child[ RBT_LEFT ]; /* find max in node->child[RBT_LEFT] */ + + while ( target->child[ RBT_RIGHT ] ) + target = target->child[ RBT_RIGHT ]; /* if the target node has a child, need to move it up the tree into * target's position (target is the right child of target->parent) @@ -134,28 +144,33 @@ void _RBTree_Extract( * should become NULL. This may cause the coloring to be violated. * For now we store the color of the node being deleted in victim_color. */ - leaf = target->child[RBT_LEFT]; - if(leaf) { + leaf = target->child[ RBT_LEFT ]; + + if ( leaf ) { leaf->parent = target->parent; } else { /* fix the tree here if the child is a null leaf. */ - _RBTree_Extract_validate(target); + _RBTree_Extract_validate( target ); } + victim_color = target->color; - dir = target != target->parent->child[0]; - target->parent->child[dir] = leaf; + dir = target != target->parent->child[ 0 ]; + target->parent->child[ dir ] = leaf; /* now replace the_node with target */ - dir = the_node != the_node->parent->child[0]; - the_node->parent->child[dir] = target; + dir = the_node != the_node->parent->child[ 0 ]; + the_node->parent->child[ dir ] = target; /* set target's new children to the original node's children */ - target->child[RBT_RIGHT] = the_node->child[RBT_RIGHT]; - if (the_node->child[RBT_RIGHT]) - the_node->child[RBT_RIGHT]->parent = target; - target->child[RBT_LEFT] = the_node->child[RBT_LEFT]; - if (the_node->child[RBT_LEFT]) - the_node->child[RBT_LEFT]->parent = target; + target->child[ RBT_RIGHT ] = the_node->child[ RBT_RIGHT ]; + + if ( the_node->child[ RBT_RIGHT ] ) + the_node->child[ RBT_RIGHT ]->parent = target; + + target->child[ RBT_LEFT ] = the_node->child[ RBT_LEFT ]; + + if ( the_node->child[ RBT_LEFT ] ) + the_node->child[ RBT_LEFT ]->parent = target; /* finally, update the parent node and recolor. target has completely * replaced the_node, and target's child has moved up the tree if needed. @@ -170,19 +185,21 @@ void _RBTree_Extract( * violated. We will fix it later. * For now we store the color of the node being deleted in victim_color. */ - leaf = the_node->child[RBT_LEFT] ? - the_node->child[RBT_LEFT] : the_node->child[RBT_RIGHT]; - if( leaf ) { + leaf = the_node->child[ RBT_LEFT ] ? + the_node->child[ RBT_LEFT ] : the_node->child[ RBT_RIGHT ]; + + if ( leaf ) { leaf->parent = the_node->parent; } else { /* fix the tree here if the child is a null leaf. */ - _RBTree_Extract_validate(the_node); + _RBTree_Extract_validate( the_node ); } + victim_color = the_node->color; /* remove the_node from the tree */ - dir = the_node != the_node->parent->child[0]; - the_node->parent->child[dir] = leaf; + dir = the_node != the_node->parent->child[ 0 ]; + the_node->parent->child[ dir ] = leaf; } /* fix coloring. leaf has moved up the tree. The color of the deleted @@ -190,15 +207,16 @@ void _RBTree_Extract( * 1. Deleted a red node, its child must be black. Nothing must be done. * 2. Deleted a black node, its child must be red. Paint child black. */ - if (victim_color == RBT_BLACK) { /* eliminate case 1 */ - if (leaf) { + if ( victim_color == RBT_BLACK ) { /* eliminate case 1 */ + if ( leaf ) { leaf->color = RBT_BLACK; /* case 2 */ } } /* Wipe the_node */ - _RBTree_Set_off_rbtree(the_node); + _RBTree_Set_off_rbtree( the_node ); /* set root to black, if it exists */ - if (the_rbtree->root) the_rbtree->root->color = RBT_BLACK; + if ( the_rbtree->root ) + the_rbtree->root->color = RBT_BLACK; } -- cgit v1.2.3