fatbase

portable OpenBSD tools
git clone git://git.2f30.org/fatbase
Log | Files | Refs

tblcmp.c (23497B)


      1 /*	$OpenBSD: tblcmp.c,v 1.6 2003/06/04 17:34:44 millert Exp $	*/
      2 
      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  *
     16  * Redistribution and use in source and binary forms, with or without
     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.
     34  */
     35 
     36 /* $Header: /cvs/src/usr.bin/lex/tblcmp.c,v 1.6 2003/06/04 17:34:44 millert Exp $ */
     37 
     38 #include "flexdef.h"
     39 
     40 
     41 /* declarations for functions that have forward references */
     42 
     43 void mkentry PROTO((int*, int, int, int, int));
     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];
    238 	int *tmp = tmpstorage, i, j;
    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 	{
    310 	int old_max = current_max_xpairs;
    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 	 */
    349 	int i;
    350 	int *state_ptr, *chk_ptr;
    351 	int *ptr_to_last_entry_in_state;
    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 	{
    444 	int i;
    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 )
    525 int *state;
    526 int numchars, statenum, deflink, totaltrans;
    527 	{
    528 	int minec, maxec, i, baseaddr;
    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 	{
    802 	int i;
    803 	int *state_ptr;
    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 	{
    877 	int i, *sp = state, *ep = ext, *protp;
    878 	int numdiff = 0;
    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 	}