Blob
1 #include "grep.h"3 void*4 mal(int n)5 {6 static char *s;7 static int m = 0;8 void *v;10 n = (n+3) & ~3;11 if(m < n) {12 if(n > Nhunk) {13 v = sbrk(n);14 memset(v, 0, n);15 return v;16 }17 s = sbrk(Nhunk);18 m = Nhunk;19 }20 v = s;21 s += n;22 m -= n;23 memset(v, 0, n);24 return v;25 }27 State*28 sal(int n)29 {30 State *s;32 s = mal(sizeof(*s));33 /* s->next = mal(256*sizeof(*s->next)); */34 s->count = n;35 s->re = mal(n*sizeof(*state0->re));36 return s;37 }39 Re*40 ral(int type)41 {42 Re *r;44 r = mal(sizeof(*r));45 r->type = type;46 maxfollow++;47 return r;48 }50 void51 error(char *s)52 {53 fprint(2, "grep: internal error: %s\n", s);54 exits(s);55 }57 int58 countor(Re *r)59 {60 int n;62 n = 0;63 loop:64 switch(r->type) {65 case Tor:66 n += countor(r->u.alt);67 r = r->next;68 goto loop;69 case Tclass:70 return n + r->u.x.hi - r->u.x.lo + 1;71 }72 return n;73 }75 Re*76 oralloc(int t, Re *r, Re *b)77 {78 Re *a;80 if(b == 0)81 return r;82 a = ral(t);83 a->u.alt = r;84 a->next = b;85 return a;86 }88 void89 case1(Re *c, Re *r)90 {91 int n;93 loop:94 switch(r->type) {95 case Tor:96 case1(c, r->u.alt);97 r = r->next;98 goto loop;100 case Tclass: /* add to character */101 for(n=r->u.x.lo; n<=r->u.x.hi; n++)102 c->u.cases[n] = oralloc(Tor, r->next, c->u.cases[n]);103 break;105 default: /* add everything unknown to next */106 c->next = oralloc(Talt, r, c->next);107 break;108 }109 }111 Re*112 addcase(Re *r)113 {114 int i, n;115 Re *a;117 if(r->gen == gen)118 return r;119 r->gen = gen;120 switch(r->type) {121 default:122 error("addcase");124 case Tor:125 n = countor(r);126 if(n >= Caselim) {127 a = ral(Tcase);128 a->u.cases = mal(256*sizeof(*a->u.cases));129 case1(a, r);130 for(i=0; i<256; i++)131 if(a->u.cases[i]) {132 r = a->u.cases[i];133 if(countor(r) < n)134 a->u.cases[i] = addcase(r);135 }136 return a;137 }138 return r;140 case Talt:141 r->next = addcase(r->next);142 r->u.alt = addcase(r->u.alt);143 return r;145 case Tbegin:146 case Tend:147 case Tclass:148 return r;149 }150 }152 void153 str2top(char *p)154 {155 Re2 oldtop;157 oldtop = topre;158 input = p;159 topre.beg = 0;160 topre.end = 0;161 yyparse();162 gen++;163 if(topre.beg == 0)164 yyerror("syntax");165 if(oldtop.beg)166 topre = re2or(oldtop, topre);167 }169 void170 appendnext(Re *a, Re *b)171 {172 Re *n;174 while(n = a->next)175 a = n;176 a->next = b;177 }179 void180 patchnext(Re *a, Re *b)181 {182 Re *n;184 while(a) {185 n = a->next;186 a->next = b;187 a = n;188 }189 }191 int192 getrec(void)193 {194 int c;196 if(flags['f']) {197 c = Bgetc(rein);198 if(c <= 0)199 return 0;200 } else201 c = *input++ & 0xff;202 if(flags['i'] && c >= 'A' && c <= 'Z')203 c += 'a'-'A';204 if(c == '\n')205 lineno++;206 return c;207 }209 Re2210 re2cat(Re2 a, Re2 b)211 {212 Re2 c;214 c.beg = a.beg;215 c.end = b.end;216 patchnext(a.end, b.beg);217 return c;218 }220 Re2221 re2star(Re2 a)222 {223 Re2 c;225 c.beg = ral(Talt);226 c.beg->u.alt = a.beg;227 patchnext(a.end, c.beg);228 c.end = c.beg;229 return c;230 }232 Re2233 re2or(Re2 a, Re2 b)234 {235 Re2 c;237 c.beg = ral(Tor);238 c.beg->u.alt = b.beg;239 c.beg->next = a.beg;240 c.end = b.end;241 appendnext(c.end, a.end);242 return c;243 }245 Re2246 re2char(int c0, int c1)247 {248 Re2 c;250 c.beg = ral(Tclass);251 c.beg->u.x.lo = c0 & 0xff;252 c.beg->u.x.hi = c1 & 0xff;253 c.end = c.beg;254 return c;255 }257 void258 reprint1(Re *a)259 {260 int i, j;262 loop:263 if(a == 0)264 return;265 if(a->gen == gen)266 return;267 a->gen = gen;268 print("%p: ", a);269 switch(a->type) {270 default:271 print("type %d\n", a->type);272 error("print1 type");274 case Tcase:275 print("case ->%p\n", a->next);276 for(i=0; i<256; i++)277 if(a->u.cases[i]) {278 for(j=i+1; j<256; j++)279 if(a->u.cases[i] != a->u.cases[j])280 break;281 print(" [%.2x-%.2x] ->%p\n", i, j-1, a->u.cases[i]);282 i = j-1;283 }284 for(i=0; i<256; i++)285 reprint1(a->u.cases[i]);286 break;288 case Tbegin:289 print("^ ->%p\n", a->next);290 break;292 case Tend:293 print("$ ->%p\n", a->next);294 break;296 case Tclass:297 print("[%.2x-%.2x] ->%p\n", a->u.x.lo, a->u.x.hi, a->next);298 break;300 case Tor:301 case Talt:302 print("| %p ->%p\n", a->u.alt, a->next);303 reprint1(a->u.alt);304 break;305 }306 a = a->next;307 goto loop;308 }310 void311 reprint(char *s, Re *r)312 {313 print("%s:\n", s);314 gen++;315 reprint1(r);316 print("\n\n");317 }