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, 30 insertions, 19 deletions

diff --git a/src/alloc.c b/src/alloc.c
index 2e6399e7f8d..15a6fc43b72 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -43,6 +43,7 @@ along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.  */
 #include "frame.h"
 #include "blockinput.h"
 #include "termhooks.h"          /* For struct terminal.  */
+#include "itree.h"
 #ifdef HAVE_WINDOW_SYSTEM
 #include TERM_HEADER
 #endif /* HAVE_WINDOW_SYSTEM */
@@ -3835,16 +3836,19 @@ free_save_value (Lisp_Object save)
 /* Return a Lisp_Misc_Overlay object with specified START, END and PLIST.  */
 
 Lisp_Object
-build_overlay (Lisp_Object start, Lisp_Object end, Lisp_Object plist)
+build_overlay (ptrdiff_t begin, ptrdiff_t end,
+               bool front_advance, bool rear_advance,
+               Lisp_Object plist)
 {
-  register Lisp_Object overlay;
+  Lisp_Object ov = allocate_misc (Lisp_Misc_Overlay);
+  struct interval_node *node = xmalloc (sizeof (*node));
 
-  overlay = allocate_misc (Lisp_Misc_Overlay);
-  OVERLAY_START (overlay) = start;
-  OVERLAY_END (overlay) = end;
-  set_overlay_plist (overlay, plist);
-  XOVERLAY (overlay)->next = NULL;
-  return overlay;
+  interval_node_init (node, begin, end, front_advance,
+                      rear_advance, ov);
+  XOVERLAY (ov)->interval = node;
+  XOVERLAY (ov)->buffer = NULL;
+  set_overlay_plist (ov, plist);
+  return ov;
 }
 
 DEFUN ("make-marker", Fmake_marker, Smake_marker, 0, 0, 0,
@@ -6280,16 +6284,10 @@ mark_compiled (struct Lisp_Vector *ptr)
 /* Mark the chain of overlays starting at PTR.  */
 
 static void
-mark_overlay (struct Lisp_Overlay *ptr)
+mark_overlay (struct Lisp_Overlay *ov)
 {
-  for (; ptr && !ptr->gcmarkbit; ptr = ptr->next)
-    {
-      ptr->gcmarkbit = 1;
-      /* These two are always markers and can be marked fast.  */
-      XMARKER (ptr->start)->gcmarkbit = 1;
-      XMARKER (ptr->end)->gcmarkbit = 1;
-      mark_object (ptr->plist);
-    }
+  ov->gcmarkbit = 1;
+  mark_object (ov->plist);
 }
 
 /* Mark Lisp_Objects and special pointers in BUFFER.  */
@@ -6308,8 +6306,15 @@ mark_buffer (struct buffer *buffer)
      a special way just before the sweep phase, and after stripping
      some of its elements that are not needed any more.  */
 
-  mark_overlay (buffer->overlays_before);
-  mark_overlay (buffer->overlays_after);
+  if (buffer->overlays)
+    {
+      struct interval_node *node;
+      buffer_overlay_iter_start (buffer, PTRDIFF_MIN, PTRDIFF_MAX, ITREE_ASCENDING);
+
+      while ((node = buffer_overlay_iter_next (buffer)))
+        mark_overlay (XOVERLAY (node->data));
+      buffer_overlay_iter_finish (buffer);
+    }
 
   /* If this is an indirect buffer, mark its base buffer.  */
   if (buffer->base_buffer && !VECTOR_MARKED_P (buffer->base_buffer))
@@ -7090,6 +7095,11 @@ sweep_misc (void)
                 unchain_marker (&mblk->markers[i].m.u_marker);
               else if (mblk->markers[i].m.u_any.type == Lisp_Misc_Finalizer)
                 unchain_finalizer (&mblk->markers[i].m.u_finalizer);
+              else if (mblk->markers[i].m.u_any.type == Lisp_Misc_Overlay)
+                {
+                  xfree (mblk->markers[i].m.u_overlay.interval);
+                  mblk->markers[i].m.u_overlay.interval = NULL;
+                }
 #ifdef HAVE_MODULES
               else if (mblk->markers[i].m.u_any.type == Lisp_Misc_User_Ptr)
                 {
@@ -7145,6 +7155,7 @@ sweep_buffers (void)
     if (!VECTOR_MARKED_P (buffer))
       {
         *bprev = buffer->next;
+        free_buffer_overlays (buffer);
         lisp_free (buffer);
       }
     else