From a66280162f907a09be23922cc80ac352392adac6 Mon Sep 17 00:00:00 2001 From: "Basil L. Contovounesios" Date: Wed, 2 Nov 2022 03:50:38 +0200 Subject: Port interval trees to --enable-checking=structs Some names under the interval_* namespace were renamed under the itree_* namespace in commits: 0. f421b58db5 of 2022-10-19 "Prefix all itree.h type names with itree_". 1. 37a1145410 of 2022-10-19 "Rename all exported itree.h functions with the itree_ prefix" Further, some values still referenced in commentary were removed in commits: 2. 258e618364 of 2022-10-17 "Delete the itree_null sentinel node, use NULL everywhere." 3. 2c4a3910b3 of 2022-10-02 "itree: Use a single iterator object" * src/emacs.c (main): Allocate global itree iterator once and for all. * src/alloc.c (mark_overlay): * src/buffer.c (set_overlays_multibyte): * src/itree.c (itree_destroy): Update commentary. (interval_stack_ensure_space, itree_insert_gap): Prefer unsigned-to-unsigned comparisons over signed-to-unsigned. (interval_stack_push_flagged, interval_tree_insert) (interval_tree_contains, itree_iterator_start) (itree_iterator_finish, itree_iterator_next, itree_iterator_narrow): Improve assertions. (itree_init): Rename... (init_itree): ...to this, for consistency with other global init functions. (itree_create): Stop leaking a global iterator allocation on each call. (interval_tree_init): Complete renames of interval_tree -> itree_tree and interval_tree_clear -> itree_clear. (interval_tree_remove_fix): Fix indentation. * src/itree.h: Declare init_itree. (ITREE_FOREACH): Fix typo in commentary. * src/pdumper.c [CHECK_STRUCTS] (dump_interval_node): Use the correct name in the HASH condition and #error message. (dump_overlay, dump_buffer): Update HASH (bug#58975). --- src/itree.c | 42 +++++++++++++++++------------------------- 1 file changed, 17 insertions(+), 25 deletions(-) (limited to 'src/itree.c') diff --git a/src/itree.c b/src/itree.c index bd4e8cc5740..3137cb6358f 100644 --- a/src/itree.c +++ b/src/itree.c @@ -191,7 +191,7 @@ interval_stack_clear (struct interval_stack *stack) } static inline void -interval_stack_ensure_space (struct interval_stack *stack, intmax_t nelements) +interval_stack_ensure_space (struct interval_stack *stack, uintmax_t nelements) { if (nelements > stack->size) { @@ -207,7 +207,7 @@ static inline void interval_stack_push_flagged (struct interval_stack *stack, struct itree_node *node, bool flag) { - eassert (node && node != NULL); + eassert (node); /* FIXME: While the stack used in the iterator is bounded by the tree depth and could be easily pre-allocated to a large enough size to avoid @@ -287,8 +287,8 @@ itree_iterator_create (struct itree_tree *tree) return g; } -static void -itree_init (void) +void +init_itree (void) { iter = itree_iterator_create (NULL); } @@ -555,16 +555,11 @@ itree_node_end (struct itree_tree *tree, return node->end; } -/* Allocate an interval_tree. Free with interval_tree_destroy. */ +/* Allocate an itree_tree. Free with itree_destroy. */ struct itree_tree * itree_create (void) { - /* FIXME? Maybe avoid the initialization of itree_null in the same - way that is used to call mem_init in alloc.c? It's not really - important though. */ - itree_init (); - struct itree_tree *tree = xmalloc (sizeof (*tree)); itree_clear (tree); return tree; @@ -584,10 +579,9 @@ itree_clear (struct itree_tree *tree) /* Initialize a pre-allocated tree (presumably on the stack). */ static void -interval_tree_init (struct interval_tree *tree) +interval_tree_init (struct itree_tree *tree) { - interval_tree_clear (tree); - /* tree->iter = itree_iterator_create (tree); */ + itree_clear (tree); } #endif @@ -596,8 +590,6 @@ void itree_destroy (struct itree_tree *tree) { eassert (tree->root == NULL); - /* if (tree->iter) - * itree_iterator_destroy (tree->iter); */ xfree (tree); } @@ -775,7 +767,7 @@ interval_tree_insert_fix (struct itree_tree *tree, static void interval_tree_insert (struct itree_tree *tree, struct itree_node *node) { - eassert (node->begin <= node->end && node != NULL); + eassert (node && node->begin <= node->end); /* FIXME: The assertion below fails because `delete_all_overlays` doesn't set left/right/parent to NULL. */ /* eassert (node->left == NULL && node->right == NULL @@ -868,7 +860,7 @@ itree_node_set_region (struct itree_tree *tree, static bool interval_tree_contains (struct itree_tree *tree, struct itree_node *node) { - eassert (node); + eassert (iter && node); struct itree_node *other; ITREE_FOREACH (other, tree, node->begin, PTRDIFF_MAX, ASCENDING) if (other == node) @@ -912,7 +904,7 @@ interval_tree_remove_fix (struct itree_tree *tree, if (parent == NULL) eassert (node == tree->root); else - eassert (node == NULL || node->parent == parent); + eassert (node == NULL || node->parent == parent); while (parent != NULL && null_safe_is_black (node)) { @@ -1151,7 +1143,7 @@ itree_iterator_start (struct itree_tree *tree, ptrdiff_t begin, ptrdiff_t end, enum itree_order order, const char *file, int line) { - /* struct itree_iterator *iter = tree->iter; */ + eassert (iter); if (iter->running) { fprintf (stderr, @@ -1179,7 +1171,7 @@ itree_iterator_start (struct itree_tree *tree, ptrdiff_t begin, void itree_iterator_finish (struct itree_iterator *iter) { - eassert (iter->running); + eassert (iter && iter->running); iter->running = false; } @@ -1212,7 +1204,7 @@ itree_insert_gap (struct itree_tree *tree, && (node->begin != node->end || node->rear_advance)) interval_stack_push (saved, node); } - for (int i = 0; i < saved->length; ++i) + for (size_t i = 0; i < saved->length; ++i) itree_remove (tree, nav_nodeptr (saved->nodes[i])); /* We can't use an iterator here, because we can't effectively @@ -1352,7 +1344,7 @@ interval_node_intersects (const struct itree_node *node, struct itree_node * itree_iterator_next (struct itree_iterator *g) { - eassert (g->running); + eassert (g && g->running); struct itree_node *const null = NULL; struct itree_node *node; @@ -1424,9 +1416,9 @@ void itree_iterator_narrow (struct itree_iterator *g, ptrdiff_t begin, ptrdiff_t end) { - eassert (g->running); + eassert (g && g->running); eassert (begin >= g->begin); eassert (end <= g->end); - g->begin = max (begin, g->begin); - g->end = min (end, g->end); + g->begin = max (begin, g->begin); + g->end = min (end, g->end); } -- cgit v1.2.1