rbtree: Format

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;
       }