From: Adam Dickmeiss Date: Mon, 3 Oct 1994 17:22:17 +0000 (+0000) Subject: Optimization of grepper. X-Git-Tag: ZEBRA.1.0~827 X-Git-Url: http://git.indexdata.com/?p=idzebra-moved-to-github.git;a=commitdiff_plain;h=c1ecb833ce85c0dc62550a4183975c7397bd4f7c Optimization of grepper. --- diff --git a/dfa/Makefile b/dfa/Makefile index b0ad65d..96de1f6 100644 --- a/dfa/Makefile +++ b/dfa/Makefile @@ -1,7 +1,7 @@ # Copyright (C) 1994, Index Data I/S # All rights reserved. # Sebastian Hammer, Adam Dickmeiss -# $Id: Makefile,v 1.3 1994-09-27 16:31:17 adam Exp $ +# $Id: Makefile,v 1.4 1994-10-03 17:22:17 adam Exp $ SHELL=/bin/sh INCLUDE=-I../include @@ -49,13 +49,15 @@ depend: depend2 depend1: mv Makefile Makefile.tmp $(YACC) $(YFLAGS) regexp.y + mv y.tab.c regexp.c sed '/^#Depend/q' Makefile - $(CPP) -M $(DEFS) *.c |sed 's/y\.tab\.o/regexp.o/g'|sed 's/y\.tab\.c/regexp.y/g' >>Makefile + $(CPP) -M $(DEFS) *.c |sed 's/regexp\.c/regexp.y/g' >>Makefile -rm Makefile.tmp depend2: $(YACC) $(YFLAGS) regexp.y - $(CPP) -M $(DEFS) *.c |sed 's/y\.tab\.o/regexp.o/g'|sed 's/y\.tab\.c/regexp.y/g' >.depend + mv y.tab.c regexp.c + $(CPP) -M $(DEFS) *.c |sed 's/regexp\.c/regexp.y/g' >.depend ifeq (.depend,$(wildcard .depend)) include .depend diff --git a/dfa/grepper.c b/dfa/grepper.c index afc8927..cb55b53 100644 --- a/dfa/grepper.c +++ b/dfa/grepper.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: grepper.c,v $ - * Revision 1.1 1994-09-27 16:31:18 adam + * 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. * */ @@ -32,7 +35,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 +45,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; 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) + { + 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 & 2) + { + DFA_state *state = dfas->sortarray[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) + { + DFA_state *state = dfas->sortarray[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) + { + DFA_state *state = dfas->sortarray[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 >= dfas->no) + return; + mask >>= 4; } + } } static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc, DFA_states *dfas) { - 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) + { + 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 & 2) + { + DFA_state *state = dfas->sortarray[s+1]; + int i = state->tran_no; + while (--i >= 0) + set_bit (mc, Rdst, 0, state->trans[i].to); + } + if (mask & 4) + { + DFA_state *state = dfas->sortarray[s+2]; + int i = state->tran_no; + while (--i >= 0) + set_bit (mc, Rdst, 0, state->trans[i].to); + } + if (mask & 8) + { + DFA_state *state = dfas->sortarray[s+3]; + int i = state->tran_no; + while (--i >= 0) + set_bit (mc, Rdst, 0, state->trans[i].to); + } + } + s += 4; + if (s >= dfas->no) + return; + mask >>= 4; } + } } static void or (MatchContext *mc, MatchWord *Rdst, @@ -129,7 +215,7 @@ static void or (MatchContext *mc, MatchWord *Rdst, static int go (MatchContext *mc, DFA_states *dfas, 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,6 +228,7 @@ 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++) @@ -162,6 +249,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 +258,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,23 +273,20 @@ 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); 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, dfas, 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, dfas); - 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++) { @@ -218,6 +304,7 @@ 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; } @@ -285,7 +372,7 @@ int main (int argc, char **argv) } else if (ret == 'v') { - log_init (atoi(arg), prog, NULL); + log_init (log_mask_str(arg), prog, NULL); } else if (ret == 's') { diff --git a/dfa/lexer.c b/dfa/lexer.c index 9729d9e..998b69f 100644 --- a/dfa/lexer.c +++ b/dfa/lexer.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: lexer.c,v $ - * Revision 1.2 1994-09-27 16:31:20 adam + * Revision 1.3 1994-10-03 17:22:19 adam + * Optimization of grepper. + * + * Revision 1.2 1994/09/27 16:31:20 adam * First version of grepper: grep with error correction. * * Revision 1.1 1994/09/26 10:16:55 adam @@ -58,7 +61,7 @@ static int lexer_options (int argc, char **argv) case 'V': fprintf (stderr, "%s: %s %s\n", prog, __DATE__, __TIME__); continue; - case 'v': + case 's': dfa_verbose = 1; continue; case 't': @@ -118,7 +121,7 @@ int main (int argc, char **argv) if (argc < 2) { - fprintf (stderr, "usage\n %s [-c] [-V] [-v] [-t] [-d[stf]] file\n", + fprintf (stderr, "usage\n %s [-c] [-V] [-s] [-t] [-d[stf]] file\n", prog); return 1; }