From 993f5acd25cc3d140689c7a0f2c1912da7b2f0f3 Mon Sep 17 00:00:00 2001
From: Sebastian Huber <sebastian.huber@embedded-brains.de>
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 +++--
 cpukit/score/src/rbtreeinsert.c  | 57 +++++++++++++++++++++++++---------------
 2 files changed, 39 insertions(+), 25 deletions(-)

(limited to 'cpukit/score/src')

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.
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index 3bccba5aaa..a7be449420 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -32,40 +32,55 @@ RTEMS_STATIC_ASSERT(
  */
 static void _RBTree_Validate_insert( RBTree_Node *the_node )
 {
-  RBTree_Node *u, *g;
+  RBTree_Node *parent = _RBTree_Parent( the_node );
+  RBTree_Node *grandparent = _RBTree_Parent( parent );
 
   /* note: the insert root case is handled already */
   /* if the parent is black, nothing needs to be done
    * otherwise may need to loop a few times */
-  while ( _RBTree_Is_red( _RBTree_Parent( the_node ) ) ) {
-    u = _RBTree_Parent_sibling( the_node );
-    g = the_node->parent->parent;
-
-    /* if uncle is red, repaint uncle/parent black and grandparent red */
-    if ( _RBTree_Is_red( u ) ) {
-      the_node->parent->color = RBT_BLACK;
-      u->color = RBT_BLACK;
-      g->color = RBT_RED;
-      the_node = g;
-    } else { /* if uncle is black */
-      RBTree_Direction dir = the_node != the_node->parent->child[ 0 ];
-      RBTree_Direction pdir = the_node->parent != g->child[ 0 ];
+  while ( parent->color == RBT_RED ) {
+    /* The root is black, so the grandparent must exist */
+    RBTree_Node *uncle = _RBTree_Sibling( parent, grandparent );
+
+    /*
+     * If uncle exists and is red, repaint uncle/parent black and grandparent
+     * red.
+     */
+    if ( uncle != NULL && uncle->color == RBT_RED ) {
+      parent->color = RBT_BLACK;
+      uncle->color = RBT_BLACK;
+      grandparent->color = RBT_RED;
+      the_node = grandparent;
+      parent = _RBTree_Parent( the_node );
+      grandparent = _RBTree_Parent( parent );
+
+      if ( grandparent == NULL )
+        break;
+    } else { /* If uncle does not exist or is black */
+      RBTree_Direction dir = _RBTree_Direction( the_node, parent );
+      RBTree_Direction parentdir = _RBTree_Direction( parent, grandparent );
 
       /* ensure node is on the same branch direction as parent */
-      if ( dir != pdir ) {
-        _RBTree_Rotate( the_node->parent, pdir );
-        the_node = the_node->child[ pdir ];
+      if ( dir != parentdir ) {
+        RBTree_Node *oldparent = parent;
+
+        parent = the_node;
+        the_node = oldparent;
+        _RBTree_Rotate( oldparent, parentdir );
       }
 
-      the_node->parent->color = RBT_BLACK;
-      g->color = RBT_RED;
+      parent->color = RBT_BLACK;
+      grandparent->color = RBT_RED;
 
       /* now rotate grandparent in the other branch direction (toward uncle) */
-      _RBTree_Rotate( g, ( 1 - pdir ) );
+      _RBTree_Rotate( grandparent, _RBTree_Opposite_direction( parentdir ) );
+
+      grandparent = _RBTree_Parent( parent );
+      break;
     }
   }
 
-  if ( !the_node->parent->parent )
+  if ( grandparent == NULL )
     the_node->color = RBT_BLACK;
 }
 
-- 
cgit v1.2.3