![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to rawwalker.ex 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.ex 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, qstate;
229: register __match *mp;
230: static short int quick[128][MAXLABELS];
231: static short int qtag[128][MAXLABELS];
232:
233: label = mtMap[np->tree];
234:
235: /*
236: * The following lines replace the line:
237: *
238: * state = _machstep(ostate, NULL, MV_LABEL(label));
239: *
240: * Statistics show that a large percentage (approx 2/3) of calls to
241: * _machstep occur in this function. The lines below attempt
242: * to reduce the number of these calls by using an unsophisticated
243: * but apparently adequate caching scheme.
244: */
245: qstate = ((ostate>>2)+2)&0177;
246: if(ostate != qtag[qstate][label]) {
247: state = _machstep(ostate, NULL, MV_LABEL(label));
248: quick[qstate][label] = state;
249: qtag[qstate][label] = ostate;
250: } else state = quick[qstate][label];
251:
252: /*
253: * this is a very poor substitute for good design of the DFA.
254: * What we need is a special case that allows any label to be accepted
255: * by the start state but we don't want the start state to recognize
256: * them after a failure.
257: */
258: if (ostate!=mtStart && state==HANG) {
259: _freematch(np);
260: return;
261: }
262:
263: np->lleaves = _getleaves (np, sp);
264: np->skel = sp;
265: if((np->mode = mtEvalCost(np, np->lleaves, sp))==xABORT)
266: {
267: _freematch(np);
268: return;
269: }
270:
271: if ((mp = sp->succ[label])!=NULL) {
272: if (!COSTLESS (np->cost, mp->cost))
273: { _freematch(np); return; }
274: else _freematch(mp);
275: }
276: if(COSTLESS(np->cost,sp->mincost)) {
277: if(np->mode==xREWRITE) {
278: sp->mincost = np->cost; sp->winner = np; }
279: else { sp->mincost = INFINITY; sp->winner = NULL; }
280: }
281: sp->succ[label] = np;
282: _closure(state, ostate, sp);
283: }
284:
285: _closure(state, ostate, skp)
286: int state, ostate;
287: skeleton *skp;
288: {
289: register struct ap { short int tree, depth; } *ap;
290: short int *sp = &mtTable[state];
291: register __match *mp;
292:
293: if(state==HANG || *sp!=ACCEPT) return(NULL);
294:
295: for(ap = (struct ap *) &mtAccept[*++sp]; ap->tree!=-1; ap++)
296: if (ap->depth==0) {
297: mp = _allocmatch();
298: mp->tree = ap->tree;
299: _addmatches (ostate, skp, mp);
300: } else {
301: register __partial *pp, *lim = &skp->partial[skp->treecnt];
302: for(pp=skp->partial; pp < lim; pp++)
303: if(pp->treeno==ap->tree)
304: break;
305: if(pp==lim) {
306: skp->treecnt++;
307: pp->treeno = ap->tree;
308: pp->bits = (1<<(ap->depth));
309: } else pp->bits |= (1<<(ap->depth));
310: }
311: }
312:
313: _merge (old, new)
314: skeleton *old, *new;
315: {
316: register __partial *op = old->partial, *np = new->partial;
317: int nson = new->nson;
318: register __partial *lim = np + new->treecnt;
319: if (nson==1) {
320: old->treecnt = new->treecnt;
321: for(; np < lim; op++, np++) {
322: op->treeno = np->treeno;
323: op->bits = np->bits/2;
324: }
325: } else {
326: __partial *newer = _allocpartial();
327: register __partial *newerp = newer;
328: register int cnt;
329: lim = op+old->treecnt;
330: for(cnt=new->treecnt; cnt-- ; np++) {
331: for(op = old->partial; op < lim; op++)
332: if (op->treeno == np->treeno) {
333: newerp->treeno = op->treeno;
334: newerp++->bits = op->bits & (np->bits/2);
335: break;
336: }
337: }
338: _freepartial(old->partial);
339: old->partial = newer;
340: old->treecnt = newerp-newer;
341: }
342: }
343:
344: /* Save and Allocate Matches */
345: #define BLKF 100
346: __match *freep = NULL;
347: static int _count = 0;
348: static __match *_blockp = NULL;
349: #ifdef CHECKMEM
350: int x_matches, f_matches;
351: #endif
352:
353: __match *
354: _allocmatch()
355: {
356: __match *mp;
357:
358: if(freep!=NULL) {
359: mp = freep;
360: freep = ((__match *)((struct freeb *) freep)->next);
361: #ifdef CHECKMEM
362: f_matches--;
363: #endif
364: } else {
365: if(_count==0) {
366: _blockp = (__match *) malloc (BLKF*sizeof (__match));
367: _count = BLKF;
368: #ifdef CHECKMEM
369: x_matches += BLKF;
370: #endif
371: }
372: mp = _blockp++;
373: _count--;
374: }
375: return(mp);
376: }
377:
378: _freematch(mp)
379: __match *mp;
380: {
381: ((struct freeb *) mp)->next = (struct freeb *) freep;
382: freep = mp;
383: #ifdef CHECKMEM
384: f_matches++;
385: #endif
386: }
387:
388: static __partial *pfreep = NULL;
389: static int pcount = 0;
390: static __partial *pblock = NULL;
391: #ifdef CHECKMEM
392: static int x_partials, f_partials;
393: #endif
394:
395: __partial *
396: _allocpartial()
397: {
398: __partial *pp;
399: if (pfreep!=NULL) {
400: pp = pfreep;
401: pfreep = *(__partial **) pp;
402: #ifdef CHECKMEM
403: f_partials--;
404: #endif
405: } else {
406: if (pcount==0) {
407: pblock=(__partial *)malloc(BLKF*MAXTREES*sizeof(__partial));
408: pcount = BLKF;
409: #ifdef CHECKMEM
410: x_partials += BLKF;
411: #endif
412: }
413: pp = pblock;
414: pblock += MAXTREES;
415: pcount--;
416: }
417: return(pp);
418: }
419:
420: _freepartial(pp)
421: __partial *pp;
422: {
423: * (__partial **)pp = pfreep;
424: pfreep = pp;
425: #ifdef CHECKMEM
426: f_partials++;
427: #endif
428: }
429:
430:
431: /* storage management */
432: static skeleton *sfreep = NULL;
433: static int scount = 0;
434: static skeleton * sblock = NULL;
435:
436: skeleton *
437: _allocskel()
438: {
439: skeleton *sp;
440: int i;
441: if(sfreep!=NULL) {
442: sp = sfreep;
443: sfreep = sp->sibling;
444: } else {
445: if(scount==0) {
446: sblock = (skeleton *) malloc (BLKF * sizeof (skeleton));
447: scount = BLKF;
448: }
449: sp = sblock++;
450: scount--;
451: }
452: sp->sibling = NULL; sp->leftchild = NULL;
453: for (i=0; i < MAXLABELS; sp->succ[i++] = NULL);
454: sp->treecnt = 0;
455: sp->partial = _allocpartial();
456: return(sp);
457: }
458:
459: _freeskel(sp)
460: skeleton *sp;
461: {
462: int i;
463: __match *mp;
464: if(sp==NULL)
465: return;
466: if(sp->leftchild)
467: _freeskel(sp->leftchild);
468: if(sp->sibling)
469: _freeskel(sp->sibling);
470: _freepartial (sp->partial);
471: for (i=0; i < MAXLABELS; i++)
472: if ((mp = sp->succ[i])!=NULL) _freematch (mp);
473: sp->sibling = sfreep;
474: sfreep = sp;
475: }
476:
477: _match()
478: {
479: skeleton *sp;
480: sp = _allocskel();
481: sp->root = NULL;
482: _mpbtop = _mpblock;
483: _freeskel(_walk(sp, HANG));
484: #ifdef CHECKMEM
485: if(f_matches+_count!=x_matches) {
486: printf(";#m %d %d %d\n", f_matches, _count, x_matches);
487: assert(0);
488: }
489: if(f_partials+pcount!=x_partials) {
490: printf(";#p %d %d %d\n", f_partials, pcount, x_partials);
491: assert(0);
492: }
493: #endif
494: }
495:
496: NODEPTR
497: _mtG(root,i)
498: NODEPTR root;
499: int i;
500: {
501: int *p = &i;
502: while(*p!=-1)
503: root = mtGetNodes(root, *p++);
504: return(root);
505: }
506:
507: /* diagnostic routines */
508:
509: _prskel (skp, lvl)
510: skeleton *skp; int lvl;
511: {
512: int i; __match *mp;
513: __partial *pp;
514: if(skp==NULL) return;
515: for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
516: printf ("###\n");
517: for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
518: for (i = 0; i < MAXLABELS; i++)
519: if ((mp=skp->succ[i])!=NULL)
520: #ifdef LINE_XREF
521: printf ("[%d<%d> %d]", mp->tree,
522: mtLine[mp->tree], mp->cost);
523: #else
524: printf ("[%d %d]", mp->tree, mp->cost);
525: #endif
526: putchar('\n');
527: for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
528: for (i = 0, pp=skp->partial; i < skp->treecnt; i++, pp++)
529: #ifdef LINE_XREF
530: printf("(%d<%d> %x)", pp->treeno, mtLine[pp->treeno],
531: pp->bits);
532: #else
533: printf ("(%d %x)", pp->treeno, pp->bits);
534: #endif
535: putchar('\n');
536: fflush(stdout);
537: _prskel (skp->leftchild, lvl+2);
538: _prskel (skp->sibling, lvl);
539: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.