Subject: Re: bug#17204: [PATCH] grep: speed-up for exact matching with begline and endline constraints

From: Paul Eggert <[email-masked]>
Date: Mon, 21 Apr 2014 07:58:43 -0700

Thanks, I looked at that, got derailed by finding and fixing a bug with 
NUL bytes that turned out to be a pre-existing bug, and finally 
installed it just now, with a slightly-reworded commit message.  I also 
installed the attached minor-improvement patch as well (some of it 
cleans up preexisting code in the neighborhood).
From 4af18dcace3879ac0b209e0a00babce45373568e Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Mon, 21 Apr 2014 07:27:14 -0700
Subject: [PATCH] dfa: minor improvements to previous patch

* src/dfa.c (dfamust): Use &=, not if-then.
* src/dfa.h (struct dfamust):
* src/dfasearch.c (begline, hwsmusts): Use bool for boolean.
* src/dfasearch.c (kwsmusts):
* src/kwsearch.c (Fcompile): Prefer decls after statements.
* src/dfasearch.c (kwsmusts): Avoid conditional branch.
* src/kwsearch.c (Fcompile): Unify the two calls to kwsincr.
---
 src/dfa.c       |  6 ++----
 src/dfa.h       |  7 ++++---
 src/dfasearch.c | 20 ++++++++------------
 src/kwsearch.c  | 17 ++++++++++-------
 4 files changed, 24 insertions(+), 26 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 0a6f061..65fc03d 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3916,10 +3916,8 @@ dfamust (struct dfa *d)
             /* Guaranteed to be.  Unlikely, but ...  */
             if (!STREQ (lmp->is, rmp->is))
               lmp->is[0] = '\0';
-            if (lmp->begline)
-              lmp->begline = rmp->begline;
-            if (lmp->endline)
-              lmp->endline = rmp->endline;
+            lmp->begline &= rmp->begline;
+            lmp->endline &= rmp->endline;
             /* Left side--easy */
             i = 0;
             while (lmp->left[i] != '\0' && lmp->left[i] == rmp->left[i])
diff --git a/src/dfa.h b/src/dfa.h
index 3829e6a..60aff11 100644
--- a/src/dfa.h
+++ b/src/dfa.h
@@ -19,15 +19,16 @@
 /* Written June, 1988 by Mike Haertel */
 
 #include <regex.h>
+#include <stdbool.h>
 #include <stddef.h>
 
 /* Element of a list of strings, at least one of which is known to
    appear in any R.E. matching the DFA. */
 struct dfamust
 {
-  int exact;
-  int begline;
-  int endline;
+  bool exact;
+  bool begline;
+  bool endline;
   char *must;
   struct dfamust *next;
 };
diff --git a/src/dfasearch.c b/src/dfasearch.c
index 34c4505..dc76397 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -51,7 +51,7 @@ static size_t pcount;
    call the regexp matcher at all. */
 static size_t kwset_exact_matches;
 
-static int begline;
+static bool begline;
 
 void
 dfaerror (char const *mesg)
@@ -87,25 +87,21 @@ kwsmusts (void)
   if (dm)
     {
       kwsinit (&kwset);
-      begline = 0;
       /* First, we compile in the substrings known to be exact
          matches.  The kwset matcher will return the index
          of the matching string that it chooses. */
       for (; dm; dm = dm->next)
         {
-          char *must, *mp;
-          size_t old_len, new_len;
           if (!dm->exact)
             continue;
           ++kwset_exact_matches;
-          old_len = strlen (dm->must);
-          new_len = old_len + dm->begline + dm->endline;
-          must = mp = xmalloc (new_len);
-          if (dm->begline)
-            {
-              (mp++)[0] = eolbyte;
-              begline = 1;
-            }
+          size_t old_len = strlen (dm->must);
+          size_t new_len = old_len + dm->begline + dm->endline;
+          char *must = xmalloc (new_len);
+          char *mp = must;
+          *mp = eolbyte;
+          mp += dm->begline;
+          begline |= dm->begline;
           memcpy (mp, dm->must, old_len);
           if (dm->endline)
             mp[old_len] = eolbyte;
diff --git a/src/kwsearch.c b/src/kwsearch.c
index 9904bfe..7c64c86 100644
--- a/src/kwsearch.c
+++ b/src/kwsearch.c
@@ -57,16 +57,19 @@ Fcompile (char const *pattern, size_t size)
           total = 0;
         }
 
+      char *buf = NULL;
       if (match_lines)
         {
-          char *buf = xmalloc (len + 2);
-          memcpy (&buf[1], p, len);
-          buf[0] = buf[len + 1] = eolbyte;
-          kwsincr (kwset, buf, len + 2);
-          free (buf);
+          buf = xmalloc (len + 2);
+          buf[0] = eolbyte;
+          memcpy (buf + 1, p, len);
+          buf[len + 1] = eolbyte;
+          p = buf;
+          len += 2;
         }
-      else
-        kwsincr (kwset, p, len);
+      kwsincr (kwset, p, len);
+      free (buf);
+
       p = sep;
     }
   while (p);
-- 
1.9.0