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