X-Git-Url: http://git.indexdata.com/?p=idzebra-moved-to-github.git;a=blobdiff_plain;f=dfa%2Fgrepper.c;h=1340247aa8a927985925dc0862efa19fd8b6f2da;hp=afc8927737774eed2eb41d9ff0daffb2e414ad99;hb=de50782bd265b584f1e7c14f5376a499dedea780;hpb=25711769a3fb5c6bf0ab3eb9634bf74ba07dc48d

diff --git a/dfa/grepper.c b/dfa/grepper.c
index afc8927..1340247 100644
--- a/dfa/grepper.c
+++ b/dfa/grepper.c
@@ -4,7 +4,27 @@
  * Sebastian Hammer, Adam Dickmeiss
  *
  * $Log: grepper.c,v $
- * Revision 1.1  1994-09-27 16:31:18  adam
+ * Revision 1.7  1996-10-29 13:57:24  adam
+ * Include of zebrautl.h instead of alexutil.h.
+ *
+ * Revision 1.6  1996/01/08 09:09:20  adam
+ * Function dfa_parse got 'const' string argument.
+ * New functions to define char mappings made public.
+ *
+ * Revision 1.5  1995/09/04  12:33:26  adam
+ * Various cleanup. YAZ util used instead.
+ *
+ * Revision 1.4  1995/01/24  16:00:21  adam
+ * Added -ansi to CFLAGS.
+ * Some changes to the dfa module.
+ *
+ * Revision 1.3  1994/10/04  17:46:43  adam
+ * Function options now returns arg with error option.
+ *
+ * Revision 1.2  1994/10/03  17:22:18  adam
+ * Optimization of grepper.
+ *
+ * Revision 1.1  1994/09/27  16:31:18  adam
  * First version of grepper: grep with error correction.
  *
  */
@@ -14,7 +34,7 @@
 #include <ctype.h>
 #include <assert.h>
 
-#include <util.h>
+#include <zebrautl.h>
 #include <dfa.h>
 #include "imalloc.h"
 
@@ -32,7 +52,9 @@ typedef struct {
 
 #define INFBUF_SIZE 16384
 
-static inline void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
+#define INLINE 
+
+static INLINE void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
 {
     int off = state & (WORD_BITS-1);
     int wno = state / WORD_BITS;
@@ -40,7 +62,8 @@ static inline void set_bit (MatchContext *mc, MatchWord *m, int ch, int state)
     m[mc->n * ch + wno] |= 1<<off;
 }
 
-static inline void reset_bit (MatchContext *mc, MatchWord *m, int ch, int state)
+static INLINE void reset_bit (MatchContext *mc, MatchWord *m, int ch,
+                              int state)
 {
     int off = state & (WORD_BITS-1);
     int wno = state / WORD_BITS;
@@ -48,7 +71,8 @@ static inline void reset_bit (MatchContext *mc, MatchWord *m, int ch, int state)
     m[mc->n * ch + wno] &= ~(1<<off);
 }
 
-static inline MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch, int state)
+static INLINE MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch,
+                                 int state)
 {
     int off = state & (WORD_BITS-1);
     int wno = state / WORD_BITS;
@@ -56,19 +80,19 @@ static inline MatchWord get_bit (MatchContext *mc, MatchWord *m, int ch, int sta
     return m[mc->n * ch + wno] & (1<<off);
 }
 
-static MatchContext *mk_MatchContext (DFA_states *dfas, int range)
+static MatchContext *mk_MatchContext (struct DFA *dfa, int range)
 {
     MatchContext *mc = imalloc (sizeof(*mc));
     int i;
 
-    mc->n = (dfas->no+WORD_BITS) / WORD_BITS;
+    mc->n = (dfa->no_states+WORD_BITS) / WORD_BITS;
     mc->range = range;
     mc->Sc = icalloc (sizeof(*mc->Sc) * 256 * mc->n);
     
-    for (i=0; i<dfas->no; i++)
+    for (i=0; i<dfa->no_states; i++)
     {
         int j;
-        DFA_state *state = dfas->sortarray[i];
+        struct DFA_state *state = dfa->states[i];
 
         for (j=0; j<state->tran_no; j++)
         {
@@ -84,38 +108,117 @@ static MatchContext *mk_MatchContext (DFA_states *dfas, int range)
     return mc;
 }
 
+
 static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
-                   DFA_states *dfas, int ch)
+                        struct DFA *dfa, int ch)
 {
-    int i, s;
+    int j, s = 0;
+    MatchWord *Rsrc_p = Rsrc, mask;
+
     Rdst[0] = 1;
-    for (i = 1; i<mc->n; i++)
-        Rdst[i] = 0;
-    for (s = 0; s<dfas->no; s++)
-        if (get_bit (mc, Rsrc, 0, s))
+    for (j = 1; j<mc->n; j++)
+        Rdst[j] = 0;
+    while (1)
+    {
+        mask = *Rsrc_p++;
+        for (j = 0; j<WORD_BITS/4; j++)
         {
-            DFA_state *state = dfas->sortarray[s];
-            int i = state->tran_no;
-            while (--i >= 0)
-                if (ch >= state->trans[i].ch[0] && ch <= state->trans[i].ch[1])
-                    set_bit (mc, Rdst, 0, state->trans[i].to);
+            if (mask & 15)
+            {
+                if (mask & 1)
+                {
+                    struct DFA_state *state = dfa->states[s];
+                    int i = state->tran_no;
+                    while (--i >= 0)
+                        if (ch >= state->trans[i].ch[0] &&
+                            ch <= state->trans[i].ch[1])
+                            set_bit (mc, Rdst, 0, state->trans[i].to);
+                }
+                if (mask & 2)
+                {
+                    struct DFA_state *state = dfa->states[s+1];
+                    int i = state->tran_no;
+                    while (--i >= 0)
+                        if (ch >= state->trans[i].ch[0] &&
+                            ch <= state->trans[i].ch[1])
+                            set_bit (mc, Rdst, 0, state->trans[i].to);
+                }
+                if (mask & 4)
+                {
+                    struct DFA_state *state = dfa->states[s+2];
+                    int i = state->tran_no;
+                    while (--i >= 0)
+                        if (ch >= state->trans[i].ch[0] &&
+                            ch <= state->trans[i].ch[1])
+                            set_bit (mc, Rdst, 0, state->trans[i].to);
+                }
+                if (mask & 8)
+                {
+                    struct DFA_state *state = dfa->states[s+3];
+                    int i = state->tran_no;
+                    while (--i >= 0)
+                        if (ch >= state->trans[i].ch[0] &&
+                            ch <= state->trans[i].ch[1])
+                            set_bit (mc, Rdst, 0, state->trans[i].to);
+                }
+            }
+            s += 4;
+            if (s >= dfa->no_states)
+                return;
+            mask >>= 4;
         }
+    }
 }
 
 static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc,
-                   DFA_states *dfas)
+                   struct DFA *dfa)
 {
-    int i, s;
-    for (i = 0; i<mc->n; i++)
-        Rdst[i] = 0;
-    for (s = 0; s<dfas->no; s++)
-        if (get_bit (mc, Rsrc, 0, s))
+    int j, s = 0;
+    MatchWord *Rsrc_p = Rsrc, mask;
+    for (j = 0; j<mc->n; j++)
+        Rdst[j] = 0;
+    while (1)
+    {
+        mask = *Rsrc_p++;
+        for (j = 0; j<WORD_BITS/4; j++)
         {
-            DFA_state *state = dfas->sortarray[s];
-            int i = state->tran_no;
-            while (--i >= 0)
-                set_bit (mc, Rdst, 0, state->trans[i].to);
+            if (mask & 15)
+            {
+                if (mask & 1)
+                {
+                    struct DFA_state *state = dfa->states[s];
+                    int i = state->tran_no;
+                    while (--i >= 0)
+                        set_bit (mc, Rdst, 0, state->trans[i].to);
+                }
+                if (mask & 2)
+                {
+                    struct DFA_state *state = dfa->states[s+1];
+                    int i = state->tran_no;
+                    while (--i >= 0)
+                        set_bit (mc, Rdst, 0, state->trans[i].to);
+                }
+                if (mask & 4)
+                {
+                    struct DFA_state *state = dfa->states[s+2];
+                    int i = state->tran_no;
+                    while (--i >= 0)
+                        set_bit (mc, Rdst, 0, state->trans[i].to);
+                }
+                if (mask & 8)
+                {
+                    struct DFA_state *state = dfa->states[s+3];
+                    int i = state->tran_no;
+                    while (--i >= 0)
+                        set_bit (mc, Rdst, 0, state->trans[i].to);
+                }
+            }
+            s += 4;
+            if (s >= dfa->no_states)
+                return;
+            mask >>= 4;
         }
+    }
 }
 
 static void or (MatchContext *mc, MatchWord *Rdst,
@@ -127,9 +230,9 @@ static void or (MatchContext *mc, MatchWord *Rdst,
 }
 
 
-static int go (MatchContext *mc, DFA_states *dfas, FILE *inf)
+static int go (MatchContext *mc, struct DFA *dfa, FILE *inf)
 {
-    MatchWord *Rj, *Rj1, *Rj_a, *Rj_b;
+    MatchWord *Rj, *Rj1, *Rj_a, *Rj_b, *Rj_c;
     int s, d, ch;
     int lineno = 1;
     char *infbuf;
@@ -142,17 +245,18 @@ static int go (MatchContext *mc, DFA_states *dfas, FILE *inf)
     Rj1 = icalloc (mc->n * (mc->range+1) * sizeof(*Rj));
     Rj_a = icalloc (mc->n * sizeof(*Rj));
     Rj_b = icalloc (mc->n * sizeof(*Rj));
+    Rj_c = icalloc (mc->n * sizeof(*Rj));
 
     set_bit (mc, Rj, 0, 0);
     for (d = 1; d<=mc->range; d++)
     {
         int s;
         memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj));
-        for (s = 0; s<dfas->no; s++)
+        for (s = 0; s<dfa->no_states; s++)
         {
             if (get_bit (mc, Rj, d-1, s))
             {
-                DFA_state *state = dfas->sortarray[s];
+                struct DFA_state *state = dfa->states[s];
                 int i = state->tran_no;
                 while (--i >= 0)
                     set_bit (mc, Rj, d, state->trans[i].to);
@@ -162,6 +266,8 @@ static int go (MatchContext *mc, DFA_states *dfas, FILE *inf)
     while ((ch = getc (inf)) != EOF)
     {
         MatchWord *Rj_t;
+        
+        infbuf[inf_ptr] = ch;
         if (ch == '\n')
         {
             if (no_match)
@@ -169,11 +275,11 @@ static int go (MatchContext *mc, DFA_states *dfas, FILE *inf)
                 int i = inf_ptr;
                 if (show_line)
                     printf ("%5d:", lineno);
-                while (infbuf[i] != '\n')
+                do
                 {
                     if (--i < 0)
                         i = INFBUF_SIZE-1;
-                }
+                } while (infbuf[i] != '\n');
                 do
                 {
                     if (++i == INFBUF_SIZE)
@@ -184,32 +290,29 @@ static int go (MatchContext *mc, DFA_states *dfas, FILE *inf)
             }
             lineno++;
         }
-        infbuf[inf_ptr++] = ch;
-        if (inf_ptr == INFBUF_SIZE)
+        if (++inf_ptr == INFBUF_SIZE)
             inf_ptr = 0;
-        mask_shift (mc, Rj1, Rj, dfas, ch);
+        mask_shift (mc, Rj1, Rj, dfa, ch);
         for (d = 1; d <= mc->range; d++)
         {
-            mask_shift (mc, Rj_b, Rj+d*mc->n, dfas, ch);/* 1 */
-
-            shift (mc, Rj_a, Rj+(d-1)*mc->n, dfas);     /* 2 */
+            mask_shift (mc, Rj_b, Rj+d*mc->n, dfa, ch);    /* 1 */
 
-            or (mc, Rj_a, Rj_a, Rj_b);                  /* 1,2 */
+            or (mc, Rj_a, Rj+(d-1)*mc->n, Rj1+(d-1)*mc->n); /* 2,3 */
 
-            shift (mc, Rj_b, Rj1+(d-1)*mc->n, dfas);    /* 3 */
+            shift (mc, Rj_c, Rj_a, dfa);
 
-            or (mc, Rj_a, Rj_a, Rj_b);                  /* 1,2,3 */
+            or (mc, Rj_a, Rj_b, Rj_c);                      /* 1,2,3*/
 
-            or (mc, Rj1+d*mc->n, Rj_a, Rj+(d-1)*mc->n); /* 1,2,3,4 */
+            or (mc, Rj1+d*mc->n, Rj_a, Rj+(d-1)*mc->n);     /* 1,2,3,4 */
         }
-        for (s = 0; s<dfas->no; s++)
+        for (s = 0; s<dfa->no_states; s++)
         {
-            if (dfas->sortarray[s]->rule_no)
+            if (dfa->states[s]->rule_no)
                 if (get_bit (mc, Rj1+mc->range*mc->n, 0, s))
                     no_match++;
         }
         for (d = 0; d <= mc->range; d++)
-            reset_bit (mc, Rj1+d*mc->n, 0, dfas->no);
+            reset_bit (mc, Rj1+d*mc->n, 0, dfa->no_states);
         Rj_t = Rj1;
         Rj1 = Rj;
         Rj = Rj_t;
@@ -218,11 +321,12 @@ static int go (MatchContext *mc, DFA_states *dfas, FILE *inf)
     ifree (Rj1);
     ifree (Rj_a);
     ifree (Rj_b);
+    ifree (Rj_c);
     ifree (infbuf);
     return 0;
 }
 
-static int grep_file (DFA_states *dfas, const char *fname, int range)
+static int grep_file (struct DFA *dfa, const char *fname, int range)
 {
     FILE *inf;
     MatchContext *mc;
@@ -232,16 +336,16 @@ static int grep_file (DFA_states *dfas, const char *fname, int range)
         inf = fopen (fname, "r");
         if (!inf)
         {
-            log (LOG_FATAL|LOG_ERRNO, "cannot open `%s'", fname);
+            logf (LOG_FATAL|LOG_ERRNO, "cannot open `%s'", fname);
             exit (1);
         }
     }
     else
         inf = stdin;
      
-    mc = mk_MatchContext (dfas, range);
+    mc = mk_MatchContext (dfa, range);
 
-    go (mc, dfas, inf);
+    go (mc, dfa, inf);
 
     if (fname)
         fclose (inf);
@@ -253,9 +357,9 @@ int main (int argc, char **argv)
     int ret;
     int range = 0;
     char *arg;
-    char *pattern = NULL;
-    DFA_states *dfas = NULL;
+    const char *pattern = NULL;
     int no_files = 0;
+    struct DFA *dfa = dfa_init();
 
     prog = argv[0];
     while ((ret = options ("nr:dsv:", argv, argc, &arg)) != -2)
@@ -265,27 +369,24 @@ int main (int argc, char **argv)
             if (!pattern)
             {
                 int i;
-                DFA *dfa = init_dfa();
                 pattern = arg;
-                i = parse_dfa (dfa, &pattern, dfa_thompson_chars);
+                i = dfa_parse (dfa, &pattern);
                 if (i || *pattern)
                 {
                     fprintf (stderr, "%s: illegal pattern\n", prog);
                     return 1;
                 }
-                dfa->root = dfa->top;
-                dfas = mk_dfas (dfa, 200);
-                rm_dfa (&dfa);
+                dfa_mkstate (dfa);
             }
             else
             {
                 no_files++;
-                grep_file (dfas, arg, range);
+                grep_file (dfa, arg, range);
             }
         }
         else if (ret == 'v')
         {
-            log_init (atoi(arg), prog, NULL);
+            log_init (log_mask_str(arg), prog, NULL);
         }
         else if (ret == 's')
         {
@@ -307,7 +408,7 @@ int main (int argc, char **argv)
         }
         else
         {
-            log (LOG_FATAL, "unknown option");
+            logf (LOG_FATAL, "Unknown option '-%s'", arg);
             exit (1);
         }
     }
@@ -319,7 +420,8 @@ int main (int argc, char **argv)
     }
     else if (no_files == 0)
     {
-        grep_file (dfas, NULL, range);
+        grep_file (dfa, NULL, range);
     }
+    dfa_delete (&dfa);
     return 0;
 }