master 10faaa3c910: Prefer `ITREE_FOREACH` over `overlays_in`

[Stefan Monnier]

branch: master
commit 10faaa3c91045390755791c21349cd562546fdea
Author: Stefan Monnier <monnier@iro.umontreal.ca>
Commit: Stefan Monnier <monnier@iro.umontreal.ca>

    Prefer `ITREE_FOREACH` over `overlays_in`
    
    Use `ITREE_FOREACH` instead of `overlays_in` if that can save us from
    allocating an array.
    
    * src/buffer.c (overlays_in): Mark as static.
    (mouse_face_overlay_overlaps): Use `ITREE_FOREACH` instead of `overlays_in`.
    (disable_line_numbers_overlay_at_eob): Same, and also change return
    value to a boolean.
    * src/buffer.h (overlays_in): Don't declare.
    * src/editfns.c (overlays_around): Delete function.
    (Fget_pos_property): Use `ITREE_FOREACH` and keep the "best so far"
    instead of using `overlays_in` and sorting the elements.
    
    * src/lisp.h (disable_line_numbers_overlay_at_eob): Change return
    type to a boolean.
    * src/xdisp.c (should_produce_line_number): Adjust accordingly.
---
 src/buffer.c  | 60 +++++++++++++++----------------------------
 src/buffer.h  |  2 --
 src/editfns.c | 82 +++++++++++++++++++----------------------------------------
 src/lisp.h    |  2 +-
 src/xdisp.c   |  2 +-
 5 files changed, 49 insertions(+), 99 deletions(-)

diff --git a/src/buffer.c b/src/buffer.c
index 352aca8ddfd..d67e1d67cd6 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -3002,7 +3002,7 @@ the normal hook `change-major-mode-hook'.  */)
    But still return the total number of overlays.
 */
 
-ptrdiff_t
+static ptrdiff_t
 overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend,
             Lisp_Object **vec_ptr, ptrdiff_t *len_ptr,
             bool empty, bool trailing,
@@ -3125,56 +3125,38 @@ mouse_face_overlay_overlaps (Lisp_Object 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];
-  USE_SAFE_ALLOCA;
+  Lisp_Object tem;
+  struct itree_node *node;
 
-  size = ARRAYELTS (vbuf);
-  v = vbuf;
-  n = overlays_in (start, end, 0, &v, &size, true, false, NULL);
-  if (n > size)
+  ITREE_FOREACH (node, current_buffer->overlays,
+                 start, min (end, ZV) + 1,
+                 ASCENDING)
     {
-      SAFE_NALLOCA (v, 1, n);
-      overlays_in (start, end, 0, &v, &n, true, false, NULL);
+      if (node->begin < end && node->end > start
+          && node->begin < node->end
+          && !EQ (node->data, overlay)
+          && (tem = Foverlay_get (overlay, Qmouse_face),
+             !NILP (tem)))
+       return true;
     }
-
-  for (i = 0; i < n; ++i)
-    if (!EQ (v[i], overlay)
-       && (tem = Foverlay_get (overlay, Qmouse_face),
-           !NILP (tem)))
-      break;
-
-  SAFE_FREE ();
-  return i < n;
+  return false;
 }
 
 /* Return the value of the 'display-line-numbers-disable' property at
    EOB, if there's an overlay at ZV with a non-nil value of that property.  */
-Lisp_Object
+bool
 disable_line_numbers_overlay_at_eob (void)
 {
-  ptrdiff_t n, i, size;
-  Lisp_Object *v, tem = Qnil;
-  Lisp_Object vbuf[10];
-  USE_SAFE_ALLOCA;
+  Lisp_Object tem = Qnil;
+  struct itree_node *node;
 
-  size = ARRAYELTS (vbuf);
-  v = vbuf;
-  n = overlays_in (ZV, ZV, 0, &v, &size, false, false, NULL);
-  if (n > size)
+  ITREE_FOREACH (node, current_buffer->overlays, ZV, ZV, ASCENDING)
     {
-      SAFE_NALLOCA (v, 1, n);
-      overlays_in (ZV, ZV, 0, &v, &n, false, false, NULL);
+      if ((tem = Foverlay_get (node->data, Qdisplay_line_numbers_disable),
+          !NILP (tem)))
+       return true;
     }
-
-  for (i = 0; i < n; ++i)
-    if ((tem = Foverlay_get (v[i], Qdisplay_line_numbers_disable),
-        !NILP (tem)))
-      break;
-
-  SAFE_FREE ();
-  return tem;
+  return false;
 }
 
 
diff --git a/src/buffer.h b/src/buffer.h
index 9e0982f5da7..87ba2802b39 100644
--- a/src/buffer.h
+++ b/src/buffer.h
@@ -1174,8 +1174,6 @@ extern void delete_all_overlays (struct buffer *);
 extern void reset_buffer (struct buffer *);
 extern void compact_buffer (struct buffer *);
 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, 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 *);
diff --git a/src/editfns.c b/src/editfns.c
index 0cecd81c07f..cce52cddbf8 100644
--- a/src/editfns.c
+++ b/src/editfns.c
@@ -272,24 +272,6 @@ If you set the marker not to point anywhere, the buffer 
will have no mark.  */)
 }
 
 
-/* Find all the overlays in the current buffer that touch position POS.
-   Return the number found, and store them in a vector in VEC
-   of length LEN.
-
-   Note: this can return overlays that do not touch POS.  The caller
-   should filter these out. */
-
-static ptrdiff_t
-overlays_around (ptrdiff_t pos, Lisp_Object *vec, ptrdiff_t len)
-{
-  /* Find all potentially rear-advance overlays at (POS - 1).  Find
-     all overlays at POS, so end at (POS + 1).  Find even empty
-     overlays, which due to the way 'overlays-in' works implies that
-     we might also fetch empty overlays starting at (POS + 1).  */
-  return overlays_in (pos - 1, pos + 1, false, &vec, &len,
-                     true, false, NULL);
-}
-
 DEFUN ("get-pos-property", Fget_pos_property, Sget_pos_property, 2, 3, 0,
        doc: /* Return the value of POSITION's property PROP, in OBJECT.
 Almost identical to `get-char-property' except for the following difference:
@@ -315,53 +297,41 @@ at POSITION.  */)
   else
     {
       EMACS_INT posn = XFIXNUM (position);
-      ptrdiff_t noverlays;
-      Lisp_Object *overlay_vec, tem;
+      Lisp_Object tem;
       struct buffer *obuf = current_buffer;
-      USE_SAFE_ALLOCA;
-
-      set_buffer_temp (XBUFFER (object));
+      struct itree_node *node;
+      struct sortvec items[2];
+      struct sortvec *result = NULL;
+      struct buffer *b = XBUFFER (object);
+      Lisp_Object res = Qnil;
 
-      /* First try with room for 40 overlays.  */
-      Lisp_Object overlay_vecbuf[40];
-      noverlays = ARRAYELTS (overlay_vecbuf);
-      overlay_vec = overlay_vecbuf;
-      noverlays = overlays_around (posn, overlay_vec, noverlays);
+      set_buffer_temp (b);
 
-      /* If there are more than 40,
-        make enough space for all, and try again.  */
-      if (ARRAYELTS (overlay_vecbuf) < noverlays)
+      ITREE_FOREACH (node, b->overlays, posn - 1, posn + 1, ASCENDING)
        {
-         SAFE_ALLOCA_LISP (overlay_vec, noverlays);
-         noverlays = overlays_around (posn, overlay_vec, noverlays);
-       }
-      noverlays = sort_overlays (overlay_vec, noverlays, NULL);
-
-      set_buffer_temp (obuf);
-
-      /* Now check the overlays in order of decreasing priority.  */
-      while (--noverlays >= 0)
-       {
-         Lisp_Object ol = overlay_vec[noverlays];
+         Lisp_Object ol = node->data;
          tem = Foverlay_get (ol, prop);
-         if (!NILP (tem))
-           {
+         if (NILP (tem)
              /* Check the overlay is indeed active at point.  */
-             if ((OVERLAY_START (ol) == posn
+             || ((node->begin == posn
                   && OVERLAY_FRONT_ADVANCE_P (ol))
-                 || (OVERLAY_END (ol) == posn
+                 || (node->end == posn
                      && ! OVERLAY_REAR_ADVANCE_P (ol))
-                 || OVERLAY_START (ol) > posn
-                 || OVERLAY_END (ol) < posn)
-               ; /* The overlay will not cover a char inserted at point.  */
-             else
-               {
-                 SAFE_FREE ();
-                 return tem;
-               }
-           }
+                 || node->begin > posn
+                 || node->end < posn))
+           /* The overlay will not cover a char inserted at point.  */
+           continue;
+
+         struct sortvec *this = (result == items ? items + 1 : items);
+          if (NILP (res)
+              || (make_sortvec_item (this, node->data),
+                  compare_overlays (result, this) < 0))
+            res = tem;
        }
-      SAFE_FREE ();
+      set_buffer_temp (obuf);
+
+      if (!NILP (res))
+        return res;
 
       { /* Now check the text properties.  */
        int stickiness = text_property_stickiness (prop, position, object);
diff --git a/src/lisp.h b/src/lisp.h
index 75134425a07..e6fd8cacb1b 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -4802,7 +4802,7 @@ extern void syms_of_editfns (void);
 
 /* Defined in buffer.c.  */
 extern bool mouse_face_overlay_overlaps (Lisp_Object);
-extern Lisp_Object disable_line_numbers_overlay_at_eob (void);
+extern bool disable_line_numbers_overlay_at_eob (void);
 extern AVOID nsberror (Lisp_Object);
 extern void adjust_overlays_for_insert (ptrdiff_t, ptrdiff_t, bool);
 extern void adjust_overlays_for_delete (ptrdiff_t, ptrdiff_t);
diff --git a/src/xdisp.c b/src/xdisp.c
index 750ebb703a6..2dcf0d58a14 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -25060,7 +25060,7 @@ should_produce_line_number (struct it *it)
      because get-char-property always returns nil for ZV, except if
      the property is in 'default-text-properties'.  */
   if (NILP (val) && IT_CHARPOS (*it) >= ZV)
-    val = disable_line_numbers_overlay_at_eob ();
+    return !disable_line_numbers_overlay_at_eob ();
   return NILP (val) ? true : false;
 }