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/rbtree.c | 8 +- cpukit/score/src/rbtreeextract.c | 154 ++++++++++++++++++++++----------------- cpukit/score/src/rbtreefind.c | 7 +- cpukit/score/src/rbtreeinsert.c | 70 ++++++++++-------- cpukit/score/src/rbtreeiterate.c | 12 +-- cpukit/score/src/rbtreenext.c | 13 ++-- 6 files changed, 147 insertions(+), 117 deletions(-) diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c index 5e8520da5e..d5f758c6f9 100644 --- a/cpukit/score/src/rbtree.c +++ b/cpukit/score/src/rbtree.c @@ -31,17 +31,19 @@ void _RBTree_Initialize( bool is_unique ) { - size_t count; + size_t count; RBTree_Node *next; /* TODO: Error message? */ - if (!the_rbtree) return; + if ( !the_rbtree ) + return; /* could do sanity checks here */ _RBTree_Initialize_empty( the_rbtree ); count = number_nodes; - next = starting_address; + next = starting_address; + while ( count-- ) { _RBTree_Insert( the_rbtree, next, compare, is_unique ); next = (RBTree_Node *) _Addresses_Add_offset( next, node_size ); 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; } diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c index ad0c9fdf80..f7676260dc 100644 --- a/cpukit/score/src/rbtreefind.c +++ b/cpukit/score/src/rbtreefind.c @@ -26,15 +26,16 @@ RBTree_Node *_RBTree_Find( bool is_unique ) { - RBTree_Node* iter_node = the_rbtree->root; - RBTree_Node* found = NULL; + RBTree_Node *iter_node = the_rbtree->root; + RBTree_Node *found = NULL; while ( iter_node != NULL ) { - int compare_result = ( *compare )( the_node, iter_node ); + int compare_result = ( *compare )( the_node, iter_node ); RBTree_Direction dir; if ( _RBTree_Is_equal( compare_result ) ) { found = iter_node; + if ( is_unique ) break; } diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c index 7174529ade..c77c5748bf 100644 --- a/cpukit/score/src/rbtreeinsert.c +++ b/cpukit/score/src/rbtreeinsert.c @@ -21,42 +21,43 @@ * @note It does NOT disable interrupts to ensure the atomicity of the * append operation. */ -static void _RBTree_Validate_insert( - RBTree_Node *the_node - ) +static void _RBTree_Validate_insert( RBTree_Node *the_node ) { - RBTree_Node *u,*g; + RBTree_Node *u, *g; /* note: the insert root case is handled already */ /* if the parent is black, nothing needs to be done * otherwise may need to loop a few times */ - while (_RBTree_Is_red(_RBTree_Parent(the_node))) { - u = _RBTree_Parent_sibling(the_node); + while ( _RBTree_Is_red( _RBTree_Parent( the_node ) ) ) { + u = _RBTree_Parent_sibling( the_node ); g = the_node->parent->parent; /* if uncle is red, repaint uncle/parent black and grandparent red */ - if(_RBTree_Is_red(u)) { + if ( _RBTree_Is_red( u ) ) { the_node->parent->color = RBT_BLACK; u->color = RBT_BLACK; g->color = RBT_RED; the_node = g; } else { /* if uncle is black */ - RBTree_Direction dir = the_node != the_node->parent->child[0]; - RBTree_Direction pdir = the_node->parent != g->child[0]; + RBTree_Direction dir = the_node != the_node->parent->child[ 0 ]; + RBTree_Direction pdir = the_node->parent != g->child[ 0 ]; /* ensure node is on the same branch direction as parent */ - if (dir != pdir) { - _RBTree_Rotate(the_node->parent, pdir); - the_node = the_node->child[pdir]; + if ( dir != pdir ) { + _RBTree_Rotate( the_node->parent, pdir ); + the_node = the_node->child[ pdir ]; } + the_node->parent->color = RBT_BLACK; g->color = RBT_RED; /* now rotate grandparent in the other branch direction (toward uncle) */ - _RBTree_Rotate(g, (1-pdir)); + _RBTree_Rotate( g, ( 1 - pdir ) ); } } - if(!the_node->parent->parent) the_node->color = RBT_BLACK; + + if ( !the_node->parent->parent ) + the_node->color = RBT_BLACK; } RBTree_Node *_RBTree_Insert( @@ -66,47 +67,54 @@ RBTree_Node *_RBTree_Insert( bool is_unique ) { - if(!the_node) return (RBTree_Node*)-1; + if ( !the_node ) + return (RBTree_Node *) -1; RBTree_Node *iter_node = the_rbtree->root; - int compare_result; - if (!iter_node) { /* special case: first node inserted */ + if ( !iter_node ) { /* special case: first node inserted */ the_node->color = RBT_BLACK; the_rbtree->root = the_node; - the_rbtree->first[0] = the_rbtree->first[1] = the_node; + the_rbtree->first[ 0 ] = the_rbtree->first[ 1 ] = the_node; the_node->parent = (RBTree_Node *) the_rbtree; - the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL; + the_node->child[ RBT_LEFT ] = the_node->child[ RBT_RIGHT ] = NULL; } else { /* typical binary search tree insert, descend tree to leaf and insert */ - while (iter_node) { - compare_result = ( *compare )( the_node, iter_node ); + while ( iter_node ) { + int compare_result = ( *compare )( the_node, iter_node ); + if ( is_unique && _RBTree_Is_equal( compare_result ) ) return iter_node; + RBTree_Direction dir = !_RBTree_Is_lesser( compare_result ); - if (!iter_node->child[dir]) { - the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL; + + if ( !iter_node->child[ dir ] ) { + the_node->child[ RBT_LEFT ] = the_node->child[ RBT_RIGHT ] = NULL; the_node->color = RBT_RED; - iter_node->child[dir] = the_node; + iter_node->child[ dir ] = the_node; the_node->parent = iter_node; /* update min/max */ compare_result = ( *compare )( 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; + + if ( + ( !dir && _RBTree_Is_lesser( compare_result ) ) + || ( dir && _RBTree_Is_greater( compare_result ) ) + ) { + the_rbtree->first[ dir ] = the_node; } + break; } else { - iter_node = iter_node->child[dir]; + iter_node = iter_node->child[ dir ]; } - } /* while(iter_node) */ /* verify red-black properties */ - _RBTree_Validate_insert(the_node); + _RBTree_Validate_insert( the_node ); } - return (RBTree_Node*)0; + + return (RBTree_Node *) 0; } diff --git a/cpukit/score/src/rbtreeiterate.c b/cpukit/score/src/rbtreeiterate.c index f325567737..8b5da1ea9f 100644 --- a/cpukit/score/src/rbtreeiterate.c +++ b/cpukit/score/src/rbtreeiterate.c @@ -28,17 +28,17 @@ void _RBTree_Iterate( const RBTree_Control *rbtree, - RBTree_Direction dir, - RBTree_Visitor visitor, - void *visitor_arg + RBTree_Direction dir, + RBTree_Visitor visitor, + void *visitor_arg ) { - RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir ); + RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir ); const RBTree_Node *current = _RBTree_First( rbtree, opp_dir ); - bool stop = false; + bool stop = false; while ( !stop && current != NULL ) { - stop = (*visitor)( current, dir, visitor_arg ); + stop = ( *visitor )( current, dir, visitor_arg ); current = _RBTree_Next( current, dir ); } diff --git a/cpukit/score/src/rbtreenext.c b/cpukit/score/src/rbtreenext.c index fde0bc6c41..2128ae59bf 100644 --- a/cpukit/score/src/rbtreenext.c +++ b/cpukit/score/src/rbtreenext.c @@ -29,25 +29,26 @@ RBTree_Node *_RBTree_Next( const RBTree_Node *node, - RBTree_Direction dir + RBTree_Direction dir ) { RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir ); - RBTree_Node *current = node->child [dir]; - RBTree_Node *next = NULL; + RBTree_Node *current = node->child[ dir ]; + RBTree_Node *next = NULL; if ( current != NULL ) { next = current; - while ( (current = current->child [opp_dir]) != NULL ) { + + while ( ( current = current->child[ opp_dir ] ) != NULL ) { next = current; } } else { RBTree_Node *parent = node->parent; - if ( parent->parent && node == parent->child [opp_dir] ) { + if ( parent->parent && node == parent->child[ opp_dir ] ) { next = parent; } else { - while ( parent->parent && node == parent->child [dir] ) { + while ( parent->parent && node == parent->child[ dir ] ) { node = parent; parent = parent->parent; } -- cgit v1.2.3