[rtems commit] score: Add _RBTree_Opposite_direction.

gedare at rtems.org gedare at rtems.org
Mon Mar 5 10:54:25 CST 2012


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

Author:    Gedare Bloom <gedare at rtems.org>
Date:      Sun Mar  4 11:42:08 2012 -0500

score: Add _RBTree_Opposite_direction.

Add a red-black tree helper method to ease obtaining the direction opposite
to the current direction. Useful for manipulating and traversing an rbtree.

---

 cpukit/score/inline/rtems/score/rbtree.inl |   16 +++++++++++++---
 cpukit/score/src/rbtreeextract.c           |   10 +++++-----
 2 files changed, 18 insertions(+), 8 deletions(-)

diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
index bbc6047..ef653e5 100644
--- a/cpukit/score/inline/rtems/score/rbtree.inl
+++ b/cpukit/score/inline/rtems/score/rbtree.inl
@@ -31,6 +31,16 @@
  *  @{
  */
 
+/**
+ * @brief Get the direction opposite to @a the_dir
+ */
+RTEMS_INLINE_ROUTINE RBTree_Direction _RBTree_Opposite_direction(
+  RBTree_Direction the_dir
+)
+{
+  return (!the_dir);
+}
+
 /** @brief Set off rbtree
  *
  *  This function sets the parent and child fields of the @a node to NULL
@@ -435,10 +445,10 @@ RTEMS_INLINE_ROUTINE void _RBTree_Rotate(
 {
   RBTree_Node *c;
   if (the_node == NULL) return;
-  if (the_node->child[(1-dir)] == NULL) return;
+  if (the_node->child[_RBTree_Opposite_direction(dir)] == NULL) return;
 
-  c = the_node->child[(1-dir)];
-  the_node->child[(1-dir)] = c->child[dir];
+  c = the_node->child[_RBTree_Opposite_direction(dir)];
+  the_node->child[_RBTree_Opposite_direction(dir)] = c->child[dir];
 
   if (c->child[dir])
     c->child[dir]->parent = the_node;
diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c
index ecbda18..4071361 100644
--- a/cpukit/score/src/rbtreeextract.c
+++ b/cpukit/score/src/rbtreeextract.c
@@ -50,7 +50,7 @@ static void _RBTree_Extract_validate_unprotected(
       sibling->color = RBT_BLACK;
       dir = the_node != parent->child[0];
       _RBTree_Rotate(parent, dir);
-      sibling = parent->child[!dir];
+      sibling = parent->child[_RBTree_Opposite_direction(dir)];
     }
 
     /* sibling is black, see if both of its children are also black. */
@@ -72,15 +72,15 @@ static void _RBTree_Extract_validate_unprotected(
        * Then switch the sibling and parent colors, and rotate through parent.
        */
       dir = the_node != parent->child[0];
-      if (!_RBTree_Is_red(sibling->child[!dir])) {
+      if (!_RBTree_Is_red(sibling->child[_RBTree_Opposite_direction(dir)])) {
         sibling->color = RBT_RED;
         sibling->child[dir]->color = RBT_BLACK;
-        _RBTree_Rotate(sibling, !dir);
-        sibling = parent->child[!dir];
+        _RBTree_Rotate(sibling, _RBTree_Opposite_direction(dir));
+        sibling = parent->child[_RBTree_Opposite_direction(dir)];
       }
       sibling->color = parent->color;
       parent->color = RBT_BLACK;
-      sibling->child[!dir]->color = RBT_BLACK;
+      sibling->child[_RBTree_Opposite_direction(dir)]->color = RBT_BLACK;
       _RBTree_Rotate(parent, dir);
       break; /* done */
     }



More information about the rtems-vc mailing list