From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Matt Armstrong Newsgroups: gmane.emacs.devel Subject: Re: noverlay branch Date: Wed, 05 Oct 2022 21:47:25 -0700 Message-ID: <87r0zld0de.fsf@rfc20.org> References: <1468ca31-1703-82a1-0c8c-be2c5b5674a7@gmail.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="37267"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel@gnu.org To: Stefan Monnier , Gerd =?utf-8?Q?M=C3=B6llman?= =?utf-8?Q?n?= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Thu Oct 06 06:49:17 2022 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1ogIov-0009Rf-2m for ged-emacs-devel@m.gmane-mx.org; Thu, 06 Oct 2022 06:49:17 +0200 Original-Received: from localhost ([::1]:46410 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ogIot-0007m4-0O for ged-emacs-devel@m.gmane-mx.org; Thu, 06 Oct 2022 00:49:15 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:58624) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogInM-00071m-8R for emacs-devel@gnu.org; Thu, 06 Oct 2022 00:47:40 -0400 Original-Received: from relay10.mail.gandi.net ([2001:4b98:dc4:8::230]:57257) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogInJ-0005zZ-TF for emacs-devel@gnu.org; Thu, 06 Oct 2022 00:47:39 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id D5630240003; Thu, 6 Oct 2022 04:47:28 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665031650; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=H9LRm5DeRge4uDMdtEaP4wsO82I70ZNmZpo809KNLa8=; b=lGvPSyp1CsrkeVgyLXrl41bYwOXkqma8RFpUQ/1LmZFrpKVLtzQ+8vVP8aRjUPRqWAIZVi DThynYJGdYU1DmWVh0HEsj+PNWPjyIBJNlE1fDL7xuROJYIFMoSnVSoQiAK89MR4VYc+h7 mBg+h3MQc9ReVvcgzIKIyy/eDz+6gtn+DnbsJfdEm9w8xDWDNmxzSCPJBBtYnkJvtFya7G 7J5AQZX0y+eOK15slMolQBf27X4rDzvWtt17sRzR0AtJ6SPBRODJZ58grOS0/UihcSfetE nLGrkwBmmpuJ8weX4OghdP+6Xxhvy9QXgJHvQYy1DfUTCALlM498ni84XMdZpg== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1ogIn7-002v7Y-1g; Wed, 05 Oct 2022 21:47:25 -0700 In-Reply-To: Received-SPF: pass client-ip=2001:4b98:dc4:8::230; envelope-from=matt@rfc20.org; helo=relay10.mail.gandi.net X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:297050 Archived-At: Stefan Monnier 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.