Re: noverlay branch

[Matt Armstrong <matt@rfc20.org>]

[-- Attachment #1: Type: text/plain, Size: 1684 bytes --]

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:


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Comment-change-explain-inheriting-dirty-offsets.patch --]
[-- Type: text/x-diff, Size: 1507 bytes --]

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