Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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 
}