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.
--- 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;