]> git.eshelyaron.com Git - emacs.git/commit
Delete the itree_null sentinel node, use NULL everywhere.
authorMatt Armstrong <matt@rfc20.org>
Wed, 12 Oct 2022 17:06:03 +0000 (10:06 -0700)
committerStefan Monnier <monnier@iro.umontreal.ca>
Mon, 17 Oct 2022 14:16:27 +0000 (10:16 -0400)
commit258e618364a878658a5bb5f3997034d5ad17fead
treea3b4df137d1efc33500f5c59e93420b1b583acba
parentb86505387480fed81629cbc81cef6b70098bd607
Delete the itree_null sentinel node, use NULL everywhere.

This effort caught a few (already commited) places that were
dereferencing through ITREE_NULL in a confusing way.  It makes some
functions have to check for NULL in more places, but in my experinece
this is worth it from a code clarity point of view.

In doing this I rewrote `interval_tree_remove` completely.  There
there was one final bug in that function that I simply could not find
when I #define'd ITREE_NULL to NULL.  I couldn't easily understand
that function, so instead I rewrote it completely with a focus on code
clarity.  Bug went away.

I have left the ITREE_NULL #define in code, to reduce code review
noise.  It is easily removed later, mechanically.

* src/itree.h: #define ITREE_NULL to NULL and leave a FIXME.
* src/itree.c (itree_null): Delete the itree_null static variable.
(null_is_sane): Delete (and all callers).
(interval_tree_insert): Insert the first node as black straight away.
(itree_newlimit): Handle NULL children.
(interval_tree_remove_fix): ditto.
(interval_tree_insert_fix): ditto.
(interval_tree_remove): Rewrite for clarity.
(null_safe_is_red): New function.
(null_safe_is_black): New function.
(interval_tree_replace_child): Renamed from interval_tree_transplant.
(interval_tree_transplant): New function that something I think is
more like a full transplantation.  (names are hard)
src/itree.c
src/itree.h