rbtree redundant assignment

Maxim Dounin mdounin at mdounin.ru
Sun Jul 9 12:24:57 UTC 2023


On Sun, Jul 09, 2023 at 10:57:20AM +0200, andrey zverev wrote:

> Hello, everyone!
> I found a very strange thing in the ngx_rbtree_delete function. It seems
> that there is redundant assignment under the following if statement:
> if (subst->parent == node) {
>   temp->parent = subst;
> Could someone please explain to me why this assignment is needed if temp
> was taken as subst->right before? Because it was a child of subst, it means
> temp had subst as its parent.

If subst->right (and therefore temp) is the sentinel, this won't 
be the case, and an explicit assignment is needed.

Just in case, "Introduction to Algorithms" by Cormen et al. might 
be a good source to refer here.

Maxim Dounin

More information about the nginx-devel mailing list