[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful
From: |
Eli Zaretskii |
Subject: |
bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful |
Date: |
Thu, 29 Sep 2022 16:23:47 +0300 |
> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: Gerd Möllmann <gerd.moellmann@gmail.com>,
> 58158@debbugs.gnu.org
> Date: Thu, 29 Sep 2022 09:10:19 -0400
>
> > I may be missing something, but it looks like the sole purpose of the
> > iter_start/iter_finish dance is to ensure only one iteration per tree
> > is running at any given time, and that's because the iteration uses
> > some state variable(s) of which there's only one instance per tree.
> >
> > Stefan, am I missing something?
>
> 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).
I'm not sure I understand how recursion is related. Are you saying
that recursion is replaced with iteration? But then, if _start and
_finish are called by the same caller, we don't really need the
protection, since no one can start another iteration while the first
one runs. Right?
> Another is the need to update the begin/end fields (these need updating
> because of insertions/deletions but they're updated lazily while
> traversing the tree to avoid an O(N) complexity during the
> insertions/deletions). Hiding that behind 'some kind of "next node"
> function keeps the code more readable.
Where in the code do you see iteration that adds or deletes nodes?
> For now, I pushed a simple fix to traverse the tree "by hand" in the GC
> rather than via the iterator.
So this removes the restriction of not having GC during iteration?
Also, I take it that you don't consider the current code is as
"harmful" as Gerd thinks it is? IOW, you don't share his opinion that
this implementation is a "no-go"?
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Eli Zaretskii, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Eli Zaretskii, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Eli Zaretskii, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Eli Zaretskii, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Stefan Monnier, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful,
Eli Zaretskii <=
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Stefan Monnier, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Eli Zaretskii, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Stefan Monnier, 2022/09/29
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Eli Zaretskii, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Gerd Möllmann, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Stefan Monnier, 2022/09/30
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Stefan Monnier, 2022/09/30