Tune by using memchr and memrchr.

* .bzrignore: Add string.h.
* admin/merge-gnulib (GNULIB_MODULES): Add memrchr.
* lib/gnulib.mk, m4/gnulib-comp.m4: Regenerate.
* lib/memrchr.c, lib/string.in.h, m4/memrchr.m4, m4/string_h.m4:
New files, from gnulib.
* src/doc.c (Fsnarf_documentation):
* src/fileio.c (Fsubstitute_in_file_name):
* src/search.c (find_newline, scan_newline):
* src/xdisp.c (pos_visible_p, display_count_lines):
Use memchr and memrchr rather than scanning byte-by-byte.
* src/search.c (find_newline): Rename from scan_buffer.
Omit first arg TARGET, as it's always '\n'.  All callers changed.

8 files changed, 150 insertions, 158 deletions

diff --git a/src/ChangeLog b/src/ChangeLog
index b3d3958853b..30470f5730a 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,5 +1,14 @@
 2013-02-11  Paul Eggert  <eggert@cs.ucla.edu>
 
+        Tune by using memchr and memrchr.
+        * doc.c (Fsnarf_documentation):
+        * fileio.c (Fsubstitute_in_file_name):
+        * search.c (find_newline, scan_newline):
+        * xdisp.c (pos_visible_p, display_count_lines):
+        Use memchr and memrchr rather than scanning byte-by-byte.
+        * search.c (find_newline): Rename from scan_buffer.
+        Omit first arg TARGET, as it's always '\n'.  All callers changed.
+
         Clean up read_key_sequence a tiny bit more.
         * keyboard.c (read_char_x_menu_prompt) [HAVE_MENUS]:
         (read_key_sequence): Remove unused locals.
diff --git a/src/doc.c b/src/doc.c
index fa2eca66a1d..7234fb38bf9 100644
--- a/src/doc.c
+++ b/src/doc.c
@@ -630,11 +630,10 @@ the same file name is found in the `doc-directory'.  */)
         break;
 
       buf[filled] = 0;
-      p = buf;
       end = buf + (filled < 512 ? filled : filled - 128);
-      while (p != end && *p != '\037') p++;
+      p = memchr (buf, '\037', end - buf);
       /* p points to ^_Ffunctionname\n or ^_Vvarname\n or ^_Sfilename\n.  */
-      if (p != end)
+      if (p)
         {
           end = strchr (p, '\n');
 
diff --git a/src/editfns.c b/src/editfns.c
index 0f88a781b88..c5cd8b0b725 100644
--- a/src/editfns.c
+++ b/src/editfns.c
@@ -735,9 +735,8 @@ Field boundaries are not noticed if `inhibit-field-text-motion' is non-nil.  */)
               /* This is the ONLY_IN_LINE case, check that NEW_POS and
                  FIELD_BOUND are on the same line by seeing whether
                  there's an intervening newline or not.  */
-              || (scan_buffer ('\n',
-                               XFASTINT (new_pos), XFASTINT (field_bound),
-                               fwd ? -1 : 1, &shortage, 1),
+              || (find_newline (XFASTINT (new_pos), XFASTINT (field_bound),
+                                fwd ? -1 : 1, &shortage, 1),
                   shortage != 0)))
         /* Constrain NEW_POS to FIELD_BOUND.  */
         new_pos = field_bound;
diff --git a/src/fileio.c b/src/fileio.c
index 98a9b32ea91..89ad3396464 100644
--- a/src/fileio.c
+++ b/src/fileio.c
@@ -1710,8 +1710,9 @@ those `/' is discarded.  */)
         else if (*p == '{')
           {
             o = ++p;
-            while (p != endp && *p != '}') p++;
-            if (*p != '}') goto missingclose;
+            p = memchr (p, '}', endp - p);
+            if (! p)
+              goto missingclose;
             s = p;
           }
         else
@@ -1779,8 +1780,9 @@ those `/' is discarded.  */)
         else if (*p == '{')
           {
             o = ++p;
-            while (p != endp && *p != '}') p++;
-            if (*p != '}') goto missingclose;
+            p = memchr (p, '}', endp - p);
+            if (! p)
+              goto missingclose;
             s = p++;
           }
         else
diff --git a/src/lisp.h b/src/lisp.h
index 14db66c6793..37d2b45e85b 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3346,8 +3346,8 @@ extern ptrdiff_t fast_c_string_match_ignore_case (Lisp_Object, const char *,
 extern ptrdiff_t fast_string_match_ignore_case (Lisp_Object, Lisp_Object);
 extern ptrdiff_t fast_looking_at (Lisp_Object, ptrdiff_t, ptrdiff_t,
                                   ptrdiff_t, ptrdiff_t, Lisp_Object);
-extern ptrdiff_t scan_buffer (int, ptrdiff_t, ptrdiff_t, ptrdiff_t,
-                              ptrdiff_t *, bool);
+extern ptrdiff_t find_newline (ptrdiff_t, ptrdiff_t, ptrdiff_t,
+                               ptrdiff_t *, bool);
 extern EMACS_INT scan_newline (ptrdiff_t, ptrdiff_t, ptrdiff_t, ptrdiff_t,
                                EMACS_INT, bool);
 extern ptrdiff_t find_next_newline (ptrdiff_t, int);
diff --git a/src/region-cache.h b/src/region-cache.h
index 697ae1c791f..e4c6b59ee95 100644
--- a/src/region-cache.h
+++ b/src/region-cache.h
@@ -40,7 +40,7 @@ along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
    existing data structure, and disturb as little of the existing code
    as possible.
 
-   So here's the tack.  We add some caching to the scan_buffer
+   So here's the tack.  We add some caching to the find_newline
    function, so that when it searches for a newline, it notes that the
    region between the start and end of the search contained no
    newlines; then, the next time around, it consults this cache to see
diff --git a/src/search.c b/src/search.c
index c4ccf6c257b..c25d2441018 100644
--- a/src/search.c
+++ b/src/search.c
@@ -619,7 +619,7 @@ newline_cache_on_off (struct buffer *buf)
 }
 
 
-/* Search for COUNT instances of the character TARGET between START and END.
+/* Search for COUNT newlines between START and END.
 
    If COUNT is positive, search forwards; END must be >= START.
    If COUNT is negative, search backwards for the -COUNTth instance;
@@ -634,14 +634,14 @@ newline_cache_on_off (struct buffer *buf)
    this is not the same as the usual convention for Emacs motion commands.
 
    If we don't find COUNT instances before reaching END, set *SHORTAGE
-   to the number of TARGETs left unfound, and return END.
+   to the number of newlines left unfound, and return END.
 
    If ALLOW_QUIT, set immediate_quit.  That's good to do
    except when inside redisplay.  */
 
 ptrdiff_t
-scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
-             ptrdiff_t count, ptrdiff_t *shortage, bool allow_quit)
+find_newline (ptrdiff_t start, ptrdiff_t end,
+              ptrdiff_t count, ptrdiff_t *shortage, bool allow_quit)
 {
   struct region_cache *newline_cache;
   ptrdiff_t end_byte = -1;
@@ -656,7 +656,7 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
   else
     {
       direction = -1;
-      if (!end) 
+      if (!end)
         end = BEGV, end_byte = BEGV_BYTE;
     }
   if (end_byte == -1)
@@ -684,7 +684,7 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
 
         /* If we're looking for a newline, consult the newline cache
            to see where we can avoid some scanning.  */
-        if (target == '\n' && newline_cache)
+        if (newline_cache)
           {
             ptrdiff_t next_change;
             immediate_quit = 0;
@@ -723,32 +723,32 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
 
           while (cursor < ceiling_addr)
             {
-              unsigned char *scan_start = cursor;
-
               /* The dumb loop.  */
-              while (*cursor != target && ++cursor < ceiling_addr)
-                ;
+              unsigned char *nl = memchr (cursor, '\n', ceiling_addr - cursor);
 
               /* If we're looking for newlines, cache the fact that
                  the region from start to cursor is free of them. */
-              if (target == '\n' && newline_cache)
-                know_region_cache (current_buffer, newline_cache,
-                                   BYTE_TO_CHAR (start_byte + scan_start - base),
-                                   BYTE_TO_CHAR (start_byte + cursor - base));
-
-              /* Did we find the target character?  */
-              if (cursor < ceiling_addr)
-                {
-                  if (--count == 0)
-                    {
-                      immediate_quit = 0;
-                      return BYTE_TO_CHAR (start_byte + cursor - base + 1);
-                    }
-                  cursor++;
-                }
+              if (newline_cache)
+                {
+                  unsigned char *low = cursor;
+                  unsigned char *lim = nl ? nl : ceiling_addr;
+                  know_region_cache (current_buffer, newline_cache,
+                                     BYTE_TO_CHAR (low - base + start_byte),
+                                     BYTE_TO_CHAR (lim - base + start_byte));
+                }
+
+              if (! nl)
+                break;
+
+              if (--count == 0)
+                {
+                  immediate_quit = 0;
+                  return BYTE_TO_CHAR (nl + 1 - base + start_byte);
+                }
+              cursor = nl + 1;
             }
 
-          start = BYTE_TO_CHAR (start_byte + cursor - base);
+          start = BYTE_TO_CHAR (ceiling_addr - base + start_byte);
         }
       }
   else
@@ -760,7 +760,7 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
         ptrdiff_t tem;
 
         /* Consult the newline cache, if appropriate.  */
-        if (target == '\n' && newline_cache)
+        if (newline_cache)
           {
             ptrdiff_t next_change;
             immediate_quit = 0;
@@ -794,31 +794,32 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
 
           while (cursor >= ceiling_addr)
             {
-              unsigned char *scan_start = cursor;
-
-              while (*cursor != target && --cursor >= ceiling_addr)
-                ;
+              unsigned char *nl = memrchr (ceiling_addr, '\n',
+                                           cursor + 1 - ceiling_addr);
 
               /* If we're looking for newlines, cache the fact that
                  the region from after the cursor to start is free of them.  */
-              if (target == '\n' && newline_cache)
-                know_region_cache (current_buffer, newline_cache,
-                                   BYTE_TO_CHAR (start_byte + cursor - base),
-                                   BYTE_TO_CHAR (start_byte + scan_start - base));
-
-              /* Did we find the target character?  */
-              if (cursor >= ceiling_addr)
-                {
-                  if (++count >= 0)
-                    {
-                      immediate_quit = 0;
-                      return BYTE_TO_CHAR (start_byte + cursor - base);
-                    }
-                  cursor--;
-                }
+              if (newline_cache)
+                {
+                  unsigned char *low = nl ? nl : ceiling_addr - 1;
+                  unsigned char *lim = cursor;
+                  know_region_cache (current_buffer, newline_cache,
+                                     BYTE_TO_CHAR (low - base + start_byte),
+                                     BYTE_TO_CHAR (lim - base + start_byte));
+                }
+
+              if (! nl)
+                break;
+
+              if (++count >= 0)
+                {
+                  immediate_quit = 0;
+                  return BYTE_TO_CHAR (nl - base + start_byte);
+                }
+              cursor = nl - 1;
             }
 
-          start = BYTE_TO_CHAR (start_byte + cursor - base);
+          start = BYTE_TO_CHAR (ceiling_addr - 1 - base + start_byte);
         }
       }
 
@@ -828,8 +829,7 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
   return start;
 }
 
-/* Search for COUNT instances of a line boundary, which means either a
-   newline or (if selective display enabled) a carriage return.
+/* Search for COUNT instances of a line boundary.
    Start at START.  If COUNT is negative, search backwards.
 
    We report the resulting position by calling TEMP_SET_PT_BOTH.
@@ -860,9 +860,6 @@ scan_newline (ptrdiff_t start, ptrdiff_t start_byte,
 
   bool old_immediate_quit = immediate_quit;
 
-  /* The code that follows is like scan_buffer
-     but checks for either newline or carriage return.  */
-
   if (allow_quit)
     immediate_quit++;
 
@@ -874,29 +871,25 @@ scan_newline (ptrdiff_t start, ptrdiff_t start_byte,
           ceiling = min (limit_byte - 1, ceiling);
           ceiling_addr = BYTE_POS_ADDR (ceiling) + 1;
           base = (cursor = BYTE_POS_ADDR (start_byte));
-          while (1)
-            {
-              while (*cursor != '\n' && ++cursor != ceiling_addr)
-                ;
 
-              if (cursor != ceiling_addr)
+          do
+            {
+              unsigned char *nl = memchr (cursor, '\n', ceiling_addr - cursor);
+              if (! nl)
+                break;
+              if (--count == 0)
                 {
-                  if (--count == 0)
-                    {
-                      immediate_quit = old_immediate_quit;
-                      start_byte = start_byte + cursor - base + 1;
-                      start = BYTE_TO_CHAR (start_byte);
-                      TEMP_SET_PT_BOTH (start, start_byte);
-                      return 0;
-                    }
-                  else
-                    if (++cursor == ceiling_addr)
-                      break;
+                  immediate_quit = old_immediate_quit;
+                  start_byte += nl - base + 1;
+                  start = BYTE_TO_CHAR (start_byte);
+                  TEMP_SET_PT_BOTH (start, start_byte);
+                  return 0;
                 }
-              else
-                break;
+              cursor = nl + 1;
             }
-          start_byte += cursor - base;
+          while (cursor < ceiling_addr);
+
+          start_byte += ceiling_addr - base;
         }
     }
   else
@@ -905,31 +898,28 @@ scan_newline (ptrdiff_t start, ptrdiff_t start_byte,
         {
           ceiling = BUFFER_FLOOR_OF (start_byte - 1);
           ceiling = max (limit_byte, ceiling);
-          ceiling_addr = BYTE_POS_ADDR (ceiling) - 1;
+          ceiling_addr = BYTE_POS_ADDR (ceiling);
           base = (cursor = BYTE_POS_ADDR (start_byte - 1) + 1);
           while (1)
             {
-              while (--cursor != ceiling_addr && *cursor != '\n')
-                ;
+              unsigned char *nl = memrchr (ceiling_addr, '\n',
+                                           cursor - ceiling_addr);
+              if (! nl)
+                break;
 
-              if (cursor != ceiling_addr)
+              if (++count == 0)
                 {
-                  if (++count == 0)
-                    {
-                      immediate_quit = old_immediate_quit;
-                      /* Return the position AFTER the match we found.  */
-                      start_byte = start_byte + cursor - base + 1;
-                      start = BYTE_TO_CHAR (start_byte);
-                      TEMP_SET_PT_BOTH (start, start_byte);
-                      return 0;
-                    }
+                  immediate_quit = old_immediate_quit;
+                  /* Return the position AFTER the match we found.  */
+                  start_byte += nl - base + 1;
+                  start = BYTE_TO_CHAR (start_byte);
+                  TEMP_SET_PT_BOTH (start, start_byte);
+                  return 0;
                 }
-              else
-                break;
+
+              cursor = nl;
             }
-          /* Here we add 1 to compensate for the last decrement
-             of CURSOR, which took it past the valid range.  */
-          start_byte += cursor - base + 1;
+          start_byte += ceiling_addr - base;
         }
     }
 
@@ -942,7 +932,7 @@ scan_newline (ptrdiff_t start, ptrdiff_t start_byte,
 ptrdiff_t
 find_next_newline_no_quit (ptrdiff_t from, ptrdiff_t cnt)
 {
-  return scan_buffer ('\n', from, 0, cnt, (ptrdiff_t *) 0, 0);
+  return find_newline (from, 0, cnt, (ptrdiff_t *) 0, 0);
 }
 
 /* Like find_next_newline, but returns position before the newline,
@@ -953,7 +943,7 @@ ptrdiff_t
 find_before_next_newline (ptrdiff_t from, ptrdiff_t to, ptrdiff_t cnt)
 {
   ptrdiff_t shortage;
-  ptrdiff_t pos = scan_buffer ('\n', from, to, cnt, &shortage, 1);
+  ptrdiff_t pos = find_newline (from, to, cnt, &shortage, 1);
 
   if (shortage == 0)
     pos--;
diff --git a/src/xdisp.c b/src/xdisp.c
index 3b82de9432d..463f4f9ef05 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -1392,21 +1392,9 @@ pos_visible_p (struct window *w, ptrdiff_t charpos, int *x, int *y,
               Lisp_Object cpos = make_number (charpos);
               Lisp_Object spec = Fget_char_property (cpos, Qdisplay, Qnil);
               Lisp_Object string = string_from_display_spec (spec);
-              int newline_in_string = 0;
-
-              if (STRINGP (string))
-                {
-                  const char *s = SSDATA (string);
-                  const char *e = s + SBYTES (string);
-                  while (s < e)
-                    {
-                      if (*s++ == '\n')
-                        {
-                          newline_in_string = 1;
-                          break;
-                        }
-                    }
-                }
+              bool newline_in_string
+                = (STRINGP (string)
+                   && memchr (SDATA (string), '\n', SBYTES (string)));
               /* The tricky code below is needed because there's a
                  discrepancy between move_it_to and how we set cursor
                  when the display line ends in a newline from a
@@ -14759,7 +14747,7 @@ compute_window_start_on_continuation_line (struct window *w)
         SET_TEXT_POS (start_pos, ZV, ZV_BYTE);
 
       /* Find the start of the continued line.  This should be fast
-         because scan_buffer is fast (newline cache).  */
+         because find_newline is fast (newline cache).  */
       row = w->desired_matrix->rows + (WINDOW_WANTS_HEADER_LINE_P (w) ? 1 : 0);
       init_iterator (&it, w, CHARPOS (start_pos), BYTEPOS (start_pos),
                      row, DEFAULT_FACE_ID);
@@ -21626,31 +21614,36 @@ display_count_lines (ptrdiff_t start_byte,
           ceiling = min (limit_byte - 1, ceiling);
           ceiling_addr = BYTE_POS_ADDR (ceiling) + 1;
           base = (cursor = BYTE_POS_ADDR (start_byte));
-          while (1)
+
+          do
             {
               if (selective_display)
-                while (*cursor != '\n' && *cursor != 015 && ++cursor != ceiling_addr)
-                  ;
+                {
+                  while (*cursor != '\n' && *cursor != 015
+                         && ++cursor != ceiling_addr)
+                    continue;
+                  if (cursor == ceiling_addr)
+                    break;
+                }
               else
-                while (*cursor != '\n' && ++cursor != ceiling_addr)
-                  ;
+                {
+                  cursor = memchr (cursor, '\n', ceiling_addr - cursor);
+                  if (! cursor)
+                    break;
+                }
+
+              cursor++;
 
-              if (cursor != ceiling_addr)
+              if (--count == 0)
                 {
-                  if (--count == 0)
-                    {
-                      start_byte += cursor - base + 1;
-                      *byte_pos_ptr = start_byte;
-                      return orig_count;
-                    }
-                  else
-                    if (++cursor == ceiling_addr)
-                      break;
+                  start_byte += cursor - base;
+                  *byte_pos_ptr = start_byte;
+                  return orig_count;
                 }
-              else
-                break;
             }
-          start_byte += cursor - base;
+          while (cursor < ceiling_addr);
+
+          start_byte += ceiling_addr - base;
         }
     }
   else
@@ -21659,35 +21652,35 @@ display_count_lines (ptrdiff_t start_byte,
         {
           ceiling = BUFFER_FLOOR_OF (start_byte - 1);
           ceiling = max (limit_byte, ceiling);
-          ceiling_addr = BYTE_POS_ADDR (ceiling) - 1;
+          ceiling_addr = BYTE_POS_ADDR (ceiling);
           base = (cursor = BYTE_POS_ADDR (start_byte - 1) + 1);
           while (1)
             {
               if (selective_display)
-                while (--cursor != ceiling_addr
-                       && *cursor != '\n' && *cursor != 015)
-                  ;
+                {
+                  while (--cursor >= ceiling_addr
+                         && *cursor != '\n' && *cursor != 015)
+                    continue;
+                  if (cursor < ceiling_addr)
+                    break;
+                }
               else
-                while (--cursor != ceiling_addr && *cursor != '\n')
-                  ;
+                {
+                  cursor = memrchr (ceiling_addr, '\n', cursor - ceiling_addr);
+                  if (! cursor)
+                    break;
+                }
 
-              if (cursor != ceiling_addr)
+              if (++count == 0)
                 {
-                  if (++count == 0)
-                    {
-                      start_byte += cursor - base + 1;
-                      *byte_pos_ptr = start_byte;
-                      /* When scanning backwards, we should
-                         not count the newline posterior to which we stop.  */
-                      return - orig_count - 1;
-                    }
+                  start_byte += cursor - base + 1;
+                  *byte_pos_ptr = start_byte;
+                  /* When scanning backwards, we should
+                     not count the newline posterior to which we stop.  */
+                  return - orig_count - 1;
                 }
-              else
-                break;
             }
-          /* Here we add 1 to compensate for the last decrement
-             of CURSOR, which took it past the valid range.  */
-          start_byte += cursor - base + 1;
+          start_byte += ceiling_addr - base;
         }
     }