[rtems commit] rbtree: Simplify _RBTree_Rotate()

[Sebastian Huber]

Module:    rtems
Branch:    master
Commit:    4752550f80206d7ab15daefb68532374f1b5a527
Changeset: http://git.rtems.org/rtems/commit/?id=4752550f80206d7ab15daefb68532374f1b5a527

Author:    Sebastian Huber <sebastian.huber at embedded-brains.de>
Date:      Wed Jul 23 13:19:09 2014 +0200

rbtree: Simplify _RBTree_Rotate()

Add and use _RBTree_Direction().

---

 cpukit/score/include/rtems/score/rbtreeimpl.h |   78 +++++++++++++++++++-----
 testsuites/sptests/sprbtree01/init.c          |    1 -
 2 files changed, 61 insertions(+), 18 deletions(-)

diff --git a/cpukit/score/include/rtems/score/rbtreeimpl.h b/cpukit/score/include/rtems/score/rbtreeimpl.h
index 451b5f4..5f5e783 100644
--- a/cpukit/score/include/rtems/score/rbtreeimpl.h
+++ b/cpukit/score/include/rtems/score/rbtreeimpl.h
@@ -77,6 +77,21 @@ RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
 }
 
 /**
+ * @brief Returns the direction of the node.
+ *
+ * @param[in] the_node The node of interest.
+ * @param[in] parent The parent of the node.  The parent must exist, thus it is
+ * invalid to use this function for the root node.
+ */
+RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Direction(
+  const RBTree_Node *the_node,
+  const RBTree_Node *parent
+)
+{
+  return (RBTree_Direction) ( the_node != parent->child[ 0 ] );
+}
+
+/**
  * @brief Is this node red.
  *
  * This function returns true if @a the_node is red and false otherwise.
@@ -166,32 +181,61 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
 }
 
 /**
- * @brief Rotate the_node in the direction passed as second argument.
+ * @brief Rotates the node in the specified direction.
  *
- * This routine rotates @a the_node to the direction @a dir, swapping
- * @a the_node with its child\[@a dir\].
+ * The node is swapped with its child in the opposite direction if it exists.
+ *
+ * Sub-tree before rotation:
+ * @dot
+ * digraph state {
+ *   parent -> the_node;
+ *   the_node -> sibling [label="dir"];
+ *   the_node -> child [label="opp_dir"];
+ *   child -> grandchild [label="dir"];
+ *   child -> grandchildsibling [label="opp_dir"];
+ * }
+ * @enddot
+ *
+ * Sub-tree after rotation:
+ * @dot
+ * digraph state {
+ *   parent -> child;
+ *   the_node -> sibling [label="dir"];
+ *   the_node -> grandchild [label="opp_dir"];
+ *   child -> the_node [label="dir"];
+ *   child -> grandchildsibling [label="opp_dir"];
+ * }
+ * @enddot
+ *
+ * @param[in] the_node The node to rotate.
+ * @param[in] dir The rotation direction.
  */
 RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
-    RBTree_Node *the_node,
-    RBTree_Direction dir
-    )
+  RBTree_Node      *the_node,
+  RBTree_Direction  dir
+)
 {
-  RBTree_Node *c;
-  if (the_node == NULL) return;
-  if (the_node->child[_RBTree_Opposite_direction(dir)] == NULL) return;
+  RBTree_Direction  opp_dir = _RBTree_Opposite_direction( dir );
+  RBTree_Node      *child = the_node->child[ opp_dir ];
+  RBTree_Node      *grandchild;
+  RBTree_Node      *parent;
+
+  if ( child == NULL)
+    return;
 
-  c = the_node->child[_RBTree_Opposite_direction(dir)];
-  the_node->child[_RBTree_Opposite_direction(dir)] = c->child[dir];
+  grandchild = child->child[ dir ];
+  the_node->child[ opp_dir ] = grandchild;
 
-  if (c->child[dir])
-    c->child[dir]->parent = the_node;
+  if ( grandchild != NULL )
+    grandchild->parent = the_node;
 
-  c->child[dir] = the_node;
+  child->child[ dir ] = the_node;
 
-  the_node->parent->child[the_node != the_node->parent->child[0]] = c;
+  parent = _RBTree_Parent( the_node );
+  parent->child[ _RBTree_Direction( the_node, parent ) ] = child;
 
-  c->parent = the_node->parent;
-  the_node->parent = c;
+  child->parent = parent;
+  the_node->parent = child;
 }
 
 /** @} */
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index ffb91b1..734530e 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -858,7 +858,6 @@ rtems_task Init( rtems_task_argument ignored )
 
   rtems_test_assert( !rtems_rbtree_is_node_off_tree( &node1.Node ) );
 
-  _RBTree_Rotate(NULL, RBT_LEFT);
   i = (node1.Node.parent == &node2.Node);
   _RBTree_Rotate( &node1.Node,
                   !node1.Node.child[RBT_LEFT] ? RBT_RIGHT : RBT_LEFT