Changeset 993f5ac in rtems


Ignore:
Timestamp:
07/23/14 11:03:54 (9 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
4.11, 5, master
Children:
0ef6e3bf
Parents:
4752550f
git-author:
Sebastian Huber <sebastian.huber@…> (07/23/14 11:03:54)
git-committer:
Sebastian Huber <sebastian.huber@…> (08/07/14 13:59:29)
Message:

rbtree: Simplify insert and extract

Simplify _RBTree_Insert() and _RBTree_Extract(). Remove more
superfluous NULL pointer checks. Change _RBTree_Is_root() to use only
the node. Add parent parameter to _RBTree_Sibling(). Delete
_RBTree_Grandparent() and _RBTree_Parent_sibling().

Files:
6 edited

Legend:

Unmodified
Added
Removed

  • cpukit/sapi/include/rtems/rbtree.h

    r4752550f r993f5ac  
    196196
    197197/**
    198  * @brief Return pointer to the parent child node from this node.
    199  *
    200  * This function returns a pointer to the parent node of @a the_node.
     198 * @copydoc _RBTree_Parent()
    201199 */
    202200RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_parent(
    … …  
    249247
    250248/**
    251  * @brief Is this node the RBTree root.
    252  *
    253  * This function returns true if @a the_node is the root of @a the_rbtree and
    254  * false otherwise.
     249 * @copydoc _RBTree_Is_root()
    255250 */
    256251RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
    257   const rtems_rbtree_control *the_rbtree,
    258   const rtems_rbtree_node *the_node
    259 )
    260 {
    261   return _RBTree_Is_root( the_rbtree, the_node );
     252  const rtems_rbtree_node *the_node
     253)
     254{
     255  return _RBTree_Is_root( the_node );
    262256}
    263257

  • cpukit/score/include/rtems/score/rbtree.h

    r4752550f r993f5ac  
    301301
    302302/**
    303  * @brief Return pointer to RBTree's root node.
    304  *
    305  * This function returns a pointer to the root node of @a the_rbtree.
     303 * @brief Returns a pointer to root node of the red-black tree.
     304 *
     305 * The root node may change after insert or extract operations.
     306 *
     307 * @param[in] the_rbtree The red-black tree control.
     308 *
     309 * @retval NULL The tree is empty.
     310 * @retval root The root node.
     311 *
     312 * @see _RBTree_Is_root().
    306313 */
    307314RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
    … …  
    327334
    328335/**
    329  * @brief Return pointer to the parent of this node.
    330  *
    331  * This function returns a pointer to the parent node of @a the_node.
     336 * @brief Returns a pointer to the parent of this node.
     337 *
     338 * The node must have a parent, thus it is invalid to use this function for the
     339 * root node or a node that is not part of a tree.  To test for the root node
     340 * compare with _RBTree_Root() or use _RBTree_Is_root().
     341 *
     342 * @param[in] the_node The node of interest.
     343 *
     344 * @retval parent The parent of this node.
     345 * @retval undefined The node is the root node or not part of a tree.
    332346 */
    333347RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
    … …  
    335349)
    336350{
    337   if (!the_node->parent->parent) return NULL;
    338351  return the_node->parent;
    339352}
    … …  
    410423
    411424/**
    412  * @brief Is this node the RBTree root.
    413  *
    414  * This function returns true if @a the_node is the root of @a the_rbtree and
     425 * @brief Returns true if this node is the root node of a red-black tree, and
    415426 * false otherwise.
    416427 *
    417  * @retval true @a the_node is the root of @a the_rbtree.
    418  * @retval false @a the_node is not the root of @a the_rbtree.
     428 * The root node may change after insert or extract operations.  In case the
     429 * node is not a node of a tree, then this function yields unpredictable
     430 * results.
     431 *
     432 * @param[in] the_node The node of interest.
     433 *
     434 * @retval true The node is the root node.
     435 * @retval false Otherwise.
     436 *
     437 * @see _RBTree_Root().
    419438 */
    420439RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
    421   const RBTree_Control *the_rbtree,
    422   const RBTree_Node    *the_node
    423 )
    424 {
    425   return (the_node == _RBTree_Root(the_rbtree));
     440  const RBTree_Node *the_node
     441)
     442{
     443  return _RBTree_Parent( _RBTree_Parent( the_node ) ) == NULL;
    426444}
    427445

  • cpukit/score/include/rtems/score/rbtreeimpl.h

    r4752550f r993f5ac  
    108108
    109109/**
    110  * @brief Return a pointer to node's grandparent.
    111  *
    112  * This function returns a pointer to the grandparent of @a the_node if it
    113  * exists, and NULL if not.
    114  */
    115 RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent(
    116   const RBTree_Node *the_node
    117 )
    118 {
    119   if(!the_node) return NULL;
    120   if(!(the_node->parent)) return NULL;
    121   if(!(the_node->parent->parent)) return NULL;
    122   if(!(the_node->parent->parent->parent)) return NULL;
    123   return(the_node->parent->parent);
    124 }
    125 
    126 /**
    127  * @brief Return a pointer to node's sibling.
    128  *
    129  * This function returns a pointer to the sibling of @a the_node if it
    130  * exists, and NULL if not.
     110 * @brief Returns the sibling of the node.
     111 *
     112 * @param[in] the_node The node of interest.
     113 * @param[in] parent The parent of the node.  The parent must exist, thus it is
     114 * invalid to use this function for the root node.
     115 *
     116 * @retval NULL No sibling exists.
     117 * @retval sibling The sibling of the node.
    131118 */
    132119RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling(
    133   const RBTree_Node *the_node
    134 )
    135 {
    136   if(!the_node) return NULL;
    137   if(!(the_node->parent)) return NULL;
    138   if(!(the_node->parent->parent)) return NULL;
    139 
    140   if(the_node == the_node->parent->child[RBT_LEFT])
    141     return the_node->parent->child[RBT_RIGHT];
    142   else
    143     return the_node->parent->child[RBT_LEFT];
    144 }
    145 
    146 /**
    147  * @brief Return a pointer to node's parent's sibling.
    148  *
    149  * This function returns a pointer to the sibling of the parent of
    150  * @a the_node if it exists, and NULL if not.
    151  */
    152 RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling(
    153   const RBTree_Node *the_node
    154 )
    155 {
    156   if(!the_node) return NULL;
    157   if(_RBTree_Grandparent(the_node) == NULL) return NULL;
    158 
    159   return _RBTree_Sibling(the_node->parent);
     120  const RBTree_Node *the_node,
     121  const RBTree_Node *parent
     122)
     123{
     124  RBTree_Node *left_child = parent->child[ RBT_LEFT ];
     125
     126  return the_node == left_child ? parent->child[ RBT_RIGHT ] : left_child;
    160127}
    161128

  • cpukit/score/src/rbtreeextract.c

    r4752550f r993f5ac  
    2323static void _RBTree_Extract_validate( RBTree_Node *the_node )
    2424{
    25   RBTree_Node     *parent, *sibling;
     25  RBTree_Node     *parent;
    2626  RBTree_Direction dir;
    2727
    … …  
    3131    return;
    3232
    33   sibling = _RBTree_Sibling( the_node );
    34 
    3533  /* continue to correct tree as long as the_node is black and not the root */
    3634  while ( !_RBTree_Is_red( the_node ) && parent->parent ) {
     35    RBTree_Node *sibling = _RBTree_Sibling( the_node, parent );
     36
    3737    /* if sibling is red, switch parent (black) and sibling colors,
    3838     * then rotate parent left, making the sibling be the_node's grandparent.
    … …  
    6060      the_node = parent;   /* done if parent is red */
    6161      parent = the_node->parent;
    62       sibling = _RBTree_Sibling( the_node );
    6362    } else {
    6463      /* at least one of sibling's children is red. we now proceed in two

  • cpukit/score/src/rbtreeinsert.c

    r4752550f r993f5ac  
    3333static void _RBTree_Validate_insert( RBTree_Node *the_node )
    3434{
    35   RBTree_Node *u, *g;
     35  RBTree_Node *parent = _RBTree_Parent( the_node );
     36  RBTree_Node *grandparent = _RBTree_Parent( parent );
    3637
    3738  /* note: the insert root case is handled already */
    3839  /* if the parent is black, nothing needs to be done
    3940   * otherwise may need to loop a few times */
    40   while ( _RBTree_Is_red( _RBTree_Parent( the_node ) ) ) {
    41     u = _RBTree_Parent_sibling( the_node );
    42     g = the_node->parent->parent;
     41  while ( parent->color == RBT_RED ) {
     42    /* The root is black, so the grandparent must exist */
     43    RBTree_Node *uncle = _RBTree_Sibling( parent, grandparent );
    4344
    44     /* if uncle is red, repaint uncle/parent black and grandparent red */
    45     if ( _RBTree_Is_red( u ) ) {
    46       the_node->parent->color = RBT_BLACK;
    47       u->color = RBT_BLACK;
    48       g->color = RBT_RED;
    49       the_node = g;
    50     } else { /* if uncle is black */
    51       RBTree_Direction dir = the_node != the_node->parent->child[ 0 ];
    52       RBTree_Direction pdir = the_node->parent != g->child[ 0 ];
     45    /*
     46     * If uncle exists and is red, repaint uncle/parent black and grandparent
     47     * red.
     48     */
     49    if ( uncle != NULL && uncle->color == RBT_RED ) {
     50      parent->color = RBT_BLACK;
     51      uncle->color = RBT_BLACK;
     52      grandparent->color = RBT_RED;
     53      the_node = grandparent;
     54      parent = _RBTree_Parent( the_node );
     55      grandparent = _RBTree_Parent( parent );
     56
     57      if ( grandparent == NULL )
     58        break;
     59    } else { /* If uncle does not exist or is black */
     60      RBTree_Direction dir = _RBTree_Direction( the_node, parent );
     61      RBTree_Direction parentdir = _RBTree_Direction( parent, grandparent );
    5362
    5463      /* ensure node is on the same branch direction as parent */
    55       if ( dir != pdir ) {
    56         _RBTree_Rotate( the_node->parent, pdir );
    57         the_node = the_node->child[ pdir ];
     64      if ( dir != parentdir ) {
     65        RBTree_Node *oldparent = parent;
     66
     67        parent = the_node;
     68        the_node = oldparent;
     69        _RBTree_Rotate( oldparent, parentdir );
    5870      }
    5971
    60       the_node->parent->color = RBT_BLACK;
    61       g->color = RBT_RED;
     72      parent->color = RBT_BLACK;
     73      grandparent->color = RBT_RED;
    6274
    6375      /* now rotate grandparent in the other branch direction (toward uncle) */
    64       _RBTree_Rotate( g, ( 1 - pdir ) );
     76      _RBTree_Rotate( grandparent, _RBTree_Opposite_direction( parentdir ) );
     77
     78      grandparent = _RBTree_Parent( parent );
     79      break;
    6580    }
    6681  }
    6782
    68   if ( !the_node->parent->parent )
     83  if ( grandparent == NULL )
    6984    the_node->color = RBT_BLACK;
    7085}

  • testsuites/sptests/sprbtree01/init.c

    r4752550f r993f5ac  
    817817
    818818  if ( td->parent == NULL ) {
    819     rtems_test_assert( td->parent == tn->Node.parent->parent );
     819    rtems_test_assert( rtems_rbtree_is_root( &tn->Node ) );
    820820  } else {
    821     rtems_test_assert( td->parent == tn->Node.parent );
    822   }
    823 
    824   rtems_test_assert( td->left == tn->Node.child[ RBT_LEFT ] );
    825   rtems_test_assert( td->right == tn->Node.child[ RBT_RIGHT ] );
     821    rtems_test_assert( td->parent == rtems_rbtree_parent( &tn->Node ) );
     822  }
     823
     824  rtems_test_assert( td->left == rtems_rbtree_left( &tn->Node ) );
     825  rtems_test_assert( td->right == rtems_rbtree_right( &tn->Node ) );
    826826  rtems_test_assert( td->color == tn->Node.color );
    827827
    … …  
    11951195  }
    11961196
    1197   if ( _RBTree_Sibling( NULL ) != NULL )
    1198     puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" );
    1199   if ( _RBTree_Sibling( rbtree1.root ) != NULL )
    1200     puts ( "INIT - ERROR ON RBTREE NULL SIBLING MISMATCH" );
    1201   if ( _RBTree_Grandparent( NULL ) != NULL )
    1202     puts ( "INIT - ERROR ON RBTREE NULL GRANDPARENT MISMATCH" );
    12031197  if ( _RBTree_Is_red( NULL ) != 0 )
    12041198    puts ( "INIT - ERROR ON RBTREE NULL IS RED MISMATCH" );
Note: See TracChangeset for help on using the changeset viewer.