Bug 1403444 - Replace rbp_lean_left and rbp_lean_right with private methods. r?njn draft
authorMike Hommey <mh+mozilla@glandium.org>
Tue, 26 Sep 2017 21:14:12 +0900
changeset 670934 13201482c1c1fa328dbc418c3254b8fc5dc29395
parent 670933 1f0294ddab99fc047da936f8d5ce17e6c03d5217
child 670935 2154d015f9f9cae085465dcf2e3e2c709a521ce6
push id81767
push userbmo:mh+mozilla@glandium.org
push dateWed, 27 Sep 2017 06:43:40 +0000
reviewersnjn
bugs1403444
milestone58.0a1
Bug 1403444 - Replace rbp_lean_left and rbp_lean_right with private methods. r?njn
memory/build/rb.h
--- a/memory/build/rb.h
+++ b/memory/build/rb.h
@@ -125,34 +125,16 @@ public:
   }
 
   void SetColor(NodeColor aColor)
   {
     mRightAndColor = (mRightAndColor & uintptr_t(~1)) | aColor;
   }
 };
 
-#define rbp_lean_left(a_type, a_field, a_node, r_node)                         \
-  do {                                                                         \
-    NodeColor rbp_ll_color;                                                    \
-    r_node = RotateLeft(a_node);                                               \
-    rbp_ll_color = a_field(a_node).Color();                                    \
-    a_field(r_node).SetColor(rbp_ll_color);                                    \
-    a_field(a_node).SetColor(NodeColor::Red);                                  \
-  } while (0)
-
-#define rbp_lean_right(a_type, a_field, a_node, r_node)                        \
-  do {                                                                         \
-    NodeColor rbp_lr_color;                                                    \
-    r_node = RotateRight(a_node);                                              \
-    rbp_lr_color = a_field(a_node).Color();                                    \
-    a_field(r_node).SetColor(rbp_lr_color);                                    \
-    a_field(a_node).SetColor(NodeColor::Red);                                  \
-  } while (0)
-
 #define rbp_move_red_left(a_type, a_field, a_node, r_node)                     \
   do {                                                                         \
     a_type *rbp_mrl_t, *rbp_mrl_u;                                             \
     rbp_mrl_t = a_field(a_node).Left();                                        \
     a_field(rbp_mrl_t).SetColor(NodeColor::Red);                               \
     rbp_mrl_t = a_field(a_node).Right();                                       \
     rbp_mrl_u = a_field(rbp_mrl_t).Left();                                     \
     if (a_field(rbp_mrl_u).IsRed()) {                                          \
@@ -364,17 +346,17 @@ struct RedBlackTree
         if (Trait::GetTreeNode(rbp_i_p).Left() == rbp_i_c) {
           Trait::GetTreeNode(rbp_i_p).SetLeft(rbp_i_t);
           rbp_i_c = rbp_i_t;
         } else {
           /* rbp_i_c was the right child of rbp_i_p, so rotate
            * left in order to maintain the left-leaning invariant. */
           MOZ_ASSERT(Trait::GetTreeNode(rbp_i_p).Right() == rbp_i_c);
           Trait::GetTreeNode(rbp_i_p).SetRight(rbp_i_t);
-          rbp_lean_left(T, Trait::GetTreeNode, rbp_i_p, rbp_i_u);
+          rbp_i_u = LeanLeft(rbp_i_p);
           if (Trait::GetTreeNode(rbp_i_g).Left() == rbp_i_p) {
             Trait::GetTreeNode(rbp_i_g).SetLeft(rbp_i_u);
           } else {
             MOZ_ASSERT(Trait::GetTreeNode(rbp_i_g).Right() == rbp_i_p);
             Trait::GetTreeNode(rbp_i_g).SetRight(rbp_i_u);
           }
           rbp_i_p = rbp_i_u;
           rbp_i_cmp = Trait::Compare(aNode, rbp_i_p);
@@ -398,17 +380,17 @@ struct RedBlackTree
       }
     }
     /* rbp_i_p now refers to the node under which to insert. */
     Trait::GetTreeNode(aNode).SetLeft(&rbt_nil);
     Trait::GetTreeNode(aNode).SetRight(&rbt_nil);
     Trait::GetTreeNode(aNode).SetColor(NodeColor::Red);
     if (rbp_i_cmp > 0) {
       Trait::GetTreeNode(rbp_i_p).SetRight(aNode);
-      rbp_lean_left(T, Trait::GetTreeNode, rbp_i_p, rbp_i_t);
+      rbp_i_t = LeanLeft(rbp_i_p);
       if (Trait::GetTreeNode(rbp_i_g).Left() == rbp_i_p) {
         Trait::GetTreeNode(rbp_i_g).SetLeft(rbp_i_t);
       } else if (Trait::GetTreeNode(rbp_i_g).Right() == rbp_i_p) {
         Trait::GetTreeNode(rbp_i_g).SetRight(rbp_i_t);
       }
     } else {
       Trait::GetTreeNode(rbp_i_p).SetLeft(aNode);
     }
@@ -450,17 +432,17 @@ struct RedBlackTree
         rbp_r_c = Trait::GetTreeNode(rbp_r_c).Left();
       }
     } else {
       if (rbp_r_cmp == 0) {
         MOZ_ASSERT(aNode == rbp_r_c);
         if (Trait::GetTreeNode(rbp_r_c).Right() == &rbt_nil) {
           /* Delete root node (which is also a leaf node). */
           if (Trait::GetTreeNode(rbp_r_c).Left() != &rbt_nil) {
-            rbp_lean_right(T, Trait::GetTreeNode, rbp_r_c, rbp_r_t);
+            rbp_r_t = LeanRight(rbp_r_c);
             Trait::GetTreeNode(rbp_r_t).SetRight(&rbt_nil);
           } else {
             rbp_r_t = &rbt_nil;
           }
           Trait::GetTreeNode(rbp_r_p).SetLeft(rbp_r_t);
         } else {
           /* This is the node we want to delete, but we will
            * instead swap it with its successor and delete the
@@ -548,17 +530,17 @@ struct RedBlackTree
         } else {
           /* Check whether to delete this node (it has to be
            * the correct node and a leaf node). */
           if (rbp_r_cmp == 0) {
             MOZ_ASSERT(aNode == rbp_r_c);
             if (Trait::GetTreeNode(rbp_r_c).Right() == &rbt_nil) {
               /* Delete leaf node. */
               if (Trait::GetTreeNode(rbp_r_c).Left() != &rbt_nil) {
-                rbp_lean_right(T, Trait::GetTreeNode, rbp_r_c, rbp_r_t);
+                rbp_r_t = LeanRight(rbp_r_c);
                 Trait::GetTreeNode(rbp_r_t).SetRight(&rbt_nil);
               } else {
                 rbp_r_t = &rbt_nil;
               }
               if (Trait::GetTreeNode(rbp_r_p).Left() == rbp_r_c) {
                 Trait::GetTreeNode(rbp_r_p).SetLeft(rbp_r_t);
               } else {
                 Trait::GetTreeNode(rbp_r_p).SetRight(rbp_r_t);
@@ -605,16 +587,34 @@ private:
 
   T* RotateRight(T* aNode)
   {
     T* node = Trait::GetTreeNode(aNode).Left();
     Trait::GetTreeNode(aNode).SetLeft(Trait::GetTreeNode(node).Right());
     Trait::GetTreeNode(node).SetRight(aNode);
     return node;
   }
+
+  T* LeanLeft(T* aNode)
+  {
+    T* node = RotateLeft(aNode);
+    NodeColor color = Trait::GetTreeNode(aNode).Color();
+    Trait::GetTreeNode(node).SetColor(color);
+    Trait::GetTreeNode(aNode).SetColor(NodeColor::Red);
+    return node;
+  }
+
+  T* LeanRight(T* aNode)
+  {
+    T* node = RotateRight(aNode);
+    NodeColor color = Trait::GetTreeNode(aNode).Color();
+    Trait::GetTreeNode(node).SetColor(color);
+    Trait::GetTreeNode(aNode).SetColor(NodeColor::Red);
+    return node;
+  }
 };
 
 /*
  * The iterators simulate recursion via an array of pointers that store the
  * current path.  This is critical to performance, since a series of calls to
  * rb_{next,prev}() would require time proportional to (n lg n), whereas this
  * implementation only requires time proportional to (n).
  *