]> git.eshelyaron.com Git - emacs.git/commit
itree.c: Fix incomplete update of `limit`s in corner cases
authorStefan Monnier <monnier@iro.umontreal.ca>
Wed, 5 Oct 2022 20:35:31 +0000 (16:35 -0400)
committerStefan Monnier <monnier@iro.umontreal.ca>
Wed, 5 Oct 2022 20:38:50 +0000 (16:38 -0400)
commit5642b4a255171f5593ae56ae76c98daf7f4cd6ad
treec1d684738771c181d6f57cd34485688e5ca1869e
parentaa5a32ca2c07691f3f10b7ec0c423ade11479220
itree.c: Fix incomplete update of `limit`s in corner cases

`interval_tree_remove` called `interval_tree_propagate_limit (subst)`
and `interval_tree_propagate_limit (min_right)` but both of those nodes
are moved without touching their subtrees, so their `limit`s are
"stable" causing `interval_tree_propagate_limit` to do nothing.
Indeed we don't need to update those nodes's `limit`s but we *do*
need to update their parents since those nodes have been moved.
Incidentally, this removes some uses of `null->parent` :-)

There are more uses of `null->parent`, tho, so I added more comments
explaining them (with the help of the matching section of the book
from which the algorithm was taken).

* src/itree.c (interval_tree_update_limit): Remove unused arg `tree`.
(interval_tree_rotate_left, interval_tree_rotate_right): Adjust callers.
(interval_tree_contains): Mark as static.
(itree_limit_is_stable, itree_limits_are_stable): New functions.
(interval_tree_remove): Fix incomplete update of `limit`s in corner
cases.
(interval_generator_next): Add sanity check to make sure the `limit`s
were properly updated.

* src/itree.h (interval_tree_contains): Remove declaration.
src/itree.c
src/itree.h