]> git.eshelyaron.com Git - emacs.git/commit
itree.c: Fix corner case errors in offsets
authorStefan Monnier <monnier@iro.umontreal.ca>
Thu, 6 Oct 2022 02:55:54 +0000 (22:55 -0400)
committerStefan Monnier <monnier@iro.umontreal.ca>
Thu, 6 Oct 2022 02:55:54 +0000 (22:55 -0400)
commit1f31534f510fdd9ed3166f761d736c0dda322db5
tree530eed551b8068a66fb0452227d465c54c301e55
parent5642b4a255171f5593ae56ae76c98daf7f4cd6ad
itree.c: Fix corner case errors in offsets

In some cases, `interval_tree_remove` could cause some nodes to
inherit fewer (or additional) offsets than the should because nodes
were transplanted between two parts of the tree where offsets had not
been propagated "equally".  So we remove/apply all offsets along the
path between the two points of a transplant before doing the transplant.

* src/itree.c (interval_tree_subtree_min): Move before first use; delete
the declaration; add an `otick` argument, and use it to update offsets
along the way.
(interval_tree_remove): Update all offsets on the way from `node` to `min`.
Reorder some of the operations so that when we transplant `min` to `node`
those nodes are in the proper state where `interval_tree_transplant`
can do its sanity checks.
(itree_total_offset): New function.
(interval_tree_transplant): Use it to sanity check that improper
offsets aren't accidentally inherited/lost because of the transplant.
(itree_newlimit): New function.
(itree_limit_is_stable, interval_tree_update_limit)
(interval_tree_propagate_limit): Use it.
(null_is_sane): Remove `inline` annotation; it's not needed.
(interval_tree_inherit_offset): Sanity check that `offset` is 0 when
`otick` is uptodate.  Skip the unneeded increments when the offset is 0.
(interval_tree_insert_fix): Add sanity check that we indeed have 2 reds.
src/itree.c