X-Git-Url: http://git.indexdata.com/?p=idzebra-moved-to-github.git;a=blobdiff_plain;f=dfa%2Fgrepper.c;h=590d78cd0f8b8d2947c7e5cbd6f5a28b2f54f859;hp=afc8927737774eed2eb41d9ff0daffb2e414ad99;hb=ecb3935e78cd9bcfdebafdee0834cfb1060d7b5e;hpb=25711769a3fb5c6bf0ab3eb9634bf74ba07dc48d diff --git a/dfa/grepper.c b/dfa/grepper.c index afc8927..590d78c 100644 --- a/dfa/grepper.c +++ b/dfa/grepper.c @@ -1,20 +1,34 @@ -/* - * Copyright (C) 1994, Index Data I/S - * All rights reserved. - * Sebastian Hammer, Adam Dickmeiss - * - * $Log: grepper.c,v $ - * Revision 1.1 1994-09-27 16:31:18 adam - * First version of grepper: grep with error correction. - * - */ +/* $Id: grepper.c,v 1.15 2006-05-10 08:13:18 adam Exp $ + Copyright (C) 1995-2005 + Index Data ApS + +This file is part of the Zebra server. + +Zebra 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 2, or (at your option) any later +version. + +Zebra 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 Zebra; see the file LICENSE.zebra. If not, write to the +Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. +*/ + + #include #include #include #include #include -#include +#include +#include #include #include "imalloc.h" @@ -32,7 +46,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 +56,8 @@ static inline void set_bit (MatchContext *mc, MatchWord *m, int ch, int state) m[mc->n * ch + wno] |= 1<n * ch + wno] &= ~(1<n * ch + wno] & (1<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; ino; i++) + for (i=0; ino_states; i++) { int j; - DFA_state *state = dfas->sortarray[i]; + struct DFA_state *state = dfa->states[i]; for (j=0; jtran_no; j++) { @@ -84,38 +102,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; in; i++) - Rdst[i] = 0; - for (s = 0; sno; s++) - if (get_bit (mc, Rsrc, 0, s)) + for (j = 1; jn; j++) + Rdst[j] = 0; + while (1) + { + mask = *Rsrc_p++; + for (j = 0; jsortarray[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; in; i++) - Rdst[i] = 0; - for (s = 0; sno; s++) - if (get_bit (mc, Rsrc, 0, s)) + int j, s = 0; + MatchWord *Rsrc_p = Rsrc, mask; + for (j = 0; jn; j++) + Rdst[j] = 0; + while (1) + { + mask = *Rsrc_p++; + for (j = 0; jsortarray[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 +224,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 +239,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; sno; s++) + for (s = 0; sno_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 +260,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 +269,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 +284,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; sno; s++) + for (s = 0; sno_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 +315,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 +330,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); + yaz_log (YLOG_FATAL|YLOG_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 +351,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 +363,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); + yaz_log_init (yaz_log_mask_str(arg), prog, NULL); } else if (ret == 's') { @@ -307,7 +402,7 @@ int main (int argc, char **argv) } else { - log (LOG_FATAL, "unknown option"); + yaz_log (YLOG_FATAL, "Unknown option '-%s'", arg); exit (1); } } @@ -319,7 +414,16 @@ 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; } +/* + * Local variables: + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + * vim: shiftwidth=4 tabstop=8 expandtab + */ +