unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
From: Stefan Monnier <monnier@iro.umontreal.ca>
To: "Gerd Möllmann" <gerd.moellmann@gmail.com>
Cc: emacs-devel@gnu.org,  matt@rfc20.org
Subject: Re: noverlay branch
Date: Thu, 29 Sep 2022 17:36:09 -0400	[thread overview]
Message-ID: <jwvpmfd98nd.fsf-monnier+emacs@gnu.org> (raw)
In-Reply-To: <1468ca31-1703-82a1-0c8c-be2c5b5674a7@gmail.com> ("Gerd Möllmann"'s message of "Thu, 29 Sep 2022 16:54:14 +0200")

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




  reply	other threads:[~2022-09-29 21:36 UTC|newest]

Thread overview: 71+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-09-25 22:38 noverlay branch Stefan Monnier
2022-09-25 22:50 ` Lars Ingebrigtsen
2022-09-25 22:56   ` Stefan Monnier
2022-09-26  2:52 ` Ihor Radchenko
2022-09-26  3:17   ` Stefan Monnier
2022-09-26  6:11   ` Eli Zaretskii
2022-09-26 13:08     ` Ihor Radchenko
2022-09-26 15:59       ` Eli Zaretskii
     [not found]         ` <87v8ovdosz.fsf@localhost>
2022-10-08  6:57           ` Eli Zaretskii
2022-10-09  3:25             ` Matt Armstrong
2022-10-09  4:30               ` Eli Zaretskii
2022-10-09  3:23           ` Matt Armstrong
2022-10-09  3:47           ` Stefan Monnier
2022-10-13 12:09             ` Ihor Radchenko
2022-09-29 18:12       ` Stefan Monnier
2022-09-27  5:12 ` Matt Armstrong
2022-09-27  6:53   ` Eli Zaretskii
2022-09-27 17:31     ` Matt Armstrong
2022-09-27 18:45       ` Stefan Monnier
2022-09-28 23:09   ` Stefan Monnier
2022-09-29 14:54     ` Gerd Möllmann
2022-09-29 21:36       ` Stefan Monnier [this message]
2022-09-30  5:20         ` Gerd Möllmann
2022-10-06  4:47         ` Matt Armstrong
2022-10-06  5:43           ` Gerd Möllmann
2022-10-07  4:11             ` Matt Armstrong
2022-10-07  4:34               ` Gerd Möllmann
2022-10-07 13:33                 ` Stefan Monnier
2022-10-07 14:29                   ` Gerd Möllmann
2022-10-07 14:51                     ` Stefan Monnier
2022-10-07 15:12                       ` Gerd Möllmann
2022-10-07 17:12                         ` Stefan Monnier
2022-10-07 14:56                   ` Stefan Monnier
2022-10-07 15:59                   ` Matt Armstrong
2022-10-07 15:34                 ` Matt Armstrong
2022-10-06 12:08           ` Stefan Monnier
2022-09-27  8:39 ` Gerd Möllmann
2022-09-27  9:38   ` Eli Zaretskii
2022-10-06 20:41 ` Matt Armstrong
2022-10-07 16:51 ` Matt Armstrong
2022-10-07 18:28   ` Stefan Monnier
2022-10-08 23:33     ` Matt Armstrong
2022-10-09  3:44       ` Matt Armstrong
2022-10-09  4:12       ` Stefan Monnier
2022-10-09 15:34         ` Stefan Monnier
2022-10-10  2:57           ` Matt Armstrong
2022-10-10  6:24             ` Eli Zaretskii
2022-10-10 16:26               ` Matt Armstrong
2022-10-10 14:44             ` Stefan Monnier
2022-10-11  3:46               ` Matt Armstrong
2022-10-11  4:09                 ` Stefan Monnier
2022-10-11 18:02                   ` Matt Armstrong
2022-10-11 18:59                     ` Stefan Monnier
2022-10-12  5:18                       ` Matt Armstrong
2022-10-12 18:02                         ` Stefan Monnier
2022-10-12 22:26                           ` Matt Armstrong
2022-10-13  4:03                             ` Stefan Monnier
2022-10-09 23:47       ` Stefan Monnier
2022-10-10  0:05         ` Emanuel Berg
2022-10-10 16:27           ` Matt Armstrong
2022-10-10 16:33         ` Matt Armstrong
2022-10-10 18:32           ` Matt Armstrong
2022-10-11 16:06             ` Stefan Monnier
2022-10-12 17:33               ` Matt Armstrong
2022-10-13  3:59                 ` Stefan Monnier
2022-10-16 21:53                   ` Matt Armstrong
2022-10-23  4:49 ` Matt Armstrong
2022-10-24  9:14   ` Stefan Kangas
2022-10-24 16:21     ` Matt Armstrong
2022-10-24 12:51   ` Eli Zaretskii
2022-10-25 20:57     ` Dmitry Gutov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://www.gnu.org/software/emacs/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=jwvpmfd98nd.fsf-monnier+emacs@gnu.org \
    --to=monnier@iro.umontreal.ca \
    --cc=emacs-devel@gnu.org \
    --cc=gerd.moellmann@gmail.com \
    --cc=matt@rfc20.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).