[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 12:40:25 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) |
Gerd Möllmann [2022-09-29 16:15:09] wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> 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.
The approach currently used is somewhat similar to that. Some of the
difference is that we need an actual "iterator/generator" object to
remember the parameter of the filtering we want to apply to the set of
objects. And the problem is that this "object" is currently implemented
not only as a global value (thus restricting us to one-iteration at
a time) but also with some parts of the data stored in the tree.
I think this is the part that really needs to be changed.
> 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++.)
Another difference is that itree.c's iterator uses a local "work stack"
instead of traversing the tree exclusively via left/right/parent like in
the code you show. I don't know if that difference is important, tho.
>> 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.
>
> Is this for buffer text changes, something akin to a delayed update of
> marker positions?
Yes, exactly.
>> 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).
>
> BTW, and related to iteration directly, did you notice this in
> interval_tree_insert?
>
> /* This suggests that nodes in the right subtree are strictly
> greater. But this is not true due to later rotations. */
> child = node->begin <= child->begin ? child->left : child->right;
No, I had not noticed that yet, and I don't understand this comment.
Stefan
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, (continued)
- 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
- 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, Eli Zaretskii, 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 <=
- bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful, Richard Stallman, 2022/09/30