Changeset 6b0a7efc in rtems


Ignore:
Timestamp:
07/21/14 16:08:07 (9 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
4.11, 5, master
Children:
d7a94693
Parents:
87894c0
git-author:
Sebastian Huber <sebastian.huber@…> (07/21/14 16:08:07)
git-committer:
Sebastian Huber <sebastian.huber@…> (07/22/14 10:30:53)
Message:

rbtree: Format

Location:
cpukit/score/src
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • cpukit/score/src/rbtree.c

    r87894c0 r6b0a7efc  
    3232)
    3333{
    34   size_t      count;
     34  size_t       count;
    3535  RBTree_Node *next;
    3636
    3737  /* TODO: Error message? */
    38   if (!the_rbtree) return;
     38  if ( !the_rbtree )
     39    return;
    3940
    4041  /* could do sanity checks here */
    … …  
    4243
    4344  count = number_nodes;
    44   next  = starting_address;
     45  next = starting_address;
     46
    4547  while ( count-- ) {
    4648    _RBTree_Insert( the_rbtree, next, compare, is_unique );

  • cpukit/score/src/rbtreeextract.c

    r87894c0 r6b0a7efc  
    2222 *        of the extract operation.
    2323 */
    24 static void _RBTree_Extract_validate(
    25     RBTree_Node *the_node
    26     )
     24static void _RBTree_Extract_validate( RBTree_Node *the_node )
    2725{
    28   RBTree_Node *parent, *sibling;
     26  RBTree_Node     *parent, *sibling;
    2927  RBTree_Direction dir;
    3028
    3129  parent = the_node->parent;
    32   if(!parent->parent) return;
    33 
    34   sibling = _RBTree_Sibling(the_node);
     30
     31  if ( !parent->parent )
     32    return;
     33
     34  sibling = _RBTree_Sibling( the_node );
    3535
    3636  /* continue to correct tree as long as the_node is black and not the root */
    37   while (!_RBTree_Is_red(the_node) && parent->parent) {
    38 
     37  while ( !_RBTree_Is_red( the_node ) && parent->parent ) {
    3938    /* if sibling is red, switch parent (black) and sibling colors,
    4039     * then rotate parent left, making the sibling be the_node's grandparent.
    … …  
    4241     * update sibling pointer.
    4342     */
    44     if (_RBTree_Is_red(sibling)) {
     43    if ( _RBTree_Is_red( sibling ) ) {
    4544      parent->color = RBT_RED;
    4645      sibling->color = RBT_BLACK;
    47       dir = the_node != parent->child[0];
    48       _RBTree_Rotate(parent, dir);
    49       sibling = parent->child[_RBTree_Opposite_direction(dir)];
     46      dir = the_node != parent->child[ 0 ];
     47      _RBTree_Rotate( parent, dir );
     48      sibling = parent->child[ _RBTree_Opposite_direction( dir ) ];
    5049    }
    5150
    5251    /* sibling is black, see if both of its children are also black. */
    53     if (!_RBTree_Is_red(sibling->child[RBT_RIGHT]) &&
    54         !_RBTree_Is_red(sibling->child[RBT_LEFT])) {
    55         sibling->color = RBT_RED;
    56         if (_RBTree_Is_red(parent)) {
    57           parent->color = RBT_BLACK;
    58           break;
    59         }
    60         the_node = parent; /* done if parent is red */
    61         parent = the_node->parent;
    62         sibling = _RBTree_Sibling(the_node);
     52    if ( !_RBTree_Is_red( sibling->child[ RBT_RIGHT ] ) &&
     53         !_RBTree_Is_red( sibling->child[ RBT_LEFT ] ) ) {
     54      sibling->color = RBT_RED;
     55
     56      if ( _RBTree_Is_red( parent ) ) {
     57        parent->color = RBT_BLACK;
     58        break;
     59      }
     60
     61      the_node = parent;   /* done if parent is red */
     62      parent = the_node->parent;
     63      sibling = _RBTree_Sibling( the_node );
    6364    } else {
    6465      /* at least one of sibling's children is red. we now proceed in two
    … …  
    6869       * Then switch the sibling and parent colors, and rotate through parent.
    6970       */
    70       dir = the_node != parent->child[0];
    71       if (!_RBTree_Is_red(sibling->child[_RBTree_Opposite_direction(dir)])) {
     71      dir = the_node != parent->child[ 0 ];
     72
     73      if (
     74        !_RBTree_Is_red( sibling->child[ _RBTree_Opposite_direction( dir ) ] )
     75      ) {
    7276        sibling->color = RBT_RED;
    73         sibling->child[dir]->color = RBT_BLACK;
    74         _RBTree_Rotate(sibling, _RBTree_Opposite_direction(dir));
    75         sibling = parent->child[_RBTree_Opposite_direction(dir)];
     77        sibling->child[ dir ]->color = RBT_BLACK;
     78        _RBTree_Rotate( sibling, _RBTree_Opposite_direction( dir ) );
     79        sibling = parent->child[ _RBTree_Opposite_direction( dir ) ];
    7680      }
     81
    7782      sibling->color = parent->color;
    7883      parent->color = RBT_BLACK;
    79       sibling->child[_RBTree_Opposite_direction(dir)]->color = RBT_BLACK;
    80       _RBTree_Rotate(parent, dir);
     84      sibling->child[ _RBTree_Opposite_direction( dir ) ]->color = RBT_BLACK;
     85      _RBTree_Rotate( parent, dir );
    8186      break; /* done */
    8287    }
    8388  } /* while */
    84   if(!the_node->parent->parent) the_node->color = RBT_BLACK;
     89
     90  if ( !the_node->parent->parent )
     91    the_node->color = RBT_BLACK;
    8592}
    8693
    … …  
    93100 */
    94101void _RBTree_Extract(
    95     RBTree_Control *the_rbtree,
    96     RBTree_Node *the_node
    97     )
     102  RBTree_Control *the_rbtree,
     103  RBTree_Node    *the_node
     104)
    98105{
    99   RBTree_Node *leaf, *target;
    100   RBTree_Color victim_color;
     106  RBTree_Node     *leaf, *target;
     107  RBTree_Color     victim_color;
    101108  RBTree_Direction dir;
    102109
    103   if (!the_node) return;
     110  if ( !the_node )
     111    return;
    104112
    105113  /* check if min needs to be updated */
    106   if (the_node == the_rbtree->first[RBT_LEFT]) {
     114  if ( the_node == the_rbtree->first[ RBT_LEFT ] ) {
    107115    RBTree_Node *next;
    108     next = _RBTree_Successor(the_node);
    109     the_rbtree->first[RBT_LEFT] = next;
     116    next = _RBTree_Successor( the_node );
     117    the_rbtree->first[ RBT_LEFT ] = next;
    110118  }
    111119
    112120  /* Check if max needs to be updated. min=max for 1 element trees so
    113121   * do not use else if here. */
    114   if (the_node == the_rbtree->first[RBT_RIGHT]) {
     122  if ( the_node == the_rbtree->first[ RBT_RIGHT ] ) {
    115123    RBTree_Node *previous;
    116     previous = _RBTree_Predecessor(the_node);
    117     the_rbtree->first[RBT_RIGHT] = previous;
     124    previous = _RBTree_Predecessor( the_node );
     125    the_rbtree->first[ RBT_RIGHT ] = previous;
    118126  }
    119127
    … …  
    125133   */
    126134
    127   if (the_node->child[RBT_LEFT] && the_node->child[RBT_RIGHT]) {
    128     target = the_node->child[RBT_LEFT]; /* find max in node->child[RBT_LEFT] */
    129     while (target->child[RBT_RIGHT]) target = target->child[RBT_RIGHT];
     135  if ( the_node->child[ RBT_LEFT ] && the_node->child[ RBT_RIGHT ] ) {
     136    target = the_node->child[ RBT_LEFT ]; /* find max in node->child[RBT_LEFT] */
     137
     138    while ( target->child[ RBT_RIGHT ] )
     139      target = target->child[ RBT_RIGHT ];
    130140
    131141    /* if the target node has a child, need to move it up the tree into
    … …  
    135145     * For now we store the color of the node being deleted in victim_color.
    136146     */
    137     leaf = target->child[RBT_LEFT];
    138     if(leaf) {
     147    leaf = target->child[ RBT_LEFT ];
     148
     149    if ( leaf ) {
    139150      leaf->parent = target->parent;
    140151    } else {
    141152      /* fix the tree here if the child is a null leaf. */
    142       _RBTree_Extract_validate(target);
    143     }
     153      _RBTree_Extract_validate( target );
     154    }
     155
    144156    victim_color = target->color;
    145     dir = target != target->parent->child[0];
    146     target->parent->child[dir] = leaf;
     157    dir = target != target->parent->child[ 0 ];
     158    target->parent->child[ dir ] = leaf;
    147159
    148160    /* now replace the_node with target */
    149     dir = the_node != the_node->parent->child[0];
    150     the_node->parent->child[dir] = target;
     161    dir = the_node != the_node->parent->child[ 0 ];
     162    the_node->parent->child[ dir ] = target;
    151163
    152164    /* set target's new children to the original node's children */
    153     target->child[RBT_RIGHT] = the_node->child[RBT_RIGHT];
    154     if (the_node->child[RBT_RIGHT])
    155       the_node->child[RBT_RIGHT]->parent = target;
    156     target->child[RBT_LEFT] = the_node->child[RBT_LEFT];
    157     if (the_node->child[RBT_LEFT])
    158       the_node->child[RBT_LEFT]->parent = target;
     165    target->child[ RBT_RIGHT ] = the_node->child[ RBT_RIGHT ];
     166
     167    if ( the_node->child[ RBT_RIGHT ] )
     168      the_node->child[ RBT_RIGHT ]->parent = target;
     169
     170    target->child[ RBT_LEFT ] = the_node->child[ RBT_LEFT ];
     171
     172    if ( the_node->child[ RBT_LEFT ] )
     173      the_node->child[ RBT_LEFT ]->parent = target;
    159174
    160175    /* finally, update the parent node and recolor. target has completely
    … …  
    171186     * For now we store the color of the node being deleted in victim_color.
    172187     */
    173     leaf = the_node->child[RBT_LEFT] ?
    174               the_node->child[RBT_LEFT] : the_node->child[RBT_RIGHT];
    175     if( leaf ) {
     188    leaf = the_node->child[ RBT_LEFT ] ?
     189           the_node->child[ RBT_LEFT ] : the_node->child[ RBT_RIGHT ];
     190
     191    if ( leaf ) {
    176192      leaf->parent = the_node->parent;
    177193    } else {
    178194      /* fix the tree here if the child is a null leaf. */
    179       _RBTree_Extract_validate(the_node);
    180     }
     195      _RBTree_Extract_validate( the_node );
     196    }
     197
    181198    victim_color = the_node->color;
    182199
    183200    /* remove the_node from the tree */
    184     dir = the_node != the_node->parent->child[0];
    185     the_node->parent->child[dir] = leaf;
     201    dir = the_node != the_node->parent->child[ 0 ];
     202    the_node->parent->child[ dir ] = leaf;
    186203  }
    187204
    … …  
    191208   *   2. Deleted a black node, its child must be red. Paint child black.
    192209   */
    193   if (victim_color == RBT_BLACK) { /* eliminate case 1 */
    194     if (leaf) {
     210  if ( victim_color == RBT_BLACK ) { /* eliminate case 1 */
     211    if ( leaf ) {
    195212      leaf->color = RBT_BLACK; /* case 2 */
    196213    }
    … …  
    198215
    199216  /* Wipe the_node */
    200   _RBTree_Set_off_rbtree(the_node);
     217  _RBTree_Set_off_rbtree( the_node );
    201218
    202219  /* set root to black, if it exists */
    203   if (the_rbtree->root) the_rbtree->root->color = RBT_BLACK;
     220  if ( the_rbtree->root )
     221    the_rbtree->root->color = RBT_BLACK;
    204222}

  • cpukit/score/src/rbtreefind.c

    r87894c0 r6b0a7efc  
    2727)
    2828{
    29   RBTree_Node* iter_node = the_rbtree->root;
    30   RBTree_Node* found = NULL;
     29  RBTree_Node *iter_node = the_rbtree->root;
     30  RBTree_Node *found = NULL;
    3131
    3232  while ( iter_node != NULL ) {
    33     int compare_result = ( *compare )( the_node, iter_node );
     33    int              compare_result = ( *compare )( the_node, iter_node );
    3434    RBTree_Direction dir;
    3535
    3636    if ( _RBTree_Is_equal( compare_result ) ) {
    3737      found = iter_node;
     38
    3839      if ( is_unique )
    3940        break;

  • cpukit/score/src/rbtreeinsert.c

    r87894c0 r6b0a7efc  
    2222 *        append operation.
    2323 */
    24 static void _RBTree_Validate_insert(
    25     RBTree_Node    *the_node
    26     )
     24static void _RBTree_Validate_insert( RBTree_Node *the_node )
    2725{
    28   RBTree_Node *u,*g;
     26  RBTree_Node *u, *g;
    2927
    3028  /* note: the insert root case is handled already */
    3129  /* if the parent is black, nothing needs to be done
    3230   * otherwise may need to loop a few times */
    33   while (_RBTree_Is_red(_RBTree_Parent(the_node))) {
    34     u = _RBTree_Parent_sibling(the_node);
     31  while ( _RBTree_Is_red( _RBTree_Parent( the_node ) ) ) {
     32    u = _RBTree_Parent_sibling( the_node );
    3533    g = the_node->parent->parent;
    3634
    3735    /* if uncle is red, repaint uncle/parent black and grandparent red */
    38     if(_RBTree_Is_red(u)) {
     36    if ( _RBTree_Is_red( u ) ) {
    3937      the_node->parent->color = RBT_BLACK;
    4038      u->color = RBT_BLACK;
    … …  
    4240      the_node = g;
    4341    } else { /* if uncle is black */
    44       RBTree_Direction dir = the_node != the_node->parent->child[0];
    45       RBTree_Direction pdir = the_node->parent != g->child[0];
     42      RBTree_Direction dir = the_node != the_node->parent->child[ 0 ];
     43      RBTree_Direction pdir = the_node->parent != g->child[ 0 ];
    4644
    4745      /* ensure node is on the same branch direction as parent */
    48       if (dir != pdir) {
    49         _RBTree_Rotate(the_node->parent, pdir);
    50         the_node = the_node->child[pdir];
     46      if ( dir != pdir ) {
     47        _RBTree_Rotate( the_node->parent, pdir );
     48        the_node = the_node->child[ pdir ];
    5149      }
     50
    5251      the_node->parent->color = RBT_BLACK;
    5352      g->color = RBT_RED;
    5453
    5554      /* now rotate grandparent in the other branch direction (toward uncle) */
    56       _RBTree_Rotate(g, (1-pdir));
     55      _RBTree_Rotate( g, ( 1 - pdir ) );
    5756    }
    5857  }
    59   if(!the_node->parent->parent) the_node->color = RBT_BLACK;
     58
     59  if ( !the_node->parent->parent )
     60    the_node->color = RBT_BLACK;
    6061}
    6162
    … …  
    6768)
    6869{
    69   if(!the_node) return (RBTree_Node*)-1;
     70  if ( !the_node )
     71    return (RBTree_Node *) -1;
    7072
    7173  RBTree_Node *iter_node = the_rbtree->root;
    72   int compare_result;
    7374
    74   if (!iter_node) { /* special case: first node inserted */
     75  if ( !iter_node ) { /* special case: first node inserted */
    7576    the_node->color = RBT_BLACK;
    7677    the_rbtree->root = the_node;
    77     the_rbtree->first[0] = the_rbtree->first[1] = the_node;
     78    the_rbtree->first[ 0 ] = the_rbtree->first[ 1 ] = the_node;
    7879    the_node->parent = (RBTree_Node *) the_rbtree;
    79     the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
     80    the_node->child[ RBT_LEFT ] = the_node->child[ RBT_RIGHT ] = NULL;
    8081  } else {
    8182    /* typical binary search tree insert, descend tree to leaf and insert */
    82     while (iter_node) {
    83       compare_result = ( *compare )( the_node, iter_node );
     83    while ( iter_node ) {
     84      int compare_result = ( *compare )( the_node, iter_node );
     85
    8486      if ( is_unique && _RBTree_Is_equal( compare_result ) )
    8587        return iter_node;
     88
    8689      RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
    87       if (!iter_node->child[dir]) {
    88         the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
     90
     91      if ( !iter_node->child[ dir ] ) {
     92        the_node->child[ RBT_LEFT ] = the_node->child[ RBT_RIGHT ] = NULL;
    8993        the_node->color = RBT_RED;
    90         iter_node->child[dir] = the_node;
     94        iter_node->child[ dir ] = the_node;
    9195        the_node->parent = iter_node;
    9296        /* update min/max */
    … …  
    9599          _RBTree_First( the_rbtree, dir )
    96100        );
    97         if ( (!dir && _RBTree_Is_lesser(compare_result)) ||
    98               (dir && _RBTree_Is_greater(compare_result)) ) {
    99           the_rbtree->first[dir] = the_node;
     101
     102        if (
     103          ( !dir && _RBTree_Is_lesser( compare_result ) )
     104            || ( dir && _RBTree_Is_greater( compare_result ) )
     105        ) {
     106          the_rbtree->first[ dir ] = the_node;
    100107        }
     108
    101109        break;
    102110      } else {
    103         iter_node = iter_node->child[dir];
     111        iter_node = iter_node->child[ dir ];
    104112      }
    105 
    106113    } /* while(iter_node) */
    107114
    108115    /* verify red-black properties */
    109     _RBTree_Validate_insert(the_node);
     116    _RBTree_Validate_insert( the_node );
    110117  }
    111   return (RBTree_Node*)0;
     118
     119  return (RBTree_Node *) 0;
    112120}

  • cpukit/score/src/rbtreeiterate.c

    r87894c0 r6b0a7efc  
    2929void _RBTree_Iterate(
    3030  const RBTree_Control *rbtree,
    31   RBTree_Direction dir,
    32   RBTree_Visitor visitor,
    33   void *visitor_arg
     31  RBTree_Direction      dir,
     32  RBTree_Visitor        visitor,
     33  void                 *visitor_arg
    3434)
    3535{
    36   RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
     36  RBTree_Direction   opp_dir = _RBTree_Opposite_direction( dir );
    3737  const RBTree_Node *current = _RBTree_First( rbtree, opp_dir );
    38   bool stop = false;
     38  bool               stop = false;
    3939
    4040  while ( !stop && current != NULL ) {
    41     stop = (*visitor)( current, dir, visitor_arg );
     41    stop = ( *visitor )( current, dir, visitor_arg );
    4242
    4343    current = _RBTree_Next( current, dir );

  • cpukit/score/src/rbtreenext.c

    r87894c0 r6b0a7efc  
    3030RBTree_Node *_RBTree_Next(
    3131  const RBTree_Node *node,
    32   RBTree_Direction dir
     32  RBTree_Direction   dir
    3333)
    3434{
    3535  RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
    36   RBTree_Node *current = node->child [dir];
    37   RBTree_Node *next = NULL;
     36  RBTree_Node     *current = node->child[ dir ];
     37  RBTree_Node     *next = NULL;
    3838
    3939  if ( current != NULL ) {
    4040    next = current;
    41     while ( (current = current->child [opp_dir]) != NULL ) {
     41
     42    while ( ( current = current->child[ opp_dir ] ) != NULL ) {
    4243      next = current;
    4344    }
    … …  
    4546    RBTree_Node *parent = node->parent;
    4647
    47     if ( parent->parent && node == parent->child [opp_dir] ) {
     48    if ( parent->parent && node == parent->child[ opp_dir ] ) {
    4849      next = parent;
    4950    } else {
    50       while ( parent->parent && node == parent->child [dir] ) {
     51      while ( parent->parent && node == parent->child[ dir ] ) {
    5152        node = parent;
    5253        parent = parent->parent;
Note: See TracChangeset for help on using the changeset viewer.