From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Gerd =?UTF-8?Q?M=C3=B6llmann?= Newsgroups: gmane.emacs.bugs Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Thu, 29 Sep 2022 16:37:51 +0200 Message-ID: References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.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="18751"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) Cc: Eli Zaretskii , 58158@debbugs.gnu.org To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Thu Sep 29 17:43:08 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@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 1odvgn-0004bt-OT for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 29 Sep 2022 17:43:05 +0200 Original-Received: from localhost ([::1]:60822 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1odvgm-0002SX-QH for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 29 Sep 2022 11:43:04 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:48944) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1odugp-0006ta-AX for bug-gnu-emacs@gnu.org; Thu, 29 Sep 2022 10:39:04 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:40154) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1odugo-0006uG-2O for bug-gnu-emacs@gnu.org; Thu, 29 Sep 2022 10:39:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1odugn-0007JN-Tc for bug-gnu-emacs@gnu.org; Thu, 29 Sep 2022 10:39:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Gerd =?UTF-8?Q?M=C3=B6llmann?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 29 Sep 2022 14:39:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 58158 X-GNU-PR-Package: emacs Original-Received: via spool by 58158-submit@debbugs.gnu.org id=B58158.166446228228027 (code B ref 58158); Thu, 29 Sep 2022 14:39:01 +0000 Original-Received: (at 58158) by debbugs.gnu.org; 29 Sep 2022 14:38:02 +0000 Original-Received: from localhost ([127.0.0.1]:39230 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odufp-0007Hp-Q5 for submit@debbugs.gnu.org; Thu, 29 Sep 2022 10:38:02 -0400 Original-Received: from mail-ej1-f45.google.com ([209.85.218.45]:46059) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1odufn-0007HU-Nt for 58158@debbugs.gnu.org; Thu, 29 Sep 2022 10:38:00 -0400 Original-Received: by mail-ej1-f45.google.com with SMTP id dv25so3203356ejb.12 for <58158@debbugs.gnu.org>; Thu, 29 Sep 2022 07:37:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:user-agent:message-id:date :references:in-reply-to:subject:cc:to:from:from:to:cc:subject:date; bh=BW9KqAyaC9VT8Y1KCNDntO52On0zO30gIztAZoX+b1w=; b=Y+MdZh22wuOapmR8I+NnA+jV3oenfaK/MaTmh/shoJi7GM5E5vwgcqwO/k9GUhjUwv NG13Y+XuobQzAM3GOGZMHFtIGCmiSrEUQYtBUL9LTZ2+EyNo1A9oisYoCBJ+upUW6mcZ CIYkFlG003seFr3bDxfS68ck4+IfJqeNa4KuROk0bjmZrXCFEv06uv5tkzWE7mdADvfK WfdNGI/HIF1ppwZ0rJ6QC928bInRSFWiBtGvQzSHhvHJX6gL015KNijlnC4YGihlFgrR Yg6hm3ei5XULU+4WBYZQGnqeccfWITfFTqp1+FOgMtsxKdXcQ8JHUGej2zcankDwpGdA bUjA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:user-agent:message-id:date :references:in-reply-to:subject:cc:to:from:x-gm-message-state:from :to:cc:subject:date; bh=BW9KqAyaC9VT8Y1KCNDntO52On0zO30gIztAZoX+b1w=; b=NO9Y/a76DKkCwuugwkCIgV3stxC+dDiHuHuo4nlYDzBMhSIggP4IowWHvCWtMApuK6 yiyAp9hZfO6xDCoXa6CIhq/CJxQ7C+J+lcg8G4F5a/uH/SHQJeJghuMUpevVF15+GTG0 GrIeZZDRjiP5CcOWtfyH7QKu6zgeT+QJi+Nin1jz9GmtXefFJKXC8z0q7Wa22y1SzvBD iUGv2jBpVp5EojC4M24dOWk7St/S0hCYGk5eEl0XfEuv7XnX784o+T+HE5k3/CG0qLeq TrvEVvjZPovXJJz2VdjXuDm/HCHjupgPDu0jOpFbBsNNJ+tC5A3MtG+JQdyCshqys27j LRww== X-Gm-Message-State: ACrzQf2vtzflTDTKgRTLhSgulQLrjGHwL+hJE7vv7c028mj8dXnOQMZP SW3VaUBlhuD9WvkXMpoMXDa11MFZtuc2mg== X-Google-Smtp-Source: AMsMyM4WJ8PZRkL+HBPRIdFE0jxU2wEOnD4HCtx0eAfZvvIFAxHmuUk1LWOX8IpjMVLSmSpyCOo16A== X-Received: by 2002:a17:907:3f8c:b0:787:a14d:65a7 with SMTP id hr12-20020a1709073f8c00b00787a14d65a7mr3065830ejc.108.1664462273346; Thu, 29 Sep 2022 07:37:53 -0700 (PDT) Original-Received: from Mini.fritz.box (pd9e36935.dip0.t-ipconnect.de. [217.227.105.53]) by smtp.gmail.com with ESMTPSA id m9-20020a509989000000b0045391f7d877sm5775857edb.53.2022.09.29.07.37.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Sep 2022 07:37:52 -0700 (PDT) In-Reply-To: ("Gerd =?UTF-8?Q?M=C3=B6llmann?="'s message of "Thu, 29 Sep 2022 16:15:09 +0200") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:243917 Archived-At: Gerd M=C3=B6llmann writes: > Stefan Monnier writes: > >> One reason is that traversing a binary tree usually requires something >> like recursion, but that wouldn't fit very conveniently with the current >> code (nor with C in general since you can't make a local recursive >> closure which accesses local variables from the surrounding function). > > Ok, usually, but not necessarily. The alternative is to implement an > iterator that starts with a node N, and an implementation of a successor > function, which return the successor of N in a given order. This > requires a parent pointer in nodes, but that we have. > > (Something like this is used for ordered containers like "map" and "set" > in C++ STL, for instance, which are based on rb-trees in GCC's > libstdc++.) The code from libstdc++ is this (from libstdc++-v3/src/c++98/tree.cc): static _Rb_tree_node_base* local_Rb_tree_increment(_Rb_tree_node_base* __x) throw () { if (__x->_M_right !=3D 0) { __x =3D __x->_M_right; while (__x->_M_left !=3D 0) __x =3D __x->_M_left; } else { _Rb_tree_node_base* __y =3D __x->_M_parent; while (__x =3D=3D __y->_M_right) { __x =3D __y; __y =3D __y->_M_parent; } if (__x->_M_right !=3D __y) __x =3D __y; } return __x; } I hope one can read that. The idea is to find the root of the smallest subtree containing the current node, and proceed from there. That's why the parent pointer is needed. Symmmetrical for max->min ordering. And finding min/max is trivial.