Bug 1402284 - Make RedBlackTree::{Insert,Remove} work when the type has a constructor. r?njn draft
authorMike Hommey <mh+mozilla@glandium.org>
Mon, 30 Oct 2017 09:55:18 +0900
changeset 689867 1540940b9ca8a28718e1ecdc2ed02d53540dbd2f
parent 689866 2db67ea386eec4d7b62095df233dff9dbdde8ab3
child 689868 eb6f9f3810fdc84596674ea05d4910f0f16cd976
child 689887 9e2b58285361b74eea3473dd7ff31532130bdca3
push id87123
push userbmo:mh+mozilla@glandium.org
push dateWed, 01 Nov 2017 02:12:10 +0000
reviewersnjn
bugs1402284
milestone58.0a1
Bug 1402284 - Make RedBlackTree::{Insert,Remove} work when the type has a constructor. r?njn RedBlackTree::{Insert,Remove} allocate an object on the stack for its RedBlackTreeNode, and that shouldn't have side effects if the type happens to have a constructor. This will allow to add constructors to some of the mozjemalloc types.
memory/build/rb.h
--- a/memory/build/rb.h
+++ b/memory/build/rb.h
@@ -62,16 +62,17 @@
  * comparison function, which makes it possible to write comparison functions
  * that treat the first argument specially.
  *
  ******************************************************************************/
 
 #ifndef RB_H_
 #define RB_H_
 
+#include "mozilla/Alignment.h"
 #include "Utils.h"
 
 enum NodeColor
 {
   Black = 0,
   Red = 1,
 };
 
@@ -322,24 +323,26 @@ private:
         break;
       }
     }
     return ret;
   }
 
   void Insert(TreeNode* aNode)
   {
-    TreeNode rbp_i_s;
+    // rbp_i_s is only used as a placeholder for its RedBlackTreeNode. Use
+    // AlignedStorage2 to avoid running the TreeNode base class constructor.
+    mozilla::AlignedStorage2<TreeNode> rbp_i_s;
     TreeNode *rbp_i_g, *rbp_i_p, *rbp_i_c, *rbp_i_t, *rbp_i_u;
     int rbp_i_cmp = 0;
     rbp_i_g = nullptr;
-    rbp_i_s.SetLeft(mRoot);
-    rbp_i_s.SetRight(nullptr);
-    rbp_i_s.SetColor(NodeColor::Black);
-    rbp_i_p = &rbp_i_s;
+    rbp_i_p = rbp_i_s.addr();
+    rbp_i_p->SetLeft(mRoot);
+    rbp_i_p->SetRight(nullptr);
+    rbp_i_p->SetColor(NodeColor::Black);
     rbp_i_c = mRoot;
     /* Iteratively search down the tree for the insertion point,
      * splitting 4-nodes as they are encountered. At the end of each
      * iteration, rbp_i_g->rbp_i_p->rbp_i_c is a 3-level path down
      * the tree, assuming a sufficiently deep tree. */
     while (rbp_i_c) {
       rbp_i_t = rbp_i_c->Left();
       rbp_i_u = rbp_i_t ? rbp_i_t->Left() : nullptr;
@@ -400,29 +403,31 @@ private:
         rbp_i_g->SetLeft(rbp_i_t);
       } else if (rbp_i_g->Right() == rbp_i_p) {
         rbp_i_g->SetRight(rbp_i_t);
       }
     } else {
       rbp_i_p->SetLeft(aNode);
     }
     /* Update the root and make sure that it is black. */
-    mRoot = rbp_i_s.Left();
+    mRoot = rbp_i_s.addr()->Left();
     mRoot->SetColor(NodeColor::Black);
   }
 
   void Remove(TreeNode* aNode)
   {
-    TreeNode rbp_r_s;
+    // rbp_r_s is only used as a placeholder for its RedBlackTreeNode. Use
+    // AlignedStorage2 to avoid running the TreeNode base class constructor.
+    mozilla::AlignedStorage2<TreeNode> rbp_r_s;
     TreeNode *rbp_r_p, *rbp_r_c, *rbp_r_xp, *rbp_r_t, *rbp_r_u;
     int rbp_r_cmp;
-    rbp_r_s.SetLeft(mRoot);
-    rbp_r_s.SetRight(nullptr);
-    rbp_r_s.SetColor(NodeColor::Black);
-    rbp_r_p = &rbp_r_s;
+    rbp_r_p = rbp_r_s.addr();
+    rbp_r_p->SetLeft(mRoot);
+    rbp_r_p->SetRight(nullptr);
+    rbp_r_p->SetColor(NodeColor::Black);
     rbp_r_c = mRoot;
     rbp_r_xp = nullptr;
     /* Iterate down the tree, but always transform 2-nodes to 3- or
      * 4-nodes in order to maintain the invariant that the current
      * node is not a 2-node. This allows simple deletion once a leaf
      * is reached. Handle the root specially though, since there may
      * be no way to convert it from a 2-node to a 3-node. */
     rbp_r_cmp = Trait::Compare(aNode, rbp_r_c);
@@ -572,17 +577,17 @@ private:
           } else {
             rbp_r_p = rbp_r_c;
             rbp_r_c = rbp_r_c->Right();
           }
         }
       }
     }
     /* Update root. */
-    mRoot = rbp_r_s.Left();
+    mRoot = rbp_r_s.addr()->Left();
   }
 
   TreeNode* RotateLeft(TreeNode* aNode)
   {
     TreeNode* node = aNode->Right();
     aNode->SetRight(node->Left());
     node->SetLeft(aNode);
     return node;