Provide a new tree data-structure for overlays.

* src/itree.c
(interval_generator_narrow, interval_generator_next)
(interval_node_init, interval_node_begin)
(interval_node_end, interval_node_set_region)
(interval_tree_create, interval_tree_clear)
(interval_tree_init, interval_tree_destroy)
(interval_tree_size, interval_tree_insert)
(interval_tree_contains, interval_tree_remove)
(interval_tree_validate, interval_tree_iter_start)
(interval_tree_iter_finish, interval_tree_iter_next)
(interval_tree_iter_ensure_space, interval_tree_max_height)
(interval_tree_insert_gap, interval_tree_delete_gap)
(interval_generator_create, interval_generator_reset)
(interval_generator_ensure_space, interval_node_intersects)
(interval_generator_next, interval_generator_narrow)
(interval_generator_destroy, interval_stack_create)
(interval_stack_destroy, interval_stack_clear)
(interval_stack_ensure_space, interval_stack_push)
(interval_stack_push_flagged, interval_stack_pop)
(interval_tree_update_limit, interval_tree_inherit_offset)
(interval_tree_propagate_limit, interval_tree_rotate_left)
(interval_tree_rotate_right, interval_tree_insert_fix)
(interval_tree_remove_fix, interval_tree_transplant)
(interval_tree_subtree_min): New file and new functions.

* src/itree.h: New file.

* configure.ac: Create Makefile for manual overlay tests.

* src/Makefile.in: Add itree.o target.

* src/alloc.c (build_overlay, mark_overlay, mark_buffer)
(sweep_misc, sweep_buffers): Adapt to new tree data-structure.

* src/buffer.c (overlays_in, overlays_at): Remove unused arguments
prev_ptr and change_req, adapt to new data-structure and reuse
code.
(copy_overlays, drop_overlays, delete_all_overlays)
(reset_buffer, kill-buffer, buffer-swap-text, next_overlay_change)
(previous_overlay_change, mouse_face_overlay_overlaps)
(disable_line_numbers_overlay_at_eob, overlay_touches_p)
(overlay_strings, adjust_overlays_for_insert)
(adjust_overlays_for_delete, overlayp, make-overlay, move-overlay)
(delete-overlay, overlay-start, overlay-end, overlay-buffer)
(overlay-properties, overlays-at, overlays-in)
(next-overlay-change, previous-overlay-change, overlay-put)
(overlay-get, report_overlay_modification, evaporate_overlays)
(init_buffer_once): Adapt to changes and tree data-structure.
(overlay-lists, overlay-recenter): Funtions are now obsolete, but
kept anyway.
(set_buffer_overlays_before, set_buffer_overlays_after)
(recenter_overlay_lists,fix_start_end_in_overlays,fix_overlays_before)
(unchain_overlay,): Removed functions of the old list
data-structure.
(swap_buffer_overlays, make_sortvec_item): New functions.
(sort_overlays): Adapt to changes and tree data-structure.
(sortvec): Moved to buffer.h .
(make_lispy_interval_node, overlay_tree, overlay-tree)
[ITREE_DEBUG]: New debugging functions.

* src/buffer.h (overlays_before, overlays_after): Removed struct
member of the list data-structure.
(overlays): Added tree struct member.
(sortvec): Moved here from buffer.c .
(GET_OVERLAYS_AT): Adapt to changes.
(set_buffer_intervals, OVERLAY_START, OVERLAY_END, OVERLAY_PLIST):
Adapt to tree data-structure.
(OVERLAY_POSITION): Removed macro of the list data-structure.
(OVERLAY_REAR_ADVANCE_P, OVERLAY_FRONT_ADVANCE_P): New macros.
(overlay_start, overlay_end)
(set_overlay_region, maybe_alloc_buffer_overlays)
(free_buffer_overlays, add_buffer_overlay)
(remove_buffer_overlay, buffer_overlay_iter_start)
(buffer_overlay_iter_next, buffer_overlay_iter_finish)
(buffer_overlay_iter_narrow): New functions.
(compare_overlays, make_sortvec_item): Export functions.

* src/editfns.c (overlays_around): Reuse overlays_in.
(get-pos-property): Adapt to tree data-structure.
(transpose-regions): Remove call to deleted function.

* src/fileio.c: (insert-file-contents): Remove
references to deleted struct member.

* src/fns.c (internal_equal): Adapt to tree data-structure.

* src/indent.c (check_display_width): Adapt to tree
data-structure.
(skip_invisible): Remove call to deleted function.

* src/insdel.c (adjust_markers_for_insert): Remove calls to
deleted functions.

* src/intervals.c (adjust_for_invis_intang): Adapt to tree
data-structure.

* src/keyboard.c (adjust_point_for_property): Adapt to tree
data-structure.

* src/lisp.h (Lisp_Overlay): Modified struct layout.

* src/print.c (temp_output_buffer_setup, print_object): Adapt to
tree data-structure.

* src/textprop.c (get_char_property_and_overlay): Adapt to tree
data-structure.  Take advantage of the new data-structure.

* src/window.h (overlay_matches_window): New function.

* src/xdisp.h (next_overlay_change): Removed function.  Use
next-overlay-change, which does not use xmalloc anymore.
(handle_single_display_spec, load_overlay_strings)
(back_to_previous_visible_line_start, note_mouse_highlight): Adapt
to tree data-structure.
(move_it_to, display_line): Remove calls to deleted functions.

* src/xfaces.c (face_at_buffer_position): Adapt to changes and
tree data-structure.

* test/src/buffer-tests.el: Many tests regarding overlays added.

* test/manual/noverlay/itree-tests.c: New file with tests of the
tree data-structure on the C level.
* test/manual/noverlay/Makefile.in: New file.
* test/manual/noverlay/check-sanitize.sh: New file.
* test/manual/noverlay/emacs-compat.h: New file.
* test/manual/noverlay/.gitignore: New file.

* test/manual/noverlay/overlay-perf.el: New file providing
performance tests.
* test/manual/noverlay/many-errors.h: New file.

1 files changed, 134 insertions, 27 deletions

diff --git a/src/buffer.h b/src/buffer.h
index ac7c5a54679..ef31ad1ed9d 100644
--- a/src/buffer.h
+++ b/src/buffer.h
@@ -26,6 +26,7 @@ along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.  */
 
 #include "character.h"
 #include "lisp.h"
+#include "itree.h"
 
 INLINE_HEADER_BEGIN
 
@@ -877,16 +878,8 @@ struct buffer
   /* Non-zero whenever the narrowing is changed in this buffer.  */
   bool_bf clip_changed : 1;
 
-  /* List of overlays that end at or before the current center,
-     in order of end-position.  */
-  struct Lisp_Overlay *overlays_before;
-
-  /* List of overlays that end after  the current center,
-     in order of start-position.  */
-  struct Lisp_Overlay *overlays_after;
-
-  /* Position where the overlay lists are centered.  */
-  ptrdiff_t overlay_center;
+  /* The inveral tree containing this buffer's overlays. */
+  struct interval_tree *overlays;
 
   /* Changes in the buffer are recorded here for undo, and t means
      don't record anything.  This information belongs to the base
@@ -896,6 +889,14 @@ struct buffer
   Lisp_Object undo_list_;
 };
 
+struct sortvec
+{
+  Lisp_Object overlay;
+  ptrdiff_t beg, end;
+  EMACS_INT priority;
+  EMACS_INT spriority;		/* Secondary priority.  */
+};
+
 INLINE bool
 BUFFERP (Lisp_Object a)
 {
@@ -1109,8 +1110,11 @@ extern void delete_all_overlays (struct buffer *);
 extern void reset_buffer (struct buffer *);
 extern void compact_buffer (struct buffer *);
 extern void evaporate_overlays (ptrdiff_t);
-extern ptrdiff_t overlays_at (EMACS_INT, bool, Lisp_Object **,
-			      ptrdiff_t *, ptrdiff_t *, ptrdiff_t *, bool);
+extern ptrdiff_t overlays_at (ptrdiff_t, bool, Lisp_Object **, ptrdiff_t *, ptrdiff_t *);
+extern ptrdiff_t overlays_in (ptrdiff_t, ptrdiff_t, bool, Lisp_Object **,
+                              ptrdiff_t *,  bool, ptrdiff_t *);
+extern ptrdiff_t previous_overlay_change (ptrdiff_t);
+extern ptrdiff_t next_overlay_change (ptrdiff_t);
 extern ptrdiff_t sort_overlays (Lisp_Object *, ptrdiff_t, struct window *);
 extern void recenter_overlay_lists (struct buffer *, ptrdiff_t);
 extern ptrdiff_t overlay_strings (ptrdiff_t, struct window *, unsigned char **);
@@ -1162,18 +1166,16 @@ record_unwind_current_buffer (void)
    If NEXTP is non-NULL, return next overlay there.
    See overlay_at arg CHANGE_REQ for meaning of CHRQ arg.  */
 
-#define GET_OVERLAYS_AT(posn, overlays, noverlays, nextp, chrq)		\
+#define GET_OVERLAYS_AT(posn, overlays, noverlays, next)                \
   do {									\
     ptrdiff_t maxlen = 40;						\
     SAFE_NALLOCA (overlays, 1, maxlen);					\
-    (noverlays) = overlays_at (posn, false, &(overlays), &maxlen,	\
-			       nextp, NULL, chrq);			\
+    (noverlays) = overlays_at (posn, false, &(overlays), &maxlen, next); \
     if ((noverlays) > maxlen)						\
       {									\
 	maxlen = noverlays;						\
 	SAFE_NALLOCA (overlays, 1, maxlen);				\
-	(noverlays) = overlays_at (posn, false, &(overlays), &maxlen,	\
-				   nextp, NULL, chrq);			\
+	(noverlays) = overlays_at (posn, false, &(overlays), &maxlen, next); \
       }									\
   } while (false)
 
@@ -1208,7 +1210,8 @@ set_buffer_intervals (struct buffer *b, INTERVAL i)
 INLINE bool
 buffer_has_overlays (void)
 {
-  return current_buffer->overlays_before || current_buffer->overlays_after;
+  return current_buffer->overlays
+    && (interval_tree_size (current_buffer->overlays) > 0);
 }
 
 /* Return character code of multi-byte form at byte position POS.  If POS
@@ -1248,23 +1251,124 @@ buffer_window_count (struct buffer *b)
 
 /* Overlays */
 
-/* Return the marker that stands for where OV starts in the buffer.  */
+INLINE ptrdiff_t
+overlay_start (struct Lisp_Overlay *ov)
+{
+  if (! ov->buffer)
+    return -1;
+  return interval_node_begin (ov->buffer->overlays, ov->interval);
+}
+
+INLINE ptrdiff_t
+overlay_end (struct Lisp_Overlay *ov)
+{
+  if (! ov->buffer)
+    return -1;
+  return interval_node_end (ov->buffer->overlays, ov->interval);
+}
+
+INLINE void
+set_overlay_region (struct Lisp_Overlay *ov, ptrdiff_t begin, ptrdiff_t end)
+{
+  eassert (ov->buffer);
+  begin = clip_to_bounds (BEG, begin, ov->buffer->text->z);
+  end = clip_to_bounds (begin, end, ov->buffer->text->z);
+  interval_node_set_region (ov->buffer->overlays, ov->interval, begin, end);
+}
+
+INLINE void
+maybe_alloc_buffer_overlays (struct buffer *b)
+{
+  if (! b->overlays)
+    b->overlays = interval_tree_create ();
+}
+
+/* FIXME: Actually this does not free any overlay, but the tree
+   only. --ap */
+
+INLINE void
+free_buffer_overlays (struct buffer *b)
+{
+  eassert (! b->overlays || 0 == interval_tree_size (b->overlays));
+  if (b->overlays)
+    {
+      interval_tree_destroy (b->overlays);
+      b->overlays = NULL;
+    }
+}
+
+INLINE void
+add_buffer_overlay (struct buffer *b, struct Lisp_Overlay *ov)
+{
+  eassert (! ov->buffer);
+  maybe_alloc_buffer_overlays (b);
+  ov->buffer = b;
+  interval_tree_insert (b->overlays, ov->interval);
+}
+
+INLINE void
+remove_buffer_overlay (struct buffer *b, struct Lisp_Overlay *ov)
+{
+  eassert (b->overlays);
+  eassert (ov->buffer == b);
+  interval_tree_remove (ov->buffer->overlays, ov->interval);
+  ov->buffer = NULL;
+}
+
+INLINE void
+buffer_overlay_iter_start (struct buffer *b, ptrdiff_t begin, ptrdiff_t end,
+                           enum interval_tree_order order)
+{
+  if (b->overlays)
+    interval_tree_iter_start (b->overlays, begin, end, order);
+}
+
+INLINE struct interval_node*
+buffer_overlay_iter_next (struct buffer *b)
+{
+  if (! b->overlays)
+    return NULL;
+  return interval_tree_iter_next (b->overlays);
+}
+
+INLINE void
+buffer_overlay_iter_finish (struct buffer *b)
+{
+  if (b->overlays)
+    interval_tree_iter_finish (b->overlays);
+}
+
+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);
+}
 
-#define OVERLAY_START(OV) XOVERLAY (OV)->start
+/* Return the start of OV in its buffer, or -1 if OV is not associated
+   with any buffer.  */
 
-/* Return the marker that stands for where OV ends in the buffer.  */
+#define OVERLAY_START(OV) (overlay_start (XOVERLAY (OV)))
 
-#define OVERLAY_END(OV) XOVERLAY (OV)->end
+/* Return the end of OV in its buffer, or -1. */
+
+#define OVERLAY_END(OV) (overlay_end (XOVERLAY (OV)))
 
 /* Return the plist of overlay OV.  */
 
-#define OVERLAY_PLIST(OV) XOVERLAY (OV)->plist
+#define OVERLAY_PLIST(OV) (XOVERLAY (OV)->plist)
+
+/* Return the buffer of overlay OV. */
+
+#define OVERLAY_BUFFER(OV) (XOVERLAY (OV)->buffer)
 
-/* Return the actual buffer position for the marker P.
-   We assume you know which buffer it's pointing into.  */
+/* Return true, if OV's rear-advance is set. */
 
-#define OVERLAY_POSITION(P) \
- (MARKERP (P) ? marker_position (P) : (emacs_abort (), 0))
+#define OVERLAY_REAR_ADVANCE_P(OV) (XOVERLAY (OV)->interval->rear_advance)
+
+/* Return true, if OV's front-advance is set. */
+
+#define OVERLAY_FRONT_ADVANCE_P(OV) (XOVERLAY (OV)->interval->front_advance)
 
 
 /***********************************************************************
@@ -1405,4 +1509,7 @@ lowercasep (int c)
 
 INLINE_HEADER_END
 
+int compare_overlays (const void *v1, const void *v2);
+void make_sortvec_item (struct sortvec *item, Lisp_Object overlay);
+
 #endif /* EMACS_BUFFER_H */