Re: noverlay branch

[Stefan Monnier <monnier@iro.umontreal.ca>]

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


        Stefan