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