From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Andreas Politz Newsgroups: gmane.emacs.bugs Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Sun, 02 Oct 2022 18:32:19 +0200 Message-ID: <87zgeegp9o.fsf@andreas-politz.de> References: <83h70qhez0.fsf@gnu.org> <83edvuhaby.fsf@gnu.org> <831qruh67o.fsf@gnu.org> <83y1u2foli.fsf@gnu.org> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="7396"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.1 (gnu/linux) Cc: Eli Zaretskii , 58158@debbugs.gnu.org, Stefan Monnier To: Gerd =?UTF-8?Q?M=C3=B6llmann?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sun Oct 02 18:52:39 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 1of2Ck-0001mL-Tv for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 02 Oct 2022 18:52:39 +0200 Original-Received: from localhost ([::1]:41846 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1of2Cj-0002eq-NT for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 02 Oct 2022 12:52:37 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:34654) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1of2CA-00027e-V9 for bug-gnu-emacs@gnu.org; Sun, 02 Oct 2022 12:52:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:48829) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1of2CA-0000E9-NX for bug-gnu-emacs@gnu.org; Sun, 02 Oct 2022 12:52:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1of2CA-0007lt-Ih for bug-gnu-emacs@gnu.org; Sun, 02 Oct 2022 12:52:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Andreas Politz Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 02 Oct 2022 16:52: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.166472951329857 (code B ref 58158); Sun, 02 Oct 2022 16:52:02 +0000 Original-Received: (at 58158) by debbugs.gnu.org; 2 Oct 2022 16:51:53 +0000 Original-Received: from localhost ([127.0.0.1]:47907 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1of2C0-0007lU-O7 for submit@debbugs.gnu.org; Sun, 02 Oct 2022 12:51:53 -0400 Original-Received: from mout.kundenserver.de ([217.72.192.75]:59777) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1of1tP-0007Gj-1U for 58158@debbugs.gnu.org; Sun, 02 Oct 2022 12:32:39 -0400 Original-Received: from localhost ([77.180.185.96]) by mrelayeu.kundenserver.de (mreue106 [213.165.67.113]) with ESMTPSA (Nemesis) id 1MTAW9-1on1jK31lX-00UejG; Sun, 02 Oct 2022 18:32:25 +0200 In-Reply-To: ("Gerd =?UTF-8?Q?M=C3=B6llmann?="'s message of "Sun, 02 Oct 2022 10:22:21 +0200") X-Provags-ID: V03:K1:mlafmVVJ5KEPMZSU7arhvU94X+ClbrYLm7vJ9kQvSmOn1LGWDVh KnS4LlkqSP4ltbxTP45Bp2Rb4LEb7dsMJSPMtOaOioulMhutKJYTKSPaL+s1ZuubhEZ7Y4h 9WHk6fFChot+yAZH+VpmFs+PM68kYim3Kyz+D9A/bjftN1fXLqjL6qMLRq3l+TRth5Fviph 2soR6glRCKAEWWNYLkTEg== X-UI-Out-Filterresults: notjunk:1;V03:K0:6o2ihyT/1cg=:mgtOyeDSARMsW7olWa/iuq tig9fpOgGjUS/koIYS8gsFSce5oFYEBYWL3wrs6fBW0FTfiufCpB/zMUY8o0n//UP0O5uap5N RpVyvjb+r3KDDz4tE26pxjhzp09seiICgvR4uVtEDbcnBvFj7pBKIbGEc+q1DYDWXsU5eqxp6 Y2hIdJx4q3KUi+ofEWJkS0RwpvYU3AqqksFt9VPBLDO8ezXarCzCbVaYWhCdrsm+wSBEdeOHH EvSnoFJAfPIIiSfA3ffEAIHD6f0p8sVFjsISckxq0jRSGmi4gBJ3P+7MkUJrOCDTNp8fSQg5R bp3wDFTx3H4TzH3daq8bP+SYezz3ChDj9nLHN5d06ULf20sZaxENNWBS0WkaQyP7TnqXriytF JDUaviax3kVWi0mRV6BHYtrAquFIhx46UA6DajIyW2npkSEZRHtZDncz/AMGaeAt4bVdOmi89 B2Xmr0LtWuUhIq0pT69gO80SnGWoMmUDhIXpFk3yMTWK3o/1vGFyhYZKcNmo1MT9FhYamNy60 HyzzMYWfT++2HyjrNuuKKwhsrn5/SJlnJx7PTWyLDwkngUtDkwPbOvZIG675GZXABOwhKUvin fts9QFfsPWwY7ZLbLvcUG2XUsH+tuTHT9W/fmGKV4mi6IOfqsvsJYlYViPFpK/KnMN0nTKzMI SsxhADxKwKXJj4qhZgxLFnYACTZ7bShQ3K1OxyTOtS+6ZGkN87fXMvYbE22sQuKM0mJN9XmNB mc/ilEhNeKrctEUklml/mCzMtu8ES6sumz8l4lzhYPn/7pJ0pkAyAHcIeJz+l0IS+hQ3ceiN X-Mailman-Approved-At: Sun, 02 Oct 2022 12:51:51 -0400 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:244245 Archived-At: --=-=-= Content-Type: text/plain I've managed to construct a prototype of this "stateless" iterator. I've only implemented the in-order case and only applied it in the overlays_in function. The only real trouble I had was with pushing the offset to the children during the tree navigation in some kind of sensible way. In the end I gave up and simply pasted calls to the corresponding function "all over the place". It seems to work, at least buffer-tests are passing. Andreas --=-=-= Content-Type: text/x-patch Content-Disposition: inline; filename=noverlay-stateless-iterator.diff diff --git a/src/buffer.c b/src/buffer.c index f59fddcbde..6a53b49aad 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -2948,15 +2948,16 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend, ptrdiff_t next = ZV; Lisp_Object *vec = *vec_ptr; struct interval_node *node; + struct interval_tree_iterator iterator; - ITREE_FOREACH (node, current_buffer->overlays, beg, - /* Find empty OV at Z ? */ - (end >= ZV && empty) ? ZV + 1 : ZV, ASCENDING) + interval_tree_iterator_init(&iterator, current_buffer->overlays, beg, + (end >= ZV && empty) ? ZV + 1 : ZV, ITREE_ASCENDING); + + while ((node = interval_tree_iterator_next(&iterator))) { if (node->begin > end) { next = min (next, node->begin); - ITREE_FOREACH_ABORT (); break; } else if (node->begin == end) @@ -2964,7 +2965,6 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend, next = node->begin; if ((! empty || end < ZV) && beg < end) { - ITREE_FOREACH_ABORT (); break; } } diff --git a/src/itree.c b/src/itree.c index eeecaf1839..21549fe8a7 100644 --- a/src/itree.c +++ b/src/itree.c @@ -1190,3 +1190,132 @@ interval_tree_subtree_min (const struct interval_tree *tree, struct interval_nod * +===================================================================================+ */ /* See Foverlay_tree in buffer.c */ + + +/* +===================================================================================+ + * | Stateless iterator + * +===================================================================================+ */ + +static bool +interval_tree_iter_traverse_p(struct interval_tree_iterator *iterator, + struct interval_node *node); +static +struct interval_node * +interval_tree_iterator_in_order_successor (struct interval_tree_iterator* iterator); + +void +interval_tree_iterator_init(struct interval_tree_iterator *iterator, + struct interval_tree *tree, + ptrdiff_t begin, + ptrdiff_t end, + enum interval_tree_order order) { + iterator->tree = tree; + iterator->node = tree && begin <= end ? ITREE_NULL : NULL; + iterator->begin = begin; + iterator->end = end; + iterator->order = order; +} + +struct interval_node * +interval_tree_iterator_next(struct interval_tree_iterator *iterator) { + if (iterator->node) { + do { + switch (iterator->order) { + case ITREE_ASCENDING: + iterator->node = interval_tree_iterator_in_order_successor (iterator); + break; + default: + fprintf (stderr, "interval_tree_order != ITREE_ASCENDING not implemented"); + emacs_abort (); + } + } while (iterator->node && + ! interval_node_intersects (iterator->node, iterator->begin, iterator->end)); + } + + if (iterator->node == ITREE_NULL) { + fprintf (stderr, "Next node: ITREE_NULL\n"); + } else if (! iterator->node) { + fprintf (stderr, "Next node: NULL\n"); + } else { + fprintf (stderr, "Next node: begin = %ld, end = %ld (iterator: begin = %ld, end = %ld)\n", + iterator->node->begin, iterator->node->end, iterator->begin, iterator->end); + } + return iterator->node; +} + +static bool +interval_tree_iter_traverse_p(struct interval_tree_iterator *iterator, + struct interval_node *node) { + eassert (node); + + if (node == ITREE_NULL) { + return false; + } else { + eassert (node->parent != ITREE_NULL); + if (node->parent->left == node) { + return iterator->begin <= node->limit + node->offset; + } else { + return node->parent->begin <= iterator->end; + } + } +} + +static +struct interval_node * +interval_tree_iterator_in_order_successor (struct interval_tree_iterator* iterator) +{ + struct interval_node *node = iterator->node; + + if (node != ITREE_NULL) { + interval_tree_inherit_offset (iterator->tree, node); + } + + if (node == ITREE_NULL) { + node = iterator->tree->root; + if (node != ITREE_NULL) { + interval_tree_inherit_offset (iterator->tree, node); + } + while (interval_tree_iter_traverse_p(iterator, node->left)) { + node = node->left; + if (node != ITREE_NULL) { + interval_tree_inherit_offset (iterator->tree, node); + } + } + } else if (interval_tree_iter_traverse_p(iterator, node->right)) + { + node = node->right; + if (node != ITREE_NULL) { + interval_tree_inherit_offset (iterator->tree, node); + } + while (interval_tree_iter_traverse_p(iterator, node->left)) { + node = node->left; + if (node != ITREE_NULL) { + interval_tree_inherit_offset (iterator->tree, node); + } + } + } + else + { + struct interval_node *parent = node->parent; + while (node == parent->right) + { + node = parent; + parent = parent->parent; + } + if (node != ITREE_NULL) + node = parent; + } + + return node == ITREE_NULL ? NULL : node; +} + +void +interval_tree_iterator_narrow (struct interval_tree_iterator *iterator, + ptrdiff_t begin, + ptrdiff_t end) +{ + eassert (begin >= iterator->begin); + eassert (end <= iterator->end); + iterator->begin = max (begin, iterator->begin); + iterator->end = min (end, iterator->end); +} diff --git a/src/itree.h b/src/itree.h index 1f019a2607..53f03cca35 100644 --- a/src/itree.h +++ b/src/itree.h @@ -72,6 +72,15 @@ #define ITREE_NULL (&itree_null) ITREE_PRE_ORDER, }; +struct interval_tree_iterator +{ + struct interval_tree *tree; + struct interval_node *node; + ptrdiff_t begin; + ptrdiff_t end; + enum interval_tree_order order; +}; + void interval_node_init (struct interval_node *, ptrdiff_t, ptrdiff_t, bool, bool, Lisp_Object); ptrdiff_t interval_node_begin (struct interval_tree *, struct interval_node *); ptrdiff_t interval_node_end (struct interval_tree *, struct interval_node *); @@ -135,4 +144,15 @@ #define ITREE_FOREACH_ABORT() \ #define ITREE_FOREACH_NARROW(beg, end) \ interval_generator_narrow (itree_iter_, beg, end) +void interval_tree_nodes (struct interval_tree *tree, struct interval_node **nodes, enum interval_tree_order order); + +void interval_tree_iterator_init(struct interval_tree_iterator *iterator, + struct interval_tree *tree, + ptrdiff_t begin, + ptrdiff_t end, + enum interval_tree_order order); +struct interval_node *interval_tree_iterator_next(struct interval_tree_iterator *iterator); +void interval_tree_iterator_narrow (struct interval_tree_iterator *iterator, + ptrdiff_t begin, + ptrdiff_t end); #endif --=-=-=--