17dd7cddfSDavid du Colombier #include "grep.h"
27dd7cddfSDavid du Colombier
37dd7cddfSDavid du Colombier void*
mal(int n)47dd7cddfSDavid du Colombier mal(int n)
57dd7cddfSDavid du Colombier {
67dd7cddfSDavid du Colombier static char *s;
77dd7cddfSDavid du Colombier static int m = 0;
87dd7cddfSDavid du Colombier void *v;
97dd7cddfSDavid du Colombier
107dd7cddfSDavid du Colombier n = (n+3) & ~3;
117dd7cddfSDavid du Colombier if(m < n) {
127dd7cddfSDavid du Colombier if(n > Nhunk) {
137dd7cddfSDavid du Colombier v = sbrk(n);
147dd7cddfSDavid du Colombier memset(v, 0, n);
157dd7cddfSDavid du Colombier return v;
167dd7cddfSDavid du Colombier }
177dd7cddfSDavid du Colombier s = sbrk(Nhunk);
187dd7cddfSDavid du Colombier m = Nhunk;
197dd7cddfSDavid du Colombier }
207dd7cddfSDavid du Colombier v = s;
217dd7cddfSDavid du Colombier s += n;
227dd7cddfSDavid du Colombier m -= n;
237dd7cddfSDavid du Colombier memset(v, 0, n);
247dd7cddfSDavid du Colombier return v;
257dd7cddfSDavid du Colombier }
267dd7cddfSDavid du Colombier
277dd7cddfSDavid du Colombier State*
sal(int n)287dd7cddfSDavid du Colombier sal(int n)
297dd7cddfSDavid du Colombier {
307dd7cddfSDavid du Colombier State *s;
317dd7cddfSDavid du Colombier
327dd7cddfSDavid du Colombier s = mal(sizeof(*s));
3380ee5cbfSDavid du Colombier // s->next = mal(256*sizeof(*s->next));
347dd7cddfSDavid du Colombier s->count = n;
357dd7cddfSDavid du Colombier s->re = mal(n*sizeof(*state0->re));
367dd7cddfSDavid du Colombier return s;
377dd7cddfSDavid du Colombier }
387dd7cddfSDavid du Colombier
397dd7cddfSDavid du Colombier Re*
ral(int type)407dd7cddfSDavid du Colombier ral(int type)
417dd7cddfSDavid du Colombier {
427dd7cddfSDavid du Colombier Re *r;
437dd7cddfSDavid du Colombier
447dd7cddfSDavid du Colombier r = mal(sizeof(*r));
457dd7cddfSDavid du Colombier r->type = type;
467dd7cddfSDavid du Colombier maxfollow++;
477dd7cddfSDavid du Colombier return r;
487dd7cddfSDavid du Colombier }
497dd7cddfSDavid du Colombier
507dd7cddfSDavid du Colombier void
error(char * s)517dd7cddfSDavid du Colombier error(char *s)
527dd7cddfSDavid du Colombier {
537dd7cddfSDavid du Colombier fprint(2, "grep: internal error: %s\n", s);
547dd7cddfSDavid du Colombier exits(s);
557dd7cddfSDavid du Colombier }
567dd7cddfSDavid du Colombier
577dd7cddfSDavid du Colombier int
countor(Re * r)587dd7cddfSDavid du Colombier countor(Re *r)
597dd7cddfSDavid du Colombier {
607dd7cddfSDavid du Colombier int n;
617dd7cddfSDavid du Colombier
627dd7cddfSDavid du Colombier n = 0;
637dd7cddfSDavid du Colombier loop:
647dd7cddfSDavid du Colombier switch(r->type) {
657dd7cddfSDavid du Colombier case Tor:
667dd7cddfSDavid du Colombier n += countor(r->alt);
677dd7cddfSDavid du Colombier r = r->next;
687dd7cddfSDavid du Colombier goto loop;
697dd7cddfSDavid du Colombier case Tclass:
707dd7cddfSDavid du Colombier return n + r->hi - r->lo + 1;
717dd7cddfSDavid du Colombier }
727dd7cddfSDavid du Colombier return n;
737dd7cddfSDavid du Colombier }
747dd7cddfSDavid du Colombier
757dd7cddfSDavid du Colombier Re*
oralloc(int t,Re * r,Re * b)767dd7cddfSDavid du Colombier oralloc(int t, Re *r, Re *b)
777dd7cddfSDavid du Colombier {
787dd7cddfSDavid du Colombier Re *a;
797dd7cddfSDavid du Colombier
807dd7cddfSDavid du Colombier if(b == 0)
817dd7cddfSDavid du Colombier return r;
827dd7cddfSDavid du Colombier a = ral(t);
837dd7cddfSDavid du Colombier a->alt = r;
847dd7cddfSDavid du Colombier a->next = b;
857dd7cddfSDavid du Colombier return a;
867dd7cddfSDavid du Colombier }
877dd7cddfSDavid du Colombier
887dd7cddfSDavid du Colombier void
case1(Re * c,Re * r)897dd7cddfSDavid du Colombier case1(Re *c, Re *r)
907dd7cddfSDavid du Colombier {
917dd7cddfSDavid du Colombier int n;
927dd7cddfSDavid du Colombier
937dd7cddfSDavid du Colombier loop:
947dd7cddfSDavid du Colombier switch(r->type) {
957dd7cddfSDavid du Colombier case Tor:
967dd7cddfSDavid du Colombier case1(c, r->alt);
977dd7cddfSDavid du Colombier r = r->next;
987dd7cddfSDavid du Colombier goto loop;
997dd7cddfSDavid du Colombier
1007dd7cddfSDavid du Colombier case Tclass: /* add to character */
1017dd7cddfSDavid du Colombier for(n=r->lo; n<=r->hi; n++)
1027dd7cddfSDavid du Colombier c->cases[n] = oralloc(Tor, r->next, c->cases[n]);
1037dd7cddfSDavid du Colombier break;
1047dd7cddfSDavid du Colombier
1057dd7cddfSDavid du Colombier default: /* add everything unknown to next */
1067dd7cddfSDavid du Colombier c->next = oralloc(Talt, r, c->next);
1077dd7cddfSDavid du Colombier break;
1087dd7cddfSDavid du Colombier }
1097dd7cddfSDavid du Colombier }
1107dd7cddfSDavid du Colombier
1117dd7cddfSDavid du Colombier Re*
addcase(Re * r)1127dd7cddfSDavid du Colombier addcase(Re *r)
1137dd7cddfSDavid du Colombier {
1147dd7cddfSDavid du Colombier int i, n;
1157dd7cddfSDavid du Colombier Re *a;
1167dd7cddfSDavid du Colombier
1177dd7cddfSDavid du Colombier if(r->gen == gen)
1187dd7cddfSDavid du Colombier return r;
1197dd7cddfSDavid du Colombier r->gen = gen;
1207dd7cddfSDavid du Colombier switch(r->type) {
1217dd7cddfSDavid du Colombier default:
1227dd7cddfSDavid du Colombier error("addcase");
1237dd7cddfSDavid du Colombier
1247dd7cddfSDavid du Colombier case Tor:
1257dd7cddfSDavid du Colombier n = countor(r);
1267dd7cddfSDavid du Colombier if(n >= Caselim) {
1277dd7cddfSDavid du Colombier a = ral(Tcase);
1287dd7cddfSDavid du Colombier a->cases = mal(256*sizeof(*a->cases));
1297dd7cddfSDavid du Colombier case1(a, r);
1307dd7cddfSDavid du Colombier for(i=0; i<256; i++)
1317dd7cddfSDavid du Colombier if(a->cases[i]) {
1327dd7cddfSDavid du Colombier r = a->cases[i];
1337dd7cddfSDavid du Colombier if(countor(r) < n)
1347dd7cddfSDavid du Colombier a->cases[i] = addcase(r);
1357dd7cddfSDavid du Colombier }
1367dd7cddfSDavid du Colombier return a;
1377dd7cddfSDavid du Colombier }
1387dd7cddfSDavid du Colombier return r;
1397dd7cddfSDavid du Colombier
1407dd7cddfSDavid du Colombier case Talt:
1417dd7cddfSDavid du Colombier r->next = addcase(r->next);
1427dd7cddfSDavid du Colombier r->alt = addcase(r->alt);
1437dd7cddfSDavid du Colombier return r;
1447dd7cddfSDavid du Colombier
1457dd7cddfSDavid du Colombier case Tbegin:
1467dd7cddfSDavid du Colombier case Tend:
1477dd7cddfSDavid du Colombier case Tclass:
1487dd7cddfSDavid du Colombier return r;
1497dd7cddfSDavid du Colombier }
1507dd7cddfSDavid du Colombier }
1517dd7cddfSDavid du Colombier
1527dd7cddfSDavid du Colombier void
str2top(char * p)1537dd7cddfSDavid du Colombier str2top(char *p)
1547dd7cddfSDavid du Colombier {
1557dd7cddfSDavid du Colombier Re2 oldtop;
1567dd7cddfSDavid du Colombier
1577dd7cddfSDavid du Colombier oldtop = topre;
1587dd7cddfSDavid du Colombier input = p;
1591052a86aSDavid du Colombier if (*p == '\0')
160*82bf8890SDavid du Colombier yyerror("empty pattern"); /* can't be a file name here */
161*82bf8890SDavid du Colombier if (!flags['f'])
162*82bf8890SDavid du Colombier pattern = p;
1637dd7cddfSDavid du Colombier topre.beg = 0;
1647dd7cddfSDavid du Colombier topre.end = 0;
1657dd7cddfSDavid du Colombier yyparse();
1667dd7cddfSDavid du Colombier gen++;
1677dd7cddfSDavid du Colombier if(topre.beg == 0)
1687dd7cddfSDavid du Colombier yyerror("syntax");
1697dd7cddfSDavid du Colombier if(oldtop.beg)
1707dd7cddfSDavid du Colombier topre = re2or(oldtop, topre);
1717dd7cddfSDavid du Colombier }
1727dd7cddfSDavid du Colombier
1737dd7cddfSDavid du Colombier void
appendnext(Re * a,Re * b)1747dd7cddfSDavid du Colombier appendnext(Re *a, Re *b)
1757dd7cddfSDavid du Colombier {
1767dd7cddfSDavid du Colombier Re *n;
1777dd7cddfSDavid du Colombier
1787dd7cddfSDavid du Colombier while(n = a->next)
1797dd7cddfSDavid du Colombier a = n;
1807dd7cddfSDavid du Colombier a->next = b;
1817dd7cddfSDavid du Colombier }
1827dd7cddfSDavid du Colombier
1837dd7cddfSDavid du Colombier void
patchnext(Re * a,Re * b)1847dd7cddfSDavid du Colombier patchnext(Re *a, Re *b)
1857dd7cddfSDavid du Colombier {
1867dd7cddfSDavid du Colombier Re *n;
1877dd7cddfSDavid du Colombier
1887dd7cddfSDavid du Colombier while(a) {
1897dd7cddfSDavid du Colombier n = a->next;
1907dd7cddfSDavid du Colombier a->next = b;
1917dd7cddfSDavid du Colombier a = n;
1927dd7cddfSDavid du Colombier }
1937dd7cddfSDavid du Colombier }
1947dd7cddfSDavid du Colombier
1957dd7cddfSDavid du Colombier int
getrec(void)1967dd7cddfSDavid du Colombier getrec(void)
1977dd7cddfSDavid du Colombier {
1987dd7cddfSDavid du Colombier int c;
1997dd7cddfSDavid du Colombier
2007dd7cddfSDavid du Colombier if(flags['f']) {
2017dd7cddfSDavid du Colombier c = Bgetc(rein);
2027dd7cddfSDavid du Colombier if(c <= 0)
2037dd7cddfSDavid du Colombier return 0;
2047dd7cddfSDavid du Colombier } else
2057dd7cddfSDavid du Colombier c = *input++ & 0xff;
2067dd7cddfSDavid du Colombier if(flags['i'] && c >= 'A' && c <= 'Z')
2077dd7cddfSDavid du Colombier c += 'a'-'A';
2087dd7cddfSDavid du Colombier if(c == '\n')
2097dd7cddfSDavid du Colombier lineno++;
2107dd7cddfSDavid du Colombier return c;
2117dd7cddfSDavid du Colombier }
2127dd7cddfSDavid du Colombier
2137dd7cddfSDavid du Colombier Re2
re2cat(Re2 a,Re2 b)2147dd7cddfSDavid du Colombier re2cat(Re2 a, Re2 b)
2157dd7cddfSDavid du Colombier {
2167dd7cddfSDavid du Colombier Re2 c;
2177dd7cddfSDavid du Colombier
2187dd7cddfSDavid du Colombier c.beg = a.beg;
2197dd7cddfSDavid du Colombier c.end = b.end;
2207dd7cddfSDavid du Colombier patchnext(a.end, b.beg);
2217dd7cddfSDavid du Colombier return c;
2227dd7cddfSDavid du Colombier }
2237dd7cddfSDavid du Colombier
2247dd7cddfSDavid du Colombier Re2
re2star(Re2 a)2257dd7cddfSDavid du Colombier re2star(Re2 a)
2267dd7cddfSDavid du Colombier {
2277dd7cddfSDavid du Colombier Re2 c;
2287dd7cddfSDavid du Colombier
2297dd7cddfSDavid du Colombier c.beg = ral(Talt);
2307dd7cddfSDavid du Colombier c.beg->alt = a.beg;
2317dd7cddfSDavid du Colombier patchnext(a.end, c.beg);
2327dd7cddfSDavid du Colombier c.end = c.beg;
2337dd7cddfSDavid du Colombier return c;
2347dd7cddfSDavid du Colombier }
2357dd7cddfSDavid du Colombier
2367dd7cddfSDavid du Colombier Re2
re2or(Re2 a,Re2 b)2377dd7cddfSDavid du Colombier re2or(Re2 a, Re2 b)
2387dd7cddfSDavid du Colombier {
2397dd7cddfSDavid du Colombier Re2 c;
2407dd7cddfSDavid du Colombier
2417dd7cddfSDavid du Colombier c.beg = ral(Tor);
2427dd7cddfSDavid du Colombier c.beg->alt = b.beg;
2437dd7cddfSDavid du Colombier c.beg->next = a.beg;
2447dd7cddfSDavid du Colombier c.end = b.end;
2457dd7cddfSDavid du Colombier appendnext(c.end, a.end);
2467dd7cddfSDavid du Colombier return c;
2477dd7cddfSDavid du Colombier }
2487dd7cddfSDavid du Colombier
2497dd7cddfSDavid du Colombier Re2
re2char(int c0,int c1)2507dd7cddfSDavid du Colombier re2char(int c0, int c1)
2517dd7cddfSDavid du Colombier {
2527dd7cddfSDavid du Colombier Re2 c;
2537dd7cddfSDavid du Colombier
2547dd7cddfSDavid du Colombier c.beg = ral(Tclass);
2557dd7cddfSDavid du Colombier c.beg->lo = c0 & 0xff;
2567dd7cddfSDavid du Colombier c.beg->hi = c1 & 0xff;
2577dd7cddfSDavid du Colombier c.end = c.beg;
2587dd7cddfSDavid du Colombier return c;
2597dd7cddfSDavid du Colombier }
2607dd7cddfSDavid du Colombier
2617dd7cddfSDavid du Colombier void
reprint1(Re * a)2627dd7cddfSDavid du Colombier reprint1(Re *a)
2637dd7cddfSDavid du Colombier {
2647dd7cddfSDavid du Colombier int i, j;
2657dd7cddfSDavid du Colombier
2667dd7cddfSDavid du Colombier loop:
2677dd7cddfSDavid du Colombier if(a == 0)
2687dd7cddfSDavid du Colombier return;
2697dd7cddfSDavid du Colombier if(a->gen == gen)
2707dd7cddfSDavid du Colombier return;
2717dd7cddfSDavid du Colombier a->gen = gen;
2727dd7cddfSDavid du Colombier print("%p: ", a);
2737dd7cddfSDavid du Colombier switch(a->type) {
2747dd7cddfSDavid du Colombier default:
2757dd7cddfSDavid du Colombier print("type %d\n", a->type);
2767dd7cddfSDavid du Colombier error("print1 type");
2777dd7cddfSDavid du Colombier
2787dd7cddfSDavid du Colombier case Tcase:
2797dd7cddfSDavid du Colombier print("case ->%p\n", a->next);
2807dd7cddfSDavid du Colombier for(i=0; i<256; i++)
2817dd7cddfSDavid du Colombier if(a->cases[i]) {
2827dd7cddfSDavid du Colombier for(j=i+1; j<256; j++)
2837dd7cddfSDavid du Colombier if(a->cases[i] != a->cases[j])
2847dd7cddfSDavid du Colombier break;
2857dd7cddfSDavid du Colombier print(" [%.2x-%.2x] ->%p\n", i, j-1, a->cases[i]);
2867dd7cddfSDavid du Colombier i = j-1;
2877dd7cddfSDavid du Colombier }
2887dd7cddfSDavid du Colombier for(i=0; i<256; i++)
2897dd7cddfSDavid du Colombier reprint1(a->cases[i]);
2907dd7cddfSDavid du Colombier break;
2917dd7cddfSDavid du Colombier
2927dd7cddfSDavid du Colombier case Tbegin:
2937dd7cddfSDavid du Colombier print("^ ->%p\n", a->next);
2947dd7cddfSDavid du Colombier break;
2957dd7cddfSDavid du Colombier
2967dd7cddfSDavid du Colombier case Tend:
2977dd7cddfSDavid du Colombier print("$ ->%p\n", a->next);
2987dd7cddfSDavid du Colombier break;
2997dd7cddfSDavid du Colombier
3007dd7cddfSDavid du Colombier case Tclass:
3017dd7cddfSDavid du Colombier print("[%.2x-%.2x] ->%p\n", a->lo, a->hi, a->next);
3027dd7cddfSDavid du Colombier break;
3037dd7cddfSDavid du Colombier
3047dd7cddfSDavid du Colombier case Tor:
3057dd7cddfSDavid du Colombier case Talt:
3067dd7cddfSDavid du Colombier print("| %p ->%p\n", a->alt, a->next);
3077dd7cddfSDavid du Colombier reprint1(a->alt);
3087dd7cddfSDavid du Colombier break;
3097dd7cddfSDavid du Colombier }
3107dd7cddfSDavid du Colombier a = a->next;
3117dd7cddfSDavid du Colombier goto loop;
3127dd7cddfSDavid du Colombier }
3137dd7cddfSDavid du Colombier
3147dd7cddfSDavid du Colombier void
reprint(char * s,Re * r)3157dd7cddfSDavid du Colombier reprint(char *s, Re *r)
3167dd7cddfSDavid du Colombier {
3177dd7cddfSDavid du Colombier print("%s:\n", s);
3187dd7cddfSDavid du Colombier gen++;
3197dd7cddfSDavid du Colombier reprint1(r);
3207dd7cddfSDavid du Colombier print("\n\n");
3217dd7cddfSDavid du Colombier }
322