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: Fri, 07 Oct 2022 08:34:14 -0700 Message-ID: <874jwffy15.fsf@rfc20.org> References: <1468ca31-1703-82a1-0c8c-be2c5b5674a7@gmail.com> <87r0zld0de.fsf@rfc20.org> <87edvki88a.fsf@rfc20.org> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="26459"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Stefan Monnier , emacs-devel@gnu.org To: Gerd =?utf-8?Q?M=C3=B6llmann?= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Fri Oct 07 18:56:05 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 1ogqdo-0006eF-Tn for ged-emacs-devel@m.gmane-mx.org; Fri, 07 Oct 2022 18:56:04 +0200 Original-Received: from localhost ([::1]:54590 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ogqdn-000807-Ub for ged-emacs-devel@m.gmane-mx.org; Fri, 07 Oct 2022 12:56:03 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:57128) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogpMn-00030E-BH for emacs-devel@gnu.org; Fri, 07 Oct 2022 11:34:25 -0400 Original-Received: from relay2-d.mail.gandi.net ([2001:4b98:dc4:8::222]:40475) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogpMl-000899-ET for emacs-devel@gnu.org; Fri, 07 Oct 2022 11:34:24 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id 92E2040008; Fri, 7 Oct 2022 15:34:17 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665156860; 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: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=ptNTuyjxFkrkdunqxGoNlF35a+LZYM0dSd9XIRIs42k=; b=YyvTDUdFlMNCZOvxK8mt5KA5sLwDH+KZRUwEZniM4LquuQvYrQfryfkRNTKco6GdVveO8C LpUM4CK8Nb02cKYSI+zMOvfyz7T/dhZSr7hpARL5x8Je1siqlTPmUzYxnu1PL5JeTUt086 FU3IdbkHYCyK6Yx7J2HoxaMJMzao07gsncpptpEr9jInXt+O90rKSuqteqY5vwBoDGrooK 030Qa8LXDzY8dj9wMmDm+R7Y7ZAt7uYRNhNsPAR0BOaGAoHd3/Mjg1lST4DoLx5TVl5Rtq B8zmdBzYtWY54prp7kToQyeg7e1BN86x1Ft3wyh4Fp0dMMwa07ffH8fpM75zEg== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1ogpMc-004JUP-2d; Fri, 07 Oct 2022 08:34:14 -0700 In-Reply-To: Received-SPF: pass client-ip=2001:4b98:dc4:8::222; envelope-from=matt@rfc20.org; helo=relay2-d.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:297163 Archived-At: Gerd M=C3=B6llmann writes: > Matt Armstrong writes: > >>> Clang libstd++ uses NULL, BTW, and I already wondered a little bit why. >> >> I believe GNU libstdc++ does not use sentinel nodes either. I have yet >> to see see sentinel nodes used in an optimized tree implementation. > > I looked it up a few days ago, out of interest, and GCC's rb-tree uses > sentinels, in Git master at least. Somewhere in this thread I posted > where to look in GCC's Git repo, I can't remember ATM. It uses a sentinel for the parent of the root node (a "header") but it does not use a sentinel node for null at the leaves. The easiest way to see it is by looking at the code for GNU libstdc++ "minimum()" algorithm on trees, which walks left ponters down to a leaf node: https://gcc.gnu.org/git/?p=3Dgcc.git;a=3Dblob;f=3Dlibstdc%2B%2B-v3/include/= bits/stl_tree.h;h=3Da4de61417652a288e361a55fcc8bb7a9838c58a5;hb=3DHEAD#l112 _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT { while (__x->_M_left !=3D 0) __x =3D __x->_M_left; return __x; } For the header node, see https://gcc.gnu.org/git?p=3Dgcc.git;a=3Dblob;f=3Dlibstdc%2B%2B-v3/include/b= its/stl_tree.h;h=3Da4de61417652a288e361a55fcc8bb7a9838c58a5;hb=3DHEAD#l89