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