From: "Gerd Möllmann" <gerd.moellmann@gmail.com>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: emacs-devel@gnu.org, matt@rfc20.org
Subject: Re: noverlay branch
Date: Fri, 30 Sep 2022 07:20:49 +0200 [thread overview]
Message-ID: <m2sfk9qvym.fsf@Mini.fritz.box> (raw)
In-Reply-To: <jwvpmfd98nd.fsf-monnier+emacs@gnu.org> (Stefan Monnier's message of "Thu, 29 Sep 2022 17:36:09 -0400")
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).
next prev parent reply other threads:[~2022-09-30 5:20 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
2022-09-30 5:20 ` Gerd Möllmann [this message]
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
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=m2sfk9qvym.fsf@Mini.fritz.box \
--to=gerd.moellmann@gmail.com \
--cc=emacs-devel@gnu.org \
--cc=matt@rfc20.org \
--cc=monnier@iro.umontreal.ca \
/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 external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.