Bug 1438427 - Fix wrong change from bug 1412722 in RedBlackTree::Remove. r=njn
authorMike Hommey <mh+mozilla@glandium.org>
Thu, 15 Feb 2018 14:38:52 +0900
changeset 403993 117cd9ec7414392ccc3f46ff0a3e2bb217c85316
parent 403992 8592fd84fc79597063b8ea3b19af8f8528bd02b8
child 403994 37910654ac3141968bbd39d864fdb6d8fb7a6e86
push id99924
push userebalazs@mozilla.com
push dateThu, 15 Feb 2018 20:43:51 +0000
treeherdermozilla-inbound@a7d2a49f46fb [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnjn
bugs1438427, 1412722, 1403444
milestone60.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1438427 - Fix wrong change from bug 1412722 in RedBlackTree::Remove. r=njn Before bug 1412722, which removed the sentinels, the code looked like: if (rbp_r_c->Right()->Left()->IsBlack()) { At that point in the code, rbp_r_c is the root node of the tree. If rbp_r_c->Right() was the sentinel, ->Right()->Left() would be the sentinel too, and the sentinel is black. Which means the condition would be true. The code after was: if (rbp_r_c->Right() && (!rbp_r_c->Right()->Left() || rbp_r_c->Right()->Left()->IsBlack())) { The second half correctly deals with the case of rbp_r_c->Right()->Left() being the sentinel. But the first half now makes things different: ->Right() being null would correspond to the previous case where it was the sentinel, and the test would not return true in that case when it would have before. When ->Right() is not null, things are normal again. The correct check is to make the branch taken when ->Right() is null. Now, looking under which conditions we may get in that branch wrongly: - The root node's right link must be empty, which means a very small tree. - The comparison between the removed key and the root node must indicate the key is greater than the value of the root node. - There's another case where the comparison result (rbp_r_cmp) can be eGreater, when it is reassigned under one of the branches under the eEqual test, and that branch is only taken when ->Right() on the root node was non-null, which was the non-broken case. So it would seem we can't reach that code when rbp_r_c->Right() is null anyways, so it /should/ practically make no difference. Better safe than sorry, though. It's hard to tell anything from crash stats, because since the templatization in bug 1403444, all crashes fit in one bucket, when there used to be 5 functions before :( While here, add a missing include in rb.h.
memory/build/rb.h
--- a/memory/build/rb.h
+++ b/memory/build/rb.h
@@ -62,16 +62,17 @@
 // that treat the first argument specially.
 //
 // ***************************************************************************
 
 #ifndef RB_H_
 #define RB_H_
 
 #include "mozilla/Alignment.h"
+#include "mozilla/Assertions.h"
 #include "Utils.h"
 
 enum NodeColor
 {
   Black = 0,
   Red = 1,
 };
 
@@ -415,18 +416,18 @@ private:
           // instead swap it with its successor and delete the
           // successor. Record enough information to do the
           // swap later. rbp_r_xp is the aNode's parent.
           rbp_r_xp = rbp_r_p;
           rbp_r_cmp = Order::eGreater; // Note that deletion is incomplete.
         }
       }
       if (rbp_r_cmp == Order::eGreater) {
-        if (rbp_r_c->Right() && (!rbp_r_c->Right()->Left() ||
-                                 rbp_r_c->Right()->Left()->IsBlack())) {
+        if (!rbp_r_c->Right() || !rbp_r_c->Right()->Left() ||
+            rbp_r_c->Right()->Left()->IsBlack()) {
           rbp_r_t = rbp_r_c->Left();
           if (rbp_r_t->IsRed()) {
             // Standard transform.
             rbp_r_t = MoveRedRight(rbp_r_c);
           } else {
             // Root-specific transform.
             rbp_r_c->SetColor(NodeColor::Red);
             rbp_r_u = rbp_r_t->Left();