if ( usemecs )		{		/* Set up doubly-linked meta-equivalence classes; these		 * are sets of equivalence classes which all have identical		 * transitions out of TEMPLATES.		 */		tecbck[1] = NIL;		for ( i = 2; i <= numecs; ++i )			{			tecbck[i] = i - 1;			tecfwd[i - 1] = i;			}		tecfwd[numecs] = NIL;		}	}/* mkdeftbl - make the default, "jam" table entries */void mkdeftbl()	{	int i;	jamstate = lastdfa + 1;	++tblend; /* room for transition on end-of-buffer character */	while ( tblend + numecs >= current_max_xpairs )		expand_nxt_chk();	/* Add in default end-of-buffer transition. */	nxt[tblend] = end_of_buffer_state;	chk[tblend] = jamstate;	for ( i = 1; i <= numecs; ++i )		{		nxt[tblend + i] = 0;		chk[tblend + i] = jamstate;		}	jambase = tblend;	base[jamstate] = jambase;	def[jamstate] = 0;	tblend += numecs;	++numtemps;	}/* mkentry - create base/def and nxt/chk entries for transition array * * synopsis *   int state[numchars + 1], numchars, statenum, deflink, totaltrans; *   mkentry( state, numchars, statenum, deflink, totaltrans ); * * "state" is a transition array "numchars" characters in size, "statenum" * is the offset to be used into the base/def tables, and "deflink" is the * entry to put in the "def" table entry.  If "deflink" is equal to * "JAMSTATE", then no attempt will be made to fit zero entries of "state" * (i.e., jam entries) into the table.  It is assumed that by linking to * "JAMSTATE" they will be taken care of.  In any case, entries in "state" * marking transitions to "SAME_TRANS" are treated as though they will be * taken care of by whereever "deflink" points.  "totaltrans" is the total * number of transitions out of the state.  If it is below a certain threshold, * the tables are searched for an interior spot that will accommodate the * state array. */void mkentry( state, numchars, statenum, deflink, totaltrans )register int *state;int numchars, statenum, deflink, totaltrans;	{	register int minec, maxec, i, baseaddr;	int tblbase, tbllast;	if ( totaltrans == 0 )		{ /* there are no out-transitions */		if ( deflink == JAMSTATE )			base[statenum] = JAMSTATE;		else			base[statenum] = 0;		def[statenum] = deflink;		return;		}	for ( minec = 1; minec <= numchars; ++minec )		{		if ( state[minec] != SAME_TRANS )			if ( state[minec] != 0 || deflink != JAMSTATE )				break;		}	if ( totaltrans == 1 )		{		/* There's only one out-transition.  Save it for later to fill		 * in holes in the tables.		 */		stack1( statenum, minec, state[minec], deflink );		return;		}	for ( maxec = numchars; maxec > 0; --maxec )		{		if ( state[maxec] != SAME_TRANS )			if ( state[maxec] != 0 || deflink != JAMSTATE )				break;		}	/* Whether we try to fit the state table in the middle of the table	 * entries we have already generated, or if we just take the state	 * table at the end of the nxt/chk tables, we must make sure that we	 * have a valid base address (i.e., non-negative).  Note that	 * negative base addresses dangerous at run-time (because indexing	 * the nxt array with one and a low-valued character will access	 * memory before the start of the array.	 */	/* Find the first transition of state that we need to worry about. */	if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE )		{		/* Attempt to squeeze it into the middle of the tables. */		baseaddr = firstfree;		while ( baseaddr < minec )			{			/* Using baseaddr would result in a negative base			 * address below; find the next free slot.			 */			for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr )				;			}		while ( baseaddr + maxec - minec + 1 >= current_max_xpairs )			expand_nxt_chk();		for ( i = minec; i <= maxec; ++i )			if ( state[i] != SAME_TRANS &&			     (state[i] != 0 || deflink != JAMSTATE) &&			     chk[baseaddr + i - minec] != 0 )				{ /* baseaddr unsuitable - find another */				for ( ++baseaddr;				      baseaddr < current_max_xpairs &&				      chk[baseaddr] != 0; ++baseaddr )					;				while ( baseaddr + maxec - minec + 1 >=					current_max_xpairs )					expand_nxt_chk();				/* Reset the loop counter so we'll start all				 * over again next time it's incremented.				 */				i = minec - 1;				}		}	else		{		/* Ensure that the base address we eventually generate is		 * non-negative.		 */		baseaddr = MAX( tblend + 1, minec );		}	tblbase = baseaddr - minec;	tbllast = tblbase + maxec;	while ( tbllast + 1 >= current_max_xpairs )		expand_nxt_chk();	base[statenum] = tblbase;	def[statenum] = deflink;	for ( i = minec; i <= maxec; ++i )		if ( state[i] != SAME_TRANS )			if ( state[i] != 0 || deflink != JAMSTATE )				{				nxt[tblbase + i] = state[i];				chk[tblbase + i] = statenum;				}	if ( baseaddr == firstfree )		/* Find next free slot in tables. */		for ( ++firstfree; chk[firstfree] != 0; ++firstfree )			;	tblend = MAX( tblend, tbllast );	}/* mk1tbl - create table entries for a state (or state fragment) which *            has only one out-transition */void mk1tbl( state, sym, onenxt, onedef )int state, sym, onenxt, onedef;	{	if ( firstfree < sym )		firstfree = sym;	while ( chk[firstfree] != 0 )		if ( ++firstfree >= current_max_xpairs )			expand_nxt_chk();	base[state] = firstfree - sym;	def[state] = onedef;	chk[firstfree] = state;	nxt[firstfree] = onenxt;	if ( firstfree > tblend )		{		tblend = firstfree++;		if ( firstfree >= current_max_xpairs )			expand_nxt_chk();		}	}/* mkprot - create new proto entry */void mkprot( state, statenum, comstate )int state[], statenum, comstate;	{	int i, slot, tblbase;	if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE )		{		/* Gotta make room for the new proto by dropping last entry in		 * the queue.		 */		slot = lastprot;		lastprot = protprev[lastprot];		protnext[lastprot] = NIL;		}	else		slot = numprots;	protnext[slot] = firstprot;	if ( firstprot != NIL )		protprev[firstprot] = slot;	firstprot = slot;	prottbl[slot] = statenum;	protcomst[slot] = comstate;	/* Copy state into save area so it can be compared with rapidly. */	tblbase = numecs * (slot - 1);	for ( i = 1; i <= numecs; ++i )		protsave[tblbase + i] = state[i];	}/* mktemplate - create a template entry based on a state, and connect the state *              to it */void mktemplate( state, statenum, comstate )int state[], statenum, comstate;	{	int i, numdiff, tmpbase, tmp[CSIZE + 1];	Char transset[CSIZE + 1];	int tsptr;	++numtemps;	tsptr = 0;	/* Calculate where we will temporarily store the transition table	 * of the template in the tnxt[] array.  The final transition table	 * gets created by cmptmps().	 */	tmpbase = numtemps * numecs;	if ( tmpbase + numecs >= current_max_template_xpairs )		{		current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT;		++num_reallocs;		tnxt = reallocate_integer_array( tnxt,			current_max_template_xpairs );		}	for ( i = 1; i <= numecs; ++i )		if ( state[i] == 0 )			tnxt[tmpbase + i] = 0;		else			{			transset[tsptr++] = i;			tnxt[tmpbase + i] = comstate;			}	if ( usemecs )		mkeccl( transset, tsptr, tecfwd, tecbck, numecs, 0 );	mkprot( tnxt + tmpbase, -numtemps, comstate );	/* We rely on the fact that mkprot adds things to the beginning	 * of the proto queue.	 */	numdiff = tbldiff( state, firstprot, tmp );	mkentry( tmp, numecs, statenum, -numtemps, numdiff );	}/* mv2front - move proto queue element to front of queue */void mv2front( qelm )int qelm;	{	if ( firstprot != qelm )		{		if ( qelm == lastprot )			lastprot = protprev[lastprot];		protnext[protprev[qelm]] = protnext[qelm];		if ( protnext[qelm] != NIL )			protprev[protnext[qelm]] = protprev[qelm];		protprev[qelm] = NIL;		protnext[qelm] = firstprot;		protprev[firstprot] = qelm;		firstprot = qelm;		}	}/* place_state - place a state into full speed transition table * * State is the statenum'th state.  It is indexed by equivalence class and * gives the number of the state to enter for a given equivalence class. * Transnum is the number of out-transitions for the state. */void place_state( state, statenum, transnum )int *state, statenum, transnum;	{	register int i;	register int *state_ptr;	int position = find_table_space( state, transnum );	/* "base" is the table of start positions. */	base[statenum] = position;	/* Put in action number marker; this non-zero number makes sure that	 * find_table_space() knows that this position in chk/nxt is taken	 * and should not be used for another accepting number in another	 * state.	 */	chk[position - 1] = 1;	/* Put in end-of-buffer marker; this is for the same purposes as	 * above.	 */	chk[position] = 1;	/* Place the state into chk and nxt. */	state_ptr = &state[1];	for ( i = 1; i <= numecs; ++i, ++state_ptr )		if ( *state_ptr != 0 )			{			chk[position + i] = i;			nxt[position + i] = *state_ptr;			}	if ( position + numecs > tblend )		tblend = position + numecs;	}/* stack1 - save states with only one out-transition to be processed later * * If there's room for another state on the "one-transition" stack, the * state is pushed onto it, to be processed later by mk1tbl.  If there's * no room, we process the sucker right now. */void stack1( statenum, sym, nextstate, deflink )int statenum, sym, nextstate, deflink;	{	if ( onesp >= ONE_STACK_SIZE - 1 )		mk1tbl( statenum, sym, nextstate, deflink );	else		{		++onesp;		onestate[onesp] = statenum;		onesym[onesp] = sym;		onenext[onesp] = nextstate;		onedef[onesp] = deflink;		}	}/* tbldiff - compute differences between two state tables * * "state" is the state array which is to be extracted from the pr'th * proto.  "pr" is both the number of the proto we are extracting from * and an index into the save area where we can find the proto's complete * state table.  Each entry in "state" which differs from the corresponding * entry of "pr" will appear in "ext". * * Entries which are the same in both "state" and "pr" will be marked * as transitions to "SAME_TRANS" in "ext".  The total number of differences * between "state" and "pr" is returned as function value.  Note that this * number is "numecs" minus the number of "SAME_TRANS" entries in "ext". */int tbldiff( state, pr, ext )int state[], pr, ext[];	{	register int i, *sp = state, *ep = ext, *protp;	register int numdiff = 0;	protp = &protsave[numecs * (pr - 1)];	for ( i = numecs; i > 0; --i )		{		if ( *++protp == *++sp )			*++ep = SAME_TRANS;		else			{			*++ep = *sp;			++numdiff;			}		}	return numdiff;	}