From 993f5acd25cc3d140689c7a0f2c1912da7b2f0f3 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Wed, 23 Jul 2014 13:03:54 +0200 Subject: 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(). --- cpukit/score/src/rbtreeextract.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'cpukit/score/src/rbtreeextract.c') diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c index a1896a960e..f3a7328e8d 100644 --- a/cpukit/score/src/rbtreeextract.c +++ b/cpukit/score/src/rbtreeextract.c @@ -22,7 +22,7 @@ */ static void _RBTree_Extract_validate( RBTree_Node *the_node ) { - RBTree_Node *parent, *sibling; + RBTree_Node *parent; RBTree_Direction dir; parent = the_node->parent; @@ -30,10 +30,10 @@ static void _RBTree_Extract_validate( RBTree_Node *the_node ) if ( !parent->parent ) return; - sibling = _RBTree_Sibling( the_node ); - /* 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, @@ -59,7 +59,6 @@ static void _RBTree_Extract_validate( RBTree_Node *the_node ) the_node = parent; /* done if parent is red */ parent = the_node->parent; - sibling = _RBTree_Sibling( the_node ); } 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. -- cgit v1.2.3