Re: noverlay branch

[Matt Armstrong <matt@rfc20.org>]

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

>>> What I'm less clear about is the use of the `null` sentinel node.
>>> It seems that this node is sometimes modified (e.g. its color changed
>>> from black to red or vice versa, and maybe also its `parent` field),
>>> even though it's pointed to from lots of different nodes, so any help
>>> documenting the way it works (or why the value in those fields doesn't
>>> matter) would be welcome.
>>
>> Maybe I can say something because I used a similar trick in alloc.c.
>> The gist of that was to make searching more elegant, and faster:
>>
>> static struct mem_node *
>> mem_find (void *start)
>> {
>>   struct mem_node *p;
>>
>> ...
>>
>>   /* Make the search always successful to speed up the loop below.  */
>>   mem_z.start = start;
>>   mem_z.end = (char *) start + 1;
>>
>>   p = mem_root;
>>   while (start < p->start || start >= p->end)
>>     p = start < p->start ? p->left : p->right;
>>   return p;
>> }
>>
>> 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 :-)
>
> 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).
> 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).
> I don't see any place where we (re)set the null's `parent` field (other
> than in `interval_tree_clear`)?  So it looks like this field is
> "garbage" but not completely.

I see you removed some of the null->parent trick just today.  I like
that idea.  It is realtively easy to use actual NULL instead of a
sentinel NULL in tree algorithms, and I think on modern processors this
works out for the better.