From e9fbaa3b48364c821f5fb8ef7d7b7504be957e0e Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Fri, 21 Aug 2015 05:59:49 +0200 Subject: rbtree: Replace implementation Use the BSD implementation since it is faster, more flexible and uses less storage. See https://github.com/sebhub/rb-bench. --- cpukit/score/src/rbtreeextract.c | 190 +-------------------------------------- 1 file changed, 3 insertions(+), 187 deletions(-) (limited to 'cpukit/score/src/rbtreeextract.c') diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c index 1aaba270e7..4d8a8f8eed 100644 --- a/cpukit/score/src/rbtreeextract.c +++ b/cpukit/score/src/rbtreeextract.c @@ -12,198 +12,14 @@ #include -/** @brief Validate and fix-up tree properties after deleting a node - * - * This routine is called on a black node, @a the_node, after its deletion. - * This function maintains the properties of the red-black tree. - * - * @note It does NOT disable interrupts to ensure the atomicity - * of the extract operation. - */ -static void _RBTree_Extract_validate( RBTree_Node *the_node ) -{ - RBTree_Node *parent; - - parent = the_node->parent; - - if ( !parent->parent ) - return; - - /* continue to correct tree as long as the_node is black and not the root */ - while ( !_RBTree_Is_red( the_node ) && parent->parent ) { - RBTree_Node *sibling = _RBTree_Sibling( the_node, parent ); - - /* if sibling is red, switch parent (black) and sibling colors, - * then rotate parent left, making the sibling be the_node's grandparent. - * Now the_node has a black sibling and red parent. After rotation, - * update sibling pointer. - */ - if ( _RBTree_Is_red( sibling ) ) { - RBTree_Direction dir = _RBTree_Direction( the_node, parent ); - RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir ); - - parent->color = RBT_RED; - sibling->color = RBT_BLACK; - _RBTree_Rotate( parent, dir ); - sibling = parent->child[ opp_dir ]; - } +RB_GENERATE_REMOVE_COLOR( RBTree_Control, RBTree_Node, Node, static ) - /* sibling is black, see if both of its children are also black. */ - if ( !_RBTree_Is_red( sibling->child[ RBT_RIGHT ] ) && - !_RBTree_Is_red( sibling->child[ RBT_LEFT ] ) ) { - sibling->color = RBT_RED; - - if ( _RBTree_Is_red( parent ) ) { - parent->color = RBT_BLACK; - break; - } - - the_node = parent; /* done if parent is red */ - parent = the_node->parent; - } else { - /* at least one of sibling's children is red. we now proceed in two - * cases, either the_node is to the left or the right of the parent. - * In both cases, first check if one of sibling's children is black, - * and if so rotate in the proper direction and update sibling pointer. - * Then switch the sibling and parent colors, and rotate through parent. - */ - RBTree_Direction dir = _RBTree_Direction( the_node, parent ); - RBTree_Direction opp_dir = _RBTree_Opposite_direction( dir ); - - if ( - !_RBTree_Is_red( sibling->child[ opp_dir ] ) - ) { - sibling->color = RBT_RED; - sibling->child[ dir ]->color = RBT_BLACK; - _RBTree_Rotate( sibling, opp_dir ); - sibling = parent->child[ opp_dir ]; - } - - sibling->color = parent->color; - parent->color = RBT_BLACK; - sibling->child[ opp_dir ]->color = RBT_BLACK; - _RBTree_Rotate( parent, dir ); - break; /* done */ - } - } /* while */ - - if ( !the_node->parent->parent ) - the_node->color = RBT_BLACK; -} +RB_GENERATE_REMOVE( RBTree_Control, RBTree_Node, Node, static ) void _RBTree_Extract( RBTree_Control *the_rbtree, RBTree_Node *the_node ) { - RBTree_Node *leaf, *target; - RBTree_Color victim_color; - RBTree_Direction dir; - - /* check if min needs to be updated */ - if ( the_node == the_rbtree->first[ RBT_LEFT ] ) { - RBTree_Node *next; - next = _RBTree_Successor( the_node ); - the_rbtree->first[ RBT_LEFT ] = next; - } - - /* Check if max needs to be updated. min=max for 1 element trees so - * do not use else if here. */ - if ( the_node == the_rbtree->first[ RBT_RIGHT ] ) { - RBTree_Node *previous; - previous = _RBTree_Predecessor( the_node ); - the_rbtree->first[ RBT_RIGHT ] = previous; - } - - /* if the_node has at most one non-null child then it is safe to proceed - * check if both children are non-null, if so then we must find a target node - * either max in node->child[RBT_LEFT] or min in node->child[RBT_RIGHT], - * and replace the_node with the target node. This maintains the binary - * search tree property, but may violate the red-black properties. - */ - - if ( the_node->child[ RBT_LEFT ] && the_node->child[ RBT_RIGHT ] ) { - target = the_node->child[ RBT_LEFT ]; /* find max in node->child[RBT_LEFT] */ - - while ( target->child[ RBT_RIGHT ] ) - target = target->child[ RBT_RIGHT ]; - - /* if the target node has a child, need to move it up the tree into - * target's position (target is the right child of target->parent) - * when target vacates it. if there is no child, then target->parent - * should become NULL. This may cause the coloring to be violated. - * For now we store the color of the node being deleted in victim_color. - */ - leaf = target->child[ RBT_LEFT ]; - - if ( leaf ) { - leaf->parent = target->parent; - } else { - /* fix the tree here if the child is a null leaf. */ - _RBTree_Extract_validate( target ); - } - - victim_color = target->color; - dir = target != target->parent->child[ 0 ]; - target->parent->child[ dir ] = leaf; - - /* now replace the_node with target */ - dir = the_node != the_node->parent->child[ 0 ]; - the_node->parent->child[ dir ] = target; - - /* set target's new children to the original node's children */ - target->child[ RBT_RIGHT ] = the_node->child[ RBT_RIGHT ]; - - if ( the_node->child[ RBT_RIGHT ] ) - the_node->child[ RBT_RIGHT ]->parent = target; - - target->child[ RBT_LEFT ] = the_node->child[ RBT_LEFT ]; - - if ( the_node->child[ RBT_LEFT ] ) - the_node->child[ RBT_LEFT ]->parent = target; - - /* finally, update the parent node and recolor. target has completely - * replaced the_node, and target's child has moved up the tree if needed. - * the_node is no longer part of the tree, although it has valid pointers - * still. - */ - target->parent = the_node->parent; - target->color = the_node->color; - } else { - /* the_node has at most 1 non-null child. Move the child in to - * the_node's location in the tree. This may cause the coloring to be - * violated. We will fix it later. - * For now we store the color of the node being deleted in victim_color. - */ - leaf = the_node->child[ RBT_LEFT ] ? - the_node->child[ RBT_LEFT ] : the_node->child[ RBT_RIGHT ]; - - if ( leaf ) { - leaf->parent = the_node->parent; - } else { - /* fix the tree here if the child is a null leaf. */ - _RBTree_Extract_validate( the_node ); - } - - victim_color = the_node->color; - - /* remove the_node from the tree */ - dir = the_node != the_node->parent->child[ 0 ]; - the_node->parent->child[ dir ] = leaf; - } - - /* fix coloring. leaf has moved up the tree. The color of the deleted - * node is in victim_color. There are two cases: - * 1. Deleted a red node, its child must be black. Nothing must be done. - * 2. Deleted a black node, its child must be red. Paint child black. - */ - if ( victim_color == RBT_BLACK ) { /* eliminate case 1 */ - if ( leaf ) { - leaf->color = RBT_BLACK; /* case 2 */ - } - } - - /* set root to black, if it exists */ - if ( the_rbtree->root ) - the_rbtree->root->color = RBT_BLACK; + RB_REMOVE( RBTree_Control, the_rbtree, the_node ); } -- cgit v1.2.3