[PATCH 1/3] rbtree: Format
Gedare Bloom
gedare at rtems.org
Mon Jul 21 20:23:58 UTC 2014
One issue with rbtree formatting is in some places if/while conditional
expressions are put on the same line as the conditional statement. We
should prefer to put them explicitly on separate lines, since that is the
prevailing style of score and I have added such a convention to our style
wiki page.
On Mon, Jul 21, 2014 at 12:57 PM, Joel Sherrill <joel.sherrill at oarcorp.com>
wrote:
> There could be something wrong here but I don't see it on a quick review.
> On 7/21/2014 11:31 AM, Sebastian Huber wrote:
> > ---
> > cpukit/score/src/rbtree.c | 7 +-
> > cpukit/score/src/rbtreeextract.c | 152
> +++++++++++++++++++++------------------
> > cpukit/score/src/rbtreefind.c | 7 +-
> > cpukit/score/src/rbtreeinsert.c | 69 ++++++++++--------
> > cpukit/score/src/rbtreeiterate.c | 12 ++--
> > cpukit/score/src/rbtreenext.c | 13 ++--
> > 6 files changed, 143 insertions(+), 117 deletions(-)
> >
> > diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c
> > index 5e8520d..2138a81 100644
> > --- a/cpukit/score/src/rbtree.c
> > +++ b/cpukit/score/src/rbtree.c
> > @@ -31,17 +31,18 @@ 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;
>
Like here.
> >
> > /* 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 9e87868..2638f63 100644
> > --- a/cpukit/score/src/rbtreeextract.c
> > +++ b/cpukit/score/src/rbtreeextract.c
> > @@ -21,45 +21,45 @@
> > * @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 +67,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 +98,29 @@ 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 +130,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 +142,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 +183,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 +205,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 ad0c9fd..f767626 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 7174529..369ef26 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,53 @@ 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 f325567..8b5da1e 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 fde0bc6..2128ae5 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;
> > }
> > --
> > 1.8.1.4
> >
> > _______________________________________________
> > devel mailing list
> > devel at rtems.org
> > http://lists.rtems.org/mailman/listinfo/devel
>
> --
> Joel Sherrill, Ph.D. Director of Research & Development
> joel.sherrill at OARcorp.com On-Line Applications Research
> Ask me about RTEMS: a free RTOS Huntsville AL 35805
> Support Available (256) 722-9985
>
> _______________________________________________
> devel mailing list
> devel at rtems.org
> http://lists.rtems.org/mailman/listinfo/devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20140721/adc4f183/attachment-0002.html>
More information about the devel
mailing list