![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to walker.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 walker.c1 CVS log | Up to [Research Unix] / researchv10no / cmd / twig |
1.1 root 1: /*
2: * The machine is laid out as a sequence of integers in the walker.
3: * The form described above is only used inside the preprocessor.
4: * Each machine state is one of the following sequence:
5: *
6: * TABLE <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
7: * or
8: * TABLE2 <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
9: * or
10: * ACCEPT <accept table index> -1
11: *
12: * The accept table is in the form:
13: *
14: * <tree index_1> ...<tree_index_m> -1
15: *
16: */
17: /* Keutzer - all "short int"'s have been changed to "short" for
18: portability to UTS. */
19: #include "symbols.h"
20: /* Keutzer 1/88- _mtG now uses varargs for portability to SUN4 etc.*/
21: #include <varargs.h>
22:
23: #ifndef FILE
24: #include <stdio.h>
25: #endif
26: #include <assert.h>
27:
28: /* These constants must be the same as the ones in machine.c */
29: #define FASTLIM 0
30: #define TABLE 1
31: #define FAIL 2
32: #define ACCEPT 3
33: #define TABLE2 4
34: #define EOT -1
35:
36: /* special machine state */
37: #define HANG -1
38:
39: /* used by the evaluator to interpret path table */
40: #define eSTOP 0
41: #define ePOP -1
42: #define eEVAL -2
43: #define eNEXT -3
44: #define ePUSH -4
45:
46: /* Tags that indicate the type of a value */
47: #define M_BRANCH 010000
48: #define M_NODE 0
49: #define M_LABEL 01000
50: #define MAX_NODE_VALUE 00777
51: #define MTAG_SHIFT 9
52: #define M_DETAG(x) ((x)&~(M_BRANCH|M_LABEL|M_NODE))
53:
54: /* predicates to tell whether a value x is of type NODE, BRANCH, or LABEL */
55: #define MI_NODE(x) (((x)&(M_BRANCH|M_LABEL))==0)
56: #define MI_DEFINED(x) ((x)!=-1)
57: #define MI_LABEL(x) (((x)&M_LABEL)!=0)
58: #define MI_BRANCH(x) (((x)&M_BRANCH)!=0)
59:
60: /* build a tagged value */
61: #define MV_NODE(x) (x)
62: #define MV_BRANCH(x) ((x)|M_BRANCH)
63: #define MV_LABEL(x) ((x)|M_LABEL)
64:
65: /* limits */
66: /*
67: * The depth of a pattern must be 7 or less. Otherwise the type of he
68: * partial mask in skeleton must be changed
69: */
70: #define MAXDEPTH 7
71:
72: /* modes */
73: #define xTOPDOWN 3
74: #define xABORT 2
75: #define xREWRITE 1
76: #define xDEFER 0
77:
78: /* macros */
79: #define tDO(m) _do((m)->skel, (m), 1)
80: #define REWRITE return(_m->cost = cost, xREWRITE)
81: #define TOPDOWN return(_m->cost = cost, xTOPDOWN)
82: #define ABORT return(xABORT)
83:
84: /*
85: * REORDER macro allows a knowledgeable user to change the order
86: * of evaluation of the leaves.
87: */
88: #ifndef REORDER
89: #define REORDER(list) _evalleaves(list)
90: #endif
91: #define EVAL REORDER(_ll)
92:
93: #define mpush(s,m) (m)->next = s, s = m
94:
95: /* skeleton structure */
96: typedef struct skeleton skeleton;
97: typedef struct __match __match;
98: typedef struct __partial __partial;
99: typedef struct __hshcls __hshcls; /* a hashed closure entry */
100: typedef int labelset; /* a bit vector of labels */
101:
102: struct __partial {
103: unsigned char treeno;
104: char bits;
105: };
106:
107: struct __hshcls {
108: __hshcls *next;
109: labelset labels;
110: int treecnt; /* number of partial matches */
111: __partial partial[MAXTREES];
112: };
113:
114: struct skeleton {
115: skeleton *sibling;
116: skeleton *leftchild; /* leftmost child */
117: skeleton *rightchild; /* rightmost child */
118: NODEPTR root;
119: NODEPTR parent; /* our parent */
120: int nson;
121: int treecnt;
122: __match *succ[MAXLABELS];
123: __partial *partial;
124: __match *winner;
125: COST mincost;
126: };
127:
128: struct __match {
129: __match **lleaves; /* labelled leaves */
130: skeleton *skel; /* back pointer to associated skeleton node */
131: COST cost;
132: short tree;
133: short mode;
134: };
135:
136: struct freeb {
137: struct freeb *next;
138: };
139:
140: struct _mem {
141: struct _mem *next;
142: int size; /* size of individual elements in bytes */
143: int blkf; /* blocking factor */
144: int bsize; /* block size */
145: char *block; /* block */
146: int cnt; /* count of free elem in block */
147: char *freelist; /* free list */
148: int totelem; /* total number elements we have */
149: int freecnt; /* number of times mem_free was called */
150: };
151:
152: /* turn this flag on if your machine has a fast byte string zero operation */
153: /*#define BZERO 1*/
154: int mtDebug = 0;
155: int treedebug = 0;
156: extern int _machstep();
157: extern short mtStart;
158: extern short mtTable[], mtAccept[], mtMap[], mtPaths[], mtPathStart[];
159: #ifdef LINE_XREF
160: extern short mtLine[];
161: #endif
162:
163: #ifndef MPBSIZE
164: #define MPBSIZE 8000
165: #endif
166:
167: #ifdef ADDCOST
168: #define DEFAULT_COST sumleaves(_ll)
169: COST sumleaves(list) __match **list;
170: {COST cost;
171: cost=ZEROCOST;
172: for(; *list; list++)
173: {ADDCOST((cost),(*list)->cost);
174: }
175: return cost;
176: }
177: #endif
178:
179: extern NODEPTR mtGetNodes(), mtAction();
180: extern skeleton *_allocskel();
181: extern __match *_allocmatch();
182: extern __partial *_allocpartial();
183:
184: __match *_mpblock[MPBSIZE], **_mpbtop;
185:
186: __match **
187: _getleaves (mp, skp)
188: register __match *mp; register skeleton *skp;
189: {
190: skeleton *stack[MAXDEPTH];
191: skeleton **stp = stack;
192: register short *sip = &mtPaths[mtPathStart[mp->tree]];
193: register __match **mmp = _mpbtop;
194: __match **mmp2 = mmp;
195: if((_mpbtop += *sip++ + 1) > &_mpblock[MPBSIZE]) {
196: printf("Tree too large: make MPBSIZE larger.\n\
197: (i.e. cc -c -DMPBSIZE=%d walker.c)\n",MPBSIZE*2);
198: assert(0);
199: }
200:
201: for(;;)
202: switch(*sip++) {
203: case ePUSH:
204: *stp++ = skp;
205: skp = skp->leftchild;
206: break;
207:
208: case eNEXT:
209: skp = skp->sibling;
210: break;
211:
212: case eEVAL:
213: if ((mp = skp->succ[M_DETAG(*sip++)])==NULL) abort();
214: *mmp++ = mp;
215: break;
216:
217: case ePOP:
218: skp = *--stp;
219: break;
220:
221: case eSTOP:
222: *mmp = NULL;
223: return (mmp2);
224: }
225: }
226:
227: _evalleaves (mpp)
228: register __match **mpp;
229: {
230: for (; *mpp!=NULL; mpp++) {
231: register __match *mp = *mpp;
232: _do (mp->skel, mp, 1);
233: }
234: }
235:
236:
237: _do(sp, winner, evalall)
238: skeleton *sp; register __match *winner; int evalall;
239: {
240: register __match **mpp;
241: register skeleton *skel = winner->skel;
242: if(winner==NULL) {
243: _nowin(sp);
244: return;
245: }
246: if(winner->mode==xDEFER || (evalall && winner->mode!=xTOPDOWN))
247: REORDER(winner->lleaves);
248: mtSetNodes (skel->parent, skel->nson,
249: skel->root=mtAction (winner->tree, winner->lleaves, sp));
250: }
251:
252: skeleton *
253: _walk(sp, ostate)
254: register skeleton *sp;
255: int ostate;
256: {
257: int state, nstate, nson;
258: register __partial *pp;
259: register __match *mp, *mp2;
260: register skeleton *nsp, *lastchild = NULL;
261: NODEPTR son, root;
262:
263: root = sp->root;
264: nson = 1; sp->mincost = INFINITY;
265: state = _machstep (ostate, root, mtValue(root));
266:
267: while((son = mtGetNodes(root, nson))!=NULL) {
268: nstate = _machstep (state, NULL, MV_BRANCH(nson));
269: nsp = _allocskel();
270: nsp->root = son;
271: nsp->parent = root;
272: nsp->nson = nson;
273: _walk(nsp, nstate);
274: if(COSTLESS(nsp->mincost,INFINITY)) {
275: assert (nsp->winner->mode==xREWRITE);
276: _do(nsp, nsp->winner, 0);
277: _freeskel(nsp);
278: continue;
279: }
280: _merge (sp, nsp);
281: if (lastchild==NULL) sp->leftchild = nsp;
282: else lastchild->sibling = nsp;
283: lastchild = nsp;
284: nson++;
285: }
286:
287: for (pp = sp->partial; pp < &sp->partial[sp->treecnt]; pp++)
288: if (pp->bits&01==1) {
289: mp = _allocmatch();
290: mp->tree = pp->treeno;
291: _addmatches (ostate, sp, mp);
292: }
293: if(son==NULL && nson==1)
294: _closure (state, ostate, sp);
295:
296: sp->rightchild = lastchild;
297: if (root==NULL) {
298: COST c; __match *win; int i; nsp = sp->leftchild;
299: c = INFINITY;
300: win = NULL;
301: for (i = 0; i < MAXLABELS; i++) {
302: mp = nsp->succ[i];
303: if (mp!=NULL && COSTLESS (mp->cost, c))
304: { c = mp->cost; win = mp; }
305: }
306: _do (nsp, win, 0);
307: }
308: return(sp);
309: }
310:
311: /*
312: * Convert the start state which has a large branching factor into
313: * a index table. This must be called before the matcher is used.
314: */
315: static short _nodetab[MAXNDVAL], _labeltab[MAXLABELS];
316: _matchinit()
317: {
318: short *sp;
319: /* Keutzer - this syntax doesn't work on UTS
320: struct pair { short val, where } *pp;
321: */
322: struct pair { short val; short where; } *pp;
323: for (sp=_nodetab; sp < &_nodetab[MAXNDVAL]; sp++) *sp = HANG;
324: for (sp=_labeltab; sp < &_labeltab[MAXLABELS]; sp++) *sp = HANG;
325: sp = &mtTable[mtStart];
326: assert (*sp==TABLE);
327: for (pp = (struct pair *) ++sp; pp->val!=EOF; pp++) {
328: if (MI_NODE(pp->val))
329: _nodetab[M_DETAG(pp->val)] = pp->where;
330: else if (MI_LABEL(pp->val))
331: _labeltab[M_DETAG(pp->val)] = pp->where;
332: }
333: }
334:
335: int
336: _machstep(state, root, input)
337: short state, input;
338: NODEPTR root;
339: {
340: register short *stp = &mtTable[state];
341: int start = 0;
342: if (state==HANG)
343: return (input==(MV_BRANCH(1)) ? mtStart : HANG);
344: rescan:
345: if (stp==&mtTable[mtStart]) {
346: if (MI_NODE(input)) return(_nodetab[M_DETAG(input)]);
347: if (MI_LABEL(input)) return(_labeltab[M_DETAG(input)]);
348: }
349:
350: for(;;) {
351: if(*stp==ACCEPT) stp += 2;
352:
353: if(*stp==TABLE) {
354: stp++;
355: while(*stp!=EOT) {
356: if(input==*stp) {
357: return(*++stp);
358: }
359: stp += 2;
360: }
361: stp++;
362: }
363: if(*stp!=FAIL) {
364: if (start) return (HANG);
365: else { stp = &mtTable[mtStart]; start = 1; goto rescan;}
366: } else {
367: stp++;
368: stp = &mtTable[*stp];
369: goto rescan;
370: }
371: }
372: }
373:
374: _addmatches(ostate, sp, np)
375: int ostate;
376: register skeleton *sp;
377: register __match *np;
378: {
379: int label;
380: int state;
381: register __match *mp;
382:
383: label = mtMap[np->tree];
384:
385: /*
386: * this is a very poor substitute for good design of the DFA.
387: * What we need is a special case that allows any label to be accepted
388: * by the start state but we don't want the start state to recognize
389: * them after a failure.
390: */
391: state = _machstep(ostate, NULL, MV_LABEL(label));
392: if (ostate!=mtStart && state==HANG) {
393: _freematch(np);
394: return;
395: }
396:
397: np->lleaves = _getleaves (np, sp);
398: np->skel = sp;
399: if((np->mode = mtEvalCost(np, np->lleaves, sp))==xABORT)
400: {
401: _freematch(np);
402: return;
403: }
404:
405: /*
406: if(np->mode==xREWRITE && COSTLESS(np->cost, sp->mincost)) {
407: sp->mincost = np->cost;
408: sp->winner = np;
409: }
410: */
411: if ((mp = sp->succ[label])!=NULL) {
412: if (!COSTLESS (np->cost, mp->cost))
413: { _freematch(np); return; }
414: else _freematch(mp);
415: }
416: if(COSTLESS(np->cost,sp->mincost)) {
417: if(np->mode==xREWRITE) {
418: sp->mincost = np->cost; sp->winner = np; }
419: else { sp->mincost = INFINITY; sp->winner = NULL; }
420: }
421: sp->succ[label] = np;
422: _closure(state, ostate, sp);
423: }
424:
425: _closure(state, ostate, skp)
426: int state, ostate;
427: skeleton *skp;
428: {
429: register struct ap { short tree, depth; } *ap;
430: short *sp = &mtTable[state];
431: register __match *mp;
432:
433: if(state==HANG || *sp!=ACCEPT) return(NULL);
434:
435: for(ap = (struct ap *) &mtAccept[*++sp]; ap->tree!=-1; ap++)
436: if (ap->depth==0) {
437: mp = _allocmatch();
438: mp->tree = ap->tree;
439: _addmatches (ostate, skp, mp);
440: } else {
441: register __partial *pp, *lim = &skp->partial[skp->treecnt];
442: for(pp=skp->partial; pp < lim; pp++)
443: if(pp->treeno==ap->tree)
444: break;
445: if(pp==lim) {
446: skp->treecnt++;
447: pp->treeno = ap->tree;
448: pp->bits = (1<<(ap->depth));
449: } else pp->bits |= (1<<(ap->depth));
450: }
451: }
452:
453: _merge (old, new)
454: skeleton *old, *new;
455: {
456: register __partial *op = old->partial, *np = new->partial;
457: int nson = new->nson;
458: register __partial *lim = np + new->treecnt;
459: if (nson==1) {
460: old->treecnt = new->treecnt;
461: for(; np < lim; op++, np++) {
462: op->treeno = np->treeno;
463: op->bits = np->bits/2;
464: }
465: } else {
466: __partial *newer = _allocpartial();
467: register __partial *newerp = newer;
468: register int cnt;
469: lim = op+old->treecnt;
470: for(cnt=new->treecnt; cnt-- ; np++) {
471: for(op = old->partial; op < lim; op++)
472: if (op->treeno == np->treeno) {
473: newerp->treeno = op->treeno;
474: newerp++->bits = op->bits & (np->bits/2);
475: break;
476: }
477: }
478: _freepartial(old->partial);
479: old->partial = newer;
480: old->treecnt = newerp-newer;
481: }
482: }
483:
484: /* Save and Allocate Matches */
485: #define BLKF 100
486: __match *freep = NULL;
487: static int _count = 0;
488: static __match *_blockp = NULL;
489: #ifdef CHECKMEM
490: int x_matches, f_matches;
491: #endif
492:
493: __match *
494: _allocmatch()
495: {
496: __match *mp;
497:
498: if(freep!=NULL) {
499: mp = freep;
500: freep = ((__match *)((struct freeb *) freep)->next);
501: #ifdef CHECKMEM
502: f_matches--;
503: #endif
504: } else {
505: if(_count==0) {
506: _blockp = (__match *) malloc (BLKF*sizeof (__match));
507: _count = BLKF;
508: #ifdef CHECKMEM
509: x_matches += BLKF;
510: #endif
511: }
512: mp = _blockp++;
513: _count--;
514: }
515: return(mp);
516: }
517:
518: _freematch(mp)
519: __match *mp;
520: {
521: ((struct freeb *) mp)->next = (struct freeb *) freep;
522: freep = mp;
523: #ifdef CHECKMEM
524: f_matches++;
525: #endif
526: }
527:
528: static __partial *pfreep = NULL;
529: static int pcount = 0;
530: static __partial *pblock = NULL;
531: #ifdef CHECKMEM
532: static int x_partials, f_partials;
533: #endif
534:
535: __partial *
536: _allocpartial()
537: {
538: __partial *pp;
539: if (pfreep!=NULL) {
540: pp = pfreep;
541: pfreep = *(__partial **) pp;
542: #ifdef CHECKMEM
543: f_partials--;
544: #endif
545: } else {
546: if (pcount==0) {
547: pblock=(__partial *)malloc(BLKF*MAXTREES*sizeof(__partial));
548: pcount = BLKF;
549: #ifdef CHECKMEM
550: x_partials += BLKF;
551: #endif
552: }
553: pp = pblock;
554: pblock += MAXTREES;
555: pcount--;
556: }
557: return(pp);
558: }
559:
560: _freepartial(pp)
561: __partial *pp;
562: {
563: * (__partial **)pp = pfreep;
564: pfreep = pp;
565: #ifdef CHECKMEM
566: f_partials++;
567: #endif
568: }
569:
570:
571: /* storage management */
572: static skeleton *sfreep = NULL;
573: static int scount = 0;
574: static skeleton * sblock = NULL;
575:
576: skeleton *
577: _allocskel()
578: {
579: skeleton *sp;
580: int i;
581: if(sfreep!=NULL) {
582: sp = sfreep;
583: sfreep = sp->sibling;
584: } else {
585: if(scount==0) {
586: sblock = (skeleton *) malloc (BLKF * sizeof (skeleton));
587: scount = BLKF;
588: }
589: sp = sblock++;
590: scount--;
591: }
592: sp->sibling = NULL; sp->leftchild = NULL;
593: for (i=0; i < MAXLABELS; sp->succ[i++] = NULL);
594: sp->treecnt = 0;
595: sp->partial = _allocpartial();
596: return(sp);
597: }
598:
599: _freeskel(sp)
600: skeleton *sp;
601: {
602: int i;
603: __match *mp;
604: if(sp==NULL) return;
605: _freeskel (sp->leftchild);
606: _freeskel (sp->sibling);
607: _freepartial (sp->partial);
608: for (i=0; i < MAXLABELS; i++)
609: if ((mp = sp->succ[i])!=NULL) _freematch (mp);
610: sp->sibling = sfreep;
611: sfreep = sp;
612: }
613:
614: _match()
615: {
616: skeleton *sp;
617: sp = _allocskel();
618: sp->root = NULL;
619: _mpbtop = _mpblock;
620: _freeskel(_walk(sp, HANG));
621: #ifdef CHECKMEM
622: if(f_matches+_count!=x_matches) {
623: printf(";#m %d %d %d\n", f_matches, _count, x_matches);
624: assert(0);
625: }
626: if(f_partials+pcount!=x_partials) {
627: printf(";#p %d %d %d\n", f_partials, pcount, x_partials);
628: assert(0);
629: }
630: #endif
631: }
632:
633: /* Keutzer 1/88- _mtG now uses varargs for portability to SUN4 etc.*/
634: NODEPTR _mtG(va_alist)
635: va_dcl
636: {
637: NODEPTR root;
638: int i=0;
639: va_list p_var;
640: va_start(p_var);
641: root = va_arg(p_var,NODEPTR);
642: while( (i = va_arg(p_var,int)) != -1){
643: root = mtGetNodes(root, i);
644: }
645: va_end(p_var);
646: return(root);
647: }
648:
649: /* diagnostic routines */
650: #ifdef NOMARK
651: markIfNoMatch(skp,mark)
652: skeleton *skp;
653: int mark;
654: {}
655: #else
656: markIfNoMatch(skp,mark) skeleton *skp; int mark;
657: {skeleton *child; int i; int found=0;
658: for(i=0; i<MAXLABELS; i++)
659: if (skp->succ[i]) found=1;
660: if (!found) skp->root->mark=mark;
661: for(child=skp->leftchild; child; child=child->sibling)
662: markIfNoMatch(child,mark);
663: }
664: #endif
665:
666: _nowin(skp) skeleton *skp;
667: {
668: markIfNoMatch(skp,1);
669: printf("# No match was found for the nodes printed in lowercase\n");
670: printTree(skp->root);
671: markIfNoMatch(skp,0);
672: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.