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.

19 files changed, 1916 insertions, 1347 deletions

diff --git a/src/Makefile.in b/src/Makefile.in
index 9a8c9c85f04..8a8df03e49f 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -395,6 +395,7 @@ base_obj = dispnew.o frame.o scroll.o xdisp.o menu.o $(XMENU_OBJ) window.o \
         $(XWIDGETS_OBJ) \
         profiler.o decompress.o \
         thread.o systhread.o \
+        itree.o \
         $(if $(HYBRID_MALLOC),sheap.o) \
         $(MSDOS_OBJ) $(MSDOS_X_OBJ) $(NS_OBJ) $(CYGWIN_OBJ) $(FONT_OBJ) \
         $(W32_OBJ) $(WINDOW_SYSTEM_OBJ) $(XGSELOBJ)
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
diff --git a/src/buffer.c b/src/buffer.c
index 76670b89545..21c040ad0e1 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -44,6 +44,7 @@ along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.  */
 #include "keymap.h"
 #include "frame.h"
 #include "xwidget.h"
+#include "itree.h"
 
 #ifdef WINDOWSNT
 #include "w32heap.h"            /* for mmap_* */
@@ -120,7 +121,7 @@ static Lisp_Object QSFundamental;	/* A string "Fundamental".  */
 
 static void alloc_buffer_text (struct buffer *, ptrdiff_t);
 static void free_buffer_text (struct buffer *b);
-static struct Lisp_Overlay * copy_overlays (struct buffer *, struct Lisp_Overlay *);
+static void copy_overlays (struct buffer *, struct buffer *);
 static void modify_overlay (struct buffer *, ptrdiff_t, ptrdiff_t);
 static Lisp_Object buffer_lisp_local_variables (struct buffer *, bool);
 
@@ -600,51 +601,30 @@ even if it is dead.  The return value is never nil.  */)
 }
 
 
-/* Return a list of overlays which is a copy of the overlay list
-   LIST, but for buffer B.  */
+/* Copy overlays of buffer FROM to buffer TO.  */
 
-static struct Lisp_Overlay *
-copy_overlays (struct buffer *b, struct Lisp_Overlay *list)
+static void
+copy_overlays (struct buffer *from, struct buffer *to)
 {
-  struct Lisp_Overlay *result = NULL, *tail = NULL;
+  eassert (to && ! to->overlays);
 
-  for (; list; list = list->next)
-    {
-      Lisp_Object overlay, start, end;
-      struct Lisp_Marker *m;
-
-      eassert (MARKERP (list->start));
-      m = XMARKER (list->start);
-      start = build_marker (b, m->charpos, m->bytepos);
-      XMARKER (start)->insertion_type = m->insertion_type;
-
-      eassert (MARKERP (list->end));
-      m = XMARKER (list->end);
-      end = build_marker (b, m->charpos, m->bytepos);
-      XMARKER (end)->insertion_type = m->insertion_type;
-
-      overlay = build_overlay (start, end, Fcopy_sequence (list->plist));
-      if (tail)
-        tail = tail->next = XOVERLAY (overlay);
-      else
-        result = tail = XOVERLAY (overlay);
-    }
-
-  return result;
-}
+  struct interval_node *node;
 
-/* Set an appropriate overlay of B.  */
+  if (! from->overlays)
+    return;
 
-static void
-set_buffer_overlays_before (struct buffer *b, struct Lisp_Overlay *o)
-{
-  b->overlays_before = o;
-}
+  buffer_overlay_iter_start (from, PTRDIFF_MIN, PTRDIFF_MAX, ITREE_ASCENDING);
 
-static void
-set_buffer_overlays_after (struct buffer *b, struct Lisp_Overlay *o)
-{
-  b->overlays_after = o;
+  while ((node = buffer_overlay_iter_next (from)))
+    {
+      Lisp_Object ov = node->data;
+      Lisp_Object copy = build_overlay (node->begin, node->end,
+                                        node->front_advance,
+                                        node->rear_advance,
+                                        Fcopy_sequence (OVERLAY_PLIST (ov)));
+      add_buffer_overlay (to, XOVERLAY (copy));
+    }
+  buffer_overlay_iter_finish (from);
 }
 
 /* Clone per-buffer values of buffer FROM.
@@ -681,8 +661,7 @@ clone_per_buffer_values (struct buffer *from, struct buffer *to)
 
   memcpy (to->local_flags, from->local_flags, sizeof to->local_flags);
 
-  set_buffer_overlays_before (to, copy_overlays (to, from->overlays_before));
-  set_buffer_overlays_after (to, copy_overlays (to, from->overlays_after));
+  copy_overlays (from, to);
 
   /* Get (a copy of) the alist of Lisp-level local variables of FROM
      and install that in TO.  */
@@ -867,17 +846,16 @@ CLONE nil means the indirect buffer's state is reset to default values.  */)
   return buf;
 }
 
-/* Mark OV as no longer associated with B.  */
+/* Mark OV as no longer associated with its buffer.  */
 
 static void
-drop_overlay (struct buffer *b, struct Lisp_Overlay *ov)
+drop_overlay (struct Lisp_Overlay *ov)
 {
-  eassert (b == XBUFFER (Fmarker_buffer (ov->start)));
-  modify_overlay (b, marker_position (ov->start),
-                  marker_position (ov->end));
-  unchain_marker (XMARKER (ov->start));
-  unchain_marker (XMARKER (ov->end));
+  if (! ov->buffer)
+    return;
 
+  modify_overlay (ov->buffer, overlay_start (ov), overlay_end (ov));
+  remove_buffer_overlay (ov->buffer, ov);
 }
 
 /* Delete all overlays of B and reset its overlay lists.  */
@@ -885,26 +863,20 @@ drop_overlay (struct buffer *b, struct Lisp_Overlay *ov)
 void
 delete_all_overlays (struct buffer *b)
 {
-  struct Lisp_Overlay *ov, *next;
+  struct interval_node *node;
 
-  /* FIXME: Since each drop_overlay will scan BUF_MARKERS to unlink its
-     markers, we have an unneeded O(N^2) behavior here.  */
-  for (ov = b->overlays_before; ov; ov = next)
-    {
-      drop_overlay (b, ov);
-      next = ov->next;
-      ov->next = NULL;
-    }
+  if (! b->overlays)
+    return;
 
-  for (ov = b->overlays_after; ov; ov = next)
+  buffer_overlay_iter_start (b, PTRDIFF_MIN, PTRDIFF_MAX, ITREE_ASCENDING);
+  while ((node = buffer_overlay_iter_next (b)))
     {
-      drop_overlay (b, ov);
-      next = ov->next;
-      ov->next = NULL;
+      modify_overlay (b, node->begin, node->end);
+      /* Where are the nodes freed ? --ap */
+      XOVERLAY (node->data)->buffer = NULL;
     }
-
-  set_buffer_overlays_before (b, NULL);
-  set_buffer_overlays_after (b, NULL);
+  buffer_overlay_iter_finish (b);
+  interval_tree_clear (b->overlays);
 }
 
 /* Reinitialize everything about a buffer except its name and contents
@@ -932,9 +904,7 @@ reset_buffer (register struct buffer *b)
   b->auto_save_failure_time = 0;
   bset_auto_save_file_name (b, Qnil);
   bset_read_only (b, Qnil);
-  set_buffer_overlays_before (b, NULL);
-  set_buffer_overlays_after (b, NULL);
-  b->overlay_center = BEG;
+  b->overlays = NULL;
   bset_mark_active (b, Qnil);
   bset_point_before_scroll (b, Qnil);
   bset_file_format (b, Qnil);
@@ -1843,10 +1813,8 @@ cleaning up all windows currently displaying the buffer to be killed. */)
 
       /* Perhaps we should explicitly free the interval tree here...  */
     }
-  /* Since we've unlinked the markers, the overlays can't be here any more
-     either.  */
-  b->overlays_before = NULL;
-  b->overlays_after = NULL;
+  delete_all_overlays (b);
+  free_buffer_overlays (b);
 
   /* Reset the local variables, so that this buffer's local values
      won't be protected from GC.  They would be protected
@@ -2254,6 +2222,31 @@ advance_to_char_boundary (ptrdiff_t byte_pos)
   return byte_pos;
 }
 
+static void
+swap_buffer_overlays (struct buffer *buffer, struct buffer *other)
+{
+  struct interval_node *node;
+
+  if (buffer->overlays)
+    {
+      buffer_overlay_iter_start  (buffer, PTRDIFF_MIN, PTRDIFF_MAX, ITREE_ASCENDING);
+      while ((node = buffer_overlay_iter_next (buffer)))
+        XOVERLAY (node->data)->buffer = other;
+      buffer_overlay_iter_finish (buffer);
+    }
+  if (other->overlays)
+    {
+      buffer_overlay_iter_start (other, PTRDIFF_MIN, PTRDIFF_MAX, ITREE_ASCENDING);
+      while ((node = buffer_overlay_iter_next (other)))
+        XOVERLAY (node->data)->buffer = buffer;
+      buffer_overlay_iter_finish (other);
+    }
+  /* Swap the interval trees. */
+  void *tmp = buffer->overlays;
+  buffer->overlays = other->overlays;
+  other->overlays = tmp;
+}
+
 DEFUN ("buffer-swap-text", Fbuffer_swap_text, Sbuffer_swap_text,
        1, 1, 0,
        doc: /* Swap the text between current buffer and BUFFER.
@@ -2324,9 +2317,6 @@ results, see Info node `(elisp)Swapping Text'.  */)
   swapfield (bidi_paragraph_cache, struct region_cache *);
   current_buffer->prevent_redisplay_optimizations_p = 1;
   other_buffer->prevent_redisplay_optimizations_p = 1;
-  swapfield (overlays_before, struct Lisp_Overlay *);
-  swapfield (overlays_after, struct Lisp_Overlay *);
-  swapfield (overlay_center, ptrdiff_t);
   swapfield_ (undo_list, Lisp_Object);
   swapfield_ (mark, Lisp_Object);
   swapfield_ (enable_multibyte_characters, Lisp_Object);
@@ -2349,6 +2339,7 @@ results, see Info node `(elisp)Swapping Text'.  */)
   current_buffer->text->end_unchanged = current_buffer->text->gpt;
   other_buffer->text->beg_unchanged = other_buffer->text->gpt;
   other_buffer->text->end_unchanged = other_buffer->text->gpt;
+  swap_buffer_overlays (current_buffer, other_buffer);
   {
     struct Lisp_Marker *m;
     for (m = BUF_MARKERS (current_buffer); m; m = m->next)
@@ -2763,285 +2754,160 @@ swap_out_buffer_local_variables (struct buffer *b)
         }
     }
 }
+
 
-/* Find all the overlays in the current buffer that contain position POS.
+/* Find all the overlays in the current buffer that overlap the range
+   [BEG, END).
+
+   If EMPTY is true, include empty overlays in that range and also at
+   END, provided END denotes the position at the end of the buffer.
+
    Return the number found, and store them in a vector in *VEC_PTR.
    Store in *LEN_PTR the size allocated for the vector.
    Store in *NEXT_PTR the next position after POS where an overlay starts,
-     or ZV if there are no more overlays between POS and ZV.
-   Store in *PREV_PTR the previous position before POS where an overlay ends,
-     or where an overlay starts which ends at or after POS;
-     or BEGV if there are no such overlays from BEGV to POS.
-   NEXT_PTR and/or PREV_PTR may be 0, meaning don't store that info.
+     or ZV if there are no more overlays.
+   NEXT_PTR may be 0, meaning don't store that info.
 
    *VEC_PTR and *LEN_PTR should contain a valid vector and size
    when this function is called.
 
-   If EXTEND, make the vector bigger if necessary.
-   If not, never extend the vector,
-   and store only as many overlays as will fit.
+   If EXTEND, make the vector bigger if necessary.  If not, never
+   extend the vector, and store only as many overlays as will fit.
    But still return the total number of overlays.
-
-   If CHANGE_REQ, any position written into *PREV_PTR or
-   *NEXT_PTR is guaranteed to be not equal to POS, unless it is the
-   default (BEGV or ZV).  */
+*/
 
 ptrdiff_t
-overlays_at (EMACS_INT pos, bool extend, Lisp_Object **vec_ptr,
-             ptrdiff_t *len_ptr,
-             ptrdiff_t *next_ptr, ptrdiff_t *prev_ptr, bool change_req)
+overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend,
+             Lisp_Object **vec_ptr, ptrdiff_t *len_ptr,  bool empty,
+             ptrdiff_t *next_ptr)
 {
-  Lisp_Object overlay, start, end;
-  struct Lisp_Overlay *tail;
   ptrdiff_t idx = 0;
   ptrdiff_t len = *len_ptr;
-  Lisp_Object *vec = *vec_ptr;
   ptrdiff_t next = ZV;
-  ptrdiff_t prev = BEGV;
-  bool inhibit_storing = 0;
-
-  for (tail = current_buffer->overlays_before; tail; tail = tail->next)
-    {
-      ptrdiff_t startpos, endpos;
+  Lisp_Object *vec = *vec_ptr;
 
-      XSETMISC (overlay, tail);
+  struct interval_node *node;
 
-      start = OVERLAY_START (overlay);
-      end = OVERLAY_END (overlay);
-      endpos = OVERLAY_POSITION (end);
-      if (endpos < pos)
-        {
-          if (prev < endpos)
-            prev = endpos;
-          break;
-        }
-      startpos = OVERLAY_POSITION (start);
-      /* This one ends at or after POS
-         so its start counts for PREV_PTR if it's before POS.  */
-      if (prev < startpos && startpos < pos)
-        prev = startpos;
-      if (endpos == pos)
-        continue;
-      if (startpos <= pos)
-        {
-          if (idx == len)
-            {
-              /* The supplied vector is full.
-                 Either make it bigger, or don't store any more in it.  */
-              if (extend)
-                {
-                  vec = xpalloc (vec, len_ptr, 1, OVERLAY_COUNT_MAX,
-                                 sizeof *vec);
-                  *vec_ptr = vec;
-                  len = *len_ptr;
-                }
-              else
-                inhibit_storing = 1;
-            }
+  if (! current_buffer->overlays)
+    return idx;
 
-          if (!inhibit_storing)
-            vec[idx] = overlay;
-          /* Keep counting overlays even if we can't return them all.  */
-          idx++;
-        }
-      else if (startpos < next)
-        next = startpos;
-    }
+  buffer_overlay_iter_start (current_buffer, beg,
+                             /* Find empty OV at Z ? */
+                             (end >= Z && empty) ? Z + 1 : ZV,
+                             ITREE_ASCENDING);
 
-  for (tail = current_buffer->overlays_after; tail; tail = tail->next)
+  while ((node = buffer_overlay_iter_next (current_buffer)))
     {
-      ptrdiff_t startpos, endpos;
-
-      XSETMISC (overlay, tail);
-
-      start = OVERLAY_START (overlay);
-      end = OVERLAY_END (overlay);
-      startpos = OVERLAY_POSITION (start);
-      if (pos < startpos)
-        {
-          if (startpos < next)
-            next = startpos;
-          break;
-        }
-      endpos = OVERLAY_POSITION (end);
-      if (pos < endpos)
-        {
-          if (idx == len)
-            {
-              if (extend)
-                {
-                  vec = xpalloc (vec, len_ptr, 1, OVERLAY_COUNT_MAX,
-                                 sizeof *vec);
-                  *vec_ptr = vec;
-                  len = *len_ptr;
-                }
-              else
-                inhibit_storing = 1;
-            }
+      if (node->begin > end)
+        {
+          next = min (next, node->begin);
+          break;
+        }
+      else if (node->begin == end)
+        {
+          next = node->begin;
+          if ((! empty || end < Z) && beg < end)
+            break;
+        }
 
-          if (!inhibit_storing)
-            vec[idx] = overlay;
-          idx++;
+      if (! empty && node->begin == node->end)
+        continue;
 
-          if (startpos < pos && startpos > prev)
-            prev = startpos;
-        }
-      else if (endpos < pos && endpos > prev)
-        prev = endpos;
-      else if (endpos == pos && startpos > prev
-               && (!change_req || startpos < pos))
-        prev = startpos;
+      if (extend && idx == len)
+        {
+          vec = xpalloc (vec, len_ptr, 1, OVERLAY_COUNT_MAX,
+                         sizeof *vec);
+          *vec_ptr = vec;
+          len = *len_ptr;
+        }
+      if (idx < len)
+        vec[idx] = node->data;
+      /* Keep counting overlays even if we can't return them all.  */
+      idx++;
     }
-
+  buffer_overlay_iter_finish (current_buffer);
   if (next_ptr)
-    *next_ptr = next;
-  if (prev_ptr)
-    *prev_ptr = prev;
+    *next_ptr = next ? next : ZV;
+
   return idx;
 }
-
-/* Find all the overlays in the current buffer that overlap the range
-   BEG-END, or are empty at BEG, or are empty at END provided END
-   denotes the position at the end of the current buffer.
 
-   Return the number found, and store them in a vector in *VEC_PTR.
-   Store in *LEN_PTR the size allocated for the vector.
-   Store in *NEXT_PTR the next position after POS where an overlay starts,
-     or ZV if there are no more overlays.
-   Store in *PREV_PTR the previous position before POS where an overlay ends,
-     or BEGV if there are no previous overlays.
-   NEXT_PTR and/or PREV_PTR may be 0, meaning don't store that info.
+/* Find all non-empty overlays in the current buffer that contain
+   position POS.
 
-   *VEC_PTR and *LEN_PTR should contain a valid vector and size
-   when this function is called.
+   See overlays_in for the meaning of the arguments.
+  */
 
-   If EXTEND, make the vector bigger if necessary.
-   If not, never extend the vector,
-   and store only as many overlays as will fit.
-   But still return the total number of overlays.  */
+ptrdiff_t
+overlays_at (ptrdiff_t pos, bool extend,
+             Lisp_Object **vec_ptr, ptrdiff_t *len_ptr,
+             ptrdiff_t *next_ptr)
+{
+  return overlays_in (pos, pos + 1, extend, vec_ptr, len_ptr, false, next_ptr);
+}
 
-static ptrdiff_t
-overlays_in (EMACS_INT beg, EMACS_INT end, bool extend,
-             Lisp_Object **vec_ptr, ptrdiff_t *len_ptr,
-             ptrdiff_t *next_ptr, ptrdiff_t *prev_ptr)
+ptrdiff_t
+next_overlay_change (ptrdiff_t pos)
 {
-  Lisp_Object overlay, ostart, oend;
-  struct Lisp_Overlay *tail;
-  ptrdiff_t idx = 0;
-  ptrdiff_t len = *len_ptr;
-  Lisp_Object *vec = *vec_ptr;
   ptrdiff_t next = ZV;
-  ptrdiff_t prev = BEGV;
-  bool inhibit_storing = 0;
-  bool end_is_Z = end == Z;
+  struct interval_node *node;
 
-  for (tail = current_buffer->overlays_before; tail; tail = tail->next)
-    {
-      ptrdiff_t startpos, endpos;
+  if (! current_buffer->overlays)
+    return next;
 
-      XSETMISC (overlay, tail);
-
-      ostart = OVERLAY_START (overlay);
-      oend = OVERLAY_END (overlay);
-      endpos = OVERLAY_POSITION (oend);
-      if (endpos < beg)
-        {
-          if (prev < endpos)
-            prev = endpos;
-          break;
-        }
-      startpos = OVERLAY_POSITION (ostart);
-      /* Count an interval if it overlaps the range, is empty at the
-         start of the range, or is empty at END provided END denotes the
-         end of the buffer.  */
-      if ((beg < endpos && startpos < end)
-          || (startpos == endpos
-              && (beg == endpos || (end_is_Z && endpos == end))))
-        {
-          if (idx == len)
-            {
-              /* The supplied vector is full.
-                 Either make it bigger, or don't store any more in it.  */
-              if (extend)
-                {
-                  vec = xpalloc (vec, len_ptr, 1, OVERLAY_COUNT_MAX,
-                                 sizeof *vec);
-                  *vec_ptr = vec;
-                  len = *len_ptr;
-                }
-              else
-                inhibit_storing = 1;
-            }
-
-          if (!inhibit_storing)
-            vec[idx] = overlay;
-          /* Keep counting overlays even if we can't return them all.  */
-          idx++;
-        }
-      else if (startpos < next)
-        next = startpos;
+  buffer_overlay_iter_start (current_buffer, pos, ZV, ITREE_ASCENDING);
+  while ((node = buffer_overlay_iter_next (current_buffer)))
+    {
+      if (node->begin > pos)
+        {
+          /* If we reach this branch, node->begin must be the least upper bound
+             of pos, because the search is limited to [pos,next) . */
+          eassert (node->begin < next);
+          next = node->begin;
+          break;
+        }
+      else if (node->begin < node->end && node->end < next)
+        {
+          next = node->end;
+          buffer_overlay_iter_narrow (current_buffer, pos, next);
+        }
     }
+  buffer_overlay_iter_finish (current_buffer);
 
-  for (tail = current_buffer->overlays_after; tail; tail = tail->next)
-    {
-      ptrdiff_t startpos, endpos;
+  return next;
+}
 
-      XSETMISC (overlay, tail);
+ptrdiff_t
+previous_overlay_change (ptrdiff_t pos)
+{
+  struct interval_node *node;
+  ptrdiff_t prev = BEGV;
 
-      ostart = OVERLAY_START (overlay);
-      oend = OVERLAY_END (overlay);
-      startpos = OVERLAY_POSITION (ostart);
-      if (end < startpos)
-        {
-          if (startpos < next)
-            next = startpos;
-          break;
-        }
-      endpos = OVERLAY_POSITION (oend);
-      /* Count an interval if it overlaps the range, is empty at the
-         start of the range, or is empty at END provided END denotes the
-         end of the buffer.  */
-      if ((beg < endpos && startpos < end)
-          || (startpos == endpos
-              && (beg == endpos || (end_is_Z && endpos == end))))
-        {
-          if (idx == len)
-            {
-              if (extend)
-                {
-                  vec = xpalloc (vec, len_ptr, 1, OVERLAY_COUNT_MAX,
-                                 sizeof *vec);
-                  *vec_ptr = vec;
-                  len = *len_ptr;
-                }
-              else
-                inhibit_storing = 1;
-            }
+  if (! current_buffer->overlays)
+    return prev;
 
-          if (!inhibit_storing)
-            vec[idx] = overlay;
-          idx++;
-        }
-      else if (endpos < beg && endpos > prev)
-        prev = endpos;
+  buffer_overlay_iter_start (current_buffer, BEGV, pos, ITREE_DESCENDING);
+  while ((node = buffer_overlay_iter_next (current_buffer)))
+    {
+      if (node->end < pos)
+        prev = node->end;
+      else
+        prev = max (prev, node->begin);
+      buffer_overlay_iter_narrow (current_buffer, prev, pos);
     }
+  buffer_overlay_iter_finish (current_buffer);
 
-  if (next_ptr)
-    *next_ptr = next;
-  if (prev_ptr)
-    *prev_ptr = prev;
-  return idx;
+  return prev;
 }
 
-
 /* Return true if there exists an overlay with a non-nil
    `mouse-face' property overlapping OVERLAY.  */
 
 bool
 mouse_face_overlay_overlaps (Lisp_Object overlay)
 {
-  ptrdiff_t start = OVERLAY_POSITION (OVERLAY_START (overlay));
-  ptrdiff_t end = OVERLAY_POSITION (OVERLAY_END (overlay));
+  ptrdiff_t start = OVERLAY_START (overlay);
+  ptrdiff_t end = OVERLAY_END (overlay);
   ptrdiff_t n, i, size;
   Lisp_Object *v, tem;
   Lisp_Object vbuf[10];
@@ -3049,11 +2915,11 @@ mouse_face_overlay_overlaps (Lisp_Object overlay)
 
   size = ARRAYELTS (vbuf);
   v = vbuf;
-  n = overlays_in (start, end, 0, &v, &size, NULL, NULL);
+  n = overlays_in (start, end, 0, &v, &size, true, NULL);
   if (n > size)
     {
       SAFE_NALLOCA (v, 1, n);
-      overlays_in (start, end, 0, &v, &n, NULL, NULL);
+      overlays_in (start, end, 0, &v, &n, true, NULL);
     }
 
   for (i = 0; i < n; ++i)
@@ -3095,52 +2961,34 @@ disable_line_numbers_overlay_at_eob (void)
 }
 
 
-/* Fast function to just test if we're at an overlay boundary.  */
+/* Fast function to just test if we're at an overlay boundary.
+
+   Returns true if some overlay starts or ends (or both) at POS,
+*/
 bool
 overlay_touches_p (ptrdiff_t pos)
 {
-  Lisp_Object overlay;
-  struct Lisp_Overlay *tail;
-
-  for (tail = current_buffer->overlays_before; tail; tail = tail->next)
-    {
-      ptrdiff_t endpos;
+  struct interval_node *node;
+  bool result = false;
 
-      XSETMISC (overlay ,tail);
-      eassert (OVERLAYP (overlay));
+  if (! current_buffer->overlays)
+    return false;
 
-      endpos = OVERLAY_POSITION (OVERLAY_END (overlay));
-      if (endpos < pos)
-        break;
-      if (endpos == pos || OVERLAY_POSITION (OVERLAY_START (overlay)) == pos)
-        return 1;
-    }
+  /* 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);
 
-  for (tail = current_buffer->overlays_after; tail; tail = tail->next)
-    {
-      ptrdiff_t startpos;
+  while (! result && (node = buffer_overlay_iter_next (current_buffer)))
+    result = (node->begin == pos || node->end == pos);
 
-      XSETMISC (overlay, tail);
-      eassert (OVERLAYP (overlay));
+  buffer_overlay_iter_finish (current_buffer);
 
-      startpos = OVERLAY_POSITION (OVERLAY_START (overlay));
-      if (pos < startpos)
-        break;
-      if (startpos == pos || OVERLAY_POSITION (OVERLAY_END (overlay)) == pos)
-        return 1;
-    }
-  return 0;
+  return result;
 }
-
-struct sortvec
-{
-  Lisp_Object overlay;
-  ptrdiff_t beg, end;
-  EMACS_INT priority;
-  EMACS_INT spriority;          /* Secondary priority.  */
-};
 
-static int
+
+int
 compare_overlays (const void *v1, const void *v2)
 {
   const struct sortvec *s1 = v1;
@@ -3169,6 +3017,33 @@ compare_overlays (const void *v1, const void *v2)
     return XLI (s1->overlay) < XLI (s2->overlay) ? -1 : 1;
 }
 
+void
+make_sortvec_item (struct sortvec *item, Lisp_Object overlay)
+{
+  Lisp_Object tem;
+  /* This overlay is good and counts: put it into sortvec.  */
+  item->overlay = overlay;
+  item->beg = OVERLAY_START (overlay);
+  item->end = OVERLAY_END (overlay);
+  tem = Foverlay_get (overlay, Qpriority);
+  if (NILP (tem))
+    {
+      item->priority = 0;
+      item->spriority = 0;
+    }
+  else if (INTEGERP (tem))
+    {
+      item->priority = XINT (tem);
+      item->spriority = 0;
+    }
+  else if (CONSP (tem))
+    {
+      Lisp_Object car = XCAR (tem);
+      Lisp_Object cdr = XCDR (tem);
+      item->priority  = INTEGERP (car) ? XINT (car) : 0;
+      item->spriority = INTEGERP (cdr) ? XINT (cdr) : 0;
+    }
+}
 /* Sort an array of overlays by priority.  The array is modified in place.
    The return value is the new size; this may be smaller than the original
    size if some of the overlays were invalid or were window-specific.  */
@@ -3185,47 +3060,18 @@ sort_overlays (Lisp_Object *overlay_vec, ptrdiff_t noverlays, struct window *w)
 
   for (i = 0, j = 0; i < noverlays; i++)
     {
-      Lisp_Object tem;
       Lisp_Object overlay;
 
       overlay = overlay_vec[i];
       if (OVERLAYP (overlay)
-          && OVERLAY_POSITION (OVERLAY_START (overlay)) > 0
-          && OVERLAY_POSITION (OVERLAY_END (overlay)) > 0)
+          && OVERLAY_START (overlay) > 0
+          && OVERLAY_END (overlay) > 0)
         {
-          /* If we're interested in a specific window, then ignore
-             overlays that are limited to some other window.  */
-          if (w)
-            {
-              Lisp_Object window;
-
-              window = Foverlay_get (overlay, Qwindow);
-              if (WINDOWP (window) && XWINDOW (window) != w)
-                continue;
-            }
-
-          /* This overlay is good and counts: put it into sortvec.  */
-          sortvec[j].overlay = overlay;
-          sortvec[j].beg = OVERLAY_POSITION (OVERLAY_START (overlay));
-          sortvec[j].end = OVERLAY_POSITION (OVERLAY_END (overlay));
-          tem = Foverlay_get (overlay, Qpriority);
-          if (NILP (tem))
-            {
-              sortvec[j].priority = 0;
-              sortvec[j].spriority = 0;
-            }
-          else if (INTEGERP (tem))
-            {
-              sortvec[j].priority = XINT (tem);
-              sortvec[j].spriority = 0;
-            }
-          else if (CONSP (tem))
-            {
-              Lisp_Object car = XCAR (tem);
-              Lisp_Object cdr = XCDR (tem);
-              sortvec[j].priority  = INTEGERP (car) ? XINT (car) : 0;
-              sortvec[j].spriority = INTEGERP (cdr) ? XINT (cdr) : 0;
-            }
+          /* If we're interested in a specific window, then ignore
+             overlays that are limited to some other window.  */
+          if (w && ! overlay_matches_window (w, overlay))
+            continue;
+          make_sortvec_item (sortvec + j, overlay);
           j++;
         }
     }
@@ -3340,68 +3186,44 @@ ptrdiff_t
 overlay_strings (ptrdiff_t pos, struct window *w, unsigned char **pstr)
 {
   Lisp_Object overlay, window, str;
-  struct Lisp_Overlay *ov;
-  ptrdiff_t startpos, endpos;
+  ptrdiff_t obegin, oend;
   bool multibyte = ! NILP (BVAR (current_buffer, enable_multibyte_characters));
+  struct interval_node *node;
 
   overlay_heads.used = overlay_heads.bytes = 0;
   overlay_tails.used = overlay_tails.bytes = 0;
-  for (ov = current_buffer->overlays_before; ov; ov = ov->next)
+
+  buffer_overlay_iter_start (current_buffer,
+                             pos - 1, pos + 1, ITREE_DESCENDING);
+  while ((node  = buffer_overlay_iter_next (current_buffer)))
     {
-      XSETMISC (overlay, ov);
+      overlay = node->data;
       eassert (OVERLAYP (overlay));
 
-      startpos = OVERLAY_POSITION (OVERLAY_START (overlay));
-      endpos = OVERLAY_POSITION (OVERLAY_END (overlay));
-      if (endpos < pos)
-        break;
-      if (endpos != pos && startpos != pos)
+      obegin = node->begin;
+      oend = node->end;
+
+      if (oend != pos && obegin != pos)
         continue;
       window = Foverlay_get (overlay, Qwindow);
       if (WINDOWP (window) && XWINDOW (window) != w)
         continue;
-      if (startpos == pos
+      if (obegin == pos
           && (str = Foverlay_get (overlay, Qbefore_string), STRINGP (str)))
         record_overlay_string (&overlay_heads, str,
-                               (startpos == endpos
+                               (obegin == oend
                                 ? Foverlay_get (overlay, Qafter_string)
                                 : Qnil),
                                Foverlay_get (overlay, Qpriority),
-                               endpos - startpos);
-      else if (endpos == pos
+                               oend - obegin);
+      else if (oend == pos
           && (str = Foverlay_get (overlay, Qafter_string), STRINGP (str)))
         record_overlay_string (&overlay_tails, str, Qnil,
                                Foverlay_get (overlay, Qpriority),
-                               endpos - startpos);
+                               oend - obegin);
     }
-  for (ov = current_buffer->overlays_after; ov; ov = ov->next)
-    {
-      XSETMISC (overlay, ov);
-      eassert (OVERLAYP (overlay));
+  buffer_overlay_iter_finish (current_buffer);
 
-      startpos = OVERLAY_POSITION (OVERLAY_START (overlay));
-      endpos = OVERLAY_POSITION (OVERLAY_END (overlay));
-      if (startpos > pos)
-        break;
-      if (endpos != pos && startpos != pos)
-        continue;
-      window = Foverlay_get (overlay, Qwindow);
-      if (WINDOWP (window) && XWINDOW (window) != w)
-        continue;
-      if (startpos == pos
-          && (str = Foverlay_get (overlay, Qbefore_string), STRINGP (str)))
-        record_overlay_string (&overlay_heads, str,
-                               (startpos == endpos
-                                ? Foverlay_get (overlay, Qafter_string)
-                                : Qnil),
-                               Foverlay_get (overlay, Qpriority),
-                               endpos - startpos);
-      else if (endpos == pos
-               && (str = Foverlay_get (overlay, Qafter_string), STRINGP (str)))
-        record_overlay_string (&overlay_tails, str, Qnil,
-                               Foverlay_get (overlay, Qpriority),
-                               endpos - startpos);
-    }
   if (overlay_tails.used > 1)
     qsort (overlay_tails.buf, overlay_tails.used, sizeof (struct sortstr),
            cmp_for_strings);
@@ -3456,385 +3278,26 @@ overlay_strings (ptrdiff_t pos, struct window *w, unsigned char **pstr)
     }
   return 0;
 }
-
-/* Shift overlays in BUF's overlay lists, to center the lists at POS.  */
-
-void
-recenter_overlay_lists (struct buffer *buf, ptrdiff_t pos)
-{
-  Lisp_Object overlay, beg, end;
-  struct Lisp_Overlay *prev, *tail, *next;
-
-  /* See if anything in overlays_before should move to overlays_after.  */
-
-  /* We don't strictly need prev in this loop; it should always be nil.
-     But we use it for symmetry and in case that should cease to be true
-     with some future change.  */
-  prev = NULL;
-  for (tail = buf->overlays_before; tail; prev = tail, tail = next)
-    {
-      next = tail->next;
-      XSETMISC (overlay, tail);
-      eassert (OVERLAYP (overlay));
-
-      beg = OVERLAY_START (overlay);
-      end = OVERLAY_END (overlay);
-
-      if (OVERLAY_POSITION (end) > pos)
-        {
-          /* OVERLAY needs to be moved.  */
-          ptrdiff_t where = OVERLAY_POSITION (beg);
-          struct Lisp_Overlay *other, *other_prev;
-
-          /* Splice the cons cell TAIL out of overlays_before.  */
-          if (prev)
-            prev->next = next;
-          else
-            set_buffer_overlays_before (buf, next);
-
-          /* Search thru overlays_after for where to put it.  */
-          other_prev = NULL;
-          for (other = buf->overlays_after; other;
-               other_prev = other, other = other->next)
-            {
-              Lisp_Object otherbeg, otheroverlay;
-
-              XSETMISC (otheroverlay, other);
-              eassert (OVERLAYP (otheroverlay));
-
-              otherbeg = OVERLAY_START (otheroverlay);
-              if (OVERLAY_POSITION (otherbeg) >= where)
-                break;
-            }
-
-          /* Add TAIL to overlays_after before OTHER.  */
-          tail->next = other;
-          if (other_prev)
-            other_prev->next = tail;
-          else
-            set_buffer_overlays_after (buf, tail);
-          tail = prev;
-        }
-      else
-        /* We've reached the things that should stay in overlays_before.
-           All the rest of overlays_before must end even earlier,
-           so stop now.  */
-        break;
-    }
-
-  /* See if anything in overlays_after should be in overlays_before.  */
-  prev = NULL;
-  for (tail = buf->overlays_after; tail; prev = tail, tail = next)
-    {
-      next = tail->next;
-      XSETMISC (overlay, tail);
-      eassert (OVERLAYP (overlay));
-
-      beg = OVERLAY_START (overlay);
-      end = OVERLAY_END (overlay);
-
-      /* Stop looking, when we know that nothing further
-         can possibly end before POS.  */
-      if (OVERLAY_POSITION (beg) > pos)
-        break;
-
-      if (OVERLAY_POSITION (end) <= pos)
-        {
-          /* OVERLAY needs to be moved.  */
-          ptrdiff_t where = OVERLAY_POSITION (end);
-          struct Lisp_Overlay *other, *other_prev;
-
-          /* Splice the cons cell TAIL out of overlays_after.  */
-          if (prev)
-            prev->next = next;
-          else
-            set_buffer_overlays_after (buf, next);
-
-          /* Search thru overlays_before for where to put it.  */
-          other_prev = NULL;
-          for (other = buf->overlays_before; other;
-               other_prev = other, other = other->next)
-            {
-              Lisp_Object otherend, otheroverlay;
-
-              XSETMISC (otheroverlay, other);
-              eassert (OVERLAYP (otheroverlay));
-
-              otherend = OVERLAY_END (otheroverlay);
-              if (OVERLAY_POSITION (otherend) <= where)
-                break;
-            }
-
-          /* Add TAIL to overlays_before before OTHER.  */
-          tail->next = other;
-          if (other_prev)
-            other_prev->next = tail;
-          else
-            set_buffer_overlays_before (buf, tail);
-          tail = prev;
-        }
-    }
-
-  buf->overlay_center = pos;
-}
 
+
 void
 adjust_overlays_for_insert (ptrdiff_t pos, ptrdiff_t length)
 {
   /* After an insertion, the lists are still sorted properly,
      but we may need to update the value of the overlay center.  */
-  if (current_buffer->overlay_center >= pos)
-    current_buffer->overlay_center += length;
+  if (! current_buffer->overlays)
+    return;
+  interval_tree_insert_gap (current_buffer->overlays, pos, length);
 }
 
 void
 adjust_overlays_for_delete (ptrdiff_t pos, ptrdiff_t length)
 {
-  if (current_buffer->overlay_center < pos)
-    /* The deletion was to our right.  No change needed; the before- and
-       after-lists are still consistent.  */
-    ;
-  else if (current_buffer->overlay_center - pos > length)
-    /* The deletion was to our left.  We need to adjust the center value
-       to account for the change in position, but the lists are consistent
-       given the new value.  */
-    current_buffer->overlay_center -= length;
-  else
-    /* We're right in the middle.  There might be things on the after-list
-       that now belong on the before-list.  Recentering will move them,
-       and also update the center point.  */
-    recenter_overlay_lists (current_buffer, pos);
-}
-
-/* Fix up overlays that were garbled as a result of permuting markers
-   in the range START through END.  Any overlay with at least one
-   endpoint in this range will need to be unlinked from the overlay
-   list and reinserted in its proper place.
-   Such an overlay might even have negative size at this point.
-   If so, we'll make the overlay empty. */
-void
-fix_start_end_in_overlays (register ptrdiff_t start, register ptrdiff_t end)
-{
-  Lisp_Object overlay;
-  struct Lisp_Overlay *before_list;
-  struct Lisp_Overlay *after_list;
-  /* These are either nil, indicating that before_list or after_list
-     should be assigned, or the cons cell the cdr of which should be
-     assigned.  */
-  struct Lisp_Overlay *beforep = NULL, *afterp = NULL;
-  /* 'Parent', likewise, indicates a cons cell or
-     current_buffer->overlays_before or overlays_after, depending
-     which loop we're in.  */
-  struct Lisp_Overlay *tail, *parent;
-  ptrdiff_t startpos, endpos;
-
-  /* This algorithm shifts links around instead of consing and GCing.
-     The loop invariant is that before_list (resp. after_list) is a
-     well-formed list except that its last element, the CDR of beforep
-     (resp. afterp) if beforep (afterp) isn't nil or before_list
-     (after_list) if it is, is still uninitialized.  So it's not a bug
-     that before_list isn't initialized, although it may look
-     strange.  */
-  for (parent = NULL, tail = current_buffer->overlays_before; tail;)
-    {
-      XSETMISC (overlay, tail);
-
-      endpos = OVERLAY_POSITION (OVERLAY_END (overlay));
-      startpos = OVERLAY_POSITION (OVERLAY_START (overlay));
-
-      /* If the overlay is backwards, make it empty.  */
-      if (endpos < startpos)
-        {
-          startpos = endpos;
-          Fset_marker (OVERLAY_START (overlay), make_number (startpos),
-                       Qnil);
-        }
-
-      if (endpos < start)
-        break;
-
-      if (endpos < end
-          || (startpos >= start && startpos < end))
-        {
-          /* Add it to the end of the wrong list.  Later on,
-             recenter_overlay_lists will move it to the right place.  */
-          if (endpos < current_buffer->overlay_center)
-            {
-              if (!afterp)
-                after_list = tail;
-              else
-                afterp->next = tail;
-              afterp = tail;
-            }
-          else
-            {
-              if (!beforep)
-                before_list = tail;
-              else
-                beforep->next = tail;
-              beforep = tail;
-            }
-          if (!parent)
-            set_buffer_overlays_before (current_buffer, tail->next);
-          else
-            parent->next = tail->next;
-          tail = tail->next;
-        }
-      else
-        parent = tail, tail = parent->next;
-    }
-  for (parent = NULL, tail = current_buffer->overlays_after; tail;)
-    {
-      XSETMISC (overlay, tail);
-
-      startpos = OVERLAY_POSITION (OVERLAY_START (overlay));
-      endpos = OVERLAY_POSITION (OVERLAY_END (overlay));
-
-      /* If the overlay is backwards, make it empty.  */
-      if (endpos < startpos)
-        {
-          startpos = endpos;
-          Fset_marker (OVERLAY_START (overlay), make_number (startpos),
-                       Qnil);
-        }
-
-      if (startpos >= end)
-        break;
-
-      if (startpos >= start
-          || (endpos >= start && endpos < end))
-        {
-          if (endpos < current_buffer->overlay_center)
-            {
-              if (!afterp)
-                after_list = tail;
-              else
-                afterp->next = tail;
-              afterp = tail;
-            }
-          else
-            {
-              if (!beforep)
-                before_list = tail;
-              else
-                beforep->next = tail;
-              beforep = tail;
-            }
-          if (!parent)
-            set_buffer_overlays_after (current_buffer, tail->next);
-          else
-            parent->next = tail->next;
-          tail = tail->next;
-        }
-      else
-        parent = tail, tail = parent->next;
-    }
-
-  /* Splice the constructed (wrong) lists into the buffer's lists,
-     and let the recenter function make it sane again.  */
-  if (beforep)
-    {
-      beforep->next = current_buffer->overlays_before;
-      set_buffer_overlays_before (current_buffer, before_list);
-    }
-
-  if (afterp)
-    {
-      afterp->next = current_buffer->overlays_after;
-      set_buffer_overlays_after (current_buffer, after_list);
-    }
-  recenter_overlay_lists (current_buffer, current_buffer->overlay_center);
-}
-
-/* We have two types of overlay: the one whose ending marker is
-   after-insertion-marker (this is the usual case) and the one whose
-   ending marker is before-insertion-marker.  When `overlays_before'
-   contains overlays of the latter type and the former type in this
-   order and both overlays end at inserting position, inserting a text
-   increases only the ending marker of the latter type, which results
-   in incorrect ordering of `overlays_before'.
-
-   This function fixes ordering of overlays in the slot
-   `overlays_before' of the buffer *BP.  Before the insertion, `point'
-   was at PREV, and now is at POS.  */
-
-void
-fix_overlays_before (struct buffer *bp, ptrdiff_t prev, ptrdiff_t pos)
-{
-  /* If parent is nil, replace overlays_before; otherwise, parent->next.  */
-  struct Lisp_Overlay *tail = bp->overlays_before, *parent = NULL, *right_pair;
-  Lisp_Object tem;
-  ptrdiff_t end UNINIT;
-
-  /* After the insertion, the several overlays may be in incorrect
-     order.  The possibility is that, in the list `overlays_before',
-     an overlay which ends at POS appears after an overlay which ends
-     at PREV.  Since POS is greater than PREV, we must fix the
-     ordering of these overlays, by moving overlays ends at POS before
-     the overlays ends at PREV.  */
-
-  /* At first, find a place where disordered overlays should be linked
-     in.  It is where an overlay which end before POS exists. (i.e. an
-     overlay whose ending marker is after-insertion-marker if disorder
-     exists).  */
-  while (tail
-         && (XSETMISC (tem, tail),
-             (end = OVERLAY_POSITION (OVERLAY_END (tem))) >= pos))
-    {
-      parent = tail;
-      tail = tail->next;
-    }
-
-  /* If we don't find such an overlay,
-     or the found one ends before PREV,
-     or the found one is the last one in the list,
-     we don't have to fix anything.  */
-  if (!tail || end < prev || !tail->next)
+  if (! current_buffer->overlays)
     return;
-
-  right_pair = parent;
-  parent = tail;
-  tail = tail->next;
-
-  /* Now, end position of overlays in the list TAIL should be before
-     or equal to PREV.  In the loop, an overlay which ends at POS is
-     moved ahead to the place indicated by the CDR of RIGHT_PAIR.  If
-     we found an overlay which ends before PREV, the remaining
-     overlays are in correct order.  */
-  while (tail)
-    {
-      XSETMISC (tem, tail);
-      end = OVERLAY_POSITION (OVERLAY_END (tem));
-
-      if (end == pos)
-        {                       /* This overlay is disordered. */
-          struct Lisp_Overlay *found = tail;
-
-          /* Unlink the found overlay.  */
-          tail = found->next;
-          parent->next = tail;
-          /* Move an overlay at RIGHT_PLACE to the next of the found one,
-             and link it into the right place.  */
-          if (!right_pair)
-            {
-              found->next = bp->overlays_before;
-              set_buffer_overlays_before (bp, found);
-            }
-          else
-            {
-              found->next = right_pair->next;
-              right_pair->next = found;
-            }
-        }
-      else if (end == prev)
-        {
-          parent = tail;
-          tail = tail->next;
-        }
-      else                      /* No more disordered overlay. */
-        break;
-    }
+  interval_tree_delete_gap (current_buffer->overlays, pos, length);
 }
+
 
 DEFUN ("overlayp", Foverlayp, Soverlayp, 1, 1, 0,
        doc: /* Return t if OBJECT is an overlay.  */)
@@ -3853,10 +3316,11 @@ for the front of the overlay advance when text is inserted there
 The fifth arg REAR-ADVANCE, if non-nil, makes the marker
 for the rear of the overlay advance when text is inserted there
 \(which means the text *is* included in the overlay).  */)
-  (Lisp_Object beg, Lisp_Object end, Lisp_Object buffer,
+  (Lisp_Object begin, Lisp_Object end, Lisp_Object buffer,
    Lisp_Object front_advance, Lisp_Object rear_advance)
 {
-  Lisp_Object overlay;
+  Lisp_Object ov;
+  ptrdiff_t obegin, oend;
   struct buffer *b;
 
   if (NILP (buffer))
@@ -3864,53 +3328,35 @@ for the rear of the overlay advance when text is inserted there
   else
     CHECK_BUFFER (buffer);
 
-  if (MARKERP (beg) && !EQ (Fmarker_buffer (beg), buffer))
-    signal_error ("Marker points into wrong buffer", beg);
+  b = XBUFFER (buffer);
+  if (! BUFFER_LIVE_P (b))
+    error ("Attempt to create overlay in a dead buffer");
+
+  if (MARKERP (begin) && !EQ (Fmarker_buffer (begin), buffer))
+    signal_error ("Marker points into wrong buffer", begin);
   if (MARKERP (end) && !EQ (Fmarker_buffer (end), buffer))
     signal_error ("Marker points into wrong buffer", end);
 
-  CHECK_NUMBER_COERCE_MARKER (beg);
+  CHECK_NUMBER_COERCE_MARKER (begin);
   CHECK_NUMBER_COERCE_MARKER (end);
 
-  if (XINT (beg) > XINT (end))
+  if (XINT (begin) > XINT (end))
     {
       Lisp_Object temp;
-      temp = beg; beg = end; end = temp;
+      temp = begin; begin = end; end = temp;
     }
 
-  b = XBUFFER (buffer);
-
-  beg = Fset_marker (Fmake_marker (), beg, buffer);
-  end = Fset_marker (Fmake_marker (), end, buffer);
-
-  if (!NILP (front_advance))
-    XMARKER (beg)->insertion_type = 1;
-  if (!NILP (rear_advance))
-    XMARKER (end)->insertion_type = 1;
-
-  overlay = build_overlay (beg, end, Qnil);
-
-  /* Put the new overlay on the wrong list.  */
-  end = OVERLAY_END (overlay);
-  if (OVERLAY_POSITION (end) < b->overlay_center)
-    {
-      eassert (b->overlays_after || (XOVERLAY (overlay)->next == NULL));
-      XOVERLAY (overlay)->next = b->overlays_after;
-      set_buffer_overlays_after (b, XOVERLAY (overlay));
-    }
-  else
-    {
-      eassert (b->overlays_before || (XOVERLAY (overlay)->next == NULL));
-      XOVERLAY (overlay)->next = b->overlays_before;
-      set_buffer_overlays_before (b, XOVERLAY (overlay));
-    }
-  /* This puts it in the right list, and in the right order.  */
-  recenter_overlay_lists (b, b->overlay_center);
+  obegin = clip_to_bounds (BEG, XINT (begin), b->text->z);
+  oend = clip_to_bounds (obegin, XINT (end), b->text->z);
+  ov = build_overlay (obegin, oend,
+                      ! NILP (front_advance),
+                      ! NILP (rear_advance), Qnil);
+  add_buffer_overlay (b, XOVERLAY (ov));
 
   /* We don't need to redisplay the region covered by the overlay, because
      the overlay has no properties at the moment.  */
 
-  return overlay;
+  return ov;
 }
 
 /* Mark a section of BUF as needing redisplay because of overlays changes.  */
@@ -3932,35 +3378,6 @@ modify_overlay (struct buffer *buf, ptrdiff_t start, ptrdiff_t end)
   ++BUF_OVERLAY_MODIFF (buf);
 }
 
-/* Remove OVERLAY from LIST.  */
-
-static struct Lisp_Overlay *
-unchain_overlay (struct Lisp_Overlay *list, struct Lisp_Overlay *overlay)
-{
-  register struct Lisp_Overlay *tail, **prev = &list;
-
-  for (tail = list; tail; prev = &tail->next, tail = *prev)
-    if (tail == overlay)
-      {
-        *prev = overlay->next;
-        overlay->next = NULL;
-        break;
-      }
-  return list;
-}
-
-/* Remove OVERLAY from both overlay lists of B.  */
-
-static void
-unchain_both (struct buffer *b, Lisp_Object overlay)
-{
-  struct Lisp_Overlay *ov = XOVERLAY (overlay);
-
-  set_buffer_overlays_before (b, unchain_overlay (b->overlays_before, ov));
-  set_buffer_overlays_after (b, unchain_overlay (b->overlays_after, ov));
-  eassert (XOVERLAY (overlay)->next == NULL);
-}
-
 DEFUN ("move-overlay", Fmove_overlay, Smove_overlay, 3, 4, 0,
        doc: /* Set the endpoints of OVERLAY to BEG and END in BUFFER.
 If BUFFER is omitted, leave OVERLAY in the same buffer it inhabits now.
@@ -3976,7 +3393,7 @@ buffer.  */)
 
   CHECK_OVERLAY (overlay);
   if (NILP (buffer))
-    buffer = Fmarker_buffer (OVERLAY_START (overlay));
+    buffer = Foverlay_buffer (overlay);
   if (NILP (buffer))
     XSETBUFFER (buffer, current_buffer);
   CHECK_BUFFER (buffer);
@@ -4000,25 +3417,28 @@ buffer.  */)
 
   specbind (Qinhibit_quit, Qt);
 
-  obuffer = Fmarker_buffer (OVERLAY_START (overlay));
+  obuffer = Foverlay_buffer (overlay);
   b = XBUFFER (buffer);
 
   if (!NILP (obuffer))
     {
       ob = XBUFFER (obuffer);
 
-      o_beg = OVERLAY_POSITION (OVERLAY_START (overlay));
-      o_end = OVERLAY_POSITION (OVERLAY_END (overlay));
-
-      unchain_both (ob, overlay);
+      o_beg = OVERLAY_START (overlay);
+      o_end = OVERLAY_END (overlay);
     }
 
+  if (! EQ (buffer, obuffer))
+    {
+      if (! NILP (obuffer))
+        remove_buffer_overlay (XBUFFER (obuffer), XOVERLAY (overlay));
+      add_buffer_overlay (XBUFFER (buffer), XOVERLAY (overlay));
+    }
   /* Set the overlay boundaries, which may clip them.  */
-  Fset_marker (OVERLAY_START (overlay), beg, buffer);
-  Fset_marker (OVERLAY_END (overlay), end, buffer);
+  set_overlay_region (XOVERLAY (overlay), XINT (beg), XINT (end));
 
-  n_beg = marker_position (OVERLAY_START (overlay));
-  n_end = marker_position (OVERLAY_END (overlay));
+  n_beg = OVERLAY_START (overlay);
+  n_end = OVERLAY_END (overlay);
 
   /* If the overlay has changed buffers, do a thorough redisplay.  */
   if (!EQ (buffer, obuffer))
@@ -4046,22 +3466,6 @@ buffer.  */)
   if (n_beg == n_end && !NILP (Foverlay_get (overlay, Qevaporate)))
     return unbind_to (count, Fdelete_overlay (overlay));
 
-  /* Put the overlay into the new buffer's overlay lists, first on the
-     wrong list.  */
-  if (n_end < b->overlay_center)
-    {
-      XOVERLAY (overlay)->next = b->overlays_after;
-      set_buffer_overlays_after (b, XOVERLAY (overlay));
-    }
-  else
-    {
-      XOVERLAY (overlay)->next = b->overlays_before;
-      set_buffer_overlays_before (b, XOVERLAY (overlay));
-    }
-
-  /* This puts it in the right list, and in the right order.  */
-  recenter_overlay_lists (b, b->overlay_center);
-
   return unbind_to (count, overlay);
 }
 
@@ -4069,21 +3473,18 @@ DEFUN ("delete-overlay", Fdelete_overlay, Sdelete_overlay, 1, 1, 0,
        doc: /* Delete the overlay OVERLAY from its buffer.  */)
   (Lisp_Object overlay)
 {
-  Lisp_Object buffer;
   struct buffer *b;
   ptrdiff_t count = SPECPDL_INDEX ();
 
   CHECK_OVERLAY (overlay);
 
-  buffer = Fmarker_buffer (OVERLAY_START (overlay));
-  if (NILP (buffer))
+  b = OVERLAY_BUFFER (overlay);
+  if (! b)
     return Qnil;
 
-  b = XBUFFER (buffer);
   specbind (Qinhibit_quit, Qt);
 
-  unchain_both (b, overlay);
-  drop_overlay (b, XOVERLAY (overlay));
+  drop_overlay (XOVERLAY (overlay));
 
   /* When deleting an overlay with before or after strings, turn off
      display optimizations for the affected buffer, on the basis that
@@ -4114,8 +3515,10 @@ DEFUN ("overlay-start", Foverlay_start, Soverlay_start, 1, 1, 0,
   (Lisp_Object overlay)
 {
   CHECK_OVERLAY (overlay);
+  if (! OVERLAY_BUFFER (overlay))
+    return Qnil;
 
-  return (Fmarker_position (OVERLAY_START (overlay)));
+  return make_number (OVERLAY_START (overlay));
 }
 
 DEFUN ("overlay-end", Foverlay_end, Soverlay_end, 1, 1, 0,
@@ -4123,8 +3526,10 @@ DEFUN ("overlay-end", Foverlay_end, Soverlay_end, 1, 1, 0,
   (Lisp_Object overlay)
 {
   CHECK_OVERLAY (overlay);
+  if (! OVERLAY_BUFFER (overlay))
+    return Qnil;
 
-  return (Fmarker_position (OVERLAY_END (overlay)));
+  return make_number (OVERLAY_END (overlay));
 }
 
 DEFUN ("overlay-buffer", Foverlay_buffer, Soverlay_buffer, 1, 1, 0,
@@ -4132,9 +3537,16 @@ DEFUN ("overlay-buffer", Foverlay_buffer, Soverlay_buffer, 1, 1, 0,
 Return nil if OVERLAY has been deleted.  */)
   (Lisp_Object overlay)
 {
+  Lisp_Object buffer;
+
   CHECK_OVERLAY (overlay);
 
-  return Fmarker_buffer (OVERLAY_START (overlay));
+  if (! OVERLAY_BUFFER (overlay))
+    return Qnil;
+
+  XSETBUFFER (buffer, OVERLAY_BUFFER (overlay));
+
+  return buffer;
 }
 
 DEFUN ("overlay-properties", Foverlay_properties, Soverlay_properties, 1, 1, 0,
@@ -4145,7 +3557,7 @@ OVERLAY.  */)
 {
   CHECK_OVERLAY (overlay);
 
-  return Fcopy_sequence (XOVERLAY (overlay)->plist);
+  return Fcopy_sequence (OVERLAY_PLIST (overlay));
 }
 
 
@@ -4169,8 +3581,7 @@ If SORTED is non-nil, then sort them by decreasing priority.  */)
 
   /* Put all the overlays we want in a vector in overlay_vec.
      Store the length in len.  */
-  noverlays = overlays_at (XINT (pos), 1, &overlay_vec, &len,
-                           NULL, NULL, 0);
+  noverlays = overlays_at (XINT (pos), 1, &overlay_vec, &len, NULL);
 
   if (!NILP (sorted))
     noverlays = sort_overlays (overlay_vec, noverlays,
@@ -4213,8 +3624,7 @@ end of the buffer.  */)
 
   /* Put all the overlays we want in a vector in overlay_vec.
      Store the length in len.  */
-  noverlays = overlays_in (XINT (beg), XINT (end), 1, &overlay_vec, &len,
-                           NULL, NULL);
+  noverlays = overlays_in (XINT (beg), XINT (end), 1, &overlay_vec, &len, true, NULL);
 
   /* Make a list of them all.  */
   result = Flist (noverlays, overlay_vec);
@@ -4230,39 +3640,12 @@ If there are no overlay boundaries from POS to (point-max),
 the value is (point-max).  */)
   (Lisp_Object pos)
 {
-  ptrdiff_t i, len, noverlays;
-  ptrdiff_t endpos;
-  Lisp_Object *overlay_vec;
-
   CHECK_NUMBER_COERCE_MARKER (pos);
 
   if (!buffer_has_overlays ())
     return make_number (ZV);
 
-  len = 10;
-  overlay_vec = xmalloc (len * sizeof *overlay_vec);
-
-  /* Put all the overlays we want in a vector in overlay_vec.
-     Store the length in len.
-     endpos gets the position where the next overlay starts.  */
-  noverlays = overlays_at (XINT (pos), 1, &overlay_vec, &len,
-                           &endpos, 0, 1);
-
-  /* If any of these overlays ends before endpos,
-     use its ending point instead.  */
-  for (i = 0; i < noverlays; i++)
-    {
-      Lisp_Object oend;
-      ptrdiff_t oendpos;
-
-      oend = OVERLAY_END (overlay_vec[i]);
-      oendpos = OVERLAY_POSITION (oend);
-      if (oendpos < endpos)
-        endpos = oendpos;
-    }
-
-  xfree (overlay_vec);
-  return make_number (endpos);
+  return make_number (next_overlay_change (XINT (pos)));
 }
 
 DEFUN ("previous-overlay-change", Fprevious_overlay_change,
@@ -4272,32 +3655,15 @@ If there are no overlay boundaries from (point-min) to POS,
 the value is (point-min).  */)
   (Lisp_Object pos)
 {
-  ptrdiff_t prevpos;
-  Lisp_Object *overlay_vec;
-  ptrdiff_t len;
 
   CHECK_NUMBER_COERCE_MARKER (pos);
 
   if (!buffer_has_overlays ())
     return make_number (BEGV);
 
-  /* At beginning of buffer, we know the answer;
-     avoid bug subtracting 1 below.  */
-  if (XINT (pos) == BEGV)
-    return pos;
-
-  len = 10;
-  overlay_vec = xmalloc (len * sizeof *overlay_vec);
-
-  /* Put all the overlays we want in a vector in overlay_vec.
-     Store the length in len.
-     prevpos gets the position of the previous change.  */
-  overlays_at (XINT (pos), 1, &overlay_vec, &len,
-               0, &prevpos, 1);
-
-  xfree (overlay_vec);
-  return make_number (prevpos);
+  return make_number (previous_overlay_change (XINT (pos)));
 }
+
 
 /* These functions are for debugging overlays.  */
 
@@ -4307,24 +3673,21 @@ The car has all the overlays before the overlay center;
 the cdr has all the overlays after the overlay center.
 Recentering overlays moves overlays between these lists.
 The lists you get are copies, so that changing them has no effect.
-However, the overlays you get are the real objects that the buffer uses.  */)
+However, the overlays you get are the real objects that the buffer uses. */)
   (void)
 {
-  struct Lisp_Overlay *ol;
-  Lisp_Object before = Qnil, after = Qnil, tmp;
+  Lisp_Object overlays = Qnil;
 
-  for (ol = current_buffer->overlays_before; ol; ol = ol->next)
-    {
-      XSETMISC (tmp, ol);
-      before = Fcons (tmp, before);
-    }
-  for (ol = current_buffer->overlays_after; ol; ol = ol->next)
+  if (current_buffer->overlays)
     {
-      XSETMISC (tmp, ol);
-      after = Fcons (tmp, after);
-    }
+      struct interval_node *node;
 
-  return Fcons (Fnreverse (before), Fnreverse (after));
+      buffer_overlay_iter_start (current_buffer, BEG, Z, ITREE_DESCENDING);
+      while ((node = buffer_overlay_iter_next (current_buffer)))
+        overlays = Fcons (node->data, overlays);
+      buffer_overlay_iter_finish (current_buffer);
+    }
+  return Fcons (overlays, Qnil);
 }
 
 DEFUN ("overlay-recenter", Foverlay_recenter, Soverlay_recenter, 1, 1, 0,
@@ -4333,11 +3696,8 @@ That makes overlay lookup faster for positions near POS (but perhaps slower
 for positions far away from POS).  */)
   (Lisp_Object pos)
 {
-  ptrdiff_t p;
   CHECK_NUMBER_COERCE_MARKER (pos);
-
-  p = clip_to_bounds (PTRDIFF_MIN, XINT (pos), PTRDIFF_MAX);
-  recenter_overlay_lists (current_buffer, p);
+  /* Noop */
   return Qnil;
 }
 
@@ -4354,12 +3714,13 @@ DEFUN ("overlay-put", Foverlay_put, Soverlay_put, 3, 3, 0,
 VALUE will be returned.*/)
   (Lisp_Object overlay, Lisp_Object prop, Lisp_Object value)
 {
-  Lisp_Object tail, buffer;
+  Lisp_Object tail;
+  struct buffer *b;
   bool changed;
 
   CHECK_OVERLAY (overlay);
 
-  buffer = Fmarker_buffer (OVERLAY_START (overlay));
+  b = OVERLAY_BUFFER (overlay);
 
   for (tail = XOVERLAY (overlay)->plist;
        CONSP (tail) && CONSP (XCDR (tail));
@@ -4375,15 +3736,14 @@ VALUE will be returned.*/)
   set_overlay_plist
     (overlay, Fcons (prop, Fcons (value, XOVERLAY (overlay)->plist)));
  found:
-  if (! NILP (buffer))
+  if (b)
     {
       if (changed)
-        modify_overlay (XBUFFER (buffer),
-                        marker_position (OVERLAY_START (overlay)),
-                        marker_position (OVERLAY_END   (overlay)));
+        modify_overlay (b, OVERLAY_START (overlay),
+                        OVERLAY_END (overlay));
       if (EQ (prop, Qevaporate) && ! NILP (value)
-          && (OVERLAY_POSITION (OVERLAY_START (overlay))
-              == OVERLAY_POSITION (OVERLAY_END (overlay))))
+          && (OVERLAY_START (overlay)
+              == OVERLAY_END (overlay)))
         Fdelete_overlay (overlay);
     }
 
@@ -4441,14 +3801,9 @@ void
 report_overlay_modification (Lisp_Object start, Lisp_Object end, bool after,
                              Lisp_Object arg1, Lisp_Object arg2, Lisp_Object arg3)
 {
-  Lisp_Object prop, overlay;
-  struct Lisp_Overlay *tail;
   /* True if this change is an insertion.  */
   bool insertion = (after ? XFASTINT (arg3) == 0 : EQ (start, end));
 
-  overlay = Qnil;
-  tail = NULL;
-
   /* We used to run the functions as soon as we found them and only register
      them in last_overlay_modification_hooks for the purpose of the `after'
      case.  But running elisp code as we traverse the list of overlays is
@@ -4459,68 +3814,35 @@ report_overlay_modification (Lisp_Object start, Lisp_Object end, bool after,
 
   if (!after)
     {
+      struct interval_node *node;
+      EMACS_INT begin_arg = XFASTINT (start);
+      EMACS_INT end_arg = XFASTINT (end);
       /* We are being called before a change.
          Scan the overlays to find the functions to call.  */
       last_overlay_modification_hooks_used = 0;
-      for (tail = current_buffer->overlays_before; tail; tail = tail->next)
-        {
-          ptrdiff_t startpos, endpos;
-          Lisp_Object ostart, oend;
-
-          XSETMISC (overlay, tail);
-
-          ostart = OVERLAY_START (overlay);
-          oend = OVERLAY_END (overlay);
-          endpos = OVERLAY_POSITION (oend);
-          if (XFASTINT (start) > endpos)
-            break;
-          startpos = OVERLAY_POSITION (ostart);
-          if (insertion && (XFASTINT (start) == startpos
-                            || XFASTINT (end) == startpos))
-            {
-              prop = Foverlay_get (overlay, Qinsert_in_front_hooks);
-              if (!NILP (prop))
-                add_overlay_mod_hooklist (prop, overlay);
-            }
-          if (insertion && (XFASTINT (start) == endpos
-                            || XFASTINT (end) == endpos))
-            {
-              prop = Foverlay_get (overlay, Qinsert_behind_hooks);
-              if (!NILP (prop))
-                add_overlay_mod_hooklist (prop, overlay);
-            }
-          /* Test for intersecting intervals.  This does the right thing
-             for both insertion and deletion.  */
-          if (XFASTINT (end) > startpos && XFASTINT (start) < endpos)
-            {
-              prop = Foverlay_get (overlay, Qmodification_hooks);
-              if (!NILP (prop))
-                add_overlay_mod_hooklist (prop, overlay);
-            }
-        }
 
-      for (tail = current_buffer->overlays_after; tail; tail = tail->next)
+      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)))
         {
-          ptrdiff_t startpos, endpos;
-          Lisp_Object ostart, oend;
-
-          XSETMISC (overlay, tail);
-
-          ostart = OVERLAY_START (overlay);
-          oend = OVERLAY_END (overlay);
-          startpos = OVERLAY_POSITION (ostart);
-          endpos = OVERLAY_POSITION (oend);
-          if (XFASTINT (end) < startpos)
-            break;
-          if (insertion && (XFASTINT (start) == startpos
-                            || XFASTINT (end) == startpos))
+          Lisp_Object overlay = node->data;
+          ptrdiff_t obegin = OVERLAY_START (overlay);
+          ptrdiff_t oend = OVERLAY_END (overlay);
+          Lisp_Object prop;
+
+          if (insertion && (begin_arg == obegin
+                            || end_arg == obegin))
             {
               prop = Foverlay_get (overlay, Qinsert_in_front_hooks);
               if (!NILP (prop))
                 add_overlay_mod_hooklist (prop, overlay);
             }
-          if (insertion && (XFASTINT (start) == endpos
-                            || XFASTINT (end) == endpos))
+          if (insertion && (begin_arg == oend
+                            || end_arg == oend))
             {
               prop = Foverlay_get (overlay, Qinsert_behind_hooks);
               if (!NILP (prop))
@@ -4528,15 +3850,15 @@ report_overlay_modification (Lisp_Object start, Lisp_Object end, bool after,
             }
           /* Test for intersecting intervals.  This does the right thing
              for both insertion and deletion.  */
-          if (XFASTINT (end) > startpos && XFASTINT (start) < endpos)
+          if (! insertion || (end_arg > obegin && begin_arg < oend))
             {
               prop = Foverlay_get (overlay, Qmodification_hooks);
               if (!NILP (prop))
                 add_overlay_mod_hooklist (prop, overlay);
             }
         }
+      buffer_overlay_iter_finish (current_buffer);
     }
-
   {
     /* Call the functions recorded in last_overlay_modification_hooks.
        First copy the vector contents, in case some of these hooks
@@ -4558,7 +3880,7 @@ report_overlay_modification (Lisp_Object start, Lisp_Object end, bool after,
            function is never called to record the overlay modification
            hook functions in the last_overlay_modification_hooks
            array, so anything we find there is not ours.  */
-        if (XMARKER (OVERLAY_START (ovl))->buffer != current_buffer)
+        if (OVERLAY_BUFFER (ovl) != current_buffer)
           return;
       }
 
@@ -4598,34 +3920,22 @@ call_overlay_mod_hooks (Lisp_Object list, Lisp_Object overlay, bool after,
 void
 evaporate_overlays (ptrdiff_t pos)
 {
-  Lisp_Object overlay, hit_list;
-  struct Lisp_Overlay *tail;
+  Lisp_Object hit_list;
+  struct interval_node *node;
+
+  if (! current_buffer->overlays)
+    return;
 
   hit_list = Qnil;
-  if (pos <= current_buffer->overlay_center)
-    for (tail = current_buffer->overlays_before; tail; tail = tail->next)
-      {
-        ptrdiff_t endpos;
-        XSETMISC (overlay, tail);
-        endpos = OVERLAY_POSITION (OVERLAY_END (overlay));
-        if (endpos < pos)
-          break;
-        if (endpos == pos && OVERLAY_POSITION (OVERLAY_START (overlay)) == pos
-            && ! NILP (Foverlay_get (overlay, Qevaporate)))
-          hit_list = Fcons (overlay, hit_list);
-      }
-  else
-    for (tail = current_buffer->overlays_after; tail; tail = tail->next)
-      {
-        ptrdiff_t startpos;
-        XSETMISC (overlay, tail);
-        startpos = OVERLAY_POSITION (OVERLAY_START (overlay));
-        if (startpos > pos)
-          break;
-        if (startpos == pos && OVERLAY_POSITION (OVERLAY_END (overlay)) == pos
-            && ! NILP (Foverlay_get (overlay, Qevaporate)))
-          hit_list = Fcons (overlay, hit_list);
-      }
+  buffer_overlay_iter_start (current_buffer, pos, pos, ITREE_ASCENDING);
+
+  while ((node = buffer_overlay_iter_next (current_buffer)))
+    {
+      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));
 }
@@ -5212,9 +4522,7 @@ init_buffer_once (void)
   bset_mark_active (&buffer_defaults, Qnil);
   bset_file_format (&buffer_defaults, Qnil);
   bset_auto_save_file_format (&buffer_defaults, Qt);
-  set_buffer_overlays_before (&buffer_defaults, NULL);
-  set_buffer_overlays_after (&buffer_defaults, NULL);
-  buffer_defaults.overlay_center = BEG;
+  buffer_defaults.overlays = NULL;
 
   XSETFASTINT (BVAR (&buffer_defaults, tab_width), 8);
   bset_truncate_lines (&buffer_defaults, Qnil);
@@ -5434,6 +4742,48 @@ defvar_per_buffer (struct Lisp_Buffer_Objfwd *bo_fwd, const char *namestring,
     emacs_abort ();
 }
 
+#ifdef ITREE_DEBUG
+static Lisp_Object
+make_lispy_interval_node (const struct interval_node *node)
+{
+  return listn (CONSTYPE_HEAP, 12,
+                intern (":begin"),
+                make_number (node->begin),
+                intern (":end"),
+                make_number (node->end),
+                intern (":limit"),
+                make_number (node->limit),
+                intern (":offset"),
+                make_number (node->offset),
+                intern (":rear-advance"),
+                node->rear_advance ? Qt : Qnil,
+                intern (":front-advance"),
+                node->front_advance ? Qt : Qnil);
+}
+
+static Lisp_Object
+overlay_tree (const struct interval_tree *tree,
+              const struct interval_node *node)
+{
+  if (node == &tree->nil)
+    return Qnil;
+  return list3 (make_lispy_interval_node (node),
+                overlay_tree (tree, node->left),
+                overlay_tree (tree, node->right));
+}
+
+DEFUN ("overlay-tree", Foverlay_tree, Soverlay_tree, 0, 1, 0,
+       doc: /* Get the overlay tree for BUFFER.  */)
+     (Lisp_Object buffer)
+{
+  struct buffer *b = decode_buffer (buffer);
+  if (! b->overlays)
+    return Qnil;
+  return overlay_tree (b->overlays, b->overlays->root);
+}
+#endif
+
+
 
 /* Initialize the buffer routines.  */
 void
@@ -6303,6 +5653,10 @@ Functions running this hook are, `get-buffer-create',
   defsubr (&Srestore_buffer_modified_p);
 
   Fput (intern_c_string ("erase-buffer"), Qdisabled, Qt);
+
+#ifdef ITREE_DEBUG
+  defsubr (&Soverlay_tree);
+#endif
 }
 
 void
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 */
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
     {
diff --git a/src/fileio.c b/src/fileio.c
index 11370279d1b..6b22b29aa70 100644
--- a/src/fileio.c
+++ b/src/fileio.c
@@ -3656,8 +3656,7 @@ by calling `format-decode', which see.  */)
                   bset_read_only (buf, Qnil);
                   bset_filename (buf, Qnil);
                   bset_undo_list (buf, Qt);
-                  eassert (buf->overlays_before == NULL);
-                  eassert (buf->overlays_after == NULL);
+                  eassert (buf->overlays == NULL);
 
                   set_buffer_internal (buf);
                   Ferase_buffer ();
diff --git a/src/fns.c b/src/fns.c
index 2311a6e041b..9f411036825 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -2240,10 +2240,9 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
         return false;
       if (OVERLAYP (o1))
         {
-          if (!internal_equal (OVERLAY_START (o1), OVERLAY_START (o2),
-                               equal_kind, depth + 1, ht)
-              || !internal_equal (OVERLAY_END (o1), OVERLAY_END (o2),
-                                  equal_kind, depth + 1, ht))
+          if (OVERLAY_START (o1) != OVERLAY_START (o2)
+              || OVERLAY_END (o1) != OVERLAY_END (o2)
+              || OVERLAY_BUFFER (o1) != OVERLAY_BUFFER (o2))
             return false;
           o1 = XOVERLAY (o1)->plist;
           o2 = XOVERLAY (o2)->plist;
diff --git a/src/indent.c b/src/indent.c
index 26507b5eb5b..8ac7c6ef109 100644
--- a/src/indent.c
+++ b/src/indent.c
@@ -225,9 +225,6 @@ skip_invisible (ptrdiff_t pos, ptrdiff_t *next_boundary_p, ptrdiff_t to, Lisp_Ob
   XSETFASTINT (position, pos);
   XSETBUFFER (buffer, current_buffer);
 
-  /* Give faster response for overlay lookup near POS.  */
-  recenter_overlay_lists (current_buffer, pos);
-
   /* We must not advance farther than the next overlay change.
      The overlay change might change the invisible property;
      or there might be overlay strings to be displayed there.  */
@@ -501,7 +498,7 @@ check_display_width (ptrdiff_t pos, ptrdiff_t col, ptrdiff_t *endpos)
         {
           ptrdiff_t start;
           if (OVERLAYP (overlay))
-            *endpos = OVERLAY_POSITION (OVERLAY_END (overlay));
+            *endpos = OVERLAY_END (overlay);
           else
             get_property_and_range (pos, Qdisplay, &val, &start, endpos, Qnil);
 
diff --git a/src/insdel.c b/src/insdel.c
index 5dfc62843a7..3e9f0c90e34 100644
--- a/src/insdel.c
+++ b/src/insdel.c
@@ -276,7 +276,6 @@ adjust_markers_for_insert (ptrdiff_t from, ptrdiff_t from_byte,
                            ptrdiff_t to, ptrdiff_t to_byte, bool before_markers)
 {
   struct Lisp_Marker *m;
-  bool adjusted = 0;
   ptrdiff_t nchars = to - from;
   ptrdiff_t nbytes = to_byte - from_byte;
 
@@ -292,8 +291,6 @@ adjust_markers_for_insert (ptrdiff_t from, ptrdiff_t from_byte,
             {
               m->bytepos = to_byte;
               m->charpos = to;
-              if (m->insertion_type)
-                adjusted = 1;
             }
         }
       else if (m->bytepos > from_byte)
@@ -302,15 +299,6 @@ adjust_markers_for_insert (ptrdiff_t from, ptrdiff_t from_byte,
           m->charpos += nchars;
         }
     }
-
-  /* Adjusting only markers whose insertion-type is t may result in
-     - disordered start and end in overlays, and
-     - disordered overlays in the slot `overlays_before' of current_buffer.  */
-  if (adjusted)
-    {
-      fix_start_end_in_overlays (from, to);
-      fix_overlays_before (current_buffer, from, to);
-    }
 }
 
 /* Adjust point for an insertion of NBYTES bytes, which are NCHARS characters.
diff --git a/src/intervals.c b/src/intervals.c
index e711212d744..3db80ebed4a 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -1810,8 +1810,8 @@ adjust_for_invis_intang (ptrdiff_t pos, ptrdiff_t test_offs, ptrdiff_t adj,
              == (test_offs == 0 ? 1 : -1))
           /* Invisible property is from an overlay.  */
           : (test_offs == 0
-             ? XMARKER (OVERLAY_START (invis_overlay))->insertion_type == 0
-             : XMARKER (OVERLAY_END (invis_overlay))->insertion_type == 1)))
+             ? ! OVERLAY_FRONT_ADVANCE_P (invis_overlay)
+             : OVERLAY_REAR_ADVANCE_P (invis_overlay))))
     pos += adj;
 
   return pos;
diff --git a/src/itree.c b/src/itree.c
new file mode 100644
index 00000000000..0c10100eef7
--- /dev/null
+++ b/src/itree.c
@@ -0,0 +1,1138 @@
+/* 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/>.  */
+
+#include <config.h>
+#include <math.h>
+#include "lisp.h"
+#include "itree.h"
+
+/*
+   Intervals of the form [BEGIN, END), are stored as nodes inside a RB
+   tree, sorted by BEGIN .  The core operation of this tree (besides
+   insert, remove, etc.) is finding all intervals intersecting with
+   some given interval.  In order to perform this operation
+   efficiently, every node stores a third value called LIMIT. (See
+   https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree and its
+   source Introduction to Algorithms (Section 14.3), Cormen et al. .)
+
+   ==== Finding intervals ====
+
+   If we search for all intervals intersecting with (X, Y], we look at
+   some node and test whether
+
+   NODE.BEGIN > Y
+
+   Due to the invariant of the search tree, we know, that we may
+   safely prune NODE's right subtree if this test succeeds, since all
+   intervals begin strictly after Y.
+
+   But we can not make such an assumptions about the left tree, since
+   all we know is that the intervals in this subtree must start before
+   or at NODE.BEGIN.  So we can't tell, whether they end before X or
+   not.  To solve this problem we add another attribute to each node,
+   called LIMIT.
+
+   The LIMIT of a node is the largest END value occurring in the nodes
+   subtree (including the node itself).  Thus, we may look at the left
+   child of some NODE and test whether
+
+   NODE.left.LIMIT < X
+
+   and this tells us, if all intervals in the left subtree of NODE end
+   before X and if they can be pruned.
+
+   Conversely, if this inequality is false, the left subtree must
+   contain at least one intersecting interval, giving a resulting time
+   complexity of O(K*log(N)) for this operation, where K is the size
+   of the result set and N the size of the tree.
+
+   ==== Adjusting intervals ====
+
+   Since this data-structure will be used for overlays in an Emacs
+   buffer, a second core operation implements the ability to insert or
+   delete gaps in resp. from the tree.  This models the insertion
+   resp. deletion of text in a buffer and the effects it may have on
+   the positions of overlays.
+
+   Consider this: Something gets inserted at position P into a buffer
+   and assume that all overlays occur strictly after P.  Ordinarily,
+   we would have to iterate all overlays and increment their BEGIN and
+   END values accordingly (the insertion of text pushes them back).
+   In order to avoid this, we introduce yet another node attribute,
+   called OFFSET.
+
+   The OFFSET of some some subtree, represented by its root, is the
+   amount of shift that needs to be applied to its BEGIN, END and
+   LIMIT values, in order to get to the real values.  Coming back to
+   the example, all we would need to do in this case, is to increment
+   the OFFSET of the tree's root, without any traversal of the tree
+   itself.
+
+   As a consequence, the real values of BEGIN, END and LIMIT of some
+   NODE need to be computed by incrementing them by the sum of NODE's
+   OFFSET and all of its ancestors offsets.  Therefore, we store a
+   counter (otick) inside every node and also the tree, by which we
+   remember the fact, that a node's path to the root has no offsets
+   applied (i.e. its values are up to date).  This is the case if some
+   node's value differs from the tree's one, the later of which is
+   incremented whenever some node's offset has changed.
+*/
+
+static struct interval_node *interval_tree_validate(struct interval_tree *, struct interval_node *);
+static void interval_generator_ensure_space(struct interval_generator *);
+static bool interval_node_intersects(const struct interval_node *, ptrdiff_t, ptrdiff_t);
+static int interval_tree_max_height(const struct interval_tree *);
+static struct interval_stack *interval_stack_create(intmax_t);
+static void interval_stack_destroy(struct interval_stack *);
+static void interval_stack_clear(struct interval_stack *);
+static void interval_stack_ensure_space(struct interval_stack *, intmax_t);
+static void interval_stack_push(struct interval_stack *, struct interval_node *);
+static void interval_stack_push_flagged(struct interval_stack *, struct interval_node *, bool);
+static struct interval_node *interval_stack_pop(struct interval_stack *);
+static void interval_tree_update_limit(const struct interval_tree *, struct interval_node *);
+static void interval_tree_inherit_offset(const struct interval_tree *, struct interval_node *);
+static void interval_tree_propagate_limit(const struct interval_tree *, struct interval_node *);
+static void interval_tree_rotate_left(struct interval_tree *, struct interval_node *);
+static void interval_tree_rotate_right(struct interval_tree *, struct interval_node *);
+static void interval_tree_insert_fix(struct interval_tree *, struct interval_node *);
+static void interval_tree_remove_fix(struct interval_tree *, struct interval_node *);
+static void interval_tree_transplant(struct interval_tree *, struct interval_node *, struct interval_node *);
+static struct interval_node *interval_tree_subtree_min(const struct interval_tree *, struct interval_node *);
+static struct interval_generator* interval_generator_create (struct interval_tree *);
+static void interval_generator_destroy (struct interval_generator *);
+static void interval_generator_reset (struct interval_generator *,
+                               ptrdiff_t, ptrdiff_t,
+                               enum interval_tree_order);
+static void
+interval_generator_narrow (struct interval_generator *g,
+                             ptrdiff_t begin, ptrdiff_t end);
+static inline struct interval_node*
+interval_generator_next (struct interval_generator *g);
+static inline void interval_tree_iter_ensure_space(struct interval_tree *);
+
+
+
+/* +------------------------------------------------------------------------------------+ */
+
+/* Simple dynamic array. */
+struct interval_stack
+{
+  struct interval_node **nodes;
+  size_t size;
+  size_t length;
+};
+
+/* State used when iterating interval. */
+struct interval_generator
+{
+  struct interval_tree *tree;
+  struct interval_stack *stack;
+  ptrdiff_t begin;
+  ptrdiff_t end;
+  enum interval_tree_order order;
+};
+
+
+
+/* +===================================================================================+
+ * | Tree operations
+ * +===================================================================================+ */
+
+/* Initialize an allocated node. */
+
+void
+interval_node_init (struct interval_node *node,
+                    ptrdiff_t begin, ptrdiff_t end,
+                    bool front_advance, bool rear_advance,
+                    Lisp_Object data)
+{
+  node->begin = begin;
+  node->end = max (begin, end);
+  node->front_advance = front_advance;
+  node->rear_advance = rear_advance;
+  node->data = data;
+}
+
+/* Return NODE's begin value, computing it if necessary. */
+
+ptrdiff_t
+interval_node_begin (struct interval_tree *tree,
+                     struct interval_node *node)
+{
+  interval_tree_validate (tree, node);
+  return node->begin;
+}
+
+/* Return NODE's end value, computing it if necessary. */
+
+ptrdiff_t
+interval_node_end (struct interval_tree *tree,
+                   struct interval_node *node)
+{
+  interval_tree_validate (tree, node);
+  return node->end;
+}
+
+/* Safely modify a node's interval. */
+
+void
+interval_node_set_region (struct interval_tree *tree,
+                          struct interval_node *node,
+                          ptrdiff_t begin, ptrdiff_t end)
+{
+  interval_tree_validate (tree, node);
+  if (begin != node->begin)
+    {
+      interval_tree_remove (tree, node);
+      node->begin = min (begin, PTRDIFF_MAX - 1);
+      node->end = max (node->begin, end);
+      interval_tree_insert (tree, node);
+    }
+  else if (end != node->end)
+    {
+      node->end = max (node->begin, end);
+      interval_tree_propagate_limit (tree, node);
+    }
+}
+
+/* Allocate an interval_tree. Free with interval_tree_destroy. */
+
+struct interval_tree*
+interval_tree_create (void)
+{
+  struct interval_tree *tree = xmalloc (sizeof (*tree));
+  interval_tree_clear (tree);
+  tree->iter = interval_generator_create (tree);
+  return tree;
+}
+
+/* Reset the tree TREE to its empty state. */
+
+void
+interval_tree_clear (struct interval_tree *tree)
+{
+  struct interval_node *nil = &tree->nil;
+  nil->left = nil->right = nil->parent = nil;
+  nil->offset = nil->otick = 0;
+  nil->begin = PTRDIFF_MIN;
+  nil->end = PTRDIFF_MIN;
+  nil->limit = PTRDIFF_MIN;     /* => max(x, nil.limit) = x */
+  nil->color = ITREE_BLACK;
+  tree->root = nil;
+  tree->otick = 1;
+  tree->size = 0;
+  tree->iter_running = 0;
+}
+
+#ifdef ITREE_TESTING
+/* Initialize a pre-allocated tree (presumably on the stack). */
+
+static void
+interval_tree_init (struct interval_tree *tree)
+{
+  interval_tree_clear (tree);
+  tree->iter = interval_generator_create (tree);
+}
+#endif
+
+/* Release a tree, freeing its allocated memory. */
+void
+interval_tree_destroy (struct interval_tree *tree)
+{
+  if (! tree)
+    return;
+  if (tree->iter)
+    interval_generator_destroy (tree->iter);
+  xfree (tree);
+}
+
+/* Return the number of nodes in TREE.  */
+
+intmax_t
+interval_tree_size (struct interval_tree *tree)
+{
+  return tree->size;
+}
+
+/* Insert a NODE into the TREE.
+
+   Note, that inserting a node twice results in undefined behaviour.
+*/
+
+void
+interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
+{
+  eassert (node && node->begin <= node->end && node != &tree->nil);
+
+  struct interval_node *parent = &tree->nil;
+  struct interval_node *child = tree->root;
+  ptrdiff_t offset = 0;
+
+  /* Find the insertion point, accumulate node's offset and update
+     ancestors limit values. */
+  while (child != &tree->nil)
+    {
+      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. */
+      child = node->begin <= child->begin ? child->left : child->right;
+    }
+
+  /* Insert the node */
+  if (parent == &tree->nil)
+    tree->root = node;
+  else if (node->begin <= parent->begin)
+    parent->left = node;
+  else
+    parent->right = node;
+
+  /* Init the node */
+  node->parent = parent;
+  node->left = &tree->nil;
+  node->right = &tree->nil;
+  node->color = ITREE_RED;
+  node->offset = offset;
+  node->limit = node->end;
+  node->otick = tree->otick - 1;
+
+  /* Fix/update the tree */
+  ++tree->size;
+  interval_tree_insert_fix (tree, node);
+  interval_tree_iter_ensure_space (tree);
+}
+
+/* Return true, if NODE is a member of TREE. */
+
+bool
+interval_tree_contains (struct interval_tree *tree, struct interval_node *node)
+{
+  struct interval_node *other;
+
+  interval_tree_iter_start (tree, node->begin, PTRDIFF_MAX, ITREE_ASCENDING);
+  while ((other = interval_tree_iter_next (tree)))
+    if (other == node)
+      break;
+
+  interval_tree_iter_finish (tree);
+  return other == node;
+}
+
+/* Remove NODE from TREE and return it. NODE must exist in TREE.*/
+
+struct interval_node*
+interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
+{
+  eassert (interval_tree_contains (tree, node));
+
+  struct interval_node *broken = NULL;
+
+  interval_tree_inherit_offset (tree, node);
+  if (node->left == &tree->nil || node->right == &tree->nil)
+    {
+      struct interval_node *subst =
+        (node->right == &tree->nil) ? node->left : node->right;
+      if (node->color == ITREE_BLACK)
+        broken = subst;
+      interval_tree_transplant (tree, subst, node);
+      interval_tree_propagate_limit (tree, subst);
+    }
+  else
+    {
+      struct interval_node *min = interval_tree_subtree_min (tree, node->right);
+      struct interval_node *min_right = min->right;
+
+      if (min->color == ITREE_BLACK)
+        broken = min->right;
+      if (min->parent == node)
+        min_right->parent = min; /* set parent, if min_right = nil */
+      else
+        {
+          interval_tree_transplant (tree, min->right, min);
+          min->right = node->right;
+          min->right->parent = min;
+        }
+      interval_tree_inherit_offset (tree, min);
+      interval_tree_transplant (tree, min, node);
+      min->left = node->left;
+      min->left->parent = min;
+      min->color = node->color;
+      interval_tree_propagate_limit (tree, min_right);
+      interval_tree_propagate_limit (tree, min);
+    }
+
+  if (broken)
+    interval_tree_remove_fix (tree, broken);
+
+  node->right = node->left = node->parent = NULL;
+  --tree->size;
+
+  eassert (tree->size == 0 || (tree->size > 0 && tree->root != &tree->nil));
+
+  return node;
+}
+
+static struct interval_node*
+interval_tree_validate (struct interval_tree *tree, struct interval_node *node)
+{
+
+  if (tree->otick == node->otick || node == &tree->nil)
+    return node;
+  if (node != tree->root)
+    interval_tree_validate (tree, node->parent);
+
+  interval_tree_inherit_offset (tree, node);
+  return node;
+}
+
+/* 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
+interval_tree_iter_start (struct interval_tree *tree,
+                          ptrdiff_t begin, ptrdiff_t end,
+                          enum interval_tree_order order)
+{
+  if (tree->iter_running)
+    emacs_abort ();
+  interval_generator_reset (tree->iter, begin, end, order);
+  tree->iter_running = 1;
+}
+
+/* Limit the search interval of the iterator to the given values.  The
+   interval can only shrink, but never grow.*/
+
+inline void
+interval_tree_iter_narrow(struct interval_tree *tree,
+                               ptrdiff_t begin, ptrdiff_t end)
+{
+  if (! tree->iter_running)
+    emacs_abort ();
+  interval_generator_narrow (tree->iter, begin, end);
+}
+
+/* Stop using the iterator. */
+
+void
+interval_tree_iter_finish (struct interval_tree *tree)
+{
+  if (! tree->iter_running)
+    emacs_abort ();
+  tree->iter_running = 0;
+}
+
+/* Return the next node of the iterator in the order given when it was
+   started; or NULL if there are no more nodes. */
+
+inline struct interval_node*
+interval_tree_iter_next (struct interval_tree *tree)
+{
+  if (! tree->iter_running)
+    emacs_abort ();
+  return interval_generator_next (tree->iter);
+}
+
+/* Ensure that the tree's iterator does not need to allocate space
+   until the tree grows in size. */
+
+static inline void
+interval_tree_iter_ensure_space (struct interval_tree *tree)
+{
+  interval_generator_ensure_space (tree->iter);
+}
+
+static int
+interval_tree_max_height (const struct interval_tree *tree)
+{
+  return 2 * log (tree->size + 1) / log (2) + 0.5;
+}
+
+
+/* +===================================================================================+
+ * | Insert/Delete Gaps
+ * +===================================================================================+ */
+
+/* Insert a gap at POS of length LENGTH expanding all intervals
+   intersecting it, while respecting their rear_advance and
+   front_advance setting. */
+
+void
+interval_tree_insert_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t length)
+{
+  if (length <= 0 || tree->size == 0)
+    return;
+
+  /* FIXME: Don't allocate generator/stack anew every time. */
+
+  /* Nodes with front_advance starting at pos may mess up the tree
+     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);
+  while ((node = interval_tree_iter_next (tree)))
+    {
+      if (node->begin == pos && node->front_advance
+          && (node->begin != node->end || node->rear_advance))
+        interval_stack_push (saved, node);
+    }
+  interval_tree_iter_finish (tree);
+  for (int i = 0; i < saved->length; ++i)
+    interval_tree_remove (tree, saved->nodes[i]);
+
+
+  /* We can't use a generator here, because we can't effectively
+     narrow AND shift some subtree at the same time. */
+  const int size = interval_tree_max_height (tree) + 1;
+  struct interval_stack *stack = interval_stack_create (size);
+  interval_stack_push (stack, tree->root);
+  while ((node = interval_stack_pop (stack)))
+    {
+      /* Process in pre-order. */
+      interval_tree_inherit_offset (tree, node);
+      if (node->right != &tree->nil)
+        {
+          if (node->begin > pos)
+            {
+              /* All nodes in this subtree are shifted by length. */
+              node->right->offset += length;
+              ++tree->otick;
+            }
+          else
+            interval_stack_push (stack, node->right);
+        }
+      if (node->left != &tree->nil && pos <= node->left->limit)
+        interval_stack_push (stack, node->left);
+
+      /* node->begin == pos implies no front-advance. */
+      if (node->begin > pos)
+        node->begin += length;
+      if (node->end > pos || (node->end == pos && node->rear_advance))
+        {
+          node->end += length;
+          interval_tree_propagate_limit (tree, node);
+        }
+    }
+  interval_stack_destroy (stack);
+
+  /* Reinsert nodes starting at POS having front-advance. */
+  while ((node = interval_stack_pop (saved)))
+    {
+      node->begin += length;
+      if (node->end != pos || node->rear_advance)
+        node->end += length;
+      interval_tree_insert (tree, node);
+    }
+
+  interval_stack_destroy (saved);
+}
+
+/* Delete a gap at POS of length LENGTH, contracting all intervals
+   intersecting it. */
+
+void
+interval_tree_delete_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t length)
+{
+  if (length <= 0 || tree->size == 0)
+    return;
+
+  /* FIXME: Don't allocate stack anew every time. */
+
+  /* Can't use the generator here, because by decrementing begin, we
+     might unintentionally bring shifted nodes back into our search
+     space. */
+  const int size = interval_tree_max_height (tree) + 1;
+  struct interval_stack *stack = interval_stack_create (size);
+  struct interval_node *node;
+
+  interval_stack_push (stack, tree->root);
+  while ((node = interval_stack_pop (stack)))
+    {
+      interval_tree_inherit_offset (tree, node);
+      if (node->right != &tree->nil)
+        {
+          if (node->begin > pos + length)
+            {
+              /* Shift right subtree to the left. */
+              node->right->offset -= length;
+              ++tree->otick;
+            }
+          else
+            interval_stack_push (stack, node->right);
+        }
+      if (node->left != &tree->nil && pos <= node->left->limit)
+        interval_stack_push (stack, node->left);
+
+      if (pos < node->begin)
+        node->begin = max (pos, node->begin - length);
+      if (node->end > pos)
+        {
+          node->end = max (pos , node->end - length);
+          interval_tree_propagate_limit (tree, node);
+        }
+    }
+  interval_stack_destroy (stack);
+}
+
+
+
+/* +===================================================================================+
+ * | Generator
+ * +===================================================================================+ */
+
+/* Allocate a new generator for TREE. */
+
+static struct interval_generator*
+interval_generator_create  (struct interval_tree *tree)
+{
+  struct interval_generator *g = xmalloc (sizeof *g);
+  const int size = interval_tree_max_height (tree) + 1;
+
+  g->stack = interval_stack_create (size);
+  g->tree = tree;
+  interval_generator_reset (g, 1, 0, 0);
+  return g;
+}
+
+/* Reset generator G such that it iterates over intervals intersecting
+   with [BEGIN, END) in the given ORDER. */
+
+void
+interval_generator_reset (struct interval_generator *g,
+                          ptrdiff_t begin, ptrdiff_t end,
+                          enum interval_tree_order order)
+{
+  if (! g) return;
+
+  g->begin = begin;
+  g->end = end;
+  g->order = order;
+  interval_stack_clear (g->stack);
+  if (begin <= end  && g->tree->size > 0)
+    interval_stack_push_flagged (g->stack, g->tree->root, false);
+}
+
+/* Allocate enough space for the tree of G in its current shape. */
+
+static inline void
+interval_generator_ensure_space (struct interval_generator *g)
+{
+  interval_stack_ensure_space (g->stack, interval_tree_max_height (g->tree) + 1);
+}
+
+/* Return true, if NODE's interval intersects with [BEGIN, END). */
+
+static inline bool
+interval_node_intersects (const struct interval_node *node,
+                          ptrdiff_t begin, ptrdiff_t end)
+{
+  return (begin < node->end && node->begin < end)
+    || (node->begin == node->end && begin == node->begin);
+}
+
+/* Return the next node of G, or NULL if there is none. */
+
+inline struct interval_node*
+interval_generator_next (struct interval_generator *g)
+{
+  if (! g) return NULL;
+
+  struct interval_node * const nil = &g->tree->nil;
+  struct interval_node *node;
+
+  do {
+    node = interval_stack_pop (g->stack);
+
+    while (node && ! node->visited)
+      {
+        struct interval_node * const left = node->left;
+        struct interval_node * const right = node->right;
+
+        interval_tree_inherit_offset (g->tree, node);
+        switch (g->order)
+          {
+          case ITREE_ASCENDING:
+            if (right != nil && node->begin <= g->end)
+              interval_stack_push_flagged (g->stack, right, false);
+            if (interval_node_intersects (node, g->begin, g->end))
+              interval_stack_push_flagged (g->stack, node, true);
+            /* Node's children may still be off-set and we need to add it. */
+            if (left != nil && g->begin <= left->limit + left->offset)
+              interval_stack_push_flagged (g->stack, left, false);
+            break;
+          case ITREE_DESCENDING:
+            if (left != nil && g->begin <= left->limit + left->offset)
+              interval_stack_push_flagged (g->stack, left, false);
+            if (interval_node_intersects (node, g->begin, g->end))
+              interval_stack_push_flagged (g->stack, node, true);
+            if (right != nil && node->begin <= g->end)
+              interval_stack_push_flagged (g->stack, right, false);
+            break;
+          case ITREE_PRE_ORDER:
+            if (right != nil && node->begin <= g->end)
+              interval_stack_push_flagged (g->stack, right, false);
+            if (left != nil && g->begin <= left->limit + left->offset)
+              interval_stack_push_flagged (g->stack, left, false);
+            if (interval_node_intersects (node, g->begin, g->end))
+              interval_stack_push_flagged (g->stack, node, true);
+            break;
+          }
+        node = interval_stack_pop (g->stack);
+      }
+    /* Node may have been invalidated by interval_generator_narrow
+       after it was pushed: Check if it still intersects. */
+  } while (node && ! interval_node_intersects (node, g->begin, g->end));
+
+  return node;
+}
+
+/* Limit G to the new interval [BEGIN, END), which must be a subset of
+   the current one.  I.E. it can't grow on either side. */
+
+static inline void
+interval_generator_narrow (struct interval_generator *g,
+                           ptrdiff_t begin, ptrdiff_t end)
+{
+  g->begin =  max (begin, g->begin);
+  g->end =  min (end, g->end);
+}
+
+/* Free the memory allocated for G. */
+
+void
+interval_generator_destroy (struct interval_generator *g)
+{
+  if (! g) return;
+  if (g->stack)
+    interval_stack_destroy (g->stack);
+  xfree (g);
+}
+
+
+/* +===================================================================================+
+ * | Stack
+ * +===================================================================================+ */
+
+/* This is just a simple dynamic array with stack semantics. */
+
+static struct interval_stack*
+interval_stack_create (intmax_t initial_size)
+{
+  struct interval_stack *stack = xmalloc (sizeof (struct interval_stack));
+  stack->size = max (0, initial_size);
+  stack->nodes = xmalloc (stack->size * sizeof (struct interval_node*));
+  stack->length = 0;
+  return stack;
+}
+
+static void
+interval_stack_destroy (struct interval_stack *stack)
+{
+  if (! stack)
+    return;
+  if (stack->nodes)
+    xfree (stack->nodes);
+  xfree (stack);
+}
+
+static void
+interval_stack_clear (struct interval_stack *stack)
+{
+  stack->length = 0;
+}
+
+static inline void
+interval_stack_ensure_space (struct interval_stack *stack, intmax_t nelements)
+{
+  if (nelements > stack->size)
+    {
+      stack->size = (nelements + 1) * 2;
+      stack->nodes = xrealloc (stack->nodes, stack->size * sizeof (*stack->nodes));
+    }
+}
+
+static inline void
+interval_stack_push (struct interval_stack *stack, struct interval_node *node)
+{
+  interval_stack_ensure_space (stack, stack->length + 1);
+  stack->nodes[stack->length] = node;
+  stack->length++;
+}
+
+/* Push NODE on the STACK, while settings its visited flag to FLAG. */
+
+static inline void
+interval_stack_push_flagged (struct interval_stack *stack,
+                             struct interval_node *node, bool flag)
+{
+  interval_stack_push (stack, node);
+  node->visited = flag;
+}
+
+static inline struct interval_node*
+interval_stack_pop (struct interval_stack *stack)
+{
+  if (stack->length == 0)
+    return NULL;
+  return stack->nodes[--stack->length];
+}
+
+
+/* +===================================================================================+
+ * | Internal Functions
+ * +===================================================================================+ */
+
+/* Update NODE's limit attribute according to its children. */
+
+static void
+interval_tree_update_limit (const struct interval_tree *tree,
+                            struct interval_node *node)
+{
+  if (node == &tree->nil)
+    return;
+
+  node->limit = max (node->end, max (node->left->limit + node->left->offset,
+                                     node->right->limit + node->right->offset));
+}
+
+/* Apply NODE's offset to its begin, end and limit values and
+   propagate it to its children.
+
+   Does nothing, if NODE is clean, i.e. NODE.otick = tree.otick .
+*/
+
+static void
+interval_tree_inherit_offset (const struct interval_tree *tree,
+                              struct interval_node *node)
+{
+
+  if (node->otick == tree->otick)
+    return;
+
+  node->begin += node->offset;
+  node->end += node->offset;
+  node->limit += node->offset;
+  if (node->left != &tree->nil)
+    node->left->offset += node->offset;
+  if (node->right != &tree->nil)
+    node->right->offset += node->offset;
+  node->offset = 0;
+  if (node == tree->root || node->parent->otick == tree->otick)
+    node->otick = tree->otick;
+}
+
+/* Update limit of NODE and its ancestors.  Stop when it becomes
+   stable, i.e. new_limit = old_limit.
+
+   NODE may also be the nil node, in which case its parent is
+   used. (This feature is due to the RB algorithm.)
+*/
+
+static void
+interval_tree_propagate_limit (const struct interval_tree *tree,
+                               struct interval_node *node)
+{
+  if (node == &tree->nil)
+    node = node->parent;
+  if (node == &tree->nil)
+    return;
+
+  while (1) {
+    ptrdiff_t newlimit = max (node->end, max (node->left->limit + node->left->offset,
+                                              node->right->limit + node->right->offset));
+    if (newlimit == node->limit)
+      break;
+    node->limit = newlimit;
+    if (node == tree->root)
+      break;
+    node = node->parent;
+  }
+}
+
+/* Perform the familiar left-rotation on node NODE. */
+
+static void
+interval_tree_rotate_left (struct interval_tree *tree, struct interval_node *node)
+{
+  eassert (node->right != &tree->nil);
+
+  struct interval_node *right = node->right;
+
+  interval_tree_inherit_offset (tree, node);
+  interval_tree_inherit_offset (tree, right);
+
+  /* Turn right's left subtree into node's right subtree.  */
+  node->right = right->left;
+  if (right->left != &tree->nil)
+    right->left->parent = node;
+
+  /* right's parent was node's parent.  */
+  if (right != &tree->nil)
+    right->parent = node->parent;
+
+  /* Get the parent to point to right instead of node.  */
+  if (node != tree->root)
+    {
+      if (node == node->parent->left)
+        node->parent->left = right;
+      else
+        node->parent->right = right;
+    }
+  else
+    tree->root = right;
+
+  /* Put node on right's left.  */
+  right->left = node;
+  if (node != &tree->nil)
+    node->parent = right;
+
+  /* Order matters here. */
+  interval_tree_update_limit (tree, node);
+  interval_tree_update_limit (tree, right);
+}
+
+/* Perform the familiar right-rotation on node NODE. */
+
+static void
+interval_tree_rotate_right (struct interval_tree *tree, struct interval_node *node)
+{
+  eassert (tree && node && node->left != &tree->nil);
+
+  struct interval_node *left = node->left;
+
+  interval_tree_inherit_offset (tree, node);
+  interval_tree_inherit_offset (tree, left);
+
+  node->left = left->right;
+  if (left->right != &tree->nil)
+    left->right->parent = node;
+
+  if (left != &tree->nil)
+    left->parent = node->parent;
+  if (node != tree->root)
+    {
+      if (node == node->parent->right)
+        node->parent->right = left;
+      else
+        node->parent->left = left;
+    }
+  else
+    tree->root = left;
+
+  left->right = node;
+  if (node != &tree->nil)
+    node->parent = left;
+
+  interval_tree_update_limit (tree, left);
+  interval_tree_update_limit (tree, node);
+}
+
+/* Repair the tree after an insertion.  Part of the RB-Tree
+   algorithm. */
+
+static void
+interval_tree_insert_fix (struct interval_tree *tree, struct interval_node *node)
+{
+  while (node->parent->color == ITREE_RED)
+    {
+      /* NODE is red and its parent is red.  This is a violation of
+         red-black tree property #3.  */
+
+      if (node->parent == node->parent->parent->left)
+        {
+          /* We're on the left side of our grandparent, and OTHER is
+             our "uncle".  */
+          struct interval_node *uncle = node->parent->parent->right;
+
+          if (uncle->color == ITREE_RED) /* case 1.a */
+            {
+              /* Uncle and parent are red but should be black because
+                 NODE is red.  Change the colors accordingly and
+                 proceed with the grandparent.  */
+              node->parent->color = ITREE_BLACK;
+              uncle->color = ITREE_BLACK;
+              node->parent->parent->color = ITREE_RED;
+              node = node->parent->parent;
+            }
+          else
+            {
+              /* Parent and uncle have different colors; parent is
+                 red, uncle is black.  */
+              if (node == node->parent->right) /* case 2.a */
+                {
+                  node = node->parent;
+                  interval_tree_rotate_left (tree, node);
+                }
+              /* case 3.a */
+              node->parent->color = ITREE_BLACK;
+              node->parent->parent->color = ITREE_RED;
+              interval_tree_rotate_right (tree, node->parent->parent);
+            }
+        }
+      else
+        {
+          /* This is the symmetrical case of above.  */
+          struct interval_node *uncle = node->parent->parent->left;
+
+          if (uncle->color == ITREE_RED) /* case 1.b */
+            {
+              node->parent->color = ITREE_BLACK;
+              uncle->color = ITREE_BLACK;
+              node->parent->parent->color = ITREE_RED;
+              node = node->parent->parent;
+            }
+          else
+            {
+              if (node == node->parent->left) /* case 2.b */
+                {
+                  node = node->parent;
+                  interval_tree_rotate_right (tree, node);
+                }
+              /* case 3.b */
+              node->parent->color = ITREE_BLACK;
+              node->parent->parent->color = ITREE_RED;
+              interval_tree_rotate_left (tree, node->parent->parent);
+            }
+        }
+    }
+
+  /* The root may have been changed to red due to the algorithm.  Set
+     it to black so that property #5 is satisfied.  */
+  tree->root->color = ITREE_BLACK;
+}
+
+/* Repair the tree after a deletion.  Part of the RB-Tree
+   algorithm. */
+
+static void
+interval_tree_remove_fix (struct interval_tree *tree, struct interval_node *node)
+{
+  while (node != tree->root && node->color == ITREE_BLACK)
+    {
+      if (node == node->parent->left)
+        {
+          struct interval_node *other = node->parent->right;
+
+          if (other->color == ITREE_RED) /* case 1.a */
+            {
+              other->color = ITREE_BLACK;
+              node->parent->color = ITREE_RED;
+              interval_tree_rotate_left (tree, node->parent);
+              other = node->parent->right;
+            }
+
+          if (other->left->color == ITREE_BLACK /* 2.a */
+              && other->right->color == ITREE_BLACK)
+            {
+              other->color = ITREE_RED;
+              node = node->parent;
+            }
+          else
+            {
+              if (other->right->color == ITREE_BLACK) /* 3.a */
+                {
+                  other->left->color = ITREE_BLACK;
+                  other->color = ITREE_RED;
+                  interval_tree_rotate_right (tree, other);
+                  other = node->parent->right;
+                }
+              other->color = node->parent->color; /* 4.a */
+              node->parent->color = ITREE_BLACK;
+              other->right->color = ITREE_BLACK;
+              interval_tree_rotate_left (tree, node->parent);
+              node = tree->root;
+            }
+        }
+      else
+        {
+          struct interval_node *other = node->parent->left;
+
+          if (other->color == ITREE_RED) /* 1.b */
+            {
+              other->color = ITREE_BLACK;
+              node->parent->color = ITREE_RED;
+              interval_tree_rotate_right (tree, node->parent);
+              other = node->parent->left;
+            }
+
+          if (other->right->color == ITREE_BLACK /* 2.b */
+              && other->left->color == ITREE_BLACK)
+            {
+              other->color = ITREE_RED;
+              node = node->parent;
+            }
+          else
+            {
+              if (other->left->color == ITREE_BLACK) /* 3.b */
+                {
+                  other->right->color = ITREE_BLACK;
+                  other->color = ITREE_RED;
+                  interval_tree_rotate_left (tree, other);
+                  other = node->parent->left;
+                }
+
+              other->color = node->parent->color; /* 4.b */
+              node->parent->color = ITREE_BLACK;
+              other->left->color = ITREE_BLACK;
+              interval_tree_rotate_right (tree, node->parent);
+              node = tree->root;
+            }
+        }
+    }
+
+  node->color = ITREE_BLACK;
+}
+
+/* Link node SOURCE in DEST's place. */
+
+static void
+interval_tree_transplant (struct interval_tree *tree, struct interval_node *source,
+                          struct interval_node *dest)
+{
+  eassert (tree && source && dest && dest != &tree->nil);
+
+  if (dest == tree->root)
+    tree->root = source;
+  else if (dest == dest->parent->left)
+    dest->parent->left = source;
+  else
+    dest->parent->right = source;
+
+  source->parent = dest->parent;
+}
+
+
+static struct interval_node*
+interval_tree_subtree_min (const struct interval_tree *tree, struct interval_node *node)
+{
+  if (node == &tree->nil)
+    return node;
+  while (node->left != &tree->nil)
+    node = node->left;
+  return node;
+}
+
+
+/* +===================================================================================+
+ * | Debugging
+ * +===================================================================================+ */
+
+/* See Foverlay_tree in buffer.c */
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
diff --git a/src/keyboard.c b/src/keyboard.c
index e8701b88708..60cdaba9f0b 100644
--- a/src/keyboard.c
+++ b/src/keyboard.c
@@ -1668,8 +1668,8 @@ adjust_point_for_property (ptrdiff_t last_pt, bool modified)
           && display_prop_intangible_p (val, overlay, PT, PT_BYTE)
           && (!OVERLAYP (overlay)
               ? get_property_and_range (PT, Qdisplay, &val, &beg, &end, Qnil)
-              : (beg = OVERLAY_POSITION (OVERLAY_START (overlay)),
-                 end = OVERLAY_POSITION (OVERLAY_END (overlay))))
+              : (beg = OVERLAY_START (overlay),
+                 end = OVERLAY_END (overlay)))
           && (beg < PT /* && end > PT   <- It's always the case.  */
               || (beg <= PT && STRINGP (val) && SCHARS (val) == 0)))
         {
diff --git a/src/lisp.h b/src/lisp.h
index 680c25d4c49..222a99950a8 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -2217,15 +2217,14 @@ struct Lisp_Overlay
    - next fields of start and end markers (singly linked list of markers).
    I.e. 9words plus 2 bits, 3words of which are for external linked lists.
 */
-  {
-    ENUM_BF (Lisp_Misc_Type) type : 16; /* = Lisp_Misc_Overlay */
-    bool_bf gcmarkbit : 1;
-    unsigned spacer : 15;
-    struct Lisp_Overlay *next;
-    Lisp_Object start;
-    Lisp_Object end;
-    Lisp_Object plist;
-  };
+{
+  ENUM_BF (Lisp_Misc_Type) type : 16;   /* = Lisp_Misc_Overlay */
+  bool_bf gcmarkbit : 1;
+  unsigned spacer : 15;
+  Lisp_Object plist;
+  struct buffer *buffer;        /* eassert (live buffer || NULL). */
+  struct interval_node *interval;
+};
 
 /* Number of bits needed to store one of the values
    SAVE_UNUSED..SAVE_OBJECT.  */
@@ -3704,7 +3703,7 @@ extern Lisp_Object make_save_funcptr_ptr_obj (void (*) (void), void *,
                                               Lisp_Object);
 extern Lisp_Object make_save_memory (Lisp_Object *, ptrdiff_t);
 extern void free_save_value (Lisp_Object);
-extern Lisp_Object build_overlay (Lisp_Object, Lisp_Object, Lisp_Object);
+extern Lisp_Object build_overlay (ptrdiff_t, ptrdiff_t, bool, bool, Lisp_Object);
 extern void free_marker (Lisp_Object);
 extern void free_cons (struct Lisp_Cons *);
 extern void init_alloc_once (void);
diff --git a/src/print.c b/src/print.c
index f280616af8a..a07baa3067a 100644
--- a/src/print.c
+++ b/src/print.c
@@ -548,8 +548,7 @@ temp_output_buffer_setup (const char *bufname)
   bset_read_only (current_buffer, Qnil);
   bset_filename (current_buffer, Qnil);
   bset_undo_list (current_buffer, Qt);
-  eassert (current_buffer->overlays_before == NULL);
-  eassert (current_buffer->overlays_after == NULL);
+  eassert (current_buffer->overlays == NULL);
   bset_enable_multibyte_characters
     (current_buffer, BVAR (&buffer_defaults, enable_multibyte_characters));
   specbind (Qinhibit_read_only, Qt);
@@ -2074,7 +2073,7 @@ print_object (Lisp_Object obj, Lisp_Object printcharfun, bool escapeflag)
               obj = XCDR (obj);
               if (!(i & 1))
                 halftail = XCDR (halftail);
-          }
+            }
 
           /* OBJ non-nil here means it's the end of a dotted list.  */
           if (!NILP (obj))
@@ -2114,15 +2113,14 @@ print_object (Lisp_Object obj, Lisp_Object printcharfun, bool escapeflag)
 
         case Lisp_Misc_Overlay:
           print_c_string ("#<overlay ", printcharfun);
-          if (! XMARKER (OVERLAY_START (obj))->buffer)
+          if (! OVERLAY_BUFFER (obj))
             print_c_string ("in no buffer", printcharfun);
           else
             {
               int len = sprintf (buf, "from %"pD"d to %"pD"d in ",
-                                 marker_position (OVERLAY_START (obj)),
-                                 marker_position (OVERLAY_END   (obj)));
+                                 OVERLAY_START (obj), OVERLAY_END (obj));
               strout (buf, len, len, printcharfun);
-              print_string (BVAR (XMARKER (OVERLAY_START (obj))->buffer, name),
+              print_string (BVAR (OVERLAY_BUFFER (obj), name),
                             printcharfun);
             }
           printchar ('>', printcharfun);
diff --git a/src/textprop.c b/src/textprop.c
index 513780c3009..aebb6524e68 100644
--- a/src/textprop.c
+++ b/src/textprop.c
@@ -617,36 +617,42 @@ get_char_property_and_overlay (Lisp_Object position, register Lisp_Object prop,
     }
   if (BUFFERP (object))
     {
-      ptrdiff_t noverlays;
-      Lisp_Object *overlay_vec;
-      struct buffer *obuf = current_buffer;
+      struct buffer *b = XBUFFER (object);
+      struct interval_node *node;
+      struct sortvec items[2];
+      struct sortvec *result = NULL;
+      Lisp_Object result_tem = Qnil;
 
-      if (XINT (position) < BUF_BEGV (XBUFFER (object))
-          || XINT (position) > BUF_ZV (XBUFFER (object)))
+      if (XINT (position) < BUF_BEGV (b) || XINT (position) > BUF_ZV (b))
         xsignal1 (Qargs_out_of_range, position);
 
-      set_buffer_temp (XBUFFER (object));
-
-      USE_SAFE_ALLOCA;
-      GET_OVERLAYS_AT (XINT (position), overlay_vec, noverlays, NULL, false);
-      noverlays = sort_overlays (overlay_vec, noverlays, w);
-
-      set_buffer_temp (obuf);
+      buffer_overlay_iter_start(b, XINT (position), XINT (position) + 1,
+                                ITREE_ASCENDING);
 
       /* Now check the overlays in order of decreasing priority.  */
-      while (--noverlays >= 0)
+      while ((node = buffer_overlay_iter_next (b)))
         {
-          Lisp_Object tem = Foverlay_get (overlay_vec[noverlays], prop);
-          if (!NILP (tem))
-            {
-              if (overlay)
-                /* Return the overlay we got the property from.  */
-                *overlay = overlay_vec[noverlays];
-              SAFE_FREE ();
-              return tem;
-            }
+          Lisp_Object tem = Foverlay_get (node->data, prop);
+          struct sortvec *this;
+
+          if (NILP (tem) || (w && ! overlay_matches_window (w, node->data)))
+            continue;
+
+          this = (result == items ? items + 1 : items);
+          make_sortvec_item (this, node->data);
+          if (! result || (compare_overlays (result, this) < 0))
+            {
+              result = this;
+              result_tem = tem;
+            }
         }
-      SAFE_FREE ();
+      buffer_overlay_iter_finish (b);
+      if (result)
+        {
+          if (overlay)
+            *overlay = result->overlay;
+          return result_tem;
+        }
     }
 
   if (overlay)
diff --git a/src/window.h b/src/window.h
index df7c23f824b..324d30b57f9 100644
--- a/src/window.h
+++ b/src/window.h
@@ -1128,6 +1128,16 @@ output_cursor_to (struct window *w, int vpos, int hpos, int y, int x)
   w->output_cursor.y = y;
 }
 
+/* Return true, if overlay OV's properties should have an effect in
+   window W. */
+INLINE bool
+overlay_matches_window (const struct window *w, Lisp_Object ov)
+{
+  eassert (OVERLAYP (ov));
+  Lisp_Object  window = Foverlay_get (ov, Qwindow);
+  return (! WINDOWP (window) || XWINDOW (window) == w);
+}
+
 INLINE_HEADER_END
 
 #endif /* not WINDOW_H_INCLUDED */
diff --git a/src/xdisp.c b/src/xdisp.c
index 86164eb9f6f..b3b9ecae377 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -873,7 +873,6 @@ static enum move_it_result
 static void get_visually_first_element (struct it *);
 static void compute_stop_pos (struct it *);
 static int face_before_or_after_it_pos (struct it *, bool);
-static ptrdiff_t next_overlay_change (ptrdiff_t);
 static int handle_display_spec (struct it *, Lisp_Object, Lisp_Object,
                                 Lisp_Object, struct text_pos *, ptrdiff_t, bool);
 static int handle_single_display_spec (struct it *, Lisp_Object, Lisp_Object,
@@ -3606,39 +3605,6 @@ compute_stop_pos (struct it *it)
                && it->stop_charpos >= IT_CHARPOS (*it)));
 }
 
-
-/* Return the position of the next overlay change after POS in
-   current_buffer.  Value is point-max if no overlay change
-   follows.  This is like `next-overlay-change' but doesn't use
-   xmalloc.  */
-
-static ptrdiff_t
-next_overlay_change (ptrdiff_t pos)
-{
-  ptrdiff_t i, noverlays;
-  ptrdiff_t endpos;
-  Lisp_Object *overlays;
-  USE_SAFE_ALLOCA;
-
-  /* Get all overlays at the given position.  */
-  GET_OVERLAYS_AT (pos, overlays, noverlays, &endpos, true);
-
-  /* If any of these overlays ends before endpos,
-     use its ending point instead.  */
-  for (i = 0; i < noverlays; ++i)
-    {
-      Lisp_Object oend;
-      ptrdiff_t oendpos;
-
-      oend = OVERLAY_END (overlays[i]);
-      oendpos = OVERLAY_POSITION (oend);
-      endpos = min (endpos, oendpos);
-    }
-
-  SAFE_FREE ();
-  return endpos;
-}
-
 /* How many characters forward to search for a display property or
    display string.  Searching too far forward makes the bidi display
    sluggish, especially in small windows.  */
@@ -5071,7 +5037,7 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
          overlay's display string/image twice.  */
       if (!NILP (overlay))
         {
-          ptrdiff_t ovendpos = OVERLAY_POSITION (OVERLAY_END (overlay));
+          ptrdiff_t ovendpos = OVERLAY_END (overlay);
 
           /* Some borderline-sane Lisp might call us with the current
              buffer narrowed so that overlay-end is outside the
@@ -5785,13 +5751,14 @@ static void
 load_overlay_strings (struct it *it, ptrdiff_t charpos)
 {
   Lisp_Object overlay, window, str, invisible;
-  struct Lisp_Overlay *ov;
   ptrdiff_t start, end;
   ptrdiff_t n = 0, i, j;
   int invis;
   struct overlay_entry entriesbuf[20];
   ptrdiff_t size = ARRAYELTS (entriesbuf);
   struct overlay_entry *entries = entriesbuf;
+  struct interval_node *node;
+
   USE_SAFE_ALLOCA;
 
   if (charpos <= 0)
@@ -5823,83 +5790,47 @@ load_overlay_strings (struct it *it, ptrdiff_t charpos)
     }                                                                   \
   while (false)
 
-  /* Process overlay before the overlay center.  */
-  for (ov = current_buffer->overlays_before; ov; ov = ov->next)
+  if (current_buffer->overlays)
     {
-      XSETMISC (overlay, ov);
-      eassert (OVERLAYP (overlay));
-      start = OVERLAY_POSITION (OVERLAY_START (overlay));
-      end = OVERLAY_POSITION (OVERLAY_END (overlay));
-
-      if (end < charpos)
-        break;
-
-      /* Skip this overlay if it doesn't start or end at IT's current
-         position.  */
-      if (end != charpos && start != charpos)
-        continue;
-
-      /* Skip this overlay if it doesn't apply to IT->w.  */
-      window = Foverlay_get (overlay, Qwindow);
-      if (WINDOWP (window) && XWINDOW (window) != it->w)
-        continue;
-
-      /* If the text ``under'' the overlay is invisible, both before-
-         and after-strings from this overlay are visible; start and
-         end position are indistinguishable.  */
-      invisible = Foverlay_get (overlay, Qinvisible);
-      invis = TEXT_PROP_MEANS_INVISIBLE (invisible);
-
-      /* If overlay has a non-empty before-string, record it.  */
-      if ((start == charpos || (end == charpos && invis != 0))
-          && (str = Foverlay_get (overlay, Qbefore_string), STRINGP (str))
-          && SCHARS (str))
-        RECORD_OVERLAY_STRING (overlay, str, false);
-
-      /* If overlay has a non-empty after-string, record it.  */
-      if ((end == charpos || (start == charpos && invis != 0))
-          && (str = Foverlay_get (overlay, Qafter_string), STRINGP (str))
-          && SCHARS (str))
-        RECORD_OVERLAY_STRING (overlay, str, true);
-    }
-
-  /* Process overlays after the overlay center.  */
-  for (ov = current_buffer->overlays_after; ov; ov = ov->next)
-    {
-      XSETMISC (overlay, ov);
-      eassert (OVERLAYP (overlay));
-      start = OVERLAY_POSITION (OVERLAY_START (overlay));
-      end = OVERLAY_POSITION (OVERLAY_END (overlay));
-
-      if (start > charpos)
-        break;
-
-      /* Skip this overlay if it doesn't start or end at IT's current
-         position.  */
-      if (end != charpos && start != charpos)
-        continue;
-
-      /* Skip this overlay if it doesn't apply to IT->w.  */
-      window = Foverlay_get (overlay, Qwindow);
-      if (WINDOWP (window) && XWINDOW (window) != it->w)
-        continue;
-
-      /* If the text ``under'' the overlay is invisible, it has a zero
-         dimension, and both before- and after-strings apply.  */
-      invisible = Foverlay_get (overlay, Qinvisible);
-      invis = TEXT_PROP_MEANS_INVISIBLE (invisible);
-
-      /* If overlay has a non-empty before-string, record it.  */
-      if ((start == charpos || (end == charpos && invis != 0))
-          && (str = Foverlay_get (overlay, Qbefore_string), STRINGP (str))
-          && SCHARS (str))
-        RECORD_OVERLAY_STRING (overlay, str, false);
-
-      /* If overlay has a non-empty after-string, record it.  */
-      if ((end == charpos || (start == charpos && invis != 0))
-          && (str = Foverlay_get (overlay, Qafter_string), STRINGP (str))
-          && SCHARS (str))
-        RECORD_OVERLAY_STRING (overlay, str, true);
+      buffer_overlay_iter_start (current_buffer,
+                                 charpos - 1, charpos + 1, ITREE_DESCENDING);
+      /* Process overlays.  */
+      while ((node = buffer_overlay_iter_next (current_buffer)))
+        {
+          overlay = node->data;
+          eassert (OVERLAYP (overlay));
+          start = node->begin;
+          end = node->end;
+
+          /* Skip this overlay if it doesn't start or end at IT's current
+             position.  */
+          if (end != charpos && start != charpos)
+            continue;
+
+          /* Skip this overlay if it doesn't apply to IT->w.  */
+          window = Foverlay_get (overlay, Qwindow);
+          if (WINDOWP (window) && XWINDOW (window) != it->w)
+            continue;
+
+          /* If the text ``under'' the overlay is invisible, both before-
+             and after-strings from this overlay are visible; start and
+             end position are indistinguishable.  */
+          invisible = Foverlay_get (overlay, Qinvisible);
+          invis = TEXT_PROP_MEANS_INVISIBLE (invisible);
+
+          /* If overlay has a non-empty before-string, record it.  */
+          if ((start == charpos || (end == charpos && invis != 0))
+              && (str = Foverlay_get (overlay, Qbefore_string), STRINGP (str))
+              && SCHARS (str))
+            RECORD_OVERLAY_STRING (overlay, str, false);
+
+          /* If overlay has a non-empty after-string, record it.  */
+          if ((end == charpos || (start == charpos && invis != 0))
+              && (str = Foverlay_get (overlay, Qafter_string), STRINGP (str))
+              && SCHARS (str))
+            RECORD_OVERLAY_STRING (overlay, str, true);
+        }
+      buffer_overlay_iter_finish (current_buffer);
     }
 
 #undef RECORD_OVERLAY_STRING
@@ -6463,7 +6394,7 @@ back_to_previous_visible_line_start (struct it *it)
             && !NILP (val = get_char_property_and_overlay
                       (make_number (pos), Qdisplay, Qnil, &overlay))
             && (OVERLAYP (overlay)
-                ? (beg = OVERLAY_POSITION (OVERLAY_START (overlay)))
+                ? (beg = OVERLAY_START (overlay))
                 : get_property_and_range (pos, Qdisplay, &val, &beg, &end, Qnil)))
           {
             RESTORE_IT (it, it, it2data);
@@ -9568,7 +9499,6 @@ move_it_to (struct it *it, ptrdiff_t to_charpos, int to_x, int to_y, int to_vpos
         }
 
       /* Reset/increment for the next run.  */
-      recenter_overlay_lists (current_buffer, IT_CHARPOS (*it));
       it->current_x = line_start_x;
       line_start_x = 0;
       it->hpos = 0;
@@ -21212,13 +21142,6 @@ display_line (struct it *it, int cursor_vpos)
   row->starts_in_middle_of_char_p = it->starts_in_middle_of_char_p;
   it->starts_in_middle_of_char_p = false;
 
-  /* Arrange the overlays nicely for our purposes.  Usually, we call
-     display_line on only one line at a time, in which case this
-     can't really hurt too much, or we call it on lines which appear
-     one after another in the buffer, in which case all calls to
-     recenter_overlay_lists but the first will be pretty cheap.  */
-  recenter_overlay_lists (current_buffer, IT_CHARPOS (*it));
-
   /* If we are going to display the cursor's line, account for the
      hscroll of that line.  We subtract the window's min_hscroll,
      because that was already accounted for in init_iterator.  */
@@ -31212,7 +31135,7 @@ note_mouse_highlight (struct frame *f, int x, int y)
       if (BUFFERP (object))
         {
           /* Put all the overlays we want in a vector in overlay_vec.  */
-          GET_OVERLAYS_AT (pos, overlay_vec, noverlays, NULL, false);
+          GET_OVERLAYS_AT (pos, overlay_vec, noverlays, NULL);
           /* Sort overlays into increasing priority order.  */
           noverlays = sort_overlays (overlay_vec, noverlays, w);
         }
diff --git a/src/xfaces.c b/src/xfaces.c
index b309c161278..b1788725eb7 100644
--- a/src/xfaces.c
+++ b/src/xfaces.c
@@ -5931,8 +5931,7 @@ face_at_buffer_position (struct window *w, ptrdiff_t pos,
   USE_SAFE_ALLOCA;
   {
     ptrdiff_t next_overlay;
-
-    GET_OVERLAYS_AT (pos, overlay_vec, noverlays, &next_overlay, false);
+    GET_OVERLAYS_AT (pos, overlay_vec, noverlays, &next_overlay);
     if (next_overlay < endpos)
       endpos = next_overlay;
   }
@@ -5975,7 +5974,6 @@ face_at_buffer_position (struct window *w, ptrdiff_t pos,
     {
       for (prop = Qnil, i = noverlays - 1; i >= 0 && NILP (prop); --i)
         {
-          Lisp_Object oend;
           ptrdiff_t oendpos;
 
           prop = Foverlay_get (overlay_vec[i], propname);
@@ -5988,8 +5986,7 @@ face_at_buffer_position (struct window *w, ptrdiff_t pos,
               merge_face_ref (f, prop, attrs, true, 0);
             }
 
-          oend = OVERLAY_END (overlay_vec[i]);
-          oendpos = OVERLAY_POSITION (oend);
+          oendpos = OVERLAY_END (overlay_vec[i]);
           if (oendpos < endpos)
             endpos = oendpos;
         }
@@ -5998,18 +5995,16 @@ face_at_buffer_position (struct window *w, ptrdiff_t pos,
     {
       for (i = 0; i < noverlays; i++)
         {
-          Lisp_Object oend;
           ptrdiff_t oendpos;
 
           prop = Foverlay_get (overlay_vec[i], propname);
           if (!NILP (prop))
             merge_face_ref (f, prop, attrs, true, 0);
 
-          oend = OVERLAY_END (overlay_vec[i]);
-          oendpos = OVERLAY_POSITION (oend);
-          if (oendpos < endpos)
-            endpos = oendpos;
-        }
+          oendpos = OVERLAY_END (overlay_vec[i]);
+          if (oendpos < endpos)
+            endpos = oendpos;
+        }
     }
 
   *endptr = endpos;