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: Sat, 01 Oct 2022 12:55:42 +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="3577"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (darwin) Cc: Eli Zaretskii , Andreas Politz , 58158@debbugs.gnu.org To: Stefan Monnier Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sat Oct 01 12:56:26 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 1oeaAU-0000nQ-9M for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 01 Oct 2022 12:56:26 +0200 Original-Received: from localhost ([::1]:37160 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oeaAT-0000jC-3b for geb-bug-gnu-emacs@m.gmane-mx.org; Sat, 01 Oct 2022 06:56:25 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:56310) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oeaA7-0000iD-20 for bug-gnu-emacs@gnu.org; Sat, 01 Oct 2022 06:56:04 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:44694) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oeaA6-0007Hp-LD for bug-gnu-emacs@gnu.org; Sat, 01 Oct 2022 06:56:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1oeaA6-00051i-Fi for bug-gnu-emacs@gnu.org; Sat, 01 Oct 2022 06:56:02 -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: Sat, 01 Oct 2022 10:56:02 +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.166462175319292 (code B ref 58158); Sat, 01 Oct 2022 10:56:02 +0000 Original-Received: (at 58158) by debbugs.gnu.org; 1 Oct 2022 10:55:53 +0000 Original-Received: from localhost ([127.0.0.1]:43770 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oea9x-000516-1w for submit@debbugs.gnu.org; Sat, 01 Oct 2022 06:55:53 -0400 Original-Received: from mail-ej1-f52.google.com ([209.85.218.52]:38513) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oea9u-00050s-Tg for 58158@debbugs.gnu.org; Sat, 01 Oct 2022 06:55:51 -0400 Original-Received: by mail-ej1-f52.google.com with SMTP id nb11so13728855ejc.5 for <58158@debbugs.gnu.org>; Sat, 01 Oct 2022 03:55:50 -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=qNAPSkWxQ7PNcU3lfdVdiVRNi9sWCpmvUKlRlu1IOBw=; b=TghEZR7fsmeLGgbkjzz9NeFF9roBNaSbxFLGMtUdNC1yvlOGkpQQpk3LH12M4QEO1R 1+1I90oXkAuXRmXFJ4DpxL1giovKmbxR8itqZ9tM/mSPSyAPCQv9qMR+3qW0QYQ8wYka UHR9nudicmkdiNr/soiqM/BWHC/Z2JauwpZ6oEdyVcsSu9m5vTu+1dSiU9ELHopnyS7P NPClaZLkn4Jxid3D2Lkg9IYCYQgin3BI1pPCodIT7CyaizjB4cUZ4zsMTv/E/QQkDDSI KGAYf8JwQv8kmtqrWefdtT3tjhf7axsiVxoOXIrKb+sl04x1gRp7Ef63yqHe754Dfofg j1cw== 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=qNAPSkWxQ7PNcU3lfdVdiVRNi9sWCpmvUKlRlu1IOBw=; b=Kx7vdc9MBnbOkTB+2hYhopBfgbikyH6P3nWFO1tgDt2RKuWoZFf0aNmiLOL5tP+rLW kNY/fvFTIb1QKXam0zmvtfUGI5doEd+NAZm3fK6zv0hz6jOS+csrqJn0NSs/ztJ+nMzo bpaTYlcVCF6rNuXzKCEOOXXuDqZ+CvvMr/4x7axhGd1D5eAs/P0flBBSgB5MmDWQAASn wRl9TG+77klqBQhWAlSaCGgmP22xXyYdd4InEMU5j9+gzZRbkzSXujMgAfGlYm73TgtC 1c/57FAUQQe6K5FiE6yyF2BSg5XQ5qJoK3NrubnGrYJS2997n/ulx2cthqaRENsx6p1J dSIw== X-Gm-Message-State: ACrzQf0Qel0sDPUZH2CFj3BSByGkqLqlfKFH3x8dCjSUS4ZuIpt0rPO6 HhzhoZrvG5/3r6XsUctnxmsp/+ibGW8= X-Google-Smtp-Source: AMsMyM66h15grNCLfDgOpde74pTAZhCHyDvO56QkLBHqjmHyW7aWzpG5wsUK49eneZMTWWzU4rCtQg== X-Received: by 2002:a17:906:a3c2:b0:783:19a2:74d3 with SMTP id ca2-20020a170906a3c200b0078319a274d3mr9290543ejb.288.1664621744561; Sat, 01 Oct 2022 03:55:44 -0700 (PDT) Original-Received: from Mini.fritz.box (p4fe3ace2.dip0.t-ipconnect.de. [79.227.172.226]) by smtp.gmail.com with ESMTPSA id cz7-20020a0564021ca700b0045724875fa2sm3353814edb.15.2022.10.01.03.55.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 01 Oct 2022 03:55:43 -0700 (PDT) In-Reply-To: ("Gerd =?UTF-8?Q?M=C3=B6llmann?="'s message of "Sat, 01 Oct 2022 09:25:47 +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:244103 Archived-At: Gerd M=C3=B6llmann writes: > I have to look at std::multimap, they manage to do this somehow. Well, I should have thought of that, because it's obvious from the fact they are able to use successor/predecessor functions :-/. The equivalent in our code would go like below, which is just written down in a hurry, so please bear with me. It's just about the idea. So: Insert a new interval_node only if overlay start is not in the tree already. If the contains a node for the start, make the node's value a list of overlays, and add the new one to it in an order that's convenient (The STL uses insertion order). As a consequence, keys is the rb-tree are unique, and it is always strictly ordered, rotations don't change that. The min node is the left-most node in a tree, and so on. So far so good. An iterator in the order min->max would have to record the interval_node in the tree plus information where in the list of overlays it is, if it is in any. Finding the next node is implemented with a successor function like the one I've shown from libstdc++. To find all overlays containing a given position POS, find the node whose start is <=3D POS. Start at the root of the tree, and walk the left link until we find the ndoes's start is <=3D POS. Then iterate forward until start > POS, returning only overlapping overlays. Finding overlays intersecting an interval [BEG, END] is not as nice, but we can exclude intervals starting after END. So we have to iterate over all overlays from the minimum of the tree, and iterate forward until we reach the first excluded one. That's so "easy" that even I can understand how it works :-). What am I overlooking?