regc_color.c

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

/*
 * colorings of characters
 * 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.
 *
 *
 *
 * Note that there are some incestuous relationships between this code and
 * NFA arc maintenance, which perhaps ought to be cleaned up sometime.
 */



#define	CISERR()	VISERR(cm->v)
#define	CERR(e)		VERR(cm->v, (e))



/*
 - initcm - set up new colormap
 ^ static VOID initcm(struct vars *, struct colormap *);
 */
static VOID
initcm(v, cm)
struct vars *v;
struct colormap *cm;
{
	int i;
	int j;
	union tree *t;
	union tree *nextt;
	struct colordesc *cd;

	cm->magic = CMMAGIC;
	cm->v = v;

	cm->ncds = NINLINECDS;
	cm->cd = cm->cdspace;
	cm->max = 0;
	cm->free = 0;

	cd = cm->cd;			/* cm->cd[WHITE] */
	cd->sub = NOSUB;
	cd->arcs = NULL;
	cd->flags = 0;
	cd->nchrs = CHR_MAX - CHR_MIN + 1;

	/* upper levels of tree */
	for (t = &cm->tree[0], j = NBYTS-1; j > 0; t = nextt, j--) {
		nextt = t + 1;
		for (i = BYTTAB-1; i >= 0; i--)
			t->tptr[i] = nextt;
	}
	/* bottom level is solid white */
	t = &cm->tree[NBYTS-1];
	for (i = BYTTAB-1; i >= 0; i--)
		t->tcolor[i] = WHITE;
	cd->block = t;
}

/*
 - freecm - free dynamically-allocated things in a colormap
 ^ static VOID freecm(struct colormap *);
 */
static VOID
freecm(cm)
struct colormap *cm;
{
	size_t i;
	union tree *cb;

	cm->magic = 0;
	if (NBYTS > 1)
		cmtreefree(cm, cm->tree, 0);
	for (i = 1; i <= cm->max; i++)		/* skip WHITE */
		if (!UNUSEDCOLOR(&cm->cd[i])) {
			cb = cm->cd[i].block;
			if (cb != NULL)
				FREE(cb);
		}
	if (cm->cd != cm->cdspace)
		FREE(cm->cd);
}

/*
 - cmtreefree - free a non-terminal part of a colormap tree
 ^ static VOID cmtreefree(struct colormap *, union tree *, int);
 */
static VOID
cmtreefree(cm, tree, level)
struct colormap *cm;
union tree *tree;
int level;			/* level number (top == 0) of this block */
{
	int i;
	union tree *t;
	union tree *fillt = &cm->tree[level+1];
	union tree *cb;

	assert(level < NBYTS-1);	/* this level has pointers */
	for (i = BYTTAB-1; i >= 0; i--) {
		t = tree->tptr[i];
		assert(t != NULL);
		if (t != fillt) {
			if (level < NBYTS-2) {	/* more pointer blocks below */
				cmtreefree(cm, t, level+1);
				FREE(t);
			} else {		/* color block below */
				cb = cm->cd[t->tcolor[0]].block;
				if (t != cb)	/* not a solid block */
					FREE(t);
			}
		}
	}
}

/*
 - setcolor - set the color of a character in a colormap
 ^ static color setcolor(struct colormap *, pchr, pcolor);
 */
static color			/* previous color */
setcolor(cm, c, co)
struct colormap *cm;
pchr c;
pcolor co;
{
	uchr uc = c;
	int shift;
	int level;
	int b;
	int bottom;
	union tree *t;
	union tree *newt;
	union tree *fillt;
	union tree *lastt;
	union tree *cb;
	color prev;

	assert(cm->magic == CMMAGIC);
	if (CISERR() || co == COLORLESS)
		return COLORLESS;

	t = cm->tree;
	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];
		bottom = (shift <= BYTBITS) ? 1 : 0;
		cb = (bottom) ? cm->cd[t->tcolor[0]].block : fillt;
		if (t == fillt || t == cb) {	/* must allocate a new block */
			newt = (union tree *)MALLOC((bottom) ?
				sizeof(struct colors) : sizeof(struct ptrs));
			if (newt == NULL) {
				CERR(REG_ESPACE);
				return COLORLESS;
			}
			if (bottom)
				memcpy(VS(newt->tcolor), VS(t->tcolor),
							BYTTAB*sizeof(color));
			else
				memcpy(VS(newt->tptr), VS(t->tptr),
						BYTTAB*sizeof(union tree *));
			t = newt;
			lastt->tptr[b] = t;
		}
	}

	b = uc & BYTMASK;
	prev = t->tcolor[b];
	t->tcolor[b] = (color)co;
	return prev;
}

/*
 - maxcolor - report largest color number in use
 ^ static color maxcolor(struct colormap *);
 */
static color
maxcolor(cm)
struct colormap *cm;
{
	if (CISERR())
		return COLORLESS;

	return (color)cm->max;
}

/*
 - newcolor - find a new color (must be subject of setcolor at once)
 * Beware:  may relocate the colordescs.
 ^ static color newcolor(struct colormap *);
 */
static color			/* COLORLESS for error */
newcolor(cm)
struct colormap *cm;
{
	struct colordesc *cd;
	struct colordesc *new;
	size_t n;

	if (CISERR())
		return COLORLESS;

	if (cm->free != 0) {
		assert(cm->free > 0);
		assert((size_t)cm->free < cm->ncds);
		cd = &cm->cd[cm->free];
		assert(UNUSEDCOLOR(cd));
		assert(cd->arcs == NULL);
		cm->free = cd->sub;
	} else if (cm->max < cm->ncds - 1) {
		cm->max++;
		cd = &cm->cd[cm->max];
	} else {
		/* oops, must allocate more */
		n = cm->ncds * 2;
		if (cm->cd == cm->cdspace) {
			new = (struct colordesc *)MALLOC(n *
						sizeof(struct colordesc));
			if (new != NULL)
				memcpy(VS(new), VS(cm->cdspace), cm->ncds *
						sizeof(struct colordesc));
		} else
			new = (struct colordesc *)REALLOC(cm->cd,
						n * sizeof(struct colordesc));
		if (new == NULL) {
			CERR(REG_ESPACE);
			return COLORLESS;
		}
		cm->cd = new;
		cm->ncds = n;
		assert(cm->max < cm->ncds - 1);
		cm->max++;
		cd = &cm->cd[cm->max];
	}

	cd->nchrs = 0;
	cd->sub = NOSUB;
	cd->arcs = NULL;
	cd->flags = 0;
	cd->block = NULL;

	return (color)(cd - cm->cd);
}

/*
 - freecolor - free a color (must have no arcs or subcolor)
 ^ static VOID freecolor(struct colormap *, pcolor);
 */
static VOID
freecolor(cm, co)
struct colormap *cm;
pcolor co;
{
	struct colordesc *cd = &cm->cd[co];
	color pco, nco;			/* for freelist scan */

	assert(co >= 0);
	if (co == WHITE)
		return;

	assert(cd->arcs == NULL);
	assert(cd->sub == NOSUB);
	assert(cd->nchrs == 0);
	cd->flags = FREECOL;
	if (cd->block != NULL) {
		FREE(cd->block);
		cd->block = NULL;	/* just paranoia */
	}

	if ((size_t)co == cm->max) {
		while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max]))
			cm->max--;
		assert(cm->free >= 0);
		while ((size_t)cm->free > cm->max)
			cm->free = cm->cd[cm->free].sub;
		if (cm->free > 0) {
			assert(cm->free < cm->max);
			pco = cm->free;
			nco = cm->cd[pco].sub;
			while (nco > 0)
				if ((size_t)nco > cm->max) {
					/* take this one out of freelist */
					nco = cm->cd[nco].sub;
					cm->cd[pco].sub = nco;
				} else {
					assert(nco < cm->max);
					pco = nco;
					nco = cm->cd[pco].sub;
				}
		}
	} else {
		cd->sub = cm->free;
		cm->free = (color)(cd - cm->cd);
	}
}

/*
 - pseudocolor - allocate a false color, to be managed by other means
 ^ static color pseudocolor(struct colormap *);
 */
static color
pseudocolor(cm)
struct colormap *cm;
{
	color co;

	co = newcolor(cm);
	if (CISERR())
		return COLORLESS;
	cm->cd[co].nchrs = 1;
	cm->cd[co].flags = PSEUDO;
	return co;
}

/*
 - subcolor - allocate a new subcolor (if necessary) to this chr
 ^ static color subcolor(struct colormap *, pchr c);
 */
static color
subcolor(cm, c)
struct colormap *cm;
pchr c;
{
	color co;			/* current color of c */
	color sco;			/* new subcolor */

	co = GETCOLOR(cm, c);
	sco = newsub(cm, co);
	if (CISERR())
		return COLORLESS;
	assert(sco != COLORLESS);

	if (co == sco)		/* already in an open subcolor */
		return co;	/* rest is redundant */
	cm->cd[co].nchrs--;
	cm->cd[sco].nchrs++;
	setcolor(cm, c, sco);
	return sco;
}

/*
 - newsub - allocate a new subcolor (if necessary) for a color
 ^ static color newsub(struct colormap *, pcolor);
 */
static color
newsub(cm, co)
struct colormap *cm;
pcolor co;
{
	color sco;			/* new subcolor */

	sco = cm->cd[co].sub;
	if (sco == NOSUB) {		/* color has no open subcolor */
		if (cm->cd[co].nchrs == 1)	/* optimization */
			return co;
		sco = newcolor(cm);	/* must create subcolor */
		if (sco == COLORLESS) {
			assert(CISERR());
			return COLORLESS;
		}
		cm->cd[co].sub = sco;