9base

revived minimalist port of Plan 9 userland to Unix
git clone git://git.suckless.org/9base
Log | Files | Refs | README | LICENSE

sub.c (4041B)


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