#1995 closed defect (fixed)

RBTree Successor and Predecessor

Reported by: Sebastian Huber Owned by: Gedare Bloom
Priority: normal Milestone: 4.11
Component: score Version: 4.11
Severity: normal Keywords:
Cc: Blocked By:
Blocking:

Description

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.

Attachments (2)

0001-PR1995-RBTree-Successor-and-Predecessor.patch (11.4 KB) - added by Gedare Bloom on Mar 5, 2012 at 2:18:15 AM.
Patch.
0001-PR1995-RBTree-Successor-and-Predecessor_v1.patch (11.9 KB) - added by Gedare Bloom on Mar 5, 2012 at 3:51:41 PM.
Updated patch.

Download all attachments as: .zip

Change History (6)

comment:1 Changed on Dec 19, 2011 at 2:56:01 PM by Sebastian Huber

Owner: changed from Joel Sherrill to Gedare Bloom

Changed on Mar 5, 2012 at 3:51:41 PM by Gedare Bloom

Updated patch.

comment:2 Changed on Mar 5, 2012 at 3:51:41 PM by Gedare Bloom

attachments.isobsolete: 01

comment:4 Changed on Nov 24, 2014 at 6:58:28 PM by Gedare Bloom

Version: HEAD4.11

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

Note: See TracTickets for help on using tickets.