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, 88 insertions, 0 deletions

diff --git a/src/itree.h b/src/itree.h
new file mode 100644
index 00000000000..d35c5afc24c
--- /dev/null
+++ b/src/itree.h
@@ -0,0 +1,88 @@
+/* This file implements an efficient interval data-structure.
+
+Copyright (C) 2017 Andreas Politz (politza@hochschule-trier.de)
+
+This file is not part of GNU Emacs.
+
+GNU Emacs is free software: you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation, either version 3 of the License, or (at
+your option) any later version.
+
+GNU Emacs is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef ITREE_H
+#define ITREE_H
+#include <config.h>
+#include <stddef.h>
+#include <inttypes.h>
+
+/* The tree and node structs are mainly here, so they can be allocated.
+
+   NOTE: The only time where it is safe to modify node.begin and
+   node.end directly, is while the node is not part of any tree.
+
+   NOTE: It is safe to read node.begin and node.end directly, if the
+   node came from a generator, because it validates the nodes it
+   returns as a side-effect.
+*/
+
+struct interval_node;
+struct interval_node
+{
+  enum { ITREE_RED, ITREE_BLACK } color;
+  struct interval_node *parent;
+  struct interval_node *left;
+  struct interval_node *right;
+  ptrdiff_t begin;		/* The beginning of this interval. */
+  ptrdiff_t end;		/* The end of the interval. */
+  ptrdiff_t limit;		/* The maximum end in this subtree. */
+  ptrdiff_t offset;		/* The amount of shift to apply to this subtree. */
+  uintmax_t otick;              /* offset modified tick */
+  Lisp_Object data;             /* Exclusively used by the client. */
+  bool_bf visited;              /* For traversal via generator. */
+  bool_bf rear_advance : 1;     /* Same as for marker and overlays.  */
+  bool_bf front_advance : 1;    /* Same as for marker and overlays.  */
+};
+
+struct interval_tree
+{
+  struct interval_node *root;
+  struct interval_node nil;	/* The tree's version of NULL. */
+  uintmax_t otick;              /* offset tick, compared with node's otick. */
+  intmax_t size;                /* Number of nodes in the tree. */
+  struct interval_generator *iter;
+  bool_bf iter_running;
+};
+
+enum interval_tree_order {
+  ITREE_ASCENDING = 0,
+  ITREE_DEFLT_ORDER = 0,
+  ITREE_DESCENDING,
+  ITREE_PRE_ORDER,
+};
+
+void interval_node_init(struct interval_node *, ptrdiff_t, ptrdiff_t, bool, bool, Lisp_Object);
+ptrdiff_t interval_node_begin(struct interval_tree *, struct interval_node *);
+ptrdiff_t interval_node_end(struct interval_tree *, struct interval_node *);
+void interval_node_set_region(struct interval_tree *, struct interval_node *, ptrdiff_t, ptrdiff_t);
+struct interval_tree *interval_tree_create(void);
+void interval_tree_destroy(struct interval_tree *);
+intmax_t interval_tree_size(struct interval_tree *);
+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);
+void interval_tree_iter_narrow(struct interval_tree *, ptrdiff_t, ptrdiff_t);
+void interval_tree_iter_finish(struct interval_tree *);
+struct interval_node *interval_tree_iter_next(struct interval_tree *);
+void interval_tree_insert_gap(struct interval_tree *, ptrdiff_t, ptrdiff_t);
+void interval_tree_delete_gap(struct interval_tree *, ptrdiff_t, ptrdiff_t);
+#endif