From 091e0f04ffe494ee4cddb67670f0c495a7c9b691 Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Thu, 17 Nov 2022 18:09:37 -0500 Subject: [PATCH] itree.c: Get rid of the old iterator code Only use the new iterator which relies on a fixed size (and small) state in the iterator. This makes non-local exits safe within ITREE_FOREACH loops. * src/itree.c (make_nav, nav_nodeptr, nav_flag, itree_stack_clear) (itree_stack_push_flagged): Delete functions. (nodeptr_and_flag): Delete type. (struct itree_stack): Make the array hold plain pointers instead. (itree_stack_push): Inline the former code of `itree_stack_push_flagged`. (itree_stack_pop): Change return type. (itree_contains): Don't call `ITREE_FOREACH_ABORT` any more. (itree_insert_gap): Simplify access to the stack of nodes. (itree_delete_gap, itree_insert_gap): Adjust code to new return type of `itree_stack_pop`. (itree_iterator_finish): Delete function. (itree_iterator_start): Don't setup the `stack` field any more. (itree_iterator_next): Delete function. (itree_iter_next): Rename to `itree_iterator_next` and make it non-static. (itree_iterator_narrow): Don't check the `running` flag any more. * src/itree.h (itree_iterator_finish): Remove declaration. (struct itree_iterator): Remove the `stack` and `running` fields. (ITREE_FOREACH_ABORT): Delete macro. (ITREE_FOREACH): Don't call `itree_iterator_finish` any more. * src/xdisp.c (strings_with_newlines): * src/buffer.c (overlays_in, next_overlay_change, overlay_touches_p): Don't call `ITREE_FOREACH_ABORT` any more. --- src/buffer.c | 12 +--- src/itree.c | 199 +++++---------------------------------------------- src/itree.h | 16 +---- src/xdisp.c | 10 +-- 4 files changed, 23 insertions(+), 214 deletions(-) diff --git a/src/buffer.c b/src/buffer.c index 9be2c4a970e..4da5b451d0f 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -2985,17 +2985,13 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend, if (node->begin > end) { next = min (next, node->begin); - ITREE_FOREACH_ABORT (); break; } else if (node->begin == end) { next = node->begin; if ((! empty || end < ZV) && beg < end) - { - ITREE_FOREACH_ABORT (); - break; - } + break; if (empty && node->begin != node->end) continue; } @@ -3050,7 +3046,6 @@ next_overlay_change (ptrdiff_t pos) of pos, because the search is limited to [pos,next) . */ eassert (node->begin < next); next = node->begin; - ITREE_FOREACH_ABORT (); break; } else if (node->begin < node->end && node->end < next) @@ -3155,10 +3150,7 @@ overlay_touches_p (ptrdiff_t pos) pos. */ ITREE_FOREACH (node, current_buffer->overlays, pos - 1, pos + 1, DESCENDING) if (node->begin == pos || node->end == pos) - { - ITREE_FOREACH_ABORT (); - return true; - } + return true; return false; } diff --git a/src/itree.c b/src/itree.c index 9e60071980d..e4d5fb304b7 100644 --- a/src/itree.c +++ b/src/itree.c @@ -131,33 +131,10 @@ along with GNU Emacs. If not, see . */ * | Stack * +=======================================================================+ */ -typedef uintptr_t nodeptr_and_flag; - -static inline nodeptr_and_flag -make_nav (struct itree_node *ptr, bool flag) -{ - uintptr_t v = (uintptr_t) ptr; - /* We assume alignment imposes the LSB is clear for us to use it. */ - eassert (!(v & 1)); - return v | !!flag; -} - -static inline struct itree_node * -nav_nodeptr (nodeptr_and_flag nav) -{ - return (struct itree_node *) (nav & (~(uintptr_t)1)); -} - -static inline bool -nav_flag (nodeptr_and_flag nav) -{ - return (bool) (nav & 1); -} - /* Simple dynamic array. */ struct itree_stack { - nodeptr_and_flag *nodes; + struct itree_node **nodes; size_t size; size_t length; }; @@ -184,12 +161,6 @@ itree_stack_destroy (struct itree_stack *stack) xfree (stack); } -static void -itree_stack_clear (struct itree_stack *stack) -{ - stack->length = 0; -} - static inline void itree_stack_ensure_space (struct itree_stack *stack, uintmax_t nelements) { @@ -204,34 +175,20 @@ itree_stack_ensure_space (struct itree_stack *stack, uintmax_t nelements) /* Push NODE on the STACK, while settings its visited flag to FLAG. */ static inline void -itree_stack_push_flagged (struct itree_stack *stack, - struct itree_node *node, bool flag) +itree_stack_push (struct itree_stack *stack, struct itree_node *node) { 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 - this "ensure" check, `itree_stack_push` is also used elsewhere to - simply collect some subset of the overlays, where it's only bounded by - the total number of overlays in the buffer (which can be large and thus - preferably not pre-allocated needlessly). */ itree_stack_ensure_space (stack, stack->length + 1); - stack->nodes[stack->length] = make_nav (node, flag); + stack->nodes[stack->length] = node; stack->length++; } -static inline void -itree_stack_push (struct itree_stack *stack, struct itree_node *node) -{ - itree_stack_push_flagged (stack, node, false); -} - -static inline nodeptr_and_flag +static inline struct itree_node * itree_stack_pop (struct itree_stack *stack) { if (stack->length == 0) - return make_nav (NULL, false); + return NULL; return stack->nodes[--stack->length]; } @@ -815,10 +772,7 @@ itree_contains (struct itree_tree *tree, struct itree_node *node) struct itree_node *other; ITREE_FOREACH (other, tree, node->begin, PTRDIFF_MAX, ASCENDING) if (other == node) - { - ITREE_FOREACH_ABORT (); - return true; - } + return true; return false; } @@ -1122,7 +1076,7 @@ itree_insert_gap (struct itree_tree *tree, } } for (size_t i = 0; i < saved->length; ++i) - itree_remove (tree, nav_nodeptr (saved->nodes[i])); + itree_remove (tree, saved->nodes[i]); /* We can't use an iterator here, because we can't effectively narrow AND shift some subtree at the same time. */ @@ -1131,9 +1085,7 @@ itree_insert_gap (struct itree_tree *tree, const int size = itree_max_height (tree) + 1; struct itree_stack *stack = itree_stack_create (size); itree_stack_push (stack, tree->root); - nodeptr_and_flag nav; - while ((nav = itree_stack_pop (stack), - node = nav_nodeptr (nav))) + while ((node = itree_stack_pop (stack))) { /* Process in pre-order. */ itree_inherit_offset (tree->otick, node); @@ -1170,9 +1122,7 @@ itree_insert_gap (struct itree_tree *tree, /* Reinsert nodes starting at POS having front-advance. */ uintmax_t notick = tree->otick; - nodeptr_and_flag nav; - while ((nav = itree_stack_pop (saved), - node = nav_nodeptr (nav))) + while ((node = itree_stack_pop (saved))) { eassert (node->otick == ootick); eassert (node->begin == pos); @@ -1205,10 +1155,8 @@ itree_delete_gap (struct itree_tree *tree, struct itree_node *node; itree_stack_push (stack, tree->root); - nodeptr_and_flag nav; - while ((nav = itree_stack_pop (stack))) + while ((node = itree_stack_pop (stack))) { - node = nav_nodeptr (nav); itree_inherit_offset (tree->otick, node); if (pos > node->limit) continue; @@ -1244,16 +1192,6 @@ itree_delete_gap (struct itree_tree *tree, * | Iterator * +=======================================================================+ */ -/* Stop using the iterator. */ - -void -itree_iterator_finish (struct itree_iterator *iter) -{ - eassert (iter && iter->running); - itree_stack_destroy (iter->stack); - iter->running = false; -} - /* Return true, if NODE's interval intersects with [BEGIN, END). Note: We always include empty nodes at BEGIN (and not at END), but if BEGIN==END, then we don't include non-empty nodes starting @@ -1436,7 +1374,7 @@ itree_iterator_first_node (struct itree_tree *tree, } /* Start a iterator enumerating all intervals in [BEGIN,END) in the - given ORDER. Only one iterator per tree can be running at any time. */ + given ORDER. */ struct itree_iterator * itree_iterator_start (struct itree_iterator *iter, @@ -1444,133 +1382,28 @@ itree_iterator_start (struct itree_iterator *iter, ptrdiff_t begin, ptrdiff_t end, enum itree_order order) { eassert (iter); - /* eassert (!iter->running); */ - /* 19 here just avoids starting with a silly-small stack. - FIXME: Since this stack only needs to be about 2*max_depth - in the worst case, we could completely pre-allocate it to something - like word-bit-size * 2 and then never worry about growing it. */ - const int size = (tree ? itree_max_height (tree) : 19) + 1; - iter->stack = itree_stack_create (size); - uintmax_t otick= tree->otick; iter->begin = begin; iter->end = end; - iter->otick = otick; + iter->otick = tree->otick; iter->order = order; - itree_stack_clear (iter->stack); - if (begin <= end && tree->root != NULL) - itree_stack_push_flagged (iter->stack, tree->root, false); - iter->running = true; - /* itree_stack_ensure_space (iter->stack, - 2 * itree_max_height (tree)); */ iter->node = itree_iterator_first_node (tree, iter); return iter; } -static struct itree_node * -itree_iter_next (struct itree_iterator *iter) +struct itree_node * +itree_iterator_next (struct itree_iterator *iter) { struct itree_node *node = iter->node; while (node && !itree_node_intersects (node, iter->begin, iter->end)) { node = itree_iter_next_in_subtree (node, iter); + eassert (itree_limit_is_stable (node)); } iter->node = node ? itree_iter_next_in_subtree (node, iter) : NULL; return node; } -/* Return the next node of the iterator in the order given when it was - started; or NULL if there are no more nodes. */ - -struct itree_node * -itree_iterator_next (struct itree_iterator *g) -{ - eassert (g && g->running); - - struct itree_node *const null = NULL; - struct itree_node *node; - - /* The `visited` flag stored in each node is used here (and only here): - We keep a "workstack" of nodes we need to consider. This stack - consist of nodes of two types: nodes that we have decided - should be returned by the iterator, and nodes which we may - need to consider (including checking their children). - We start an iteration with a stack containing just the root - node marked as "not visited" which means that it (and its children) - needs to be considered but we haven't yet decided whether it's included - in the iterator's output. */ - - do - { - nodeptr_and_flag nav; - bool visited; - while ((nav = itree_stack_pop (g->stack), - node = nav_nodeptr (nav), - visited = nav_flag (nav), - node && !visited)) - { - struct itree_node *const left = node->left; - struct itree_node *const right = node->right; - - itree_inherit_offset (g->otick, node); - eassert (itree_limit_is_stable (node)); - switch (g->order) - { - case ITREE_ASCENDING: - if (right != null && node->begin <= g->end) - itree_stack_push_flagged (g->stack, right, false); - if (itree_node_intersects (node, g->begin, g->end)) - itree_stack_push_flagged (g->stack, node, true); - /* Node's children may still be off-set and we need to add it. */ - if (left != null && g->begin <= left->limit + left->offset) - itree_stack_push_flagged (g->stack, left, false); - break; - case ITREE_DESCENDING: - if (left != null && g->begin <= left->limit + left->offset) - itree_stack_push_flagged (g->stack, left, false); - if (itree_node_intersects (node, g->begin, g->end)) - itree_stack_push_flagged (g->stack, node, true); - if (right != null && node->begin <= g->end) - itree_stack_push_flagged (g->stack, right, false); - break; - case ITREE_PRE_ORDER: - if (right != null && node->begin <= g->end) - itree_stack_push_flagged (g->stack, right, false); - if (left != null && g->begin <= left->limit + left->offset) - itree_stack_push_flagged (g->stack, left, false); - if (itree_node_intersects (node, g->begin, g->end)) - itree_stack_push_flagged (g->stack, node, true); - break; - case ITREE_POST_ORDER: - if (itree_node_intersects (node, g->begin, g->end)) - itree_stack_push_flagged (g->stack, node, true); - if (right != null && node->begin <= g->end) - itree_stack_push_flagged (g->stack, right, false); - if (left != null && g->begin <= left->limit + left->offset) - itree_stack_push_flagged (g->stack, left, false); - break; - } - } - /* Node may have been invalidated by itree_iterator_narrow - after it was pushed: Check if it still intersects. */ - } while (node && ! itree_node_intersects (node, g->begin, g->end)); - - struct itree_node *old_node = g->node; - struct itree_node *other_node = itree_iter_next (g); - if (other_node != node) - { - fprintf (stderr, "WOW!! %ld..%ld vs %ld..%ld\n", - other_node ? other_node->begin : -1, - other_node ? other_node->end : -1, - node ? node->begin : -1, - node ? node->end : -1); - fprintf (stderr, "ON=%lx N=%lx OlN=%lx\n", other_node, node, - old_node); - emacs_abort (); - } - return node; -} - /* 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. */ @@ -1578,7 +1411,7 @@ void itree_iterator_narrow (struct itree_iterator *g, ptrdiff_t begin, ptrdiff_t end) { - eassert (g && g->running); + eassert (g); eassert (begin >= g->begin); eassert (end <= g->end); g->begin = max (begin, g->begin); diff --git a/src/itree.h b/src/itree.h index 37cd423d34a..291fa53fd30 100644 --- a/src/itree.h +++ b/src/itree.h @@ -132,24 +132,21 @@ extern struct itree_iterator *itree_iterator_start (struct itree_iterator *, enum itree_order); extern void itree_iterator_narrow (struct itree_iterator *, ptrdiff_t, ptrdiff_t); -extern void itree_iterator_finish (struct itree_iterator *); extern struct itree_node *itree_iterator_next (struct itree_iterator *); /* State used when iterating interval. */ struct itree_iterator { - struct itree_node *node; /* FIXME: It should be either `node` or `stack`. */ - struct itree_stack *stack; + struct itree_node *node; ptrdiff_t begin; ptrdiff_t end; uintmax_t otick; /* A copy of the tree's `otick`. */ enum itree_order order; - bool running; }; /* Iterate over the intervals between BEG and END in the tree T. N will hold successive nodes. ORDER can be one of : `ASCENDING`, - `DESCENDING`, or `PRE_ORDER`. + `DESCENDING`, `POST_ORDER`, or `PRE_ORDER`. It should be used as: ITREE_FOREACH (n, t, beg, end, order) @@ -160,9 +157,6 @@ struct itree_iterator BEWARE: - The expression T may be evaluated more than once, so make sure it is cheap and pure. - - If you need to exit the loop early, you *have* to call `ITREE_ABORT` - just before exiting (e.g. with `break` or `return`). - - Non-local exits are not supported within the body of the loop. - Don't modify the tree during the iteration. */ #define ITREE_FOREACH(n, t, beg, end, order) \ @@ -179,11 +173,7 @@ struct itree_iterator *itree_iter_ \ = itree_iterator_start (&itree_local_iter_, \ t, beg, end, ITREE_##order); \ - ((n = itree_iterator_next (itree_iter_)) \ - || (itree_iterator_finish (itree_iter_), false));) - -#define ITREE_FOREACH_ABORT() \ - itree_iterator_finish (itree_iter_) + ((n = itree_iterator_next (itree_iter_)));) #define ITREE_FOREACH_NARROW(beg, end) \ itree_iterator_narrow (itree_iter_, beg, end) diff --git a/src/xdisp.c b/src/xdisp.c index f6a279636a0..414ee9bfe28 100644 --- a/src/xdisp.c +++ b/src/xdisp.c @@ -7036,17 +7036,11 @@ strings_with_newlines (ptrdiff_t startpos, ptrdiff_t endpos, struct window *w) str = Foverlay_get (overlay, Qbefore_string); if (STRINGP (str) && SCHARS (str) && memchr (SDATA (str), '\n', SBYTES (str))) - { - ITREE_FOREACH_ABORT (); - return true; - } + return true; str = Foverlay_get (overlay, Qafter_string); if (STRINGP (str) && SCHARS (str) && memchr (SDATA (str), '\n', SBYTES (str))) - { - ITREE_FOREACH_ABORT (); - return true; - } + return true; } /* Check for 'display' properties whose values include strings. */ -- 2.39.5