[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful
From: |
Stefan Monnier |
Subject: |
bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful |
Date: |
Thu, 29 Sep 2022 09:10:19 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) |
> 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).
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.
But yes, the current restriction to have a single iteration at a time is
a bit of a problem, especially because it's very "global". I added
a comment yesterday describing how we could make it non-global (hence
getting rid of the `visited` flag in the nodes).
For now, I pushed a simple fix to traverse the tree "by hand" in the GC
rather than via the iterator.
Stefan
- 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 <=
- 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, 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