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, 6 insertions, 50 deletions

diff --git a/src/editfns.c b/src/editfns.c
index 4dcf7cbe6ef..8628b1b2d49 100644
--- a/src/editfns.c
+++ b/src/editfns.c
@@ -457,51 +457,9 @@ If you set the marker not to point anywhere, the buffer will have no mark.  */)
    of length LEN.  */
 
 static ptrdiff_t
-overlays_around (EMACS_INT pos, Lisp_Object *vec, ptrdiff_t len)
+overlays_around (ptrdiff_t pos, Lisp_Object *vec, ptrdiff_t len)
 {
-  Lisp_Object overlay, start, end;
-  struct Lisp_Overlay *tail;
-  ptrdiff_t startpos, endpos;
-  ptrdiff_t idx = 0;
-
-  for (tail = current_buffer->overlays_before; tail; tail = tail->next)
-    {
-      XSETMISC (overlay, tail);
-
-      end = OVERLAY_END (overlay);
-      endpos = OVERLAY_POSITION (end);
-      if (endpos < pos)
-	  break;
-      start = OVERLAY_START (overlay);
-      startpos = OVERLAY_POSITION (start);
-      if (startpos <= pos)
-	{
-	  if (idx < len)
-	    vec[idx] = overlay;
-	  /* Keep counting overlays even if we can't return them all.  */
-	  idx++;
-	}
-    }
-
-  for (tail = current_buffer->overlays_after; tail; tail = tail->next)
-    {
-      XSETMISC (overlay, tail);
-
-      start = OVERLAY_START (overlay);
-      startpos = OVERLAY_POSITION (start);
-      if (pos < startpos)
-	break;
-      end = OVERLAY_END (overlay);
-      endpos = OVERLAY_POSITION (end);
-      if (pos <= endpos)
-	{
-	  if (idx < len)
-	    vec[idx] = overlay;
-	  idx++;
-	}
-    }
-
-  return idx;
+  return overlays_in (pos - 1, pos, false, &vec, &len, false, NULL);
 }
 
 DEFUN ("get-pos-property", Fget_pos_property, Sget_pos_property, 2, 3, 0,
@@ -561,11 +519,10 @@ at POSITION.  */)
 	  if (!NILP (tem))
 	    {
 	      /* Check the overlay is indeed active at point.  */
-	      Lisp_Object start = OVERLAY_START (ol), finish = OVERLAY_END (ol);
-	      if ((OVERLAY_POSITION (start) == posn
-		   && XMARKER (start)->insertion_type == 1)
-		  || (OVERLAY_POSITION (finish) == posn
-		      && XMARKER (finish)->insertion_type == 0))
+	      if ((OVERLAY_START (ol) == posn
+		   && OVERLAY_FRONT_ADVANCE_P (ol))
+		  || (OVERLAY_END (ol) == posn
+		      && ! OVERLAY_REAR_ADVANCE_P (ol)))
 		; /* The overlay will not cover a char inserted at point.  */
 	      else
 		{
@@ -5385,7 +5342,6 @@ Transposing beyond buffer boundaries is an error.  */)
       transpose_markers (start1, end1, start2, end2,
 			 start1_byte, start1_byte + len1_byte,
 			 start2_byte, start2_byte + len2_byte);
-      fix_start_end_in_overlays (start1, end2);
     }
   else
     {