1 #include "grep.h" 2 3 void* 4 mal(int n) 5 { 6 static char *s; 7 static int m = 0; 8 void *v; 9 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 } 26 27 State* 28 sal(int n) 29 { 30 State *s; 31 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 } 38 39 Re* 40 ral(int type) 41 { 42 Re *r; 43 44 r = mal(sizeof(*r)); 45 r->type = type; 46 maxfollow++; 47 return r; 48 } 49 50 void 51 error(char *s) 52 { 53 fprint(2, "grep: internal error: %s\n", s); 54 exits(s); 55 } 56 57 int 58 countor(Re *r) 59 { 60 int n; 61 62 n = 0; 63 loop: 64 switch(r->type) { 65 case Tor: 66 n += countor(r->alt); 67 r = r->next; 68 goto loop; 69 case Tclass: 70 return n + r->hi - r->lo + 1; 71 } 72 return n; 73 } 74 75 Re* 76 oralloc(int t, Re *r, Re *b) 77 { 78 Re *a; 79 80 if(b == 0) 81 return r; 82 a = ral(t); 83 a->alt = r; 84 a->next = b; 85 return a; 86 } 87 88 void 89 case1(Re *c, Re *r) 90 { 91 int n; 92 93 loop: 94 switch(r->type) { 95 case Tor: 96 case1(c, r->alt); 97 r = r->next; 98 goto loop; 99 100 case Tclass: /* add to character */ 101 for(n=r->lo; n<=r->hi; n++) 102 c->cases[n] = oralloc(Tor, r->next, c->cases[n]); 103 break; 104 105 default: /* add everything unknown to next */ 106 c->next = oralloc(Talt, r, c->next); 107 break; 108 } 109 } 110 111 Re* 112 addcase(Re *r) 113 { 114 int i, n; 115 Re *a; 116 117 if(r->gen == gen) 118 return r; 119 r->gen = gen; 120 switch(r->type) { 121 default: 122 error("addcase"); 123 124 case Tor: 125 n = countor(r); 126 if(n >= Caselim) { 127 a = ral(Tcase); 128 a->cases = mal(256*sizeof(*a->cases)); 129 case1(a, r); 130 for(i=0; i<256; i++) 131 if(a->cases[i]) { 132 r = a->cases[i]; 133 if(countor(r) < n) 134 a->cases[i] = addcase(r); 135 } 136 return a; 137 } 138 return r; 139 140 case Talt: 141 r->next = addcase(r->next); 142 r->alt = addcase(r->alt); 143 return r; 144 145 case Tbegin: 146 case Tend: 147 case Tclass: 148 return r; 149 } 150 } 151 152 void 153 str2top(char *p) 154 { 155 Re2 oldtop; 156 157 oldtop = topre; 158 input = p; 159 if (*p == '\0') 160 yyerror("empty pattern"); /* can't be a file name here */ 161 if (!flags['f']) 162 pattern = p; 163 topre.beg = 0; 164 topre.end = 0; 165 yyparse(); 166 gen++; 167 if(topre.beg == 0) 168 yyerror("syntax"); 169 if(oldtop.beg) 170 topre = re2or(oldtop, topre); 171 } 172 173 void 174 appendnext(Re *a, Re *b) 175 { 176 Re *n; 177 178 while(n = a->next) 179 a = n; 180 a->next = b; 181 } 182 183 void 184 patchnext(Re *a, Re *b) 185 { 186 Re *n; 187 188 while(a) { 189 n = a->next; 190 a->next = b; 191 a = n; 192 } 193 } 194 195 int 196 getrec(void) 197 { 198 int c; 199 200 if(flags['f']) { 201 c = Bgetc(rein); 202 if(c <= 0) 203 return 0; 204 } else 205 c = *input++ & 0xff; 206 if(flags['i'] && c >= 'A' && c <= 'Z') 207 c += 'a'-'A'; 208 if(c == '\n') 209 lineno++; 210 return c; 211 } 212 213 Re2 214 re2cat(Re2 a, Re2 b) 215 { 216 Re2 c; 217 218 c.beg = a.beg; 219 c.end = b.end; 220 patchnext(a.end, b.beg); 221 return c; 222 } 223 224 Re2 225 re2star(Re2 a) 226 { 227 Re2 c; 228 229 c.beg = ral(Talt); 230 c.beg->alt = a.beg; 231 patchnext(a.end, c.beg); 232 c.end = c.beg; 233 return c; 234 } 235 236 Re2 237 re2or(Re2 a, Re2 b) 238 { 239 Re2 c; 240 241 c.beg = ral(Tor); 242 c.beg->alt = b.beg; 243 c.beg->next = a.beg; 244 c.end = b.end; 245 appendnext(c.end, a.end); 246 return c; 247 } 248 249 Re2 250 re2char(int c0, int c1) 251 { 252 Re2 c; 253 254 c.beg = ral(Tclass); 255 c.beg->lo = c0 & 0xff; 256 c.beg->hi = c1 & 0xff; 257 c.end = c.beg; 258 return c; 259 } 260 261 void 262 reprint1(Re *a) 263 { 264 int i, j; 265 266 loop: 267 if(a == 0) 268 return; 269 if(a->gen == gen) 270 return; 271 a->gen = gen; 272 print("%p: ", a); 273 switch(a->type) { 274 default: 275 print("type %d\n", a->type); 276 error("print1 type"); 277 278 case Tcase: 279 print("case ->%p\n", a->next); 280 for(i=0; i<256; i++) 281 if(a->cases[i]) { 282 for(j=i+1; j<256; j++) 283 if(a->cases[i] != a->cases[j]) 284 break; 285 print(" [%.2x-%.2x] ->%p\n", i, j-1, a->cases[i]); 286 i = j-1; 287 } 288 for(i=0; i<256; i++) 289 reprint1(a->cases[i]); 290 break; 291 292 case Tbegin: 293 print("^ ->%p\n", a->next); 294 break; 295 296 case Tend: 297 print("$ ->%p\n", a->next); 298 break; 299 300 case Tclass: 301 print("[%.2x-%.2x] ->%p\n", a->lo, a->hi, a->next); 302 break; 303 304 case Tor: 305 case Talt: 306 print("| %p ->%p\n", a->alt, a->next); 307 reprint1(a->alt); 308 break; 309 } 310 a = a->next; 311 goto loop; 312 } 313 314 void 315 reprint(char *s, Re *r) 316 { 317 print("%s:\n", s); 318 gen++; 319 reprint1(r); 320 print("\n\n"); 321 } 322