RBTree Successor and Predecessor

[Sebastian Huber]

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.

[Gedare Bloom]

Patch.

[Gedare Bloom]

Updated patch.

[Sebastian Huber]

​http://git.rtems.org/rtems/commit/?id=dc62a48cc5fc95f9bbe7ab2ed2712b70987bde6f

[Gedare Bloom]

Replace Version=HEAD with Version=4.11 for the tickets with Milestone >= 4.11