regc_nfa.c

来自「A*算法 A*算法 A*算法 A*算法A*算法A*算法」· C语言 代码 · 共 1,583 行 · 第 1/3 页

/*
 * NFA utilities.
 * This file is #included by regcomp.c.
 *
 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
 * 
 * Development of this software was funded, in part, by Cray Research Inc.,
 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
 * Corporation, none of whom are responsible for the results.  The author
 * thanks all of them. 
 * 
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 * 
 * I'd appreciate being given credit for this package in the documentation
 * of software which uses it, but that is not a requirement.
 * 
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 *
 * One or two things that technically ought to be in here
 * are actually in color.c, thanks to some incestuous relationships in
 * the color chains.
 */

#define	NISERR()	VISERR(nfa->v)
#define	NERR(e)		VERR(nfa->v, (e))


/*
 - newnfa - set up an NFA
 ^ static struct nfa *newnfa(struct vars *, struct colormap *, struct nfa *);
 */
static struct nfa *		/* the NFA, or NULL */
newnfa(v, cm, parent)
struct vars *v;
struct colormap *cm;
struct nfa *parent;		/* NULL if primary NFA */
{
	struct nfa *nfa;

	nfa = (struct nfa *)MALLOC(sizeof(struct nfa));
	if (nfa == NULL)
		return NULL;

	nfa->states = NULL;
	nfa->slast = NULL;
	nfa->free = NULL;
	nfa->nstates = 0;
	nfa->cm = cm;
	nfa->v = v;
	nfa->bos[0] = nfa->bos[1] = COLORLESS;
	nfa->eos[0] = nfa->eos[1] = COLORLESS;
	nfa->post = newfstate(nfa, '@');	/* number 0 */
	nfa->pre = newfstate(nfa, '>');		/* number 1 */
	nfa->parent = parent;

	nfa->init = newstate(nfa);		/* may become invalid later */
	nfa->final = newstate(nfa);
	if (ISERR()) {
		freenfa(nfa);
		return NULL;
	}
	rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->pre, nfa->init);
	newarc(nfa, '^', 1, nfa->pre, nfa->init);
	newarc(nfa, '^', 0, nfa->pre, nfa->init);
	rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->final, nfa->post);
	newarc(nfa, '$', 1, nfa->final, nfa->post);
	newarc(nfa, '$', 0, nfa->final, nfa->post);

	if (ISERR()) {
		freenfa(nfa);
		return NULL;
	}
	return nfa;
}

/*
 - freenfa - free an entire NFA
 ^ static VOID freenfa(struct nfa *);
 */
static VOID
freenfa(nfa)
struct nfa *nfa;
{
	struct state *s;

	while ((s = nfa->states) != NULL) {
		s->nins = s->nouts = 0;		/* don't worry about arcs */
		freestate(nfa, s);
	}
	while ((s = nfa->free) != NULL) {
		nfa->free = s->next;
		destroystate(nfa, s);
	}

	nfa->slast = NULL;
	nfa->nstates = -1;
	nfa->pre = NULL;
	nfa->post = NULL;
	FREE(nfa);
}

/*
 - newstate - allocate an NFA state, with zero flag value
 ^ static struct state *newstate(struct nfa *);
 */
static struct state *		/* NULL on error */
newstate(nfa)
struct nfa *nfa;
{
	struct state *s;

	if (nfa->free != NULL) {
		s = nfa->free;
		nfa->free = s->next;
	} else {
		s = (struct state *)MALLOC(sizeof(struct state));
		if (s == NULL) {
			NERR(REG_ESPACE);
			return NULL;
		}
		s->oas.next = NULL;
		s->free = NULL;
		s->noas = 0;
	}

	assert(nfa->nstates >= 0);
	s->no = nfa->nstates++;
	s->flag = 0;
	if (nfa->states == NULL)
		nfa->states = s;
	s->nins = 0;
	s->ins = NULL;
	s->nouts = 0;
	s->outs = NULL;
	s->tmp = NULL;
	s->next = NULL;
	if (nfa->slast != NULL) {
		assert(nfa->slast->next == NULL);
		nfa->slast->next = s;
	}
	s->prev = nfa->slast;
	nfa->slast = s;
	return s;
}

/*
 - newfstate - allocate an NFA state with a specified flag value
 ^ static struct state *newfstate(struct nfa *, int flag);
 */
static struct state *		/* NULL on error */
newfstate(nfa, flag)
struct nfa *nfa;
int flag;
{
	struct state *s;

	s = newstate(nfa);
	if (s != NULL)
		s->flag = (char)flag;
	return s;
}

/*
 - dropstate - delete a state's inarcs and outarcs and free it
 ^ static VOID dropstate(struct nfa *, struct state *);
 */
static VOID
dropstate(nfa, s)
struct nfa *nfa;
struct state *s;
{
	struct arc *a;

	while ((a = s->ins) != NULL)
		freearc(nfa, a);
	while ((a = s->outs) != NULL)
		freearc(nfa, a);
	freestate(nfa, s);
}

/*
 - freestate - free a state, which has no in-arcs or out-arcs
 ^ static VOID freestate(struct nfa *, struct state *);
 */
static VOID
freestate(nfa, s)
struct nfa *nfa;
struct state *s;
{
	assert(s != NULL);
	assert(s->nins == 0 && s->nouts == 0);

	s->no = FREESTATE;
	s->flag = 0;
	if (s->next != NULL)
		s->next->prev = s->prev;
	else {
		assert(s == nfa->slast);
		nfa->slast = s->prev;
	}
	if (s->prev != NULL)
		s->prev->next = s->next;
	else {
		assert(s == nfa->states);
		nfa->states = s->next;
	}
	s->prev = NULL;
	s->next = nfa->free;	/* don't delete it, put it on the free list */
	nfa->free = s;
}

/*
 - destroystate - really get rid of an already-freed state
 ^ static VOID destroystate(struct nfa *, struct state *);
 */
static VOID
destroystate(nfa, s)
struct nfa *nfa;
struct state *s;
{
	struct arcbatch *ab;
	struct arcbatch *abnext;

	assert(s->no == FREESTATE);
	for (ab = s->oas.next; ab != NULL; ab = abnext) {
		abnext = ab->next;
		FREE(ab);
	}
	s->ins = NULL;
	s->outs = NULL;
	s->next = NULL;
	FREE(s);
}

/*
 - newarc - set up a new arc within an NFA
 ^ static VOID newarc(struct nfa *, int, pcolor, struct state *, 
 ^	struct state *);
 */
static VOID
newarc(nfa, t, co, from, to)
struct nfa *nfa;
int t;
pcolor co;
struct state *from;
struct state *to;
{
	struct arc *a;

	assert(from != NULL && to != NULL);

	/* check for duplicates */
	for (a = from->outs; a != NULL; a = a->outchain)
		if (a->to == to && a->co == co && a->type == t)
			return;

	a = allocarc(nfa, from);
	if (NISERR())
		return;
	assert(a != NULL);

	a->type = t;
	a->co = (color)co;
	a->to = to;
	a->from = from;

	/*
	 * Put the new arc on the beginning, not the end, of the chains.
	 * Not only is this easier, it has the very useful side effect that 
	 * deleting the most-recently-added arc is the cheapest case rather
	 * than the most expensive one.
	 */
	a->inchain = to->ins;
	to->ins = a;
	a->outchain = from->outs;
	from->outs = a;

	from->nouts++;
	to->nins++;

	if (COLORED(a) && nfa->parent == NULL)
		colorchain(nfa->cm, a);

	return;
}

/*
 - allocarc - allocate a new out-arc within a state
 ^ static struct arc *allocarc(struct nfa *, struct state *);
 */
static struct arc *		/* NULL for failure */
allocarc(nfa, s)
struct nfa *nfa;
struct state *s;
{
	struct arc *a;
	struct arcbatch *new;
	int i;

	/* shortcut */
	if (s->free == NULL && s->noas < ABSIZE) {
		a = &s->oas.a[s->noas];
		s->noas++;
		return a;
	}

	/* if none at hand, get more */
	if (s->free == NULL) {
		new = (struct arcbatch *)MALLOC(sizeof(struct arcbatch));
		if (new == NULL) {
			NERR(REG_ESPACE);
			return NULL;
		}
		new->next = s->oas.next;
		s->oas.next = new;

		for (i = 0; i < ABSIZE; i++) {
			new->a[i].type = 0;
			new->a[i].freechain = &new->a[i+1];
		}
		new->a[ABSIZE-1].freechain = NULL;
		s->free = &new->a[0];
	}
	assert(s->free != NULL);

	a = s->free;
	s->free = a->freechain;
	return a;
}

/*
 - freearc - free an arc
 ^ static VOID freearc(struct nfa *, struct arc *);
 */
static VOID
freearc(nfa, victim)
struct nfa *nfa;
struct arc *victim;
{
	struct state *from = victim->from;
	struct state *to = victim->to;
	struct arc *a;

	assert(victim->type != 0);

	/* take it off color chain if necessary */
	if (COLORED(victim) && nfa->parent == NULL)
		uncolorchain(nfa->cm, victim);

	/* take it off source's out-chain */
	assert(from != NULL);
	assert(from->outs != NULL);
	a = from->outs;
	if (a == victim)		/* simple case:  first in chain */
		from->outs = victim->outchain;
	else {
		for (; a != NULL && a->outchain != victim; a = a->outchain)
			continue;
		assert(a != NULL);
		a->outchain = victim->outchain;
	}
	from->nouts--;

	/* take it off target's in-chain */
	assert(to != NULL);
	assert(to->ins != NULL);
	a = to->ins;
	if (a == victim)		/* simple case:  first in chain */
		to->ins = victim->inchain;
	else {
		for (; a != NULL && a->inchain != victim; a = a->inchain)
			continue;
		assert(a != NULL);
		a->inchain = victim->inchain;
	}
	to->nins--;

	/* clean up and place on free list */
	victim->type = 0;
	victim->from = NULL;		/* precautions... */
	victim->to = NULL;
	victim->inchain = NULL;
	victim->outchain = NULL;
	victim->freechain = from->free;
	from->free = victim;
}

/*
 - findarc - find arc, if any, from given source with given type and color
 * If there is more than one such arc, the result is random.
 ^ static struct arc *findarc(struct state *, int, pcolor);
 */
static struct arc *
findarc(s, type, co)
struct state *s;
int type;
pcolor co;
{
	struct arc *a;

	for (a = s->outs; a != NULL; a = a->outchain)
		if (a->type == type && a->co == co)
			return a;
	return NULL;
}

/*
 - cparc - allocate a new arc within an NFA, copying details from old one
 ^ static VOID cparc(struct nfa *, struct arc *, struct state *, 
 ^ 	struct state *);
 */
static VOID
cparc(nfa, oa, from, to)
struct nfa *nfa;
struct arc *oa;
struct state *from;
struct state *to;
{
	newarc(nfa, oa->type, oa->co, from, to);
}

/*
 - moveins - move all in arcs of a state to another state
 * You might think this could be done better by just updating the
 * existing arcs, and you would be right if it weren't for the desire
 * for duplicate suppression, which makes it easier to just make new
 * ones to exploit the suppression built into newarc.
 ^ static VOID moveins(struct nfa *, struct state *, struct state *);
 */
static VOID
moveins(nfa, old, new)
struct nfa *nfa;
struct state *old;
struct state *new;
{
	struct arc *a;

	assert(old != new);

	while ((a = old->ins) != NULL) {
		cparc(nfa, a, a->from, new);
		freearc(nfa, a);
	}
	assert(old->nins == 0);
	assert(old->ins == NULL);
}

/*
 - copyins - copy all in arcs of a state to another state
 ^ static VOID copyins(struct nfa *, struct state *, struct state *);
 */
static VOID
copyins(nfa, old, new)
struct nfa *nfa;
struct state *old;
struct state *new;
{
	struct arc *a;

	assert(old != new);

	for (a = old->ins; a != NULL; a = a->inchain)
		cparc(nfa, a, a->from, new);
}

/*
 - moveouts - move all out arcs of a state to another state
 ^ static VOID moveouts(struct nfa *, struct state *, struct state *);
 */
static VOID
moveouts(nfa, old, new)
struct nfa *nfa;
struct state *old;
struct state *new;
{
	struct arc *a;

	assert(old != new);

	while ((a = old->outs) != NULL) {
		cparc(nfa, a, new, a->to);
		freearc(nfa, a);
	}
}

/*
 - copyouts - copy all out arcs of a state to another state
 ^ static VOID copyouts(struct nfa *, struct state *, struct state *);
 */
static VOID
copyouts(nfa, old, new)
struct nfa *nfa;
struct state *old;
struct state *new;
{
	struct arc *a;

	assert(old != new);

	for (a = old->outs; a != NULL; a = a->outchain)
		cparc(nfa, a, new, a->to);
}

/*
 - cloneouts - copy out arcs of a state to another state pair, modifying type
 ^ static VOID cloneouts(struct nfa *, struct state *, struct state *,
 ^ 	struct state *, int);
 */
static VOID
cloneouts(nfa, old, from, to, type)
struct nfa *nfa;
struct state *old;
struct state *from;
struct state *to;