[PATCH 1/3] rbtree: Format
Sebastian Huber
sebastian.huber at embedded-brains.de
Mon Jul 21 16:31:57 UTC 2014
---
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
More information about the devel
mailing list