sub.c - 9base - revived minimalist port of Plan 9 userland to Unix
(HTM) git clone git://git.suckless.org/9base
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) 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 }