![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to rawwalker.c1 CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / twig|
Return to rawwalker.c1 CVS log | Up to [Research Unix] / researchv10no / cmd / twig |
1.1 root 1: /*
2: * See Aho, Corasick Comm ACM 18:6, and Hoffman and O'Donell JACM 29:1
3: * for detail of the matching algorithm
4: */
5:
6: /* turn this flag on if your machine has a fast byte string zero operation */
7: /*#define BZERO 1*/
8: int mtDebug = 0;
9: int treedebug = 0;
10: extern int _machstep();
11: extern short int mtStart;
12: extern short int mtTable[], mtAccept[], mtMap[], mtPaths[], mtPathStart[];
13: #ifdef LINE_XREF
14: extern short int mtLine[];
15: #endif
16: extern NODEPTR mtGetNodes(), mtAction();
17: extern skeleton *_allocskel();
18: extern __match *_allocmatch();
19: extern __partial *_allocpartial();
20:
21: #define MPBLOCKSIZ 3000
22: __match *_mpblock[MPBLOCKSIZ], **_mpbtop;
23:
24: /*
25: * See sym.h in the preprocessor for details
26: * Basically used to support eh $%n$ construct.
27: */
28: __match **
29: _getleaves (mp, skp)
30: register __match *mp; register skeleton *skp;
31: {
32: skeleton *stack[MAXDEPTH];
33: skeleton **stp = stack;
34: register short int *sip = &mtPaths[mtPathStart[mp->tree]];
35: register __match **mmp = _mpbtop;
36: __match **mmp2 = mmp;
37: if((_mpbtop += *sip++ + 1) > &_mpblock[MPBLOCKSIZ]) {
38: printf ("ich: %d\n", _mpbtop-_mpblock);
39: assert(0);
40: }
41:
42: for(;;)
43: switch(*sip++) {
44: case ePUSH:
45: *stp++ = skp;
46: skp = skp->leftchild;
47: break;
48:
49: case eNEXT:
50: skp = skp->sibling;
51: break;
52:
53: case eEVAL:
54: if ((mp = skp->succ[M_DETAG(*sip++)])==NULL) abort();
55: *mmp++ = mp;
56: break;
57:
58: case ePOP:
59: skp = *--stp;
60: break;
61:
62: case eSTOP:
63: *mmp = NULL;
64: return (mmp2);
65: }
66: }
67:
68: _evalleaves (mpp)
69: register __match **mpp;
70: {
71: for (; *mpp!=NULL; mpp++) {
72: register __match *mp = *mpp;
73: _do (mp->skel, mp, 1);
74: }
75: }
76:
77:
78: _do(sp, winner, evalall)
79: skeleton *sp; register __match *winner; int evalall;
80: {
81: register __match **mpp;
82: register skeleton *skel = winner->skel;
83: if(winner==NULL) {
84: _prskel(sp, 0);
85: puts ("no winner");
86: return;
87: }
88: if(winner->mode==xDEFER || (evalall && winner->mode!=xTOPDOWN))
89: REORDER (winner->lleaves);
90: mtSetNodes (skel->parent, skel->nson,
91: skel->root=mtAction (winner->tree, winner->lleaves, sp));
92: }
93:
94: skeleton *
95: _walk(sp, ostate)
96: register skeleton *sp;
97: int ostate;
98: {
99: int state, nstate, nson;
100: register __partial *pp;
101: register __match *mp, *mp2;
102: register skeleton *nsp, *lastchild = NULL;
103: NODEPTR son, root;
104:
105: root = sp->root;
106: nson = 1; sp->mincost = INFINITY;
107: state = _machstep (ostate, root, mtValue(root));
108:
109: while((son = mtGetNodes(root, nson))!=NULL) {
110: nstate = _machstep (state, NULL, MV_BRANCH(nson));
111: nsp = _allocskel();
112: nsp->root = son;
113: nsp->parent = root;
114: nsp->nson = nson;
115: _walk(nsp, nstate);
116: if(COSTLESS(nsp->mincost, INFINITY)) {
117: assert (nsp->winner->mode==xREWRITE);
118: if (mtDebug || treedebug) {
119: printf ("rewrite\n");
120: _prskel (nsp, 0);
121: }
122: _do(nsp, nsp->winner, 0);
123: _freeskel(nsp);
124: continue;
125: }
126: _merge (sp, nsp);
127: if (lastchild==NULL) sp->leftchild = nsp;
128: else lastchild->sibling = nsp;
129: lastchild = nsp;
130: nson++;
131: }
132:
133: for (pp = sp->partial; pp < &sp->partial[sp->treecnt]; pp++)
134: if (pp->bits&01==1) {
135: mp = _allocmatch();
136: mp->tree = pp->treeno;
137: _addmatches (ostate, sp, mp);
138: }
139: if(son==NULL && nson==1)
140: _closure (state, ostate, sp);
141:
142: sp->rightchild = lastchild;
143: if (root==NULL) {
144: COST c; __match *win; int i; nsp = sp->leftchild;
145: c = INFINITY;
146: win = NULL;
147: for (i = 0; i < MAXLABELS; i++) {
148: mp = nsp->succ[i];
149: if (mp!=NULL && COSTLESS (mp->cost, c))
150: { c = mp->cost; win = mp; }
151: }
152: if (mtDebug || treedebug)
153: _prskel (nsp, 0);
154: _do (nsp, win, 0);
155: }
156: if (mtDebug)
157: _prskel (sp, 0);
158: return(sp);
159: }
160:
161: static short int _nodetab[MAXNDVAL], _labeltab[MAXLABELS];
162:
163: /*
164: * Convert the start state which has a large branching factor into
165: * a index table. This must be called before the matcher is used.
166: */
167: _matchinit()
168: {
169: short int *sp;
170: struct pair { short int val, where } *pp;
171: for (sp=_nodetab; sp < &_nodetab[MAXNDVAL]; sp++) *sp = HANG;
172: for (sp=_labeltab; sp < &_labeltab[MAXLABELS]; sp++) *sp = HANG;
173: sp = &mtTable[mtStart];
174: assert (*sp==TABLE);
175: for (pp = (struct pair *) ++sp; pp->val!=EOF; pp++) {
176: if (MI_NODE(pp->val))
177: _nodetab[M_DETAG(pp->val)] = pp->where;
178: else if (MI_LABEL(pp->val))
179: _labeltab[M_DETAG(pp->val)] = pp->where;
180: }
181: }
182:
183: int
184: _machstep(state, root, input)
185: short int state, input;
186: NODEPTR root;
187: {
188: register short int *stp = &mtTable[state];
189: int start = 0;
190: if (state==HANG)
191: return (input==(MV_BRANCH(1)) ? mtStart : HANG);
192: rescan:
193: if (stp==&mtTable[mtStart]) {
194: if (MI_NODE(input)) return(_nodetab[M_DETAG(input)]);
195: if (MI_LABEL(input)) return(_labeltab[M_DETAG(input)]);
196: }
197:
198: for(;;) {
199: if(*stp==ACCEPT) stp += 2;
200:
201: if(*stp==TABLE) {
202: stp++;
203: while(*stp!=EOT) {
204: if(input==*stp) {
205: return(*++stp);
206: }
207: stp += 2;
208: }
209: stp++;
210: }
211: if(*stp!=FAIL) {
212: if (start) return (HANG);
213: else { stp = &mtTable[mtStart]; start = 1; goto rescan;}
214: } else {
215: stp++;
216: stp = &mtTable[*stp];
217: goto rescan;
218: }
219: }
220: }
221:
222: _addmatches(ostate, sp, np)
223: int ostate;
224: register skeleton *sp;
225: register __match *np;
226: {
227: int label;
228: int state;
229: register __match *mp;
230:
231: label = mtMap[np->tree];
232:
233: /*
234: * this is a very poor substitute for good design of the DFA.
235: * What we need is a special case that allows any label to be accepted
236: * by the start state but we don't want the start state to recognize
237: * them after a failure.
238: */
239: state = _machstep(ostate, NULL, MV_LABEL(label));
240: if (ostate!=mtStart && state==HANG) {
241: _freematch(np);
242: return;
243: }
244:
245: np->lleaves = _getleaves (np, sp);
246: np->skel = sp;
247: if((np->mode = mtEvalCost(np, np->lleaves, sp))==xABORT)
248: {
249: _freematch(np);
250: return;
251: }
252:
253: /*
254: if(np->mode==xREWRITE && COSTLESS(np->cost, sp->mincost)) {
255: sp->mincost = np->cost;
256: sp->winner = np;
257: }
258: */
259: if ((mp = sp->succ[label])!=NULL) {
260: if (!COSTLESS (np->cost, mp->cost))
261: { _freematch(np); return; }
262: else _freematch(mp);
263: }
264: if(COSTLESS(np->cost,sp->mincost)) {
265: if(np->mode==xREWRITE) {
266: sp->mincost = np->cost; sp->winner = np; }
267: else { sp->mincost = INFINITY; sp->winner = NULL; }
268: }
269: sp->succ[label] = np;
270: _closure(state, ostate, sp);
271: }
272:
273: _closure(state, ostate, skp)
274: int state, ostate;
275: skeleton *skp;
276: {
277: register struct ap { short int tree, depth; } *ap;
278: short int *sp = &mtTable[state];
279: register __match *mp;
280:
281: if(state==HANG || *sp!=ACCEPT) return(NULL);
282:
283: for(ap = (struct ap *) &mtAccept[*++sp]; ap->tree!=-1; ap++)
284: if (ap->depth==0) {
285: mp = _allocmatch();
286: mp->tree = ap->tree;
287: _addmatches (ostate, skp, mp);
288: } else {
289: register __partial *pp, *lim = &skp->partial[skp->treecnt];
290: for(pp=skp->partial; pp < lim; pp++)
291: if(pp->treeno==ap->tree)
292: break;
293: if(pp==lim) {
294: skp->treecnt++;
295: pp->treeno = ap->tree;
296: pp->bits = (1<<(ap->depth));
297: } else pp->bits |= (1<<(ap->depth));
298: }
299: }
300:
301: _merge (old, new)
302: skeleton *old, *new;
303: {
304: register __partial *op = old->partial, *np = new->partial;
305: int nson = new->nson;
306: register __partial *lim = np + new->treecnt;
307: if (nson==1) {
308: old->treecnt = new->treecnt;
309: for(; np < lim; op++, np++) {
310: op->treeno = np->treeno;
311: op->bits = np->bits/2;
312: }
313: } else {
314: __partial *newer = _allocpartial();
315: register __partial *newerp = newer;
316: register int cnt;
317: lim = op+old->treecnt;
318: for(cnt=new->treecnt; cnt-- ; np++) {
319: for(op = old->partial; op < lim; op++)
320: if (op->treeno == np->treeno) {
321: newerp->treeno = op->treeno;
322: newerp++->bits = op->bits & (np->bits/2);
323: break;
324: }
325: }
326: _freepartial(old->partial);
327: old->partial = newer;
328: old->treecnt = newerp-newer;
329: }
330: }
331:
332: /* Save and Allocate Matches */
333: #define BLKF 100
334: __match *freep = NULL;
335: static int _count = 0;
336: static __match *_blockp = NULL;
337: #ifdef CHECKMEM
338: int x_matches, f_matches;
339: #endif
340:
341: __match *
342: _allocmatch()
343: {
344: __match *mp;
345:
346: if(freep!=NULL) {
347: mp = freep;
348: freep = ((__match *)((struct freeb *) freep)->next);
349: #ifdef CHECKMEM
350: f_matches--;
351: #endif
352: } else {
353: if(_count==0) {
354: _blockp = (__match *) malloc (BLKF*sizeof (__match));
355: _count = BLKF;
356: #ifdef CHECKMEM
357: x_matches += BLKF;
358: #endif
359: }
360: mp = _blockp++;
361: _count--;
362: }
363: return(mp);
364: }
365:
366: _freematch(mp)
367: __match *mp;
368: {
369: ((struct freeb *) mp)->next = (struct freeb *) freep;
370: freep = mp;
371: #ifdef CHECKMEM
372: f_matches++;
373: #endif
374: }
375:
376: static __partial *pfreep = NULL;
377: static int pcount = 0;
378: static __partial *pblock = NULL;
379: #ifdef CHECKMEM
380: static int x_partials, f_partials;
381: #endif
382:
383: __partial *
384: _allocpartial()
385: {
386: __partial *pp;
387: if (pfreep!=NULL) {
388: pp = pfreep;
389: pfreep = *(__partial **) pp;
390: #ifdef CHECKMEM
391: f_partials--;
392: #endif
393: } else {
394: if (pcount==0) {
395: pblock=(__partial *)malloc(BLKF*MAXTREES*sizeof(__partial));
396: pcount = BLKF;
397: #ifdef CHECKMEM
398: x_partials += BLKF;
399: #endif
400: }
401: pp = pblock;
402: pblock += MAXTREES;
403: pcount--;
404: }
405: return(pp);
406: }
407:
408: _freepartial(pp)
409: __partial *pp;
410: {
411: * (__partial **)pp = pfreep;
412: pfreep = pp;
413: #ifdef CHECKMEM
414: f_partials++;
415: #endif
416: }
417:
418:
419: /* storage management */
420: static skeleton *sfreep = NULL;
421: static int scount = 0;
422: static skeleton * sblock = NULL;
423:
424: skeleton *
425: _allocskel()
426: {
427: skeleton *sp;
428: int i;
429: if(sfreep!=NULL) {
430: sp = sfreep;
431: sfreep = sp->sibling;
432: } else {
433: if(scount==0) {
434: sblock = (skeleton *) malloc (BLKF * sizeof (skeleton));
435: scount = BLKF;
436: }
437: sp = sblock++;
438: scount--;
439: }
440: sp->sibling = NULL; sp->leftchild = NULL;
441: for (i=0; i < MAXLABELS; sp->succ[i++] = NULL);
442: sp->treecnt = 0;
443: sp->partial = _allocpartial();
444: return(sp);
445: }
446:
447: _freeskel(sp)
448: skeleton *sp;
449: {
450: int i;
451: __match *mp;
452: if(sp==NULL)
453: return;
454: if(sp->leftchild)
455: _freeskel(sp->leftchild);
456: if(sp->sibling)
457: _freeskel(sp->sibling);
458: _freepartial (sp->partial);
459: for (i=0; i < MAXLABELS; i++)
460: if ((mp = sp->succ[i])!=NULL) _freematch (mp);
461: sp->sibling = sfreep;
462: sfreep = sp;
463: }
464:
465: _match()
466: {
467: skeleton *sp;
468: sp = _allocskel();
469: sp->root = NULL;
470: _mpbtop = _mpblock;
471: _freeskel(_walk(sp, HANG));
472: #ifdef CHECKMEM
473: if(f_matches+_count!=x_matches) {
474: printf(";#m %d %d %d\n", f_matches, _count, x_matches);
475: assert(0);
476: }
477: if(f_partials+pcount!=x_partials) {
478: printf(";#p %d %d %d\n", f_partials, pcount, x_partials);
479: assert(0);
480: }
481: #endif
482: }
483:
484: NODEPTR
485: _mtG(root,i)
486: NODEPTR root;
487: int i;
488: {
489: int *p = &i;
490: while(*p!=-1)
491: root = mtGetNodes(root, *p++);
492: return(root);
493: }
494:
495: /* diagnostic routines */
496:
497: _prskel (skp, lvl)
498: skeleton *skp; int lvl;
499: {
500: int i; __match *mp;
501: __partial *pp;
502: if(skp==NULL) return;
503: for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
504: printf ("###\n");
505: for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
506: for (i = 0; i < MAXLABELS; i++)
507: if ((mp=skp->succ[i])!=NULL)
508: #ifdef LINE_XREF
509: printf ("[%d<%d> %d]", mp->tree,
510: mtLine[mp->tree], mp->cost);
511: #else
512: printf ("[%d %d]", mp->tree, mp->cost);
513: #endif
514: putchar('\n');
515: for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
516: for (i = 0, pp=skp->partial; i < skp->treecnt; i++, pp++)
517: #ifdef LINE_XREF
518: printf("(%d<%d> %x)", pp->treeno, mtLine[pp->treeno],
519: pp->bits);
520: #else
521: printf ("(%d %x)", pp->treeno, pp->bits);
522: #endif
523: putchar('\n');
524: fflush(stdout);
525: _prskel (skp->leftchild, lvl+2);
526: _prskel (skp->sibling, lvl);
527: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.