[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: noverlay branch
From: |
Matt Armstrong |
Subject: |
Re: noverlay branch |
Date: |
Sat, 08 Oct 2022 20:44:46 -0700 |
Matt Armstrong <matt@rfc20.org> writes:
> From 87204feaa4f50744701481f3aa051483647cf9da Mon Sep 17 00:00:00 2001
> From: Matt Armstrong <matt@rfc20.org>
> Date: Sat, 8 Oct 2022 09:15:26 -0700
> Subject: [PATCH 1/2] Comment change: explain inheriting "dirty" offsets
>
> ; * src/itree.c (interval_generator_next): explain why the code
> handles inheriting offsets from dirty nodes.
> ---
> src/itree.c | 14 +++++++++++---
> 1 file changed, 11 insertions(+), 3 deletions(-)
>
> diff --git a/src/itree.c b/src/itree.c
> index de16af5b0c..1fc711b021 100644
> --- a/src/itree.c
> +++ b/src/itree.c
> @@ -1086,9 +1086,17 @@ interval_tree_inherit_offset (uintmax_t otick, struct
> interval_node *node)
> node->right->offset += node->offset;
> node->offset = 0;
> }
> - /* FIXME: I wonder when/why this condition can be false, and more generally
> - why we'd want to propagate offsets that may not be fully up-to-date. */
> - if (node->parent == ITREE_NULL || node->parent->otick == otick)
> + /* FIXME: I wonder when/why this condition can be false, and more
> + generally why we'd want to propagate offsets that may not be
> + fully up-to-date. --stef
> +
> + Offsets can be inherited from dirty nodes (with out of date
> + otick) during insert and remove. Offsets aren't inherited
> + downward from the root for these operations so rotations are
> + performed on potentially "dirty" nodes. We could fix this by
> + always inheriting offsets downward from the root for every insert
> + and remove. --matt
> + */
> node->otick = otick;
> }
Correction to the above patch, where I inadvertently deleted a line of
code:
>From 30f52202775155c1d301af3634d0122c3d7851f8 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Sat, 8 Oct 2022 09:15:26 -0700
Subject: [PATCH 1/3] Comment change: explain inheriting "dirty" offsets
; * src/itree.c (interval_generator_next): explain why the code
handles inheriting offsets from dirty nodes.
---
src/itree.c | 13 +++++++++++--
1 file changed, 11 insertions(+), 2 deletions(-)
diff --git a/src/itree.c b/src/itree.c
index de16af5b0c..05851007f5 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -1086,8 +1086,17 @@ interval_tree_inherit_offset (uintmax_t otick, struct
interval_node *node)
node->right->offset += node->offset;
node->offset = 0;
}
- /* FIXME: I wonder when/why this condition can be false, and more generally
- why we'd want to propagate offsets that may not be fully up-to-date. */
+ /* FIXME: I wonder when/why this condition can be false, and more
+ generally why we'd want to propagate offsets that may not be
+ fully up-to-date. --stef
+
+ Offsets can be inherited from dirty nodes (with out of date
+ otick) during insert and remove. Offsets aren't inherited
+ downward from the root for these operations so rotations are
+ performed on potentially "dirty" nodes. We could fix this by
+ always inheriting offsets downward from the root for every insert
+ and remove. --matt
+ */
if (node->parent == ITREE_NULL || node->parent->otick == otick)
node->otick = otick;
}
--
2.35.1
Re: noverlay branch, Stefan Monnier, 2022/10/06
Re: noverlay branch, Matt Armstrong, 2022/10/06
Re: noverlay branch, Matt Armstrong, 2022/10/07
- Re: noverlay branch, Stefan Monnier, 2022/10/07
- Re: noverlay branch, Matt Armstrong, 2022/10/08
- Re: noverlay branch,
Matt Armstrong <=
- Re: noverlay branch, Stefan Monnier, 2022/10/09
- Re: noverlay branch, Stefan Monnier, 2022/10/09
- Re: noverlay branch, Matt Armstrong, 2022/10/09
- Re: noverlay branch, Eli Zaretskii, 2022/10/10
- Re: noverlay branch, Matt Armstrong, 2022/10/10
- Re: noverlay branch, Stefan Monnier, 2022/10/10
- Re: noverlay branch, Matt Armstrong, 2022/10/10
- Re: noverlay branch, Stefan Monnier, 2022/10/11
- Re: noverlay branch, Matt Armstrong, 2022/10/11
- Re: noverlay branch, Stefan Monnier, 2022/10/11