/*
 *	DFA core functions.
 *
 *	(For a good look, set tabstops every 4 columns)
 *
 *	March 1990  --  W. Gish
 */
#include <ncbi.h>

#define __DFAEXTERN
#include <dfa.h>

	/* a pair of state pointers linked by a state transition */
typedef struct {
		DFA_StatePtr	from;
		DFA_StatePtr	to;
	} DFA_StatePair, PNTR DFA_StatePairPtr;

	/*
		The wrap-around buffer is implemented as a cyclically
		linked list of DFA_WABufs.
	 */
typedef struct _DFA_WABuf {
		struct _DFA_WABuf PNTR	chain;		/* pointer to next piece */
		DFA_StatePairPtr	maxwabuf;	/* allocation limit for this piece */
		DFA_StatePair		sp[1];		/* the buffer's content */
		} DFA_WABuf, PNTR DFA_WABufPtr;

/* the static functions used in this module... */
static DFA_StatePtr dfa_newstate PROTO((DFAPtr dp));
static void	dfa_initstate PROTO((DFAPtr dp, DFA_StatePtr S));
static CharPtr dfa_alloc PROTO((DFAPtr dp, size_t nbytes));
static CharPtr dfa_balloc PROTO((DFAPtr dp, size_t nbytes));
static DFA_WABufPtr dfa_getwabuf PROTO((DFAPtr dp));
static void	dfa_dropwabuf PROTO((DFA_WABufPtr));

 
/* default memory allocator */
static Nlm_VoidPtr	(_cdecl *memalloc) PROTO((size_t nbytes))
							= (Nlm_VoidPtr (_cdecl *) PROTO((size_t)))malloc;

/* default size in bytes for many allocation requests */
static size_t	memincr = DFA_MEMINCR_DEFAULT;

/* default memory freer */
static void		(_cdecl *memfree) PROTO((Nlm_VoidPtr))
							= (void (_cdecl *) PROTO((Nlm_VoidPtr)))free;


size_t _cdecl
dfa_memest(amin, amax)
	int	amin, amax;
{
	size_t	asize;
	unsigned long	memest;

	if (amin > amax) {
		dfaerrno = dfaErrAlphaRange;
		return 0;
	}

	asize = amax - amin + 1;
	/* Estimate the minimum storage required to get started */
	memest = sizeof(DFA)				/* DFA header */
			+ asize						/* alphabet control vector */
			+ asize*sizeof(DFA_State)	/* storage for one state */
			+ 32;						/* safety element */

	if (memest > MAXALLOC || memest > (size_t)1<<(sizeof(size_t)*CHAR_BIT - 2)) {
		dfaerrno = dfaErrNoMem;
		return 0;
	}
	return (size_t)memest;
}

DFAPtr _cdecl
dfa_new(amin, amax)
	int	amin, amax;
{
	DFAPtr dp;
	long	minbuf;
	int	i;

	if (amin > amax) {
		dfaerrno = dfaErrAlphaRange;
		return NULL;
	}

	minbuf = dfa_memest(amin, amax);
	if (minbuf == 0)
		return NULL;

	/*
		memincr should really be checked for sufficiency later,
		after the alphabet has been examined in detail,
		for instance, to see if duplicate letters arise in the
		user-supplied list of letters.
	*/
	/* Allocate our own dfa structure */
	if (memincr < minbuf) {
		dfaerrno = dfaErrMemincrTooSml;
		return NULL;
	}
	dp = (DFAPtr)(*memalloc)(memincr);
	if (dp == NULL) {
		dfaerrno = dfaErrNoMem;
		return NULL;
	}
	{ /* Zero-fill the DFA structure */
		CharPtr	cp = (CharPtr)dp;
		for (i=0; i<sizeof(DFA); ++i)
			cp[i] = '\0';
	}

	dp->magic = DFA_MAGIC;
	dp->opstate = dfaOpstateInit;
	dp->amin = amin;
	dp->amax = amax;
	dp->accsize = sizeof(DFA_Accept);
	dp->patsize = sizeof(DFA_Patlist);
	dp->idsize = dp->xlen = 0;

	/* Set up for dfa_alloc()'s memory allocation */
	dp->freeptr = (CharPtr)dp->buf0.buf;	/* Set start of free memory */
	dp->buf0.bused = 0;
	dp->memavail = dp->buf0.bsize =
					memincr - sizeof(DFA) + sizeof(dp->buf0.buf);
	dp->lastbuf = &dp->buf0;
	dp->buf0.chain = NULL;
	/* Make sure memory allocation is aligned on a word boundary */
	i = (unsigned long)dp->freeptr & (sizeof(CharPtr)-1);
	if (i != 0) {
		dp->freeptr += (sizeof(CharPtr) - i);
		dp->memavail -= (sizeof(CharPtr) - i);
	}

	dp->opstate = dfaOpstateMemInit;
	dp->asize = amax - amin + 1;
	dp->ctl = dfa_balloc(dp, dp->asize);
	for (i=0; i<dp->asize; ++i)
		dp->ctl[i] = '\0';
	dp->ctl -= amin;
	dp->opstate = dfaOpstateAlphaInit;

	/* Determine the size (in bytes) of each DFA_State */
	dp->statesize = dp->asize * sizeof(DFA_State);

	dp->opstate = dfaOpstateVirgin;
	return dp;
}

size_t _cdecl
dfa_xlen(dp, xlen)
	DFAPtr	dp;
	size_t	xlen;
{
	size_t	nbytes;
	DFA_Accept	acc;
	DFA_Patlist	pl;

	if (dp == NULL || dp->magic != DFA_MAGIC)
		return dfaerrno = dfaErrBadPtr;
	if (xlen == 0) /* inquiring minds want to know */
		return dp->xlen;
	if (dp->opstate != dfaOpstateVirgin) {
		dfaerrno = dfaErrOpstate;
		return 0;
	}
	nbytes = xlen + (sizeof(Nlm_VoidPtr) - 1);
	nbytes &= 0xffffffff - (sizeof(Nlm_VoidPtr) - 1);
	dp->accsize = sizeof(DFA_Accept) - sizeof(acc.pl.patID) + nbytes;
	dp->patsize = sizeof(DFA_Patlist) - sizeof(pl.patID) + nbytes;
	dp->idsize = nbytes;
	dp->xlen = xlen;
	return xlen;
}

DFA_Error _cdecl
dfa_restore(dp, ch)
	DFAPtr	dp;
	int	ch;
{
	if (dp == NULL || dp->magic != DFA_MAGIC)
		return dfaerrno = dfaErrBadPtr;
	if (dp->opstate != dfaOpstateVirgin)
		return dfaerrno = dfaErrOpstate;
	if (ch < dp->amin || ch > dp->amax)
		return dfaerrno = dfaErrNonAlpha;

	dp->ctl[ch] = 0;
	return dfaErrNone;
}

DFA_Error _cdecl
dfa_ignore(dp, ch)
	DFAPtr	dp;
	int	ch;
{
	if (dp == NULL || dp->magic != DFA_MAGIC)
		return dfaerrno = dfaErrBadPtr;
	if (dp->opstate != dfaOpstateVirgin)
		return dfaerrno = dfaErrOpstate;
	if (ch < dp->amin || ch > dp->amax)
		return dfaerrno = dfaErrNonAlpha;

	dp->ctl[ch] = 1;
	return dfaErrNone;
}

DFA_Error _cdecl
dfa_halton(dp, ch)
	DFAPtr	dp;
	int	ch;
{
	if (dp == NULL || dp->magic != DFA_MAGIC)
		return dfaerrno = dfaErrBadPtr;
	if (dp->opstate != dfaOpstateVirgin)
		return dfaerrno = dfaErrOpstate;
	if (ch < dp->amin || ch > dp->amax)
		return dfaerrno = dfaErrNonAlpha;

	dp->ctl[ch] = 2;
	return dfaErrNone;
}

DFA_Error _cdecl
dfa_begin(dp)
	DFAPtr	dp;
{
	DFA_StatePtr	S;
	int		i;

	if (dp == NULL || dp->magic != DFA_MAGIC)
		return dfaerrno = dfaErrBadPtr;
	if (dp->opstate != dfaOpstateVirgin)
		return dfaerrno = dfaErrOpstate;

	for (i = dp->amin; i <= dp->amax; ++i) {
		switch (dp->ctl[i]) {
		case 1:
			++dp->nignore;
			break;
		case 2:
			++dp->nhalton;
			break;
		default:
			break;
		}
	}

	if (dp->nignore > 0) {
		dp->ignore = (int PNTR)dfa_balloc(dp, dp->nignore * sizeof(int));
		if (dp->ignore == NULL)
			return dfaerrno;
	}
	if (dp->nhalton > 0) {
		dp->halton = (int PNTR)dfa_balloc(dp, dp->nhalton * sizeof(int));
		if (dp->halton == NULL)
			return dfaerrno;
	}
	dp->nignore = dp->nhalton = 0;

	for (i = dp->amin; i <= dp->amax; ++i) {
		switch (dp->ctl[i]) {
		case 1:
			dp->ignore[dp->nignore++] = i;
			break;
		case 2:
			dp->halton[dp->nhalton++] = i;
			break;
		default:
			break;
		}
	}

	/* Create the initial state of the automaton */
	S = dp->state0 = dfa_newstate(dp);
	if (S == NULL) {
		dp->opstate = dfaOpstateZombie;
		return dfaerrno;
	}
	dfa_initstate(dp, S);
	dp->opstate = dfaOpstateOpen;
	return dfaErrNone;
}

DFA_PatlistPtr _cdecl
dfa_addx(dp, pattern, patlen, idptr)
	DFAPtr	dp;
	unsigned char PNTR	pattern;
	size_t	patlen;
	Nlm_VoidPtr	idptr;
{
	DFA_StatePtr	curState, nextState;
	int	i;
	int	patChr;
	DFA_StatePtr	state0;
	DFA_AcceptPtr	ap;
	DFA_PatlistPtr	plp;

#ifndef DFA_THENEED4SPEED
	if (dp == NULL || dp->magic != DFA_MAGIC) {
		dfaerrno = dfaErrBadPtr;
		return NULL;
	}
	if (patlen == 0) {
		dfaerrno = dfaErrPatlen;
		return NULL;
	}
	if (dp->opstate != dfaOpstateOpen) {
		dfaerrno = dfaErrOpstate;
		return NULL;
	}
	if (dp->xlen == 0) {
		dfaerrno = dfaErrIncompat;
		return NULL;
	}
	dp->opstate = dfaOpstateBuilding;
#endif /* !DFA_THENEED4SPEED */

	/*
		Work down the tree, using the new pattern as the guide
		and adding new nodes as necessary.
	*/
	curState = state0 = dp->state0;
	for (i=0; i<patlen-1; ++i, curState = nextState) {
#ifndef DFA_THENEED4SPEED
		if ((patChr = *pattern++) < dp->amin || patChr > dp->amax)
			goto BadLetter;
		nextState = curState->next[patChr];
#else
		nextState = curState->next[patChr = *pattern++];
#endif
		if (nextState == state0) {
			if ((nextState = dfa_newstate(dp)) != NULL) {
				dfa_initstate(dp, curState->next[patChr] = nextState);
				continue;
			}
			goto Error;
		}
		if (!DFA_ISACCEPTING(nextState))
			continue;
		ap = (DFA_AcceptPtr)DFA_UNMUNGED(nextState);
		if ((nextState = ap->retState) == state0) {
			if ((nextState = dfa_newstate(dp)) == NULL)
				goto Error;
			dfa_initstate(dp, ap->retState = nextState);
		}
	}

	/*
		Create an accepting transition at this node of the tree
		(unless one already exists); if an output list does not
		exist, create one; then add the current pattern's patID
		to the output list.
	*/
#ifndef DFA_THENEED4SPEED
	if ((patChr = *pattern) < dp->amin || patChr > dp->amax)
		goto BadLetter;
	nextState = curState->next[patChr];
#else
	nextState = curState->next[patChr = *pattern];
#endif
	if (!DFA_ISACCEPTING(nextState)) {
		/* Make a new accepting transition */
		dp->naccepts++;
		if ((ap = (DFA_AcceptPtr)dfa_alloc(dp, dp->accsize)) == NULL)
			goto Error;
		curState->next[patChr] = (DFA_StatePtr)DFA_MUNGED(ap);
		ap->retState = nextState;
		ap->pl.chain = NULL;
		Nlm_MemCpy((CharPtr)&ap->pl.patID, (CharPtr)idptr, dp->xlen);
	}
	else {
		/* Prepend to an existing accepting transition's output list */
		if ((plp = (DFA_PatlistPtr)dfa_alloc(dp, dp->patsize)) == NULL)
			goto Error;
		ap = (DFA_AcceptPtr)DFA_UNMUNGED(nextState);
		plp->chain = ap->pl.chain;
		Nlm_MemCpy((CharPtr)&plp->patID, (CharPtr)&ap->pl.patID, dp->xlen);
		ap->pl.chain = plp;
		Nlm_MemCpy((CharPtr)&ap->pl.patID, (CharPtr)idptr, dp->xlen);
	}
	
#ifndef DFA_THENEED4SPEED
	dp->opstate = dfaOpstateOpen;
#endif
	return &ap->pl;

BadLetter:
	dfaerrno = dfaErrNonAlpha;
Error:
	dp->opstate = dfaOpstateZombie;
	return NULL;
}

DFA_PatlistPtr _cdecl
dfa_iaddx(dp, pattern, patlen, idptr)
	DFAPtr	dp;
	int PNTR	pattern;
	size_t	patlen;
	Nlm_VoidPtr	idptr;
{
	DFA_StatePtr	curState, nextState;
	int	i;
	int	patChr;
	DFA_StatePtr	state0;
	DFA_AcceptPtr	ap;
	DFA_PatlistPtr	plp;

#ifndef DFA_THENEED4SPEED
	if (dp == NULL || dp->magic != DFA_MAGIC) {
		dfaerrno = dfaErrBadPtr;
		return NULL;
	}
	if (patlen == 0) {
		dfaerrno = dfaErrPatlen;
		return NULL;
	}
	if (dp->opstate != dfaOpstateOpen) {
		dfaerrno = dfaErrOpstate;
		return NULL;
	}
	if (dp->xlen == 0) {
		dfaerrno = dfaErrIncompat;
		return NULL;
	}
	dp->opstate = dfaOpstateBuilding;
#endif /* !DFA_THENEED4SPEED */

	/*
		Work down the tree, using the new pattern as the guide
		and adding new nodes as necessary.
	*/
	curState = state0 = dp->state0;
	for (i=0; i<patlen-1; ++i, curState = nextState) {
#ifndef DFA_THENEED4SPEED
		if ((patChr = *pattern++) < dp->amin || patChr > dp->amax)
			goto BadLetter;
		nextState = curState->next[patChr];
#else
		nextState = curState->next[patChr = *pattern++];
#endif
		if (nextState == state0) {
			if ((nextState = dfa_newstate(dp)) != NULL) {
				dfa_initstate(dp, curState->next[patChr] = nextState);
				continue;
			}
			goto Error;
		}
		if (!DFA_ISACCEPTING(nextState))
			continue;
		ap = (DFA_AcceptPtr)DFA_UNMUNGED(nextState);
		if ((nextState = ap->retState) == state0) {
			if ((nextState = dfa_newstate(dp)) == NULL)
				goto Error;
			dfa_initstate(dp, ap->retState = nextState);
		}
	}

	/*
		Create an accepting transition at this node of the tree
		(unless one already exists); if an output list does not
		exist, create one; then add the current pattern's patID
		to the output list.
	*/
#ifndef DFA_THENEED4SPEED
	if ((patChr = *pattern) < dp->amin || patChr > dp->amax)
		goto BadLetter;
	nextState = curState->next[patChr];
#else
	nextState = curState->next[patChr = *pattern];
#endif
	if (!DFA_ISACCEPTING(nextState)) {
		/* Make a new accepting transition */
		dp->naccepts++;
		if ((ap = (DFA_AcceptPtr)dfa_alloc(dp, dp->accsize)) == NULL)
			goto Error;
		curState->next[patChr] = (DFA_StatePtr)DFA_MUNGED(ap);
		ap->retState = nextState;
		ap->pl.chain = NULL;
		Nlm_MemCpy((CharPtr)&ap->pl.patID, (CharPtr)idptr, dp->xlen);
	}
	else {
		/* Prepend to an existing accepting transition's output list */
		if ((plp = (DFA_PatlistPtr)dfa_alloc(dp, dp->patsize)) == NULL)
			goto Error;
		ap = (DFA_AcceptPtr)DFA_UNMUNGED(nextState);
		plp->chain = ap->pl.chain;
		Nlm_MemCpy((CharPtr)&plp->patID, (CharPtr)&ap->pl.patID, dp->xlen);
		ap->pl.chain = plp;
		Nlm_MemCpy((CharPtr)&ap->pl.patID, (CharPtr)idptr, dp->xlen);
	}
	
#ifndef DFA_THENEED4SPEED
	dp->opstate = dfaOpstateOpen;
#endif
	return &ap->pl;

BadLetter:
	dfaerrno = dfaErrNonAlpha;
Error:
	dp->opstate = dfaOpstateZombie;
	return NULL;
}

/****************************************************************************
*    dfa_add(dp, pattern, patlen, patID)
*
*    Add the specified pattern/patID combination to the skeletal automaton.
*    Return value:  a pointer to the new output list item on success;
*                   NULL on failure.
****************************************************************************/
DFA_PatlistPtr _cdecl
dfa_add(dp, pattern, patlen, patID)
	DFAPtr	dp;		/* the initialized DFA structure */
	unsigned char PNTR	pattern;	/* the pattern to incorporate in the DFA */
	size_t	patlen;	/* length of the pattern */
	DFA_PatID	patID;	/* value to return to programmer upon finding */
{
	DFA_StatePtr	curState, nextState;
	int	i;
	int	patChr;
	DFA_StatePtr	state0;
	DFA_AcceptPtr	ap;
	DFA_PatlistPtr	plp;

#ifndef DFA_THENEED4SPEED
	if (dp == NULL || dp->magic != DFA_MAGIC) {
		dfaerrno = dfaErrBadPtr;
		return NULL;
	}
	if (patlen == 0) {
		dfaerrno = dfaErrPatlen;
		return NULL;
	}
	if (dp->opstate != dfaOpstateOpen) {
		dfaerrno = dfaErrOpstate;
		return NULL;
	}
	if (dp->xlen != 0) {
		dfaerrno = dfaErrIncompat;
		return NULL;
	}
	dp->opstate = dfaOpstateBuilding;
#endif /* !DFA_THENEED4SPEED */

	/*
		Work down the tree, using the new pattern as the guide
		and adding new nodes as necessary.
	*/
	curState = state0 = dp->state0;
	for (i=0; i<patlen-1; ++i, curState = nextState) {
#ifndef DFA_THENEED4SPEED
		if ((patChr = *pattern++) < dp->amin || patChr > dp->amax)
			goto BadLetter;
		nextState = curState->next[patChr];
#else
		nextState = curState->next[patChr = *pattern++];
#endif
		if (nextState == state0) {
			if ((nextState = dfa_newstate(dp)) != NULL) {
				dfa_initstate(dp, curState->next[patChr] = nextState);
				continue;
			}
			goto Error;
		}
		if (!DFA_ISACCEPTING(nextState))
			continue;
		ap = (DFA_AcceptPtr)DFA_UNMUNGED(nextState);
		if ((nextState = ap->retState) == state0) {
			if ((nextState = dfa_newstate(dp)) == NULL)
				goto Error;
			dfa_initstate(dp, ap->retState = nextState);
		}
	}

	/*
		Create an accepting transition at this node of the tree
		(unless one already exists); if an output list does not
		exist, create one; then add the current pattern's patID
		to the output list.
	*/
#ifndef DFA_THENEED4SPEED
	if ((patChr = *pattern) < dp->amin || patChr > dp->amax)
		goto BadLetter;
	nextState = curState->next[patChr];
#else
	nextState = curState->next[patChr = *pattern];
#endif
	if (!DFA_ISACCEPTING(nextState)) {
		/* Make a new accepting transition */
		dp->naccepts++;
		if ((ap = (DFA_AcceptPtr)dfa_alloc(dp, sizeof(DFA_Accept))) == NULL)
			goto Error;
		curState->next[patChr] = (DFA_StatePtr)DFA_MUNGED(ap);
		ap->retState = nextState;
		ap->pl.chain = NULL;
		ap->pl.patID = patID;
	}
	else {
		/* Prepend to an existing accepting transition's output list */
		if ((plp = (DFA_PatlistPtr)dfa_alloc(dp, sizeof(DFA_Patlist))) == NULL)
			goto Error;
		ap = (DFA_AcceptPtr)DFA_UNMUNGED(nextState);
		plp->chain = ap->pl.chain;
		plp->patID = ap->pl.patID;
		ap->pl.chain = plp;
		ap->pl.patID = patID;
	}
	
#ifndef DFA_THENEED4SPEED
	dp->opstate = dfaOpstateOpen;
#endif
	return &ap->pl;

BadLetter:
	dfaerrno = dfaErrNonAlpha;
Error:
	dp->opstate = dfaOpstateZombie;
	return NULL;
}

/****************************************************************************
*   dfa_iadd(dp, pattern, patlen, patID)
*
*   Add the specified int pattern/patID combination to the skeletal automaton.
*   Return value:  a pointer to the new output list item on success;
*                  NULL on failure.
****************************************************************************/
DFA_PatlistPtr _cdecl
dfa_iadd(dp, pattern, patlen, patID)
	DFAPtr	dp;		/* the initialized DFA structure */
	int PNTR	pattern;	/* the pattern to incorporate in the DFA */
	size_t	patlen;	/* length of the pattern */
	DFA_PatID	patID;	/* value to return to programmer upon finding */
{
	DFA_StatePtr	curState, nextState;
	int	i;
	int	patChr;
	DFA_StatePtr	state0;
	DFA_AcceptPtr	ap;
	DFA_PatlistPtr	plp;

#ifndef DFA_THENEED4SPEED
	if (dp == NULL || dp->magic != DFA_MAGIC) {
		dfaerrno = dfaErrBadPtr;
		return NULL;
	}
	if (patlen == 0) {
		dfaerrno = dfaErrPatlen;
		return NULL;
	}
	if (dp->opstate != dfaOpstateOpen) {
		dfaerrno = dfaErrOpstate;
		return NULL;
	}
	if (dp->xlen != 0) {
		dfaerrno = dfaErrIncompat;
		return NULL;
	}
	dp->opstate = dfaOpstateBuilding;
#endif /* !DFA_THENEED4SPEED */

	/*
		Work down the tree, using the new pattern as the guide
		and adding new nodes as necessary.
	*/
	curState = state0 = dp->state0;
	for (i=0; i<patlen-1; ++i, curState = nextState) {
#ifndef DFA_THENEED4SPEED
		if ((patChr = *pattern++) < dp->amin || patChr > dp->amax)
			goto BadLetter;
		nextState = curState->next[patChr];
#else
		nextState = curState->next[patChr = *pattern++];
#endif
		if (nextState == state0) {
			if ((nextState = dfa_newstate(dp)) != NULL) {
				dfa_initstate(dp, curState->next[patChr] = nextState);
				continue;
			}
			goto Error;
		}
		if (!DFA_ISACCEPTING(nextState))
			continue;
		ap = (DFA_AcceptPtr)DFA_UNMUNGED(nextState);
		if ((nextState = ap->retState) == state0) {
			if ((nextState = dfa_newstate(dp)) == NULL)
				goto Error;
			dfa_initstate(dp, ap->retState = nextState);
		}
	}

	/*
		Create an accepting transition at this node of the tree
		(unless one already exists); if an output list does not
		exist, create one; then add the current pattern's patID
		to the output list.
	*/
#ifndef DFA_THENEED4SPEED
	if ((patChr = *pattern) < dp->amin || patChr > dp->amax)
		goto BadLetter;
	nextState = curState->next[patChr];
#else
	nextState = curState->next[patChr = *pattern];
#endif
	if (!DFA_ISACCEPTING(nextState)) {
		/* Make a new accepting transition */
		dp->naccepts++;
		if ((ap = (DFA_AcceptPtr)dfa_alloc(dp, sizeof(DFA_Accept))) == NULL)
			goto Error;
		curState->next[patChr] = (DFA_StatePtr)DFA_MUNGED(ap);
		ap->retState = nextState;
		ap->pl.chain = NULL;
		ap->pl.patID = patID;
	}
	else {
		/* Prepend to an existing accepting transition's output list */
		if ((plp = (DFA_PatlistPtr)dfa_alloc(dp, sizeof(DFA_Patlist))) == NULL)
			goto Error;
		ap = (DFA_AcceptPtr)DFA_UNMUNGED(nextState);
		plp->chain = ap->pl.chain;
		plp->patID = ap->pl.patID;
		ap->pl.chain = plp;
		ap->pl.patID = patID;
	}
	
#ifndef DFA_THENEED4SPEED
	dp->opstate = dfaOpstateOpen;
#endif
	return &ap->pl;

BadLetter:
	dfaerrno = dfaErrNonAlpha;
Error:
	dp->opstate = dfaOpstateZombie;
	return NULL;
}

/*
 * dfa_close(dbuf)
 *
 * No more patterns are to be added to the DFA--the skeletal automaton
 * is complete.
 * This routine works through states in the skeletal automaton one level
 * at a time, adding the necessary loop-back transitions.
 */
DFA_Error _cdecl
dfa_close(dp)
	DFAPtr dp;
{
	DFA_AcceptPtr	ap, bp;
	DFA_PatlistPtr	plp;
	DFA_StatePtr	istate, jstate;
	DFA_StatePtr	iState, jState;
	DFA_StatePtr	nextState, state0;
	DFA_StatePairPtr	head, tail;
	DFA_WABufPtr	Q0, hQnext, tQnext;
	DFA_StatePairPtr	hQmax, tQmax;
	int		ch;
	size_t	qcnt = 0; /* No. of items in the queue */

#define HEAD_UPDATE if(head>=hQmax)head=hQnext->sp,hQmax=hQnext->maxwabuf,hQnext=hQnext->chain

#define TAIL_UPDATE if(++tail>=tQmax)tail=tQnext->sp,tQmax=tQnext->maxwabuf,tQnext=tQnext->chain

#define PUSH(a,b) {++qcnt; head->from=(a); head++->to=(b); HEAD_UPDATE;}
#define PULL(a,b) {--qcnt; a=tail->from; b=tail->to; TAIL_UPDATE;}

	if (dp == NULL || dp->magic != DFA_MAGIC)
		return dfaerrno = dfaErrBadPtr;
	if (dp->opstate != dfaOpstateOpen && dp->opstate != dfaOpstateVirgin)
		return dfaerrno = dfaErrOpstate;

	dp->opstate = dfaOpstateClosing;

	/*
		Allocate the wrap-around buffer.  State pointers are queued in pairs.
		One extra pair is allocated for easier empty-queue detection.
	*/
	Q0 = dfa_getwabuf(dp);
	if (Q0 == NULL) {
		dp->opstate = dfaOpstateOpen;
		return dfaerrno;
	}
	head = tail = Q0->sp;
	hQmax = tQmax = Q0->maxwabuf;
	hQnext = tQnext = Q0->chain;

	/*
		Initialize the wrap-around buffer/queue.
		Begin at the initial state of the skeletal automaton and
		examine all transitions from it, pushing onto the wrap-around
		buffer only those transitions which do not point right
		back to the initial state.
	*/
	state0 = dp->state0;
	for (ch = dp->amin; ch <= dp->amax; ++ch) {
		if (dp->ctl[ch] != 0)
			continue;
		if ((nextState = state0->next[ch]) == state0)
			continue;
		if (DFA_ISACCEPTING(nextState)) {
			/* Check the return state for transition to state0 */
			nextState = (DFA_StatePtr)DFA_UNMUNGED(nextState);
			if ((nextState = ((DFA_AcceptPtr)nextState)->retState) == state0)
				continue;
		}
		PUSH(state0, nextState);
	}

	/*
		Now process the states that were pushed onto the wrap-around queue.
	*/
	/* While there are more pairs of DFA_State pointers in the queue... */
	while (qcnt > 0) {
		/* Pull off a from-to pair of DFA_State pointers */
		PULL(iState, jState);
		/*
			For every letter in the alphabet, examine the state transition
			pointers leading out of the just-pulled "to" state.
			If they point to state0, replace them with wherever the
			"from" state points to on input of the same letter;
			If they are accepting, merge their list of patIDs with
			the list of patIDS (if any) accepted by the "from" state
			on input of the same letter.
		*/
		for (ch = dp->amin; ch <= dp->amax; ++ch) {
			if (dp->ctl[ch] != 0)
				continue;
			istate = iState->next[ch];
			if ((jstate = jState->next[ch]) == state0) {
				/*
					transition state is changed to be the same
					as the "from" state's transition on input
					of the same letter (which may still be state0,
					but that's ok).
				*/
				jState->next[ch] = istate; /* re-direction */
				continue;
			}
			if (DFA_ISACCEPTING(jstate)) {
				ap = (DFA_AcceptPtr)DFA_UNMUNGED(jstate);
				jstate = ap->retState;
				if (DFA_ISACCEPTING(istate)) { /* Join lists */
					bp = (DFA_AcceptPtr)DFA_UNMUNGED(istate);
					/* Stop at the last item in the list */
					plp = &ap->pl;
					while (plp->chain != NULL)
						plp = plp->chain;
					plp->chain = &bp->pl;
					if (jstate == state0) {
						ap->retState = bp->retState;
						continue;
					}
					/* Push a from-to pair */
					PUSH(bp->retState, jstate);
					continue;
				}
				if (jstate == state0) {
					ap->retState = istate;
					continue;
				}
				PUSH(istate, jstate);
				continue;
			}

			if (!DFA_ISACCEPTING(istate)) {
				PUSH(istate, jstate);
				continue;
			}
			dp->naccepts++;
			if ((ap = (DFA_AcceptPtr)dfa_alloc(dp, dp->accsize)) == NULL)
				goto Error;
			jState->next[ch] = (DFA_StatePtr)DFA_MUNGED(ap);
			ap->retState = jstate;
			bp = (DFA_AcceptPtr)DFA_UNMUNGED(istate);
			if (dp->xlen > 0)
				Nlm_MemCpy((CharPtr)&ap->pl.patID, (CharPtr)&bp->pl.patID, dp->xlen);
			else
				ap->pl.patID = bp->pl.patID;
			ap->pl.chain = bp->pl.chain;
			PUSH(bp->retState, jstate);
		}
	}

	/* Normal return */
	dfa_dropwabuf(Q0);
	dp->opstate = dfaOpstateClosed;
	return dfaErrNone;

Error:
	dfa_dropwabuf(Q0);
	dp->opstate = dfaOpstateZombie;
	return dfaerrno;
}

/*************************************************************************
 * dfa_destruct(dp)
 *
 *    Release memory associated with) the DFA pointed to by dp.
 *************************************************************************/
DFA_Error _cdecl
dfa_destruct(dp)
	DFAPtr	dp;
{
	DFA_BufPtr	bp, bp2;

	if (dp == NULL || dp->magic != DFA_MAGIC)
		return dfaerrno = dfaErrBadPtr;

	if (dp->opstate < dfaOpstateMemInit || dp->opstate >= dfaOpstateDestroyed)
		return dfaerrno = dfaErrOpstate;

	dp->magic = 0;
	dp->opstate = dfaOpstateDestroyed;

	bp = &dp->buf0;
	bp = bp->chain;

	while (bp != NULL) {
		bp2 = bp->chain;
		(*memfree)(bp);
		bp = bp2;
	}
	(*memfree)(dp);
	return dfaErrNone;
}

/*************************************************************************
 *
 *        Memory management functions for the DFA library
 *
 *************************************************************************/

Nlm_VoidPtr _cdecl (_cdecl *dfa_memalloc(f)) ()
	Nlm_VoidPtr	(_cdecl *f)();
{
	Nlm_VoidPtr (_cdecl *f_orig)();
 
	if (f == NULL)
		f = (Nlm_VoidPtr (_cdecl *)() ) malloc;
	f_orig = memalloc;
	memalloc = f;
	return f_orig;
}
 
size_t _cdecl
dfa_memincr(newincr)
	size_t	newincr;
{
	size_t	memincr_orig;
 
	memincr_orig = memincr;
	if (newincr == 0)
		newincr = DFA_MEMINCR_DEFAULT;
	memincr = newincr;
	return memincr_orig;
}
 
void _cdecl (_cdecl *dfa_memfree(f)) ()
	void	(_cdecl *f)();
{
	void _cdecl	(*f_orig)();
 
	f_orig = memfree;
	if (f == NULL)
		f = (void (_cdecl *)() ) free;
	memfree = f;
	return f_orig;
}

/*************************************************************************
 *	dfa_alloc(dp, nbytes)
 *
 *	Allocate 'nbytes' bytes of memory from the pool maintained for 'dp'.
 *	'nbytes' must be guaranteed to be a multiple of sizeof(Nlm_VoidPtr).
 *************************************************************************/
static CharPtr
dfa_alloc(dp, nbytes)
	register DFAPtr	dp;
	register size_t	nbytes;
{
	register CharPtr	freesave;
	register DFA_BufPtr	dbp;

	/*
		Is there enough storage in the current buffer to satisfy this request?
	*/
	if (nbytes <= dp->memavail) {
		dp->memavail -= nbytes;
		freesave = dp->freeptr;
		dp->freeptr += nbytes; /* Update the pointer to free memory */
		return freesave;
	}

	/* Additional storage is needed to satisfy request */

	/* Allocate another buffer of size 'memincr' */
	if (nbytes > memincr - (sizeof(dp->buf0) - sizeof(dp->buf0.buf))) {
		dfaerrno = dfaErrMemincrTooSml;
		return NULL;
	}
	if ((dbp = (DFA_BufPtr)(*memalloc)(memincr)) == NULL) {
		dfaerrno = dfaErrNoMem;
		return NULL;
	}
	/* Add the new buffer to the linked list */
	if (dp->lastbuf != NULL) {
		dp->lastbuf->chain = dbp;
		dp->lastbuf->bused = dp->lastbuf->bsize - dp->memavail;
	}
	dp->lastbuf = dbp;
	dbp->chain = NULL;
	dbp->bused = 0;
	dp->freeptr = (CharPtr)dbp->buf;
	dp->memavail = dbp->bsize =
					memincr - (sizeof(dp->buf0) - sizeof(dp->buf0.buf));
	return dfa_alloc(dp, nbytes);
}

/*************************************************************************
 *	dfa_balloc(dp, nbytes)
 *
 *	Allocate 'nbytes' bytes of memory from the pool maintained for 'dp'
 *	'nbytes' itself need not be a multiple of sizeof(Nlm_VoidPtr).
 *************************************************************************/
static CharPtr
dfa_balloc(dp, nbytes)
	register DFAPtr	dp;
	register size_t	nbytes;
{
	/* Make nbytes a multiple of sizeof(Nlm_VoidPtr) */
	nbytes += sizeof(Nlm_VoidPtr)-1;
	nbytes &= 0xffffffff - (sizeof(Nlm_VoidPtr) - 1);
	/* Allocate storage in the usual way */
	return dfa_alloc(dp, nbytes);
}

/*************************************************************************
 *  dfa_newstate(dp)
 *
 *	Allocate a new state, and initialize as necessary for DFA_HALTEOF.
 *************************************************************************/
static DFA_StatePtr
dfa_newstate(dp)
	register DFAPtr	dp;
{
	register DFA_StatePtr	S;

	if ((S = (DFA_StatePtr)dfa_alloc(dp, dp->statesize)) == NULL)
		return NULL;
	dp->nstates++;
	return S - dp->amin;
}

/*************************************************************************
 *	dfa_initstate(dp, S)
 *
 *	Initialize state S in the DFA.
 *************************************************************************/
static void
dfa_initstate(dp, S)
	DFAPtr	dp;
	register DFA_StatePtr	S;
{
	DFA_StatePtr	S0 = S;
	register DFA_StatePtr	state0 = dp->state0;
	register DFA_StatePtr	SMax;
	register size_t	n;
	register size_t	nmax;

	S += dp->amin;
	SMax = S + dp->asize;

	do
		S->next[0] = state0;
	while (++S < SMax);


	S = S0;
	for (n = 0, nmax = dp->nignore; n < nmax; ++n) {
		S->next[dp->ignore[n]] = S;
	}
	for (n = 0, nmax = dp->nhalton; n < nmax; ++n) {
		S->next[dp->halton[n]] = (DFA_StatePtr)DFA_MUNGED(NULL);
	}

	return;
}

/*************************************************************************
 *	dfa_getwabuf(dp)
 *
 *	Allocate a wrap-around buffer, implemented as a cyclically linked list
 *	of buffers no larger than memincr bytes each.
 *************************************************************************/
static DFA_WABufPtr
dfa_getwabuf(dp)
	DFAPtr	dp;
{
	DFA_WABufPtr	qp, oqp, qp0 = NULL;
	size_t	npairs;		/* no. of pairs of DFA_State pointers required */
	long	overhead,	/* no. of bytes of overhead per wabuf_piece */
			nperalloc,	/* no. of pairs of ptrs that fit in memincr bytes */
			thisalloc;	/* amt. to request in this cycle of the loop */
	size_t	segsize;
	long	wabmem;

	overhead = sizeof(DFA_WABuf) - sizeof(DFA_StatePair);

	wabmem = dfa_wabsize(dp);
	if (wabmem > MAXALLOC)
		return NULL;

	npairs = wabmem / sizeof(DFA_StatePair);

	/* determine no. of pairs of pointers that fit in one allocation block */
	segsize = memincr;
	nperalloc = (segsize - overhead)/sizeof(DFA_StatePair);

	if (nperalloc < 1) {
		dfaerrno = dfaErrMemincrTooSml;
		return NULL;
	}

	/* allocate blocks and add them to the linked list */
	while (npairs > 0) {
		thisalloc = nperalloc;
		if (npairs < nperalloc) {
			thisalloc = npairs;
			segsize = overhead + thisalloc*sizeof(DFA_StatePair);
		}
		npairs -= thisalloc;
		qp = (DFA_WABufPtr)(*memalloc)(segsize);
		if (qp == NULL) {
			dfa_dropwabuf(qp0);
			return NULL;
		}
		if (qp0 == NULL)
			qp0 = qp;
		else
			oqp->chain = qp;
		oqp = qp;
		qp->maxwabuf = &qp->sp[thisalloc];
		/* make the linked list cyclical */
		qp->chain = qp0;
	}
	return qp0;
}

/**************************************************************************
 *	dfa_dropwabuf(dp)
 *
 *	De-allocate the wrap-around buffer.
 **************************************************************************/
static void
dfa_dropwabuf(qp0)
	DFA_WABufPtr	qp0;
{
	DFA_WABufPtr	qp = qp0, oqp;

	while (qp != NULL) {
		oqp = qp->chain;
		(*memfree)(qp);
		qp = oqp;
		if (qp == qp0) /* Is this the tail of the cycle of buffers? */
			break;
	}
}

/****************************************************************************
*	dfa_wabsize(dp)
*
*	Return the no. of bytes of storage required for the wrap-around buffer.
*	This value may change as more patterns are added to the DFA.
****************************************************************************/
long _cdecl
dfa_wabsize(dp)
	DFAPtr	dp;
{
	if (dp->opstate < dfaOpstateOpen && dp->opstate > dfaOpstateClosing) {
		dfaerrno = dfaErrOpstate;
		return 0;
	}

	return (long)(dp->nstates+1) * sizeof(DFA_StatePair);
}