From 30f52202775155c1d301af3634d0122c3d7851f8 Mon Sep 17 00:00:00 2001 From: Matt Armstrong Date: Sat, 8 Oct 2022 09:15:26 -0700 Subject: [PATCH] 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 de16af5b0c2..05851007f5a 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.39.2