From ab2926aad3e15c6cfa0e4b31ae9274c47a58baf2 Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Fri, 30 Sep 2022 20:37:15 -0400 Subject: [PATCH] itree.c: Improve division between tree and iterator * src/buffer.c (delete_all_overlays): Add comment. * src/itree.c (struct interval_generator): New fields `running`, `file`, and `line` moved from `interval_tree`. (interval_stack_push_flagged): Adjust comment to resolve a FIXME. (interval_tree_clear): Replace assignment with an a (interval_tree_iter_next): Delete function. (interval_tree_clear): Don't set `iter_running` here any more. (interval_generator_create): Set it here instead. (interval_tree_iter_start): Fetch `iter` once and for all. (interval_generator_narrow): Mark it as non-static. (interval_tree_iter_next, interval_tree_iter_narrow): Delete functions. Inline their old bodies in the callers. (interval_tree_iter_finish): Take the iter rather than the whole tree. Adjust all callers. (interval_generator_next): Move `running `assertion here from `interval_tree_iter_next`. * src/buffer.h: Adjust accordingly. * src/itree.h (struct interval_tree): Remove fields `iter_running`, `file`, and `line`, moved to `interval_generator`. (interval_generator_narrow): Replace `interval_tree_iter_narrow`. --- src/buffer.c | 8 +++++ src/buffer.h | 6 ++-- src/itree.c | 93 ++++++++++++++++++++++++---------------------------- src/itree.h | 9 ++--- 4 files changed, 56 insertions(+), 60 deletions(-) diff --git a/src/buffer.c b/src/buffer.c index 2f026584bbf..19937216ed5 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -921,6 +921,14 @@ delete_all_overlays (struct buffer *b) if (! b->overlays) return; + /* FIXME: This loop sets the overlays' `buffer` field to NULL but + doesn't set the interval_nodes' `parent`, `left` and `right` + fields accordingly. I believe it's harmless, but a bit untidy since + other parts of the code are careful to set those fields to NULL when + the overlay is deleted. + Of course, we can't set them to NULL from within the iteration + because the iterator may need them (tho we could if we added + an ITREE_POST_ORDER iteration order). */ buffer_overlay_iter_start (b, PTRDIFF_MIN, PTRDIFF_MAX, ITREE_ASCENDING); while ((node = buffer_overlay_iter_next (b))) { diff --git a/src/buffer.h b/src/buffer.h index 447be06594c..ad3b2ad6df5 100644 --- a/src/buffer.h +++ b/src/buffer.h @@ -1458,21 +1458,21 @@ buffer_overlay_iter_next (struct buffer *b) { if (! b->overlays) return NULL; - return interval_tree_iter_next (b->overlays); + return interval_generator_next (b->overlays->iter); } INLINE void buffer_overlay_iter_finish (struct buffer *b) { if (b->overlays) - interval_tree_iter_finish (b->overlays); + interval_tree_iter_finish (b->overlays->iter); } INLINE void buffer_overlay_iter_narrow (struct buffer *b, ptrdiff_t begin, ptrdiff_t end) { if (b->overlays) - interval_tree_iter_narrow (b->overlays, begin, end); + interval_generator_narrow (b->overlays->iter, begin, end); } /* Return the start of OV in its buffer, or -1 if OV is not associated diff --git a/src/itree.c b/src/itree.c index 6d97dd2a715..4f8aea924ac 100644 --- a/src/itree.c +++ b/src/itree.c @@ -94,6 +94,9 @@ along with GNU Emacs. If not, see . */ incremented whenever some node's offset has changed. */ +/* FIXME: The code seems to use "generator" and "iterator" + inconsistently/interchangeably. We should fix this naming. */ + static struct interval_node *interval_tree_validate (struct interval_tree *, struct interval_node *); static void interval_generator_ensure_space (struct interval_generator *); static bool interval_node_intersects (const struct interval_node *, ptrdiff_t, ptrdiff_t); @@ -110,13 +113,8 @@ static struct interval_node *interval_tree_subtree_min (const struct interval_tr static struct interval_generator* interval_generator_create (struct interval_tree *); static void interval_generator_destroy (struct interval_generator *); static void interval_generator_reset (struct interval_generator *, - ptrdiff_t, ptrdiff_t, - enum interval_tree_order); -static void -interval_generator_narrow (struct interval_generator *g, - ptrdiff_t begin, ptrdiff_t end); -static inline struct interval_node* -interval_generator_next (struct interval_generator *g); + ptrdiff_t, ptrdiff_t, + enum interval_tree_order); static inline void interval_tree_iter_ensure_space (struct interval_tree *); /* The sentinel node, the null node. */ @@ -149,6 +147,9 @@ struct interval_generator ptrdiff_t begin; ptrdiff_t end; enum interval_tree_order order; + bool_bf running : 1; + const char* file; + int line; }; @@ -221,8 +222,11 @@ static inline void interval_stack_push_flagged (struct interval_stack *stack, struct interval_node *node, bool flag) { - /* FIXME: Isn't this redundant with the calls that are passed - `interval_tree_max_height` before the iteration? */ + /* FIXME: This call to `interval_stack_ensure_space` is a bit redundant + with the work of `interval_generator_ensure_space` but it's still needed + here because `interval_generator_next` can push up to 3 elements per + node it visits, so for a tree of depth N it can use up a stack + space up to 3 times larger than what we computed. :-( */ interval_stack_ensure_space (stack, stack->length + 1); stack->nodes[stack->length] = make_nav (node, flag); @@ -338,7 +342,6 @@ interval_tree_clear (struct interval_tree *tree) tree->root = null; tree->otick = 1; tree->size = 0; - tree->iter_running = false; } #ifdef ITREE_TESTING @@ -430,11 +433,11 @@ interval_tree_contains (struct interval_tree *tree, struct interval_node *node) struct interval_node *other; interval_tree_iter_start (tree, node->begin, PTRDIFF_MAX, ITREE_ASCENDING, __FILE__, __LINE__); - while ((other = interval_tree_iter_next (tree))) + while ((other = interval_generator_next (tree->iter))) if (other == node) break; - interval_tree_iter_finish (tree); + interval_tree_iter_finish (tree->iter); return other == node; } @@ -519,12 +522,12 @@ interval_tree_nodes (struct interval_tree *tree, struct interval_node *node; interval_tree_iter_start (tree, PTRDIFF_MIN, PTRDIFF_MAX, order, __FILE__, __LINE__); - while ((node = interval_tree_iter_next (tree))) + while ((node = interval_generator_next (tree->iter))) { *nodes = node; ++nodes; } - interval_tree_iter_finish (tree); + interval_tree_iter_finish (tree->iter); } /* Start a generator iterating all intervals in [BEGIN,END) in the @@ -538,47 +541,27 @@ interval_tree_iter_start (struct interval_tree *tree, enum interval_tree_order order, const char* file, int line) { - if (tree->iter_running) + struct interval_generator *iter = tree->iter; + if (iter->running) { fprintf (stderr, "Detected nested iteration!\nOuter: %s:%d\nInner: %s:%d\n", - tree->file, tree->line, file, line); + iter->file, iter->line, file, line); emacs_abort (); } - interval_generator_reset (tree->iter, begin, end, order); - tree->iter_running = true; - tree->file = file; - tree->line = line; -} - -/* Limit the search interval of the iterator to the given values. The - interval can only shrink, but never grow.*/ - -inline void -interval_tree_iter_narrow (struct interval_tree *tree, - ptrdiff_t begin, ptrdiff_t end) -{ - eassert (tree->iter_running); - interval_generator_narrow (tree->iter, begin, end); + interval_generator_reset (iter, begin, end, order); + iter->running = true; + iter->file = file; + iter->line = line; } /* Stop using the iterator. */ void -interval_tree_iter_finish (struct interval_tree *tree) -{ - eassert (tree->iter_running); - tree->iter_running = false; -} - -/* Return the next node of the iterator in the order given when it was - started; or NULL if there are no more nodes. */ - -inline struct interval_node* -interval_tree_iter_next (struct interval_tree *tree) +interval_tree_iter_finish (struct interval_generator *iter) { - eassert (tree->iter_running); - return interval_generator_next (tree->iter); + eassert (iter->running); + iter->running = false; } /* Ensure that the tree's iterator does not need to allocate space @@ -617,14 +600,15 @@ interval_tree_insert_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l order, so we need to remove them first. */ struct interval_stack *saved = interval_stack_create (0); struct interval_node *node = NULL; - interval_tree_iter_start (tree, pos, pos + 1, ITREE_PRE_ORDER, __FILE__, __LINE__); - while ((node = interval_tree_iter_next (tree))) + interval_tree_iter_start (tree, pos, pos + 1, + ITREE_PRE_ORDER, __FILE__, __LINE__); + while ((node = interval_generator_next (tree->iter))) { if (node->begin == pos && node->front_advance && (node->begin != node->end || node->rear_advance)) interval_stack_push (saved, node); } - interval_tree_iter_finish (tree); + interval_tree_iter_finish (tree->iter); for (int i = 0; i < saved->length; ++i) interval_tree_remove (tree, nav_nodeptr (saved->nodes[i])); @@ -737,14 +721,16 @@ interval_tree_delete_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l /* Allocate a new generator for TREE. */ -static struct interval_generator* -interval_generator_create (struct interval_tree *tree) +static struct interval_generator * +interval_generator_create (struct interval_tree *tree) { struct interval_generator *g = xmalloc (sizeof *g); + /* FIXME: Is tree ever non-empty here? */ const int size = interval_tree_max_height (tree) + 1; g->stack = interval_stack_create (size); g->tree = tree; + g->running = false; interval_generator_reset (g, 1, 0, ITREE_ASCENDING); return g; } @@ -791,11 +777,13 @@ interval_node_intersects (const struct interval_node *node, || (node->begin == node->end && begin == node->begin); } -/* Return the next node of G, or NULL if there is none. */ +/* Return the next node of the iterator in the order given when it was + started; or NULL if there are no more nodes. */ inline struct interval_node* interval_generator_next (struct interval_generator *g) { + eassert (g->running); if (! g) return NULL; struct interval_node * const null = ITREE_NULL; @@ -862,10 +850,11 @@ interval_generator_next (struct interval_generator *g) /* Limit G to the new interval [BEGIN, END), which must be a subset of the current one. I.E. it can't grow on either side. */ -static inline void +inline void interval_generator_narrow (struct interval_generator *g, ptrdiff_t begin, ptrdiff_t end) { + eassert (g->running); eassert (begin >= g->begin); eassert (end <= g->end); g->begin = max (begin, g->begin); @@ -923,6 +912,8 @@ interval_tree_inherit_offset (const struct interval_tree *tree, if (node->right != ITREE_NULL) node->right->offset += node->offset; node->offset = 0; + /* FIXME: I wonder when/why this condition can be false, and more generally + why we'd want to propagate offsets that may not be fully up-to-date. */ if (node == tree->root || node->parent->otick == tree->otick) node->otick = tree->otick; } diff --git a/src/itree.h b/src/itree.h index f1ef7f99463..b9294c5662c 100644 --- a/src/itree.h +++ b/src/itree.h @@ -60,9 +60,6 @@ struct interval_tree uintmax_t otick; /* offset tick, compared with node's otick. */ intmax_t size; /* Number of nodes in the tree. */ struct interval_generator *iter; - bool_bf iter_running : 1; - const char* file; - int line; }; enum interval_tree_order { @@ -84,9 +81,9 @@ bool interval_tree_contains (struct interval_tree *, struct interval_node *); struct interval_node *interval_tree_remove (struct interval_tree *, struct interval_node *); void interval_tree_iter_start (struct interval_tree *, ptrdiff_t, ptrdiff_t, enum interval_tree_order, const char* file, int line); -void interval_tree_iter_narrow (struct interval_tree *, ptrdiff_t, ptrdiff_t); -void interval_tree_iter_finish (struct interval_tree *); -struct interval_node *interval_tree_iter_next (struct interval_tree *); +void interval_generator_narrow (struct interval_generator *, ptrdiff_t, ptrdiff_t); +void interval_tree_iter_finish (struct interval_generator *); +struct interval_node *interval_generator_next (struct interval_generator *); void interval_tree_insert_gap (struct interval_tree *, ptrdiff_t, ptrdiff_t); void interval_tree_delete_gap (struct interval_tree *, ptrdiff_t, ptrdiff_t); void interval_tree_nodes (struct interval_tree *tree, struct interval_node **nodes, enum interval_tree_order order); -- 2.39.2