[PATCH 1/3] rbtree: Format
Joel Sherrill
joel.sherrill at oarcorp.com
Mon Jul 21 16:57:06 UTC 2014
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;
>
> /* 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
More information about the devel
mailing list