1464999 - SplayTree assumes mRight and mLeft are nullptr on insert()

Status: RESOLVED FIXED

(Core :: MFBT, enhancement)

Description

[Daniel Stenberg [:bagder]]

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.

Comment 1

[Daniel Stenberg [:bagder]]

Attachment: bug 1464999 - make SplayTree.remove clear mRight and mLeft

... to allow a user to remove() an entry, update the values and
re-insert() it into a tree.

Review commit: https://reviewboard.mozilla.org/r/247490/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/247490/

Comment 2

[Nathan Froyd [:froydnj]]

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.

Comment 3

[Daniel Stenberg [:bagder]]

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!

Comment 4

[Daniel Stenberg [:bagder]]

Comment on attachment 8981349 [details]
bug 1464999 - make SplayTree.remove clear mRight and mLeft

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/247490/diff/1-2/

Comment 5

[Daniel Stenberg [:bagder]]

Blah, screwed up and push the same a second time. I'll try again!

Comment 6

[Daniel Stenberg [:bagder]]

Comment on attachment 8981349 [details]
bug 1464999 - make SplayTree.remove clear mRight and mLeft

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/247490/diff/2-3/

Comment 7

[Nicholas Nethercote [inactive]]

I redirected the review request to froydnj; he's already given feedback, and I'm not an MFBT peer.

Comment 8

[Nathan Froyd [:froydnj]]

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?

Comment 9

[Daniel Stenberg [:bagder]]

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

Comment 10

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/ec2b59b0c7ff
make SplayTree.remove clear mRight and mLeft r=froydnj

Comment 11

[Arthur Iakab [arthur_iakab]]

https://hg.mozilla.org/mozilla-central/rev/ec2b59b0c7ff