![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to tblcmp.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / pgrm / lex|
Return to tblcmp.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / pgrm / lex |
1.1 root 1: /* tblcmp - table compression routines */
2:
3: /*-
4: * Copyright (c) 1990 The Regents of the University of California.
5: * All rights reserved.
6: *
7: * This code is derived from software contributed to Berkeley by
8: * Vern Paxson.
9: *
10: * The United States Government has rights in this work pursuant
11: * to contract no. DE-AC03-76SF00098 between the United States
12: * Department of Energy and the University of California.
13: *
14: * Redistribution and use in source and binary forms are permitted provided
15: * that: (1) source distributions retain this entire copyright notice and
16: * comment, and (2) distributions including binaries display the following
17: * acknowledgement: ``This product includes software developed by the
18: * University of California, Berkeley and its contributors'' in the
19: * documentation or other materials provided with the distribution and in
20: * all advertising materials mentioning features or use of this software.
21: * Neither the name of the University nor the names of its contributors may
22: * be used to endorse or promote products derived from this software without
23: * specific prior written permission.
24: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
25: * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
26: * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
27: */
28:
29: #ifndef lint
30: static char sccsid[] = "@(#)tblcmp.c 5.2 (Berkeley) 6/18/90";
31: #endif /* not lint */
32:
33: #include "flexdef.h"
34:
35: /* declarations for functions that have forward references */
36:
37: void mkentry PROTO((register int*, int, int, int, int));
38: void mkprot PROTO((int[], int, int));
39: void mktemplate PROTO((int[], int, int));
40: void mv2front PROTO((int));
41: int tbldiff PROTO((int[], int, int[]));
42:
43:
44: /* bldtbl - build table entries for dfa state
45: *
46: * synopsis
47: * int state[numecs], statenum, totaltrans, comstate, comfreq;
48: * bldtbl( state, statenum, totaltrans, comstate, comfreq );
49: *
50: * State is the statenum'th dfa state. It is indexed by equivalence class and
51: * gives the number of the state to enter for a given equivalence class.
52: * totaltrans is the total number of transitions out of the state. Comstate
53: * is that state which is the destination of the most transitions out of State.
54: * Comfreq is how many transitions there are out of State to Comstate.
55: *
56: * A note on terminology:
57: * "protos" are transition tables which have a high probability of
58: * either being redundant (a state processed later will have an identical
59: * transition table) or nearly redundant (a state processed later will have
60: * many of the same out-transitions). A "most recently used" queue of
61: * protos is kept around with the hope that most states will find a proto
62: * which is similar enough to be usable, and therefore compacting the
63: * output tables.
64: * "templates" are a special type of proto. If a transition table is
65: * homogeneous or nearly homogeneous (all transitions go to the same
66: * destination) then the odds are good that future states will also go
67: * to the same destination state on basically the same character set.
68: * These homogeneous states are so common when dealing with large rule
69: * sets that they merit special attention. If the transition table were
70: * simply made into a proto, then (typically) each subsequent, similar
71: * state will differ from the proto for two out-transitions. One of these
72: * out-transitions will be that character on which the proto does not go
73: * to the common destination, and one will be that character on which the
74: * state does not go to the common destination. Templates, on the other
75: * hand, go to the common state on EVERY transition character, and therefore
76: * cost only one difference.
77: */
78:
79: void bldtbl( state, statenum, totaltrans, comstate, comfreq )
80: int state[], statenum, totaltrans, comstate, comfreq;
81:
82: {
83: int extptr, extrct[2][CSIZE + 1];
84: int mindiff, minprot, i, d;
85: int checkcom;
86:
87: /* If extptr is 0 then the first array of extrct holds the result of the
88: * "best difference" to date, which is those transitions which occur in
89: * "state" but not in the proto which, to date, has the fewest differences
90: * between itself and "state". If extptr is 1 then the second array of
91: * extrct hold the best difference. The two arrays are toggled
92: * between so that the best difference to date can be kept around and
93: * also a difference just created by checking against a candidate "best"
94: * proto.
95: */
96:
97: extptr = 0;
98:
99: /* if the state has too few out-transitions, don't bother trying to
100: * compact its tables
101: */
102:
103: if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) )
104: mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
105:
106: else
107: {
108: /* checkcom is true if we should only check "state" against
109: * protos which have the same "comstate" value
110: */
111:
112: checkcom = comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE;
113:
114: minprot = firstprot;
115: mindiff = totaltrans;
116:
117: if ( checkcom )
118: {
119: /* find first proto which has the same "comstate" */
120: for ( i = firstprot; i != NIL; i = protnext[i] )
121: if ( protcomst[i] == comstate )
122: {
123: minprot = i;
124: mindiff = tbldiff( state, minprot, extrct[extptr] );
125: break;
126: }
127: }
128:
129: else
130: {
131: /* since we've decided that the most common destination out
132: * of "state" does not occur with a high enough frequency,
133: * we set the "comstate" to zero, assuring that if this state
134: * is entered into the proto list, it will not be considered
135: * a template.
136: */
137: comstate = 0;
138:
139: if ( firstprot != NIL )
140: {
141: minprot = firstprot;
142: mindiff = tbldiff( state, minprot, extrct[extptr] );
143: }
144: }
145:
146: /* we now have the first interesting proto in "minprot". If
147: * it matches within the tolerances set for the first proto,
148: * we don't want to bother scanning the rest of the proto list
149: * to see if we have any other reasonable matches.
150: */
151:
152: if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE )
153: { /* not a good enough match. Scan the rest of the protos */
154: for ( i = minprot; i != NIL; i = protnext[i] )
155: {
156: d = tbldiff( state, i, extrct[1 - extptr] );
157: if ( d < mindiff )
158: {
159: extptr = 1 - extptr;
160: mindiff = d;
161: minprot = i;
162: }
163: }
164: }
165:
166: /* check if the proto we've decided on as our best bet is close
167: * enough to the state we want to match to be usable
168: */
169:
170: if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE )
171: {
172: /* no good. If the state is homogeneous enough, we make a
173: * template out of it. Otherwise, we make a proto.
174: */
175:
176: if ( comfreq * 100 >= totaltrans * TEMPLATE_SAME_PERCENTAGE )
177: mktemplate( state, statenum, comstate );
178:
179: else
180: {
181: mkprot( state, statenum, comstate );
182: mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
183: }
184: }
185:
186: else
187: { /* use the proto */
188: mkentry( extrct[extptr], numecs, statenum,
189: prottbl[minprot], mindiff );
190:
191: /* if this state was sufficiently different from the proto
192: * we built it from, make it, too, a proto
193: */
194:
195: if ( mindiff * 100 >= totaltrans * NEW_PROTO_DIFF_PERCENTAGE )
196: mkprot( state, statenum, comstate );
197:
198: /* since mkprot added a new proto to the proto queue, it's possible
199: * that "minprot" is no longer on the proto queue (if it happened
200: * to have been the last entry, it would have been bumped off).
201: * If it's not there, then the new proto took its physical place
202: * (though logically the new proto is at the beginning of the
203: * queue), so in that case the following call will do nothing.
204: */
205:
206: mv2front( minprot );
207: }
208: }
209: }
210:
211:
212: /* cmptmps - compress template table entries
213: *
214: * synopsis
215: * cmptmps();
216: *
217: * template tables are compressed by using the 'template equivalence
218: * classes', which are collections of transition character equivalence
219: * classes which always appear together in templates - really meta-equivalence
220: * classes. until this point, the tables for templates have been stored
221: * up at the top end of the nxt array; they will now be compressed and have
222: * table entries made for them.
223: */
224:
225: void cmptmps()
226:
227: {
228: int tmpstorage[CSIZE + 1];
229: register int *tmp = tmpstorage, i, j;
230: int totaltrans, trans;
231:
232: peakpairs = numtemps * numecs + tblend;
233:
234: if ( usemecs )
235: {
236: /* create equivalence classes base on data gathered on template
237: * transitions
238: */
239:
240: nummecs = cre8ecs( tecfwd, tecbck, numecs );
241: }
242:
243: else
244: nummecs = numecs;
245:
246: if ( lastdfa + numtemps + 1 >= current_max_dfas )
247: increase_max_dfas();
248:
249: /* loop through each template */
250:
251: for ( i = 1; i <= numtemps; ++i )
252: {
253: totaltrans = 0; /* number of non-jam transitions out of this template */
254:
255: for ( j = 1; j <= numecs; ++j )
256: {
257: trans = tnxt[numecs * i + j];
258:
259: if ( usemecs )
260: {
261: /* the absolute value of tecbck is the meta-equivalence class
262: * of a given equivalence class, as set up by cre8ecs
263: */
264: if ( tecbck[j] > 0 )
265: {
266: tmp[tecbck[j]] = trans;
267:
268: if ( trans > 0 )
269: ++totaltrans;
270: }
271: }
272:
273: else
274: {
275: tmp[j] = trans;
276:
277: if ( trans > 0 )
278: ++totaltrans;
279: }
280: }
281:
282: /* it is assumed (in a rather subtle way) in the skeleton that
283: * if we're using meta-equivalence classes, the def[] entry for
284: * all templates is the jam template, i.e., templates never default
285: * to other non-jam table entries (e.g., another template)
286: */
287:
288: /* leave room for the jam-state after the last real state */
289: mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans );
290: }
291: }
292:
293:
294:
295: /* expand_nxt_chk - expand the next check arrays */
296:
297: void expand_nxt_chk()
298:
299: {
300: register int old_max = current_max_xpairs;
301:
302: current_max_xpairs += MAX_XPAIRS_INCREMENT;
303:
304: ++num_reallocs;
305:
306: nxt = reallocate_integer_array( nxt, current_max_xpairs );
307: chk = reallocate_integer_array( chk, current_max_xpairs );
308:
309: bzero( (char *) (chk + old_max),
310: MAX_XPAIRS_INCREMENT * sizeof( int ) / sizeof( char ) );
311: }
312:
313:
314: /* find_table_space - finds a space in the table for a state to be placed
315: *
316: * synopsis
317: * int *state, numtrans, block_start;
318: * int find_table_space();
319: *
320: * block_start = find_table_space( state, numtrans );
321: *
322: * State is the state to be added to the full speed transition table.
323: * Numtrans is the number of out-transitions for the state.
324: *
325: * find_table_space() returns the position of the start of the first block (in
326: * chk) able to accommodate the state
327: *
328: * In determining if a state will or will not fit, find_table_space() must take
329: * into account the fact that an end-of-buffer state will be added at [0],
330: * and an action number will be added in [-1].
331: */
332:
333: int find_table_space( state, numtrans )
334: int *state, numtrans;
335:
336: {
337: /* firstfree is the position of the first possible occurrence of two
338: * consecutive unused records in the chk and nxt arrays
339: */
340: register int i;
341: register int *state_ptr, *chk_ptr;
342: register int *ptr_to_last_entry_in_state;
343:
344: /* if there are too many out-transitions, put the state at the end of
345: * nxt and chk
346: */
347: if ( numtrans > MAX_XTIONS_FULL_INTERIOR_FIT )
348: {
349: /* if table is empty, return the first available spot in chk/nxt,
350: * which should be 1
351: */
352: if ( tblend < 2 )
353: return ( 1 );
354:
355: i = tblend - numecs; /* start searching for table space near the
356: * end of chk/nxt arrays
357: */
358: }
359:
360: else
361: i = firstfree; /* start searching for table space from the
362: * beginning (skipping only the elements
363: * which will definitely not hold the new
364: * state)
365: */
366:
367: while ( 1 ) /* loops until a space is found */
368: {
369: if ( i + numecs > current_max_xpairs )
370: expand_nxt_chk();
371:
372: /* loops until space for end-of-buffer and action number are found */
373: while ( 1 )
374: {
375: if ( chk[i - 1] == 0 ) /* check for action number space */
376: {
377: if ( chk[i] == 0 ) /* check for end-of-buffer space */
378: break;
379:
380: else
381: i += 2; /* since i != 0, there is no use checking to
382: * see if (++i) - 1 == 0, because that's the
383: * same as i == 0, so we skip a space
384: */
385: }
386:
387: else
388: ++i;
389:
390: if ( i + numecs > current_max_xpairs )
391: expand_nxt_chk();
392: }
393:
394: /* if we started search from the beginning, store the new firstfree for
395: * the next call of find_table_space()
396: */
397: if ( numtrans <= MAX_XTIONS_FULL_INTERIOR_FIT )
398: firstfree = i + 1;
399:
400: /* check to see if all elements in chk (and therefore nxt) that are
401: * needed for the new state have not yet been taken
402: */
403:
404: state_ptr = &state[1];
405: ptr_to_last_entry_in_state = &chk[i + numecs + 1];
406:
407: for ( chk_ptr = &chk[i + 1]; chk_ptr != ptr_to_last_entry_in_state;
408: ++chk_ptr )
409: if ( *(state_ptr++) != 0 && *chk_ptr != 0 )
410: break;
411:
412: if ( chk_ptr == ptr_to_last_entry_in_state )
413: return ( i );
414:
415: else
416: ++i;
417: }
418: }
419:
420:
421: /* inittbl - initialize transition tables
422: *
423: * synopsis
424: * inittbl();
425: *
426: * Initializes "firstfree" to be one beyond the end of the table. Initializes
427: * all "chk" entries to be zero. Note that templates are built in their
428: * own tbase/tdef tables. They are shifted down to be contiguous
429: * with the non-template entries during table generation.
430: */
431: void inittbl()
432:
433: {
434: register int i;
435:
436: bzero( (char *) chk, current_max_xpairs * sizeof( int ) / sizeof( char ) );
437:
438: tblend = 0;
439: firstfree = tblend + 1;
440: numtemps = 0;
441:
442: if ( usemecs )
443: {
444: /* set up doubly-linked meta-equivalence classes
445: * these are sets of equivalence classes which all have identical
446: * transitions out of TEMPLATES
447: */
448:
449: tecbck[1] = NIL;
450:
451: for ( i = 2; i <= numecs; ++i )
452: {
453: tecbck[i] = i - 1;
454: tecfwd[i - 1] = i;
455: }
456:
457: tecfwd[numecs] = NIL;
458: }
459: }
460:
461:
462: /* mkdeftbl - make the default, "jam" table entries
463: *
464: * synopsis
465: * mkdeftbl();
466: */
467:
468: void mkdeftbl()
469:
470: {
471: int i;
472:
473: jamstate = lastdfa + 1;
474:
475: ++tblend; /* room for transition on end-of-buffer character */
476:
477: if ( tblend + numecs > current_max_xpairs )
478: expand_nxt_chk();
479:
480: /* add in default end-of-buffer transition */
481: nxt[tblend] = end_of_buffer_state;
482: chk[tblend] = jamstate;
483:
484: for ( i = 1; i <= numecs; ++i )
485: {
486: nxt[tblend + i] = 0;
487: chk[tblend + i] = jamstate;
488: }
489:
490: jambase = tblend;
491:
492: base[jamstate] = jambase;
493: def[jamstate] = 0;
494:
495: tblend += numecs;
496: ++numtemps;
497: }
498:
499:
500: /* mkentry - create base/def and nxt/chk entries for transition array
501: *
502: * synopsis
503: * int state[numchars + 1], numchars, statenum, deflink, totaltrans;
504: * mkentry( state, numchars, statenum, deflink, totaltrans );
505: *
506: * "state" is a transition array "numchars" characters in size, "statenum"
507: * is the offset to be used into the base/def tables, and "deflink" is the
508: * entry to put in the "def" table entry. If "deflink" is equal to
509: * "JAMSTATE", then no attempt will be made to fit zero entries of "state"
510: * (i.e., jam entries) into the table. It is assumed that by linking to
511: * "JAMSTATE" they will be taken care of. In any case, entries in "state"
512: * marking transitions to "SAME_TRANS" are treated as though they will be
513: * taken care of by whereever "deflink" points. "totaltrans" is the total
514: * number of transitions out of the state. If it is below a certain threshold,
515: * the tables are searched for an interior spot that will accommodate the
516: * state array.
517: */
518:
519: void mkentry( state, numchars, statenum, deflink, totaltrans )
520: register int *state;
521: int numchars, statenum, deflink, totaltrans;
522:
523: {
524: register int minec, maxec, i, baseaddr;
525: int tblbase, tbllast;
526:
527: if ( totaltrans == 0 )
528: { /* there are no out-transitions */
529: if ( deflink == JAMSTATE )
530: base[statenum] = JAMSTATE;
531: else
532: base[statenum] = 0;
533:
534: def[statenum] = deflink;
535: return;
536: }
537:
538: for ( minec = 1; minec <= numchars; ++minec )
539: {
540: if ( state[minec] != SAME_TRANS )
541: if ( state[minec] != 0 || deflink != JAMSTATE )
542: break;
543: }
544:
545: if ( totaltrans == 1 )
546: {
547: /* there's only one out-transition. Save it for later to fill
548: * in holes in the tables.
549: */
550: stack1( statenum, minec, state[minec], deflink );
551: return;
552: }
553:
554: for ( maxec = numchars; maxec > 0; --maxec )
555: {
556: if ( state[maxec] != SAME_TRANS )
557: if ( state[maxec] != 0 || deflink != JAMSTATE )
558: break;
559: }
560:
561: /* Whether we try to fit the state table in the middle of the table
562: * entries we have already generated, or if we just take the state
563: * table at the end of the nxt/chk tables, we must make sure that we
564: * have a valid base address (i.e., non-negative). Note that not only are
565: * negative base addresses dangerous at run-time (because indexing the
566: * next array with one and a low-valued character might generate an
567: * array-out-of-bounds error message), but at compile-time negative
568: * base addresses denote TEMPLATES.
569: */
570:
571: /* find the first transition of state that we need to worry about. */
572: if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE )
573: { /* attempt to squeeze it into the middle of the tabls */
574: baseaddr = firstfree;
575:
576: while ( baseaddr < minec )
577: {
578: /* using baseaddr would result in a negative base address below
579: * find the next free slot
580: */
581: for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr )
582: ;
583: }
584:
585: if ( baseaddr + maxec - minec >= current_max_xpairs )
586: expand_nxt_chk();
587:
588: for ( i = minec; i <= maxec; ++i )
589: if ( state[i] != SAME_TRANS )
590: if ( state[i] != 0 || deflink != JAMSTATE )
591: if ( chk[baseaddr + i - minec] != 0 )
592: { /* baseaddr unsuitable - find another */
593: for ( ++baseaddr;
594: baseaddr < current_max_xpairs &&
595: chk[baseaddr] != 0;
596: ++baseaddr )
597: ;
598:
599: if ( baseaddr + maxec - minec >= current_max_xpairs )
600: expand_nxt_chk();
601:
602: /* reset the loop counter so we'll start all
603: * over again next time it's incremented
604: */
605:
606: i = minec - 1;
607: }
608: }
609:
610: else
611: {
612: /* ensure that the base address we eventually generate is
613: * non-negative
614: */
615: baseaddr = max( tblend + 1, minec );
616: }
617:
618: tblbase = baseaddr - minec;
619: tbllast = tblbase + maxec;
620:
621: if ( tbllast >= current_max_xpairs )
622: expand_nxt_chk();
623:
624: base[statenum] = tblbase;
625: def[statenum] = deflink;
626:
627: for ( i = minec; i <= maxec; ++i )
628: if ( state[i] != SAME_TRANS )
629: if ( state[i] != 0 || deflink != JAMSTATE )
630: {
631: nxt[tblbase + i] = state[i];
632: chk[tblbase + i] = statenum;
633: }
634:
635: if ( baseaddr == firstfree )
636: /* find next free slot in tables */
637: for ( ++firstfree; chk[firstfree] != 0; ++firstfree )
638: ;
639:
640: tblend = max( tblend, tbllast );
641: }
642:
643:
644: /* mk1tbl - create table entries for a state (or state fragment) which
645: * has only one out-transition
646: *
647: * synopsis
648: * int state, sym, onenxt, onedef;
649: * mk1tbl( state, sym, onenxt, onedef );
650: */
651:
652: void mk1tbl( state, sym, onenxt, onedef )
653: int state, sym, onenxt, onedef;
654:
655: {
656: if ( firstfree < sym )
657: firstfree = sym;
658:
659: while ( chk[firstfree] != 0 )
660: if ( ++firstfree >= current_max_xpairs )
661: expand_nxt_chk();
662:
663: base[state] = firstfree - sym;
664: def[state] = onedef;
665: chk[firstfree] = state;
666: nxt[firstfree] = onenxt;
667:
668: if ( firstfree > tblend )
669: {
670: tblend = firstfree++;
671:
672: if ( firstfree >= current_max_xpairs )
673: expand_nxt_chk();
674: }
675: }
676:
677:
678: /* mkprot - create new proto entry
679: *
680: * synopsis
681: * int state[], statenum, comstate;
682: * mkprot( state, statenum, comstate );
683: */
684:
685: void mkprot( state, statenum, comstate )
686: int state[], statenum, comstate;
687:
688: {
689: int i, slot, tblbase;
690:
691: if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE )
692: {
693: /* gotta make room for the new proto by dropping last entry in
694: * the queue
695: */
696: slot = lastprot;
697: lastprot = protprev[lastprot];
698: protnext[lastprot] = NIL;
699: }
700:
701: else
702: slot = numprots;
703:
704: protnext[slot] = firstprot;
705:
706: if ( firstprot != NIL )
707: protprev[firstprot] = slot;
708:
709: firstprot = slot;
710: prottbl[slot] = statenum;
711: protcomst[slot] = comstate;
712:
713: /* copy state into save area so it can be compared with rapidly */
714: tblbase = numecs * (slot - 1);
715:
716: for ( i = 1; i <= numecs; ++i )
717: protsave[tblbase + i] = state[i];
718: }
719:
720:
721: /* mktemplate - create a template entry based on a state, and connect the state
722: * to it
723: *
724: * synopsis
725: * int state[], statenum, comstate, totaltrans;
726: * mktemplate( state, statenum, comstate, totaltrans );
727: */
728:
729: void mktemplate( state, statenum, comstate )
730: int state[], statenum, comstate;
731:
732: {
733: int i, numdiff, tmpbase, tmp[CSIZE + 1];
734: Char transset[CSIZE + 1];
735: int tsptr;
736:
737: ++numtemps;
738:
739: tsptr = 0;
740:
741: /* calculate where we will temporarily store the transition table
742: * of the template in the tnxt[] array. The final transition table
743: * gets created by cmptmps()
744: */
745:
746: tmpbase = numtemps * numecs;
747:
748: if ( tmpbase + numecs >= current_max_template_xpairs )
749: {
750: current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT;
751:
752: ++num_reallocs;
753:
754: tnxt = reallocate_integer_array( tnxt, current_max_template_xpairs );
755: }
756:
757: for ( i = 1; i <= numecs; ++i )
758: if ( state[i] == 0 )
759: tnxt[tmpbase + i] = 0;
760: else
761: {
762: transset[tsptr++] = i;
763: tnxt[tmpbase + i] = comstate;
764: }
765:
766: if ( usemecs )
767: mkeccl( transset, tsptr, tecfwd, tecbck, numecs, 0 );
768:
769: mkprot( tnxt + tmpbase, -numtemps, comstate );
770:
771: /* we rely on the fact that mkprot adds things to the beginning
772: * of the proto queue
773: */
774:
775: numdiff = tbldiff( state, firstprot, tmp );
776: mkentry( tmp, numecs, statenum, -numtemps, numdiff );
777: }
778:
779:
780: /* mv2front - move proto queue element to front of queue
781: *
782: * synopsis
783: * int qelm;
784: * mv2front( qelm );
785: */
786:
787: void mv2front( qelm )
788: int qelm;
789:
790: {
791: if ( firstprot != qelm )
792: {
793: if ( qelm == lastprot )
794: lastprot = protprev[lastprot];
795:
796: protnext[protprev[qelm]] = protnext[qelm];
797:
798: if ( protnext[qelm] != NIL )
799: protprev[protnext[qelm]] = protprev[qelm];
800:
801: protprev[qelm] = NIL;
802: protnext[qelm] = firstprot;
803: protprev[firstprot] = qelm;
804: firstprot = qelm;
805: }
806: }
807:
808:
809: /* place_state - place a state into full speed transition table
810: *
811: * synopsis
812: * int *state, statenum, transnum;
813: * place_state( state, statenum, transnum );
814: *
815: * State is the statenum'th state. It is indexed by equivalence class and
816: * gives the number of the state to enter for a given equivalence class.
817: * Transnum is the number of out-transitions for the state.
818: */
819:
820: void place_state( state, statenum, transnum )
821: int *state, statenum, transnum;
822:
823: {
824: register int i;
825: register int *state_ptr;
826: int position = find_table_space( state, transnum );
827:
828: /* base is the table of start positions */
829: base[statenum] = position;
830:
831: /* put in action number marker; this non-zero number makes sure that
832: * find_table_space() knows that this position in chk/nxt is taken
833: * and should not be used for another accepting number in another state
834: */
835: chk[position - 1] = 1;
836:
837: /* put in end-of-buffer marker; this is for the same purposes as above */
838: chk[position] = 1;
839:
840: /* place the state into chk and nxt */
841: state_ptr = &state[1];
842:
843: for ( i = 1; i <= numecs; ++i, ++state_ptr )
844: if ( *state_ptr != 0 )
845: {
846: chk[position + i] = i;
847: nxt[position + i] = *state_ptr;
848: }
849:
850: if ( position + numecs > tblend )
851: tblend = position + numecs;
852: }
853:
854:
855: /* stack1 - save states with only one out-transition to be processed later
856: *
857: * synopsis
858: * int statenum, sym, nextstate, deflink;
859: * stack1( statenum, sym, nextstate, deflink );
860: *
861: * if there's room for another state one the "one-transition" stack, the
862: * state is pushed onto it, to be processed later by mk1tbl. If there's
863: * no room, we process the sucker right now.
864: */
865:
866: void stack1( statenum, sym, nextstate, deflink )
867: int statenum, sym, nextstate, deflink;
868:
869: {
870: if ( onesp >= ONE_STACK_SIZE - 1 )
871: mk1tbl( statenum, sym, nextstate, deflink );
872:
873: else
874: {
875: ++onesp;
876: onestate[onesp] = statenum;
877: onesym[onesp] = sym;
878: onenext[onesp] = nextstate;
879: onedef[onesp] = deflink;
880: }
881: }
882:
883:
884: /* tbldiff - compute differences between two state tables
885: *
886: * synopsis
887: * int state[], pr, ext[];
888: * int tbldiff, numdifferences;
889: * numdifferences = tbldiff( state, pr, ext )
890: *
891: * "state" is the state array which is to be extracted from the pr'th
892: * proto. "pr" is both the number of the proto we are extracting from
893: * and an index into the save area where we can find the proto's complete
894: * state table. Each entry in "state" which differs from the corresponding
895: * entry of "pr" will appear in "ext".
896: * Entries which are the same in both "state" and "pr" will be marked
897: * as transitions to "SAME_TRANS" in "ext". The total number of differences
898: * between "state" and "pr" is returned as function value. Note that this
899: * number is "numecs" minus the number of "SAME_TRANS" entries in "ext".
900: */
901:
902: int tbldiff( state, pr, ext )
903: int state[], pr, ext[];
904:
905: {
906: register int i, *sp = state, *ep = ext, *protp;
907: register int numdiff = 0;
908:
909: protp = &protsave[numecs * (pr - 1)];
910:
911: for ( i = numecs; i > 0; --i )
912: {
913: if ( *++protp == *++sp )
914: *++ep = SAME_TRANS;
915: else
916: {
917: *++ep = *sp;
918: ++numdiff;
919: }
920: }
921:
922: return ( numdiff );
923: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.