Re: noverlay branch

["Gerd Möllmann" <gerd.moellmann@gmail.com>]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

W>> If that's done for the same reason in itree.c, I don't know.  A hint that it
>> is not, might be that each tree has a separated null node...
>
> OTOH there's a single mem tree, so in a sense you also have a separate
> mem_nil node per tree :-)

Hehe, true :-).

> I actually do understand the above use.  What I don't understand is code
> such as:
>
>     interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
>     {
>       struct interval_node *broken = NULL;
>       if (node->left == &tree->null || node->right == &tree->null)
>         { ... }
>       else
>         {
>           struct interval_node *min = interval_tree_subtree_min (tree, node->right);
>           struct interval_node *min_right = min->right;
>     
>           if (!min->red)
>             broken = min->right;
>           if (min->parent == node)
>             min_right->parent = min; /* set parent, if min_right = null */
>
> where `min_right` on this last line can definitely be the null node (my
> tests confirm it).

Ok.

> So what does it mean that we set the null nodes' `parent` field here?
> How does it interact with other places where we use the `parent` field
> (such as the last-but-one line where I confirmed that `min` can also be
> the null node).

Yes, that's odd, but it should be harmless.  In general, walking the
tree should always stop at null, and not proceed with null itself.  So
null->parent shouldn't matter.

But it feels odd.  I don't remember other rb-tree implementations doing
that.  Maybe it's something special to Corman's implementation?
(Introduction to Algorithms was always quite expensive here, so I never
bought it).