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.

1 files changed, 0 insertions, 1 deletions

diff --git a/src/itree.h b/src/itree.h
index a04ff6827cf..8f6bb667d64 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -76,7 +76,6 @@ void interval_tree_destroy (struct interval_tree *);
 intmax_t interval_tree_size (struct interval_tree *);
 void interval_tree_clear (struct interval_tree *);
 void interval_tree_insert (struct interval_tree *, struct interval_node *);
-bool interval_tree_contains (struct interval_tree *, struct interval_node *);
 struct interval_node *interval_tree_remove (struct interval_tree *, struct interval_node *);
 struct interval_generator *interval_tree_iter_start (struct interval_tree *, ptrdiff_t, ptrdiff_t, enum interval_tree_order,
 			       const char* file, int line);