[Bug 1995] New: RBTree Successor and Predecessor

[bugzilla-daemon at rtems.org]

https://www.rtems.org/bugzilla/show_bug.cgi?id=1995

           Summary: RBTree Successor and Predecessor
           Product: RTEMS
           Version: HEAD
          Platform: All
        OS/Version: RTEMS
            Status: NEW
          Severity: normal
          Priority: P3
         Component: cpukit
        AssignedTo: joel.sherrill at oarcorp.com
        ReportedBy: sebastian.huber at embedded-brains.de


The _RBTree_Successor() and _RBTree_Predecessor() are quite heavy for inline
functions.  They should implemented in a source file.  Due to the left and
right symmetry they can also share a common implementation:

const RBTree_Node *_RBTree_Immutable_next(
  const RBTree_Control *rbtree,
  const RBTree_Node *node,
  RBTree_Direction dir
)
{
  RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
  const RBTree_Node *current = node->child [dir];
  const RBTree_Node *next = NULL;

  if (current != NULL) {
    next = current;
    while ((current = current->child [opp_dir]) != NULL) {
      next = current;
    }
  } else {
    const RBTree_Node *null = (const RBTree_Node *) rbtree;
    const RBTree_Node *parent = node->parent;

    if (parent != null && node == parent->child [opp_dir]) {
      next = parent;
    } else {
      while (parent != null && node == parent->child [dir]) {
        node = parent;
        parent = node->parent;
      }

      if (parent != null) {
        next = parent;
      }
    }
  }

  return next;
}

This implementation fixes several bugs.  It can be used to implement the
following iteration routine:

void _RBTree_Iterate(
  const RBTree_Control *rbtree,
  RBTree_Direction dir,
  RBTree_Node_visitor visitor,
  void *visitor_arg
)
{
  RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir );
  const RBTree_Node *current = _RBTree_Immutable_first( rbtree, opp_dir );
  bool stop = false;

  while ( !stop && current != NULL ) {
    RBTree_Node *next = _RBTree_Immutable_next( rbtree, current, dir );

    stop = (*visitor)( current, dir, visitor_arg );

    current = next;
  }
}

It is a bit ugly to use

    const RBTree_Node *null = (const RBTree_Node *) rbtree;

to test for the root node.  One problem is that we need access to the RBTree
control structure to get the next node.  I guess this root node construction is
necessary on other places and is difficult to change?  The other problem is the
cast.  This may be solved analogues to the Chain_Control union.

-- 
Configure bugmail: https://www.rtems.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching all bug changes.