Closed Bug 1464999 Opened Last year Closed Last year

SplayTree assumes mRight and mLeft are nullptr on insert()

Categories

(Core :: MFBT, enhancement)

enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla62
Tracking Status
firefox62 --- fixed

People

(Reporter: bagder, Assigned: bagder)

References

(Blocks 1 open bug)

Details

Attachments

(1 file)

I'm using the SplayTree in code that removes a node from the tree, update its value and re-adds the same node to the same tree again to get it splayed to a new position.

When doing so, the tree gets completely garbled because the insert() method assumes that mRight and mLeft are cleared (from the object creation presumably). In may case they're left from the remove() call...

I propose that we clear mRight and mLeft first in the insert() method. I have a patch that works for me and that plays fine on try.
Assignee: nobody → daniel
Blocks: 1463374
WDYT about performing the nulling on `remove()`?   Putting the op there feels better to me (removing things from the tree should clear tree-related state), and doesn't penalize inserts, which I suspect (I have no data to back this up, feel free to argue) are more common than removals.
Flags: needinfo?(daniel)
I'm fine with that too, I don't have any particular preference and your "clear on remove" feels like a good enough reason. I went with the insert() simply because it seemed to have a single natural place to do it while remove() has two separate returns.

But now that I look at the remove() method again, the clearing is only necessary for one of the return paths...

I'll update my patch!
Flags: needinfo?(daniel)
Blah, screwed up and push the same a second time. I'll try again!
Attachment #8981349 - Flags: review?(n.nethercote) → review?(nfroyd)
I redirected the review request to froydnj; he's already given feedback, and I'm not an MFBT peer.
Comment on attachment 8981349 [details]
bug 1464999 - make SplayTree.remove clear mRight and mLeft

https://reviewboard.mozilla.org/r/247490/#review254010

Thank you!

::: mfbt/SplayTree.h:151
(Diff revision 3)
> +    last->mLeft = nullptr;
> +    last->mRight = nullptr;

Should we reset `mParent` here too?
Attachment #8981349 - Flags: review?(nfroyd) → review+
Comment on attachment 8981349 [details]
bug 1464999 - make SplayTree.remove clear mRight and mLeft

https://reviewboard.mozilla.org/r/247490/#review254010

> Should we reset `mParent` here too?

From my understanding how this works; removing a node from the splay tree means first moving it to the root, and a root node has no parent (ie it is already cleared). So when a node is removed, the mParent pointer *should* already be cleared...
Pushed by daniel@haxx.se:
https://hg.mozilla.org/integration/autoland/rev/ec2b59b0c7ff
make SplayTree.remove clear mRight and mLeft r=froydnj
https://hg.mozilla.org/mozilla-central/rev/ec2b59b0c7ff
Status: NEW → RESOLVED
Closed: Last year
Resolution: --- → FIXED
Target Milestone: --- → mozilla62
You need to log in before you can comment on or make changes to this bug.