diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/buffer.c | 97 | ||||
| -rw-r--r-- | src/buffer.h | 33 | ||||
| -rw-r--r-- | src/itree.c | 57 | ||||
| -rw-r--r-- | src/itree.h | 52 | ||||
| -rw-r--r-- | src/textprop.c | 5 | ||||
| -rw-r--r-- | src/xdisp.c | 17 |
6 files changed, 113 insertions, 148 deletions
diff --git a/src/buffer.c b/src/buffer.c index 19937216ed5..8d02d705b55 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -647,8 +647,7 @@ copy_overlays (struct buffer *from, struct buffer *to) eassert (to && ! to->overlays); struct interval_node *node; - buffer_overlay_iter_start (from, PTRDIFF_MIN, PTRDIFF_MAX, ITREE_ASCENDING); - while ((node = buffer_overlay_iter_next (from))) + ITREE_FOREACH (node, from->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING) { Lisp_Object ov = node->data; Lisp_Object copy = build_overlay (node->begin, node->end, @@ -657,7 +656,6 @@ copy_overlays (struct buffer *from, struct buffer *to) Fcopy_sequence (OVERLAY_PLIST (ov))); add_buffer_overlay (to, XOVERLAY (copy)); } - buffer_overlay_iter_finish (from); } bool @@ -929,14 +927,12 @@ delete_all_overlays (struct buffer *b) 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))) + ITREE_FOREACH (node, b->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING) { modify_overlay (b, node->begin, node->end); /* Where are the nodes freed ? --ap */ XOVERLAY (node->data)->buffer = NULL; } - buffer_overlay_iter_finish (b); interval_tree_clear (b->overlays); } @@ -944,7 +940,6 @@ static void free_buffer_overlays (struct buffer *b) { /* Actually this does not free any overlay, but the tree only. --ap */ - eassert (! b->overlays || 0 == interval_tree_size (b->overlays)); if (b->overlays) { interval_tree_destroy (b->overlays); @@ -969,9 +964,16 @@ set_overlays_multibyte (bool multibyte) struct interval_tree *tree = current_buffer->overlays; const intmax_t size = interval_tree_size (tree); + /* We can't use `interval_node_set_region` at the same time + as we iterate over the itree, so we need an auxiliary storage + to keep the list of nodes. */ USE_SAFE_ALLOCA; SAFE_NALLOCA (nodes, 1, size); - interval_tree_nodes (tree, nodes, ITREE_ASCENDING); + { + struct interval_node *node, **cursor = nodes; + ITREE_FOREACH (node, tree, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING) + *(cursor++) = node; + } for (int i = 0; i < size; ++i, ++nodes) { @@ -2418,15 +2420,11 @@ swap_buffer_overlays (struct buffer *buffer, struct buffer *other) { struct interval_node *node; - buffer_overlay_iter_start (buffer, PTRDIFF_MIN, PTRDIFF_MAX, ITREE_ASCENDING); - while ((node = buffer_overlay_iter_next (buffer))) + ITREE_FOREACH (node, buffer->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING) XOVERLAY (node->data)->buffer = other; - buffer_overlay_iter_finish (buffer); - buffer_overlay_iter_start (other, PTRDIFF_MIN, PTRDIFF_MAX, ITREE_ASCENDING); - while ((node = buffer_overlay_iter_next (other))) + ITREE_FOREACH (node, other->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING) XOVERLAY (node->data)->buffer = buffer; - buffer_overlay_iter_finish (other); /* Swap the interval trees. */ void *tmp = buffer->overlays; @@ -2951,23 +2949,24 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend, Lisp_Object *vec = *vec_ptr; struct interval_node *node; - buffer_overlay_iter_start (current_buffer, beg, - /* Find empty OV at Z ? */ - (end >= ZV && empty) ? ZV + 1 : ZV, - ITREE_ASCENDING); - - while ((node = buffer_overlay_iter_next (current_buffer))) + ITREE_FOREACH (node, current_buffer->overlays, beg, + /* Find empty OV at Z ? */ + (end >= ZV && empty) ? ZV + 1 : ZV, ASCENDING) { 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) - break; + { + ITREE_FOREACH_ABORT (); + break; + } } if (! empty && node->begin == node->end) @@ -2985,7 +2984,6 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend, /* Keep counting overlays even if we can't return them all. */ idx++; } - buffer_overlay_iter_finish (current_buffer); if (next_ptr) *next_ptr = next ? next : ZV; @@ -3012,8 +3010,7 @@ next_overlay_change (ptrdiff_t pos) ptrdiff_t next = ZV; struct interval_node *node; - buffer_overlay_iter_start (current_buffer, pos, next, ITREE_ASCENDING); - while ((node = buffer_overlay_iter_next (current_buffer))) + ITREE_FOREACH (node, current_buffer->overlays, pos, next, ASCENDING) { if (node->begin > pos) { @@ -3021,15 +3018,15 @@ 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) { next = node->end; - buffer_overlay_iter_narrow (current_buffer, pos, next); + ITREE_FOREACH_NARROW (pos, next); } } - buffer_overlay_iter_finish (current_buffer); return next; } @@ -3040,16 +3037,14 @@ previous_overlay_change (ptrdiff_t pos) struct interval_node *node; ptrdiff_t prev = BEGV; - buffer_overlay_iter_start (current_buffer, prev, pos, ITREE_DESCENDING); - while ((node = buffer_overlay_iter_next (current_buffer))) + ITREE_FOREACH (node, current_buffer->overlays, prev, pos, DESCENDING) { if (node->end < pos) prev = node->end; else prev = max (prev, node->begin); - buffer_overlay_iter_narrow (current_buffer, prev, pos); + ITREE_FOREACH_NARROW (prev, pos); } - buffer_overlay_iter_finish (current_buffer); return prev; } @@ -3123,19 +3118,16 @@ bool overlay_touches_p (ptrdiff_t pos) { struct interval_node *node; - bool result = false; /* We need to find overlays ending in pos, as well as empty ones at pos. */ - buffer_overlay_iter_start (current_buffer, - pos - 1, pos + 1, ITREE_DESCENDING); - - while (! result && (node = buffer_overlay_iter_next (current_buffer))) - result = (node->begin == pos || node->end == pos); - - buffer_overlay_iter_finish (current_buffer); - - return result; + ITREE_FOREACH (node, current_buffer->overlays, pos - 1, pos + 1, DESCENDING) + if (node->begin == pos || node->end == pos) + { + ITREE_FOREACH_ABORT (); + return true; + } + return false; } @@ -3342,9 +3334,7 @@ overlay_strings (ptrdiff_t pos, struct window *w, unsigned char **pstr) overlay_heads.used = overlay_heads.bytes = 0; overlay_tails.used = overlay_tails.bytes = 0; - buffer_overlay_iter_start (current_buffer, - pos - 1, pos + 1, ITREE_DESCENDING); - while ((node = buffer_overlay_iter_next (current_buffer))) + ITREE_FOREACH (node, current_buffer->overlays, pos - 1, pos + 1, DESCENDING) { Lisp_Object overlay = node->data; eassert (OVERLAYP (overlay)); @@ -3358,6 +3348,8 @@ overlay_strings (ptrdiff_t pos, struct window *w, unsigned char **pstr) if (WINDOWP (window) && XWINDOW (window) != w) continue; Lisp_Object str; + /* FIXME: Are we really sure that `record_overlay_string` can + never cause a non-local exit? */ if (startpos == pos && (str = Foverlay_get (overlay, Qbefore_string), STRINGP (str))) record_overlay_string (&overlay_heads, str, @@ -3372,7 +3364,6 @@ overlay_strings (ptrdiff_t pos, struct window *w, unsigned char **pstr) Foverlay_get (overlay, Qpriority), endpos - startpos); } - buffer_overlay_iter_finish (current_buffer); if (overlay_tails.used > 1) qsort (overlay_tails.buf, overlay_tails.used, sizeof (struct sortstr), @@ -3842,10 +3833,8 @@ However, the overlays you get are the real objects that the buffer uses. */) Lisp_Object overlays = Qnil; struct interval_node *node; - buffer_overlay_iter_start (current_buffer, BEG, Z, ITREE_DESCENDING); - while ((node = buffer_overlay_iter_next (current_buffer))) + ITREE_FOREACH (node, current_buffer->overlays, BEG, Z, DESCENDING) overlays = Fcons (node->data, overlays); - buffer_overlay_iter_finish (current_buffer); return Fcons (overlays, Qnil); } @@ -3983,11 +3972,10 @@ report_overlay_modification (Lisp_Object start, Lisp_Object end, bool after, if (! current_buffer->overlays) return; - buffer_overlay_iter_start (current_buffer, - begin_arg - (insertion ? 1 : 0), - end_arg + (insertion ? 1 : 0), - ITREE_ASCENDING); - while ((node = buffer_overlay_iter_next (current_buffer))) + ITREE_FOREACH (node, current_buffer->overlays, + begin_arg - (insertion ? 1 : 0), + end_arg + (insertion ? 1 : 0), + ASCENDING) { Lisp_Object overlay = node->data; ptrdiff_t obegin = OVERLAY_START (overlay); @@ -4016,7 +4004,6 @@ report_overlay_modification (Lisp_Object start, Lisp_Object end, bool after, add_overlay_mod_hooklist (prop, overlay); } } - buffer_overlay_iter_finish (current_buffer); } { /* Call the functions recorded in last_overlay_modification_hooks. @@ -4070,14 +4057,12 @@ evaporate_overlays (ptrdiff_t pos) Lisp_Object hit_list = Qnil; struct interval_node *node; - buffer_overlay_iter_start (current_buffer, pos, pos, ITREE_ASCENDING); - while ((node = buffer_overlay_iter_next (current_buffer))) + ITREE_FOREACH (node, current_buffer->overlays, pos, pos, ASCENDING) { if (node->end == pos && ! NILP (Foverlay_get (node->data, Qevaporate))) hit_list = Fcons (node->data, hit_list); } - buffer_overlay_iter_finish (current_buffer); for (; CONSP (hit_list); hit_list = XCDR (hit_list)) Fdelete_overlay (XCAR (hit_list)); diff --git a/src/buffer.h b/src/buffer.h index ad3b2ad6df5..a4e3934cad2 100644 --- a/src/buffer.h +++ b/src/buffer.h @@ -1442,39 +1442,6 @@ remove_buffer_overlay (struct buffer *b, struct Lisp_Overlay *ov) ov->buffer = NULL; } -INLINE void -buffer_overlay_iter_start1 (struct buffer *b, ptrdiff_t begin, ptrdiff_t end, - enum interval_tree_order order, const char* file, int line) -{ - if (b->overlays) - interval_tree_iter_start (b->overlays, begin, end, order, file, line); -} - -#define buffer_overlay_iter_start(b, begin, end, order) \ - buffer_overlay_iter_start1 ((b), (begin), (end), (order), __FILE__, __LINE__) - -INLINE struct interval_node* -buffer_overlay_iter_next (struct buffer *b) -{ - if (! b->overlays) - return NULL; - 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->iter); -} - -INLINE void -buffer_overlay_iter_narrow (struct buffer *b, ptrdiff_t begin, ptrdiff_t end) -{ - if (b->overlays) - interval_generator_narrow (b->overlays->iter, begin, end); -} - /* Return the start of OV in its buffer, or -1 if OV is not associated with any buffer. */ diff --git a/src/itree.c b/src/itree.c index 4f8aea924ac..eeecaf1839a 100644 --- a/src/itree.c +++ b/src/itree.c @@ -325,7 +325,7 @@ interval_tree_create (void) return tree; } -/* Reset the tree TREE to its empty state. */ +/* Reset the tree TREE to its empty state. */ void interval_tree_clear (struct interval_tree *tree) @@ -345,7 +345,7 @@ interval_tree_clear (struct interval_tree *tree) } #ifdef ITREE_TESTING -/* Initialize a pre-allocated tree (presumably on the stack). */ +/* Initialize a pre-allocated tree (presumably on the stack). */ static void interval_tree_init (struct interval_tree *tree) @@ -355,12 +355,11 @@ interval_tree_init (struct interval_tree *tree) } #endif -/* Release a tree, freeing its allocated memory. */ +/* Release a tree, freeing its allocated memory. */ void interval_tree_destroy (struct interval_tree *tree) { - if (! tree) - return; + eassert (tree->root == ITREE_NULL); if (tree->iter) interval_generator_destroy (tree->iter); xfree (tree); @@ -389,14 +388,14 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node) ptrdiff_t offset = 0; /* Find the insertion point, accumulate node's offset and update - ancestors limit values. */ + ancestors limit values. */ while (child != ITREE_NULL) { parent = child; offset += child->offset; child->limit = max (child->limit, node->end - offset); /* This suggests that nodes in the right subtree are strictly - greater. But this is not true due to later rotations. */ + greater. But this is not true due to later rotations. */ child = node->begin <= child->begin ? child->left : child->right; } @@ -430,15 +429,16 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node) bool interval_tree_contains (struct interval_tree *tree, struct interval_node *node) { + eassert (node); struct interval_node *other; - - interval_tree_iter_start (tree, node->begin, PTRDIFF_MAX, ITREE_ASCENDING, __FILE__, __LINE__); - while ((other = interval_generator_next (tree->iter))) + ITREE_FOREACH (other, tree, node->begin, PTRDIFF_MAX, ASCENDING) if (other == node) - break; + { + ITREE_FOREACH_ABORT (); + return true; + } - interval_tree_iter_finish (tree->iter); - return other == node; + return false; } /* Remove NODE from TREE and return it. NODE must exist in TREE. */ @@ -508,34 +508,12 @@ interval_tree_validate (struct interval_tree *tree, struct interval_node *node) return node; } -/* Fill memory pointed at via NODES with all nodes of TREE in the - given ORDER. - - The size of NODES must be sufficiently large. - */ - -void -interval_tree_nodes (struct interval_tree *tree, - struct interval_node **nodes, - enum interval_tree_order order) -{ - struct interval_node *node; - - interval_tree_iter_start (tree, PTRDIFF_MIN, PTRDIFF_MAX, order, __FILE__, __LINE__); - while ((node = interval_generator_next (tree->iter))) - { - *nodes = node; - ++nodes; - } - interval_tree_iter_finish (tree->iter); -} - /* Start a generator iterating all intervals in [BEGIN,END) in the given ORDER. Only one iterator per tree can be running at any time. */ -void +struct interval_generator * interval_tree_iter_start (struct interval_tree *tree, ptrdiff_t begin, ptrdiff_t end, enum interval_tree_order order, @@ -553,6 +531,7 @@ interval_tree_iter_start (struct interval_tree *tree, iter->running = true; iter->file = file; iter->line = line; + return iter; } /* Stop using the iterator. */ @@ -600,15 +579,12 @@ 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_generator_next (tree->iter))) + ITREE_FOREACH (node, tree, pos, pos + 1, PRE_ORDER) { if (node->begin == pos && node->front_advance && (node->begin != node->end || node->rear_advance)) interval_stack_push (saved, node); } - interval_tree_iter_finish (tree->iter); for (int i = 0; i < saved->length; ++i) interval_tree_remove (tree, nav_nodeptr (saved->nodes[i])); @@ -784,7 +760,6 @@ 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; struct interval_node *node; diff --git a/src/itree.h b/src/itree.h index b9294c5662c..1f019a2607e 100644 --- a/src/itree.h +++ b/src/itree.h @@ -59,6 +59,10 @@ struct interval_tree struct interval_node *root; uintmax_t otick; /* offset tick, compared with node's otick. */ intmax_t size; /* Number of nodes in the tree. */ + /* FIXME: We can only have one iteration active per tree, which is very + restrictive. Actually, in practice this is no better than limiting + to a single active iteration *globally*, so we could move this `iter` + to a global variable! */ struct interval_generator *iter; }; @@ -79,12 +83,56 @@ 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 *); -void interval_tree_iter_start (struct interval_tree *, ptrdiff_t, ptrdiff_t, enum interval_tree_order, +struct interval_generator *interval_tree_iter_start (struct interval_tree *, ptrdiff_t, ptrdiff_t, enum interval_tree_order, const char* file, int line); 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); + +/* 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`. + It should be used as: + + ITREE_FOREACH (n, t, beg, end, order) + { + .. do the thing with n .. + } + + BEWARE: + - The expression T may be evaluated more than once, so make sure + it is cheap a pure. + - Only a single iteration can happen at a time, so make sure none of the + code within the loop can start another tree_itertion. + - 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, + unless the caller makes sure `ITREE_ABORT` is called via some + kind of unwind_protect. + - Don't modify the tree during the iteration. + */ +#define ITREE_FOREACH(n, t, beg, end, order) \ + /* FIXME: We'd want to declare `x` right here, but I can't figure out + how to make that work here: the `for` syntax only allows a single + clause for the var declarations where we need 2 different types. + We could use the `struct {foo x; bar y; } p;` trick to declare two + vars `p.x` and `p.y` of unrelated types, but then none of the names + of the vars matches the `n` we receive :-(. */ \ + if (!t) \ + { } \ + else \ + for (struct interval_generator *itree_iter_ \ + = interval_tree_iter_start (t, beg, end, ITREE_##order, \ + __FILE__, __LINE__); \ + ((n = interval_generator_next (itree_iter_)) \ + || (interval_tree_iter_finish (itree_iter_), false));) + +#define ITREE_FOREACH_ABORT() \ + interval_tree_iter_finish (itree_iter_) + +#define ITREE_FOREACH_NARROW(beg, end) \ + interval_generator_narrow (itree_iter_, beg, end) + #endif diff --git a/src/textprop.c b/src/textprop.c index c2c3622d05f..04fae528097 100644 --- a/src/textprop.c +++ b/src/textprop.c @@ -643,10 +643,8 @@ get_char_property_and_overlay (Lisp_Object position, register Lisp_Object prop, && pos <= BUF_ZV (b))) xsignal1 (Qargs_out_of_range, position); - buffer_overlay_iter_start (b, pos, pos + 1, ITREE_ASCENDING); - /* Now check the overlays in order of decreasing priority. */ - while ((node = buffer_overlay_iter_next (b))) + ITREE_FOREACH (node, b->overlays, pos, pos + 1, ASCENDING) { Lisp_Object tem = Foverlay_get (node->data, prop); struct sortvec *this; @@ -662,7 +660,6 @@ get_char_property_and_overlay (Lisp_Object position, register Lisp_Object prop, result_tem = tem; } } - buffer_overlay_iter_finish (b); if (result) { if (overlay) diff --git a/src/xdisp.c b/src/xdisp.c index 6ecd3bdf24f..d585d57fd05 100644 --- a/src/xdisp.c +++ b/src/xdisp.c @@ -6568,10 +6568,8 @@ load_overlay_strings (struct it *it, ptrdiff_t charpos) while (false) - buffer_overlay_iter_start (current_buffer, - charpos - 1, charpos + 1, ITREE_DESCENDING); /* Process overlays. */ - while ((node = buffer_overlay_iter_next (current_buffer))) + ITREE_FOREACH (node, current_buffer->overlays, charpos - 1, charpos + 1, DESCENDING) { Lisp_Object overlay = node->data; eassert (OVERLAYP (overlay)); @@ -6607,7 +6605,6 @@ load_overlay_strings (struct it *it, ptrdiff_t charpos) && SCHARS (str)) RECORD_OVERLAY_STRING (overlay, str, true); } - buffer_overlay_iter_finish (current_buffer); #undef RECORD_OVERLAY_STRING @@ -7005,10 +7002,8 @@ static bool strings_with_newlines (ptrdiff_t startpos, ptrdiff_t endpos, struct window *w) { struct interval_node *node; - /* Process overlays before the overlay center. */ - buffer_overlay_iter_start (current_buffer, - startpos, endpos, ITREE_DESCENDING); - while ((node = buffer_overlay_iter_next (current_buffer))) + /* Process overlays. */ + ITREE_FOREACH (node, current_buffer->overlays, startpos, endpos, DESCENDING) { Lisp_Object overlay = node->data; eassert (OVERLAYP (overlay)); @@ -7032,20 +7027,18 @@ strings_with_newlines (ptrdiff_t startpos, ptrdiff_t endpos, struct window *w) if (STRINGP (str) && SCHARS (str) && memchr (SDATA (str), '\n', SBYTES (str))) { - buffer_overlay_iter_finish (current_buffer); + ITREE_FOREACH_ABORT (); return true; } str = Foverlay_get (overlay, Qafter_string); if (STRINGP (str) && SCHARS (str) && memchr (SDATA (str), '\n', SBYTES (str))) { - buffer_overlay_iter_finish (current_buffer); + ITREE_FOREACH_ABORT (); return true; } } - buffer_overlay_iter_finish (current_buffer); - /* Check for 'display' properties whose values include strings. */ Lisp_Object cpos = make_fixnum (startpos); Lisp_Object limpos = make_fixnum (endpos); |