Changeset 993f5ac in rtems for cpukit/score/include


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().

Location:
cpukit/score/include/rtems/score
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • 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
Note: See TracChangeset for help on using the changeset viewer.