regc_color.c

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

		cm->cd[sco].sub = sco;	/* open subcolor points to self */
	}
	assert(sco != NOSUB);

	return sco;
}

/*
 - subrange - allocate new subcolors to this range of chrs, fill in arcs
 ^ static VOID subrange(struct vars *, pchr, pchr, struct state *,
 ^ 	struct state *);
 */
static VOID
subrange(v, from, to, lp, rp)
struct vars *v;
pchr from;
pchr to;
struct state *lp;
struct state *rp;
{
	uchr uf;
	int i;

	assert(from <= to);

	/* first, align "from" on a tree-block boundary */
	uf = (uchr)from;
	i = (int)( ((uf + BYTTAB-1) & (uchr)~BYTMASK) - uf );
	for (; from <= to && i > 0; i--, from++)
		newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
	if (from > to)			/* didn't reach a boundary */
		return;

	/* deal with whole blocks */
	for (; to - from >= BYTTAB; from += BYTTAB)
		subblock(v, from, lp, rp);

	/* clean up any remaining partial table */
	for (; from <= to; from++)
		newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
}

/*
 - subblock - allocate new subcolors for one tree block of chrs, fill in arcs
 ^ static VOID subblock(struct vars *, pchr, struct state *, struct state *);
 */
static VOID
subblock(v, start, lp, rp)
struct vars *v;
pchr start;			/* first of BYTTAB chrs */
struct state *lp;
struct state *rp;
{
	uchr uc = start;
	struct colormap *cm = v->cm;
	int shift;
	int level;
	int i;
	int b = 0;
	union tree *t;
	union tree *cb;
	union tree *fillt;
	union tree *lastt = NULL;
	int previ;
	int ndone;
	color co;
	color sco;

	assert((uc % BYTTAB) == 0);

	/* find its color block, making new pointer blocks as needed */
	t = cm->tree;
	fillt = NULL;
	for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0;
						level++, shift -= BYTBITS) {
		b = (uc >> shift) & BYTMASK;
		lastt = t;
		t = lastt->tptr[b];
		assert(t != NULL);
		fillt = &cm->tree[level+1];
		if (t == fillt && shift > BYTBITS) {	/* need new ptr block */
			t = (union tree *)MALLOC(sizeof(struct ptrs));
			if (t == NULL) {
				CERR(REG_ESPACE);
				return;
			}
			memcpy(VS(t->tptr), VS(fillt->tptr),
						BYTTAB*sizeof(union tree *));
			lastt->tptr[b] = t;
		}
	}

	/* special cases:  fill block or solid block */
	co = t->tcolor[0];
	cb = cm->cd[co].block;
	if (t == fillt || t == cb) {
		/* either way, we want a subcolor solid block */
		sco = newsub(cm, co);
		t = cm->cd[sco].block;
		if (t == NULL) {	/* must set it up */
			t = (union tree *)MALLOC(sizeof(struct colors));
			if (t == NULL) {
				CERR(REG_ESPACE);
				return;
			}
			for (i = 0; i < BYTTAB; i++)
				t->tcolor[i] = sco;
			cm->cd[sco].block = t;
		}
		/* find loop must have run at least once */
		lastt->tptr[b] = t;
		newarc(v->nfa, PLAIN, sco, lp, rp);
		cm->cd[co].nchrs -= BYTTAB;
		cm->cd[sco].nchrs += BYTTAB;
		return;
	}

	/* general case, a mixed block to be altered */
	i = 0;
	while (i < BYTTAB) {
		co = t->tcolor[i];
		sco = newsub(cm, co);
		newarc(v->nfa, PLAIN, sco, lp, rp);
		previ = i;
		do {
			t->tcolor[i++] = sco;
		} while (i < BYTTAB && t->tcolor[i] == co);
		ndone = i - previ;
		cm->cd[co].nchrs -= ndone;
		cm->cd[sco].nchrs += ndone;
	}
}

/*
 - okcolors - promote subcolors to full colors
 ^ static VOID okcolors(struct nfa *, struct colormap *);
 */
static VOID
okcolors(nfa, cm)
struct nfa *nfa;
struct colormap *cm;
{
	struct colordesc *cd;
	struct colordesc *end = CDEND(cm);
	struct colordesc *scd;
	struct arc *a;
	color co;
	color sco;

	for (cd = cm->cd, co = 0; cd < end; cd++, co++) {
		sco = cd->sub;
		if (UNUSEDCOLOR(cd) || sco == NOSUB) {
			/* has no subcolor, no further action */
		} else if (sco == co) {
			/* is subcolor, let parent deal with it */
		} else if (cd->nchrs == 0) {
			/* parent empty, its arcs change color to subcolor */
			cd->sub = NOSUB;
			scd = &cm->cd[sco];
			assert(scd->nchrs > 0);
			assert(scd->sub == sco);
			scd->sub = NOSUB;
			while ((a = cd->arcs) != NULL) {
				assert(a->co == co);
				/* uncolorchain(cm, a); */
				cd->arcs = a->colorchain;
				a->co = sco;
				/* colorchain(cm, a); */
				a->colorchain = scd->arcs;
				scd->arcs = a;
			}
			freecolor(cm, co);
		} else {
			/* parent's arcs must gain parallel subcolor arcs */
			cd->sub = NOSUB;
			scd = &cm->cd[sco];
			assert(scd->nchrs > 0);
			assert(scd->sub == sco);
			scd->sub = NOSUB;
			for (a = cd->arcs; a != NULL; a = a->colorchain) {
				assert(a->co == co);
				newarc(nfa, a->type, sco, a->from, a->to);
			}
		}
	}
}

/*
 - colorchain - add this arc to the color chain of its color
 ^ static VOID colorchain(struct colormap *, struct arc *);
 */
static VOID
colorchain(cm, a)
struct colormap *cm;
struct arc *a;
{
	struct colordesc *cd = &cm->cd[a->co];

	a->colorchain = cd->arcs;
	cd->arcs = a;
}

/*
 - uncolorchain - delete this arc from the color chain of its color
 ^ static VOID uncolorchain(struct colormap *, struct arc *);
 */
static VOID
uncolorchain(cm, a)
struct colormap *cm;
struct arc *a;
{
	struct colordesc *cd = &cm->cd[a->co];
	struct arc *aa;

	aa = cd->arcs;
	if (aa == a)		/* easy case */
		cd->arcs = a->colorchain;
	else {
		for (; aa != NULL && aa->colorchain != a; aa = aa->colorchain)
			continue;
		assert(aa != NULL);
		aa->colorchain = a->colorchain;
	}
	a->colorchain = NULL;	/* paranoia */
}

/*
 - singleton - is this character in its own color?
 ^ static int singleton(struct colormap *, pchr c);
 */
static int			/* predicate */
singleton(cm, c)
struct colormap *cm;
pchr c;
{
	color co;			/* color of c */

	co = GETCOLOR(cm, c);
	if (cm->cd[co].nchrs == 1 && cm->cd[co].sub == NOSUB)
		return 1;
	return 0;
}

/*
 - rainbow - add arcs of all full colors (but one) between specified states
 ^ static VOID rainbow(struct nfa *, struct colormap *, int, pcolor,
 ^ 	struct state *, struct state *);
 */
static VOID
rainbow(nfa, cm, type, but, from, to)
struct nfa *nfa;
struct colormap *cm;
int type;
pcolor but;			/* COLORLESS if no exceptions */
struct state *from;
struct state *to;
{
	struct colordesc *cd;
	struct colordesc *end = CDEND(cm);
	color co;

	for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
		if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but &&
							!(cd->flags&PSEUDO))
			newarc(nfa, type, co, from, to);
}

/*
 - colorcomplement - add arcs of complementary colors
 * The calling sequence ought to be reconciled with cloneouts().
 ^ static VOID colorcomplement(struct nfa *, struct colormap *, int,
 ^ 	struct state *, struct state *, struct state *);
 */
static VOID
colorcomplement(nfa, cm, type, of, from, to)
struct nfa *nfa;
struct colormap *cm;
int type;
struct state *of;		/* complements of this guy's PLAIN outarcs */
struct state *from;
struct state *to;
{
	struct colordesc *cd;
	struct colordesc *end = CDEND(cm);
	color co;

	assert(of != from);
	for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
		if (!UNUSEDCOLOR(cd) && !(cd->flags&PSEUDO))
			if (findarc(of, PLAIN, co) == NULL)
				newarc(nfa, type, co, from, to);
}



#ifdef REG_DEBUG
/*
 ^ #ifdef REG_DEBUG
 */

/*
 - dumpcolors - debugging output
 ^ static VOID dumpcolors(struct colormap *, FILE *);
 */
static VOID
dumpcolors(cm, f)
struct colormap *cm;
FILE *f;
{
	struct colordesc *cd;
	struct colordesc *end;
	color co;
	chr c;
	char *has;

	fprintf(f, "max %ld\n", (long)cm->max);
	if (NBYTS > 1)
		fillcheck(cm, cm->tree, 0, f);
	end = CDEND(cm);
	for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++)	/* skip 0 */
		if (!UNUSEDCOLOR(cd)) {
			assert(cd->nchrs > 0);
			has = (cd->block != NULL) ? "#" : "";
			if (cd->flags&PSEUDO)
				fprintf(f, "#%2ld%s(ps): ", (long)co, has);
			else
				fprintf(f, "#%2ld%s(%2d): ", (long)co,
							has, cd->nchrs);
			/* it's hard to do this more efficiently */
			for (c = CHR_MIN; c < CHR_MAX; c++)
				if (GETCOLOR(cm, c) == co)
					dumpchr(c, f);
			assert(c == CHR_MAX);
			if (GETCOLOR(cm, c) == co)
				dumpchr(c, f);
			fprintf(f, "\n");
		}
}

/*
 - fillcheck - check proper filling of a tree
 ^ static VOID fillcheck(struct colormap *, union tree *, int, FILE *);
 */
static VOID
fillcheck(cm, tree, level, f)
struct colormap *cm;
union tree *tree;
int level;			/* level number (top == 0) of this block */
FILE *f;
{
	int i;
	union tree *t;
	union tree *fillt = &cm->tree[level+1];

	assert(level < NBYTS-1);	/* this level has pointers */
	for (i = BYTTAB-1; i >= 0; i--) {
		t = tree->tptr[i];
		if (t == NULL)
			fprintf(f, "NULL found in filled tree!\n");
		else if (t == fillt)
			{}
		else if (level < NBYTS-2)	/* more pointer blocks below */
			fillcheck(cm, t, level+1, f);
	}
}

/*
 - dumpchr - print a chr
 * Kind of char-centric but works well enough for debug use.
 ^ static VOID dumpchr(pchr, FILE *);
 */
static VOID
dumpchr(c, f)
pchr c;
FILE *f;
{
	if (c == '\\')
		fprintf(f, "\\\\");
	else if (c > ' ' && c <= '~')
		putc((char)c, f);
	else
		fprintf(f, "\\u%04lx", (long)c);
}

/*
 ^ #endif
 */
#endif				/* ifdef REG_DEBUG */