src/regex/regc_color.c

/*
 * 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.
 *
 * $Header$
 *
 *
 * 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 * 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 * 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 * 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					/* previous color */
setcolor(struct colormap * cm,
		 chr 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 * 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					/* COLORLESS for error */
newcolor(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 * 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 * 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 * cm, chr 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 * 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;
		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 * v,
		 chr from,
		 chr 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 * v,
		 chr 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;
	union tree *t;
	union tree *cb;
	union tree *fillt;
	union tree *lastt;
	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 * 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 * 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 * 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						/* predicate */
singleton(struct colormap * cm,
		  chr 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 * 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 * 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

/*
 * dumpcolors - debugging output
 */
static void
dumpcolors(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 * 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(chr c,
		FILE *f)
{
	if (c == '\\')
		fprintf(f, "\\\\");
	else if (c > ' ' && c <= '~')
		putc((char) c, f);
	else
		fprintf(f, "\\u%04lx", (long) c);
}

#endif   /* REG_DEBUG */
Commit	Line	Data
	1	/*
	2	* colorings of characters
	3	* This file is #included by regcomp.c.
	4	*
	5	* Copyright (c) 1998, 1999 Henry Spencer. All rights reserved.
	6	*
	7	* Development of this software was funded, in part, by Cray Research Inc.,
	8	* UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
	9	* Corporation, none of whom are responsible for the results. The author
	10	* thanks all of them.
	11	*
	12	* Redistribution and use in source and binary forms -- with or without
	13	* modification -- are permitted for any purpose, provided that
	14	* redistributions in source form retain this entire copyright notice and
	15	* indicate the origin and nature of any modifications.
	16	*
	17	* I'd appreciate being given credit for this package in the documentation
	18	* of software which uses it, but that is not a requirement.
	19	*
	20	* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
	21	* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
	22	* AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
	23	* HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	24	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	25	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
	26	* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
	27	* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
	28	* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
	29	* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	30	*
	31	* $Header$
	32	*
	33	*
	34	* Note that there are some incestuous relationships between this code and
	35	* NFA arc maintenance, which perhaps ought to be cleaned up sometime.
	36	*/
	37
	38
	39
	40	#define CISERR() VISERR(cm->v)
	41	#define CERR(e) VERR(cm->v, (e))
	42
	43
	44
	45	/*
	46	* initcm - set up new colormap
	47	*/
	48	static void
	49	initcm(struct vars * v,
	50	struct colormap * cm)
	51	{
	52	int i;
	53	int j;
	54	union tree *t;
	55	union tree *nextt;
	56	struct colordesc *cd;
	57
	58	cm->magic = CMMAGIC;
	59	cm->v = v;
	60
	61	cm->ncds = NINLINECDS;
	62	cm->cd = cm->cdspace;
	63	cm->max = 0;
	64	cm->free = 0;
	65
	66	cd = cm->cd; /* cm->cd[WHITE] */
	67	cd->sub = NOSUB;
	68	cd->arcs = NULL;
	69	cd->flags = 0;
	70	cd->nchrs = CHR_MAX - CHR_MIN + 1;
	71
	72	/* upper levels of tree */
	73	for (t = &cm->tree[0], j = NBYTS - 1; j > 0; t = nextt, j--)
	74	{
	75	nextt = t + 1;
	76	for (i = BYTTAB - 1; i >= 0; i--)
	77	t->tptr[i] = nextt;
	78	}
	79	/* bottom level is solid white */
	80	t = &cm->tree[NBYTS - 1];
	81	for (i = BYTTAB - 1; i >= 0; i--)
	82	t->tcolor[i] = WHITE;
	83	cd->block = t;
	84	}
	85
	86	/*
	87	* freecm - free dynamically-allocated things in a colormap
	88	*/
	89	static void
	90	freecm(struct colormap * cm)
	91	{
	92	size_t i;
	93	union tree *cb;
	94
	95	cm->magic = 0;
	96	if (NBYTS > 1)
	97	cmtreefree(cm, cm->tree, 0);
	98	for (i = 1; i <= cm->max; i++) /* skip WHITE */
	99	if (!UNUSEDCOLOR(&cm->cd[i]))
	100	{
	101	cb = cm->cd[i].block;
	102	if (cb != NULL)
	103	FREE(cb);
	104	}
	105	if (cm->cd != cm->cdspace)
	106	FREE(cm->cd);
	107	}
	108
	109	/*
	110	* cmtreefree - free a non-terminal part of a colormap tree
	111	*/
	112	static void
	113	cmtreefree(struct colormap * cm,
	114	union tree * tree,
	115	int level) /* level number (top == 0) of this block */
	116	{
	117	int i;
	118	union tree *t;
	119	union tree *fillt = &cm->tree[level + 1];
	120	union tree *cb;
	121
	122	assert(level < NBYTS - 1); /* this level has pointers */
	123	for (i = BYTTAB - 1; i >= 0; i--)
	124	{
	125	t = tree->tptr[i];
	126	assert(t != NULL);
	127	if (t != fillt)
	128	{
	129	if (level < NBYTS - 2)
	130	{ /* more pointer blocks below */
	131	cmtreefree(cm, t, level + 1);
	132	FREE(t);
	133	}
	134	else
	135	{ /* color block below */
	136	cb = cm->cd[t->tcolor[0]].block;
	137	if (t != cb) /* not a solid block */
	138	FREE(t);
	139	}
	140	}
	141	}
	142	}
	143
	144	/*
	145	* setcolor - set the color of a character in a colormap
	146	*/
	147	static color /* previous color */
	148	setcolor(struct colormap * cm,
	149	chr c,
	150	pcolor co)
	151	{
	152	uchr uc = c;
	153	int shift;
	154	int level;
	155	int b;
	156	int bottom;
	157	union tree *t;
	158	union tree *newt;
	159	union tree *fillt;
	160	union tree *lastt;
	161	union tree *cb;
	162	color prev;
	163
	164	assert(cm->magic == CMMAGIC);
	165	if (CISERR() \|\| co == COLORLESS)
	166	return COLORLESS;
	167
	168	t = cm->tree;
	169	for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0;
	170	level++, shift -= BYTBITS)
	171	{
	172	b = (uc >> shift) & BYTMASK;
	173	lastt = t;
	174	t = lastt->tptr[b];
	175	assert(t != NULL);
	176	fillt = &cm->tree[level + 1];
	177	bottom = (shift <= BYTBITS) ? 1 : 0;
	178	cb = (bottom) ? cm->cd[t->tcolor[0]].block : fillt;
	179	if (t == fillt \|\| t == cb)
	180	{ /* must allocate a new block */
	181	newt = (union tree *) MALLOC((bottom) ?
	182	sizeof(struct colors) : sizeof(struct ptrs));
	183	if (newt == NULL)
	184	{
	185	CERR(REG_ESPACE);
	186	return COLORLESS;
	187	}
	188	if (bottom)
	189	memcpy(VS(newt->tcolor), VS(t->tcolor),
	190	BYTTAB * sizeof(color));
	191	else
	192	memcpy(VS(newt->tptr), VS(t->tptr),
	193	BYTTAB * sizeof(union tree *));
	194	t = newt;
	195	lastt->tptr[b] = t;
	196	}
	197	}
	198
	199	b = uc & BYTMASK;
	200	prev = t->tcolor[b];
	201	t->tcolor[b] = (color) co;
	202	return prev;
	203	}
	204
	205	/*
	206	* maxcolor - report largest color number in use
	207	*/
	208	static color
	209	maxcolor(struct colormap * cm)
	210	{
	211	if (CISERR())
	212	return COLORLESS;
	213
	214	return (color) cm->max;
	215	}
	216
	217	/*
	218	* newcolor - find a new color (must be subject of setcolor at once)
	219	* Beware: may relocate the colordescs.
	220	*/
	221	static color /* COLORLESS for error */
	222	newcolor(struct colormap * cm)
	223	{
	224	struct colordesc *cd;
	225	struct colordesc *new;
	226	size_t n;
	227
	228	if (CISERR())
	229	return COLORLESS;
	230
	231	if (cm->free != 0)
	232	{
	233	assert(cm->free > 0);
	234	assert((size_t) cm->free < cm->ncds);
	235	cd = &cm->cd[cm->free];
	236	assert(UNUSEDCOLOR(cd));
	237	assert(cd->arcs == NULL);
	238	cm->free = cd->sub;
	239	}
	240	else if (cm->max < cm->ncds - 1)
	241	{
	242	cm->max++;
	243	cd = &cm->cd[cm->max];
	244	}
	245	else
	246	{
	247	/* oops, must allocate more */
	248	n = cm->ncds * 2;
	249	if (cm->cd == cm->cdspace)
	250	{
	251	new = (struct colordesc ) MALLOC(n
	252	sizeof(struct colordesc));
	253	if (new != NULL)
	254	memcpy(VS(new), VS(cm->cdspace), cm->ncds *
	255	sizeof(struct colordesc));
	256	}
	257	else
	258	new = (struct colordesc *) REALLOC(cm->cd,
	259	n * sizeof(struct colordesc));
	260	if (new == NULL)
	261	{
	262	CERR(REG_ESPACE);
	263	return COLORLESS;
	264	}
	265	cm->cd = new;
	266	cm->ncds = n;
	267	assert(cm->max < cm->ncds - 1);
	268	cm->max++;
	269	cd = &cm->cd[cm->max];
	270	}
	271
	272	cd->nchrs = 0;
	273	cd->sub = NOSUB;
	274	cd->arcs = NULL;
	275	cd->flags = 0;
	276	cd->block = NULL;
	277
	278	return (color) (cd - cm->cd);
	279	}
	280
	281	/*
	282	* freecolor - free a color (must have no arcs or subcolor)
	283	*/
	284	static void
	285	freecolor(struct colormap * cm,
	286	pcolor co)
	287	{
	288	struct colordesc *cd = &cm->cd[co];
	289	color pco,
	290	nco; /* for freelist scan */
	291
	292	assert(co >= 0);
	293	if (co == WHITE)
	294	return;
	295
	296	assert(cd->arcs == NULL);
	297	assert(cd->sub == NOSUB);
	298	assert(cd->nchrs == 0);
	299	cd->flags = FREECOL;
	300	if (cd->block != NULL)
	301	{
	302	FREE(cd->block);
	303	cd->block = NULL; /* just paranoia */
	304	}
	305
	306	if ((size_t) co == cm->max)
	307	{
	308	while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max]))
	309	cm->max--;
	310	assert(cm->free >= 0);
	311	while ((size_t) cm->free > cm->max)
	312	cm->free = cm->cd[cm->free].sub;
	313	if (cm->free > 0)
	314	{
	315	assert(cm->free < cm->max);
	316	pco = cm->free;
	317	nco = cm->cd[pco].sub;
	318	while (nco > 0)
	319	if ((size_t) nco > cm->max)
	320	{
	321	/* take this one out of freelist */
	322	nco = cm->cd[nco].sub;
	323	cm->cd[pco].sub = nco;
	324	}
	325	else
	326	{
	327	assert(nco < cm->max);
	328	pco = nco;
	329	nco = cm->cd[pco].sub;
	330	}
	331	}
	332	}
	333	else
	334	{
	335	cd->sub = cm->free;
	336	cm->free = (color) (cd - cm->cd);
	337	}
	338	}
	339
	340	/*
	341	* pseudocolor - allocate a false color, to be managed by other means
	342	*/
	343	static color
	344	pseudocolor(struct colormap * cm)
	345	{
	346	color co;
	347
	348	co = newcolor(cm);
	349	if (CISERR())
	350	return COLORLESS;
	351	cm->cd[co].nchrs = 1;
	352	cm->cd[co].flags = PSEUDO;
	353	return co;
	354	}
	355
	356	/*
	357	* subcolor - allocate a new subcolor (if necessary) to this chr
	358	*/
	359	static color
	360	subcolor(struct colormap * cm, chr c)
	361	{
	362	color co; /* current color of c */
	363	color sco; /* new subcolor */
	364
	365	co = GETCOLOR(cm, c);
	366	sco = newsub(cm, co);
	367	if (CISERR())
	368	return COLORLESS;
	369	assert(sco != COLORLESS);
	370
	371	if (co == sco) /* already in an open subcolor */
	372	return co; /* rest is redundant */
	373	cm->cd[co].nchrs--;
	374	cm->cd[sco].nchrs++;
	375	setcolor(cm, c, sco);
	376	return sco;
	377	}
	378
	379	/*
	380	* newsub - allocate a new subcolor (if necessary) for a color
	381	*/
	382	static color
	383	newsub(struct colormap * cm,
	384	pcolor co)
	385	{
	386	color sco; /* new subcolor */
	387
	388	sco = cm->cd[co].sub;
	389	if (sco == NOSUB)
	390	{ /* color has no open subcolor */
	391	if (cm->cd[co].nchrs == 1) /* optimization */
	392	return co;
	393	sco = newcolor(cm); /* must create subcolor */
	394	if (sco == COLORLESS)
	395	{
	396	assert(CISERR());
	397	return COLORLESS;
	398	}
	399	cm->cd[co].sub = sco;
	400	cm->cd[sco].sub = sco; /* open subcolor points to self */
	401	}
	402	assert(sco != NOSUB);
	403
	404	return sco;
	405	}
	406
	407	/*
	408	* subrange - allocate new subcolors to this range of chrs, fill in arcs
	409	*/
	410	static void
	411	subrange(struct vars * v,
	412	chr from,
	413	chr to,
	414	struct state * lp,
	415	struct state * rp)
	416	{
	417	uchr uf;
	418	int i;
	419
	420	assert(from <= to);
	421
	422	/* first, align "from" on a tree-block boundary */
	423	uf = (uchr) from;
	424	i = (int) (((uf + BYTTAB - 1) & (uchr) ~BYTMASK) - uf);
	425	for (; from <= to && i > 0; i--, from++)
	426	newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
	427	if (from > to) /* didn't reach a boundary */
	428	return;
	429
	430	/* deal with whole blocks */
	431	for (; to - from >= BYTTAB; from += BYTTAB)
	432	subblock(v, from, lp, rp);
	433
	434	/* clean up any remaining partial table */
	435	for (; from <= to; from++)
	436	newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
	437	}
	438
	439	/*
	440	* subblock - allocate new subcolors for one tree block of chrs, fill in arcs
	441	*/
	442	static void
	443	subblock(struct vars * v,
	444	chr start, /* first of BYTTAB chrs */
	445	struct state * lp,
	446	struct state * rp)
	447	{
	448	uchr uc = start;
	449	struct colormap *cm = v->cm;
	450	int shift;
	451	int level;
	452	int i;
	453	int b;
	454	union tree *t;
	455	union tree *cb;
	456	union tree *fillt;
	457	union tree *lastt;
	458	int previ;
	459	int ndone;
	460	color co;
	461	color sco;
	462
	463	assert((uc % BYTTAB) == 0);
	464
	465	/* find its color block, making new pointer blocks as needed */
	466	t = cm->tree;
	467	fillt = NULL;
	468	for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0;
	469	level++, shift -= BYTBITS)
	470	{
	471	b = (uc >> shift) & BYTMASK;
	472	lastt = t;
	473	t = lastt->tptr[b];
	474	assert(t != NULL);
	475	fillt = &cm->tree[level + 1];
	476	if (t == fillt && shift > BYTBITS)
	477	{ /* need new ptr block */
	478	t = (union tree *) MALLOC(sizeof(struct ptrs));
	479	if (t == NULL)
	480	{
	481	CERR(REG_ESPACE);
	482	return;
	483	}
	484	memcpy(VS(t->tptr), VS(fillt->tptr),
	485	BYTTAB * sizeof(union tree *));
	486	lastt->tptr[b] = t;
	487	}
	488	}
	489
	490	/* special cases: fill block or solid block */
	491	co = t->tcolor[0];
	492	cb = cm->cd[co].block;
	493	if (t == fillt \|\| t == cb)
	494	{
	495	/* either way, we want a subcolor solid block */
	496	sco = newsub(cm, co);
	497	t = cm->cd[sco].block;
	498	if (t == NULL)
	499	{ /* must set it up */
	500	t = (union tree *) MALLOC(sizeof(struct colors));
	501	if (t == NULL)
	502	{
	503	CERR(REG_ESPACE);
	504	return;
	505	}
	506	for (i = 0; i < BYTTAB; i++)
	507	t->tcolor[i] = sco;
	508	cm->cd[sco].block = t;
	509	}
	510	/* find loop must have run at least once */
	511	lastt->tptr[b] = t;
	512	newarc(v->nfa, PLAIN, sco, lp, rp);
	513	cm->cd[co].nchrs -= BYTTAB;
	514	cm->cd[sco].nchrs += BYTTAB;
	515	return;
	516	}
	517
	518	/* general case, a mixed block to be altered */
	519	i = 0;
	520	while (i < BYTTAB)
	521	{
	522	co = t->tcolor[i];
	523	sco = newsub(cm, co);
	524	newarc(v->nfa, PLAIN, sco, lp, rp);
	525	previ = i;
	526	do
	527	{
	528	t->tcolor[i++] = sco;
	529	} while (i < BYTTAB && t->tcolor[i] == co);
	530	ndone = i - previ;
	531	cm->cd[co].nchrs -= ndone;
	532	cm->cd[sco].nchrs += ndone;
	533	}
	534	}
	535
	536	/*
	537	* okcolors - promote subcolors to full colors
	538	*/
	539	static void
	540	okcolors(struct nfa * nfa,
	541	struct colormap * cm)
	542	{
	543	struct colordesc *cd;
	544	struct colordesc *end = CDEND(cm);
	545	struct colordesc *scd;
	546	struct arc *a;
	547	color co;
	548	color sco;
	549
	550	for (cd = cm->cd, co = 0; cd < end; cd++, co++)
	551	{
	552	sco = cd->sub;
	553	if (UNUSEDCOLOR(cd) \|\| sco == NOSUB)
	554	{
	555	/* has no subcolor, no further action */
	556	}
	557	else if (sco == co)
	558	{
	559	/* is subcolor, let parent deal with it */
	560	}
	561	else if (cd->nchrs == 0)
	562	{
	563	/* parent empty, its arcs change color to subcolor */
	564	cd->sub = NOSUB;
	565	scd = &cm->cd[sco];
	566	assert(scd->nchrs > 0);
	567	assert(scd->sub == sco);
	568	scd->sub = NOSUB;
	569	while ((a = cd->arcs) != NULL)
	570	{
	571	assert(a->co == co);
	572	/* uncolorchain(cm, a); */
	573	cd->arcs = a->colorchain;
	574	a->co = sco;
	575	/* colorchain(cm, a); */
	576	a->colorchain = scd->arcs;
	577	scd->arcs = a;
	578	}
	579	freecolor(cm, co);
	580	}
	581	else
	582	{
	583	/* parent's arcs must gain parallel subcolor arcs */
	584	cd->sub = NOSUB;
	585	scd = &cm->cd[sco];
	586	assert(scd->nchrs > 0);
	587	assert(scd->sub == sco);
	588	scd->sub = NOSUB;
	589	for (a = cd->arcs; a != NULL; a = a->colorchain)
	590	{
	591	assert(a->co == co);
	592	newarc(nfa, a->type, sco, a->from, a->to);
	593	}
	594	}
	595	}
	596	}
	597
	598	/*
	599	* colorchain - add this arc to the color chain of its color
	600	*/
	601	static void
	602	colorchain(struct colormap * cm,
	603	struct arc * a)
	604	{
	605	struct colordesc *cd = &cm->cd[a->co];
	606
	607	a->colorchain = cd->arcs;
	608	cd->arcs = a;
	609	}
	610
	611	/*
	612	* uncolorchain - delete this arc from the color chain of its color
	613	*/
	614	static void
	615	uncolorchain(struct colormap * cm,
	616	struct arc * a)
	617	{
	618	struct colordesc *cd = &cm->cd[a->co];
	619	struct arc *aa;
	620
	621	aa = cd->arcs;
	622	if (aa == a) /* easy case */
	623	cd->arcs = a->colorchain;
	624	else
	625	{
	626	for (; aa != NULL && aa->colorchain != a; aa = aa->colorchain)
	627	continue;
	628	assert(aa != NULL);
	629	aa->colorchain = a->colorchain;
	630	}
	631	a->colorchain = NULL; /* paranoia */
	632	}
	633
	634	/*
	635	* singleton - is this character in its own color?
	636	*/
	637	static int /* predicate */
	638	singleton(struct colormap * cm,
	639	chr c)
	640	{
	641	color co; /* color of c */
	642
	643	co = GETCOLOR(cm, c);
	644	if (cm->cd[co].nchrs == 1 && cm->cd[co].sub == NOSUB)
	645	return 1;
	646	return 0;
	647	}
	648
	649	/*
	650	* rainbow - add arcs of all full colors (but one) between specified states
	651	*/
	652	static void
	653	rainbow(struct nfa * nfa,
	654	struct colormap * cm,
	655	int type,
	656	pcolor but, /* COLORLESS if no exceptions */
	657	struct state * from,
	658	struct state * to)
	659	{
	660	struct colordesc *cd;
	661	struct colordesc *end = CDEND(cm);
	662	color co;
	663
	664	for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
	665	if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but &&
	666	!(cd->flags & PSEUDO))
	667	newarc(nfa, type, co, from, to);
	668	}
	669
	670	/*
	671	* colorcomplement - add arcs of complementary colors
	672	*
	673	* The calling sequence ought to be reconciled with cloneouts().
	674	*/
	675	static void
	676	colorcomplement(struct nfa * nfa,
	677	struct colormap * cm,
	678	int type,
	679	struct state * of, /* complements of this guy's PLAIN
	680	* outarcs */
	681	struct state * from,
	682	struct state * to)
	683	{
	684	struct colordesc *cd;
	685	struct colordesc *end = CDEND(cm);
	686	color co;
	687
	688	assert(of != from);
	689	for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
	690	if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO))
	691	if (findarc(of, PLAIN, co) == NULL)
	692	newarc(nfa, type, co, from, to);
	693	}
	694
	695
	696	#ifdef REG_DEBUG
	697
	698	/*
	699	* dumpcolors - debugging output
	700	*/
	701	static void
	702	dumpcolors(struct colormap * cm,
	703	FILE *f)
	704	{
	705	struct colordesc *cd;
	706	struct colordesc *end;
	707	color co;
	708	chr c;
	709	char *has;
	710
	711	fprintf(f, "max %ld\n", (long) cm->max);
	712	if (NBYTS > 1)
	713	fillcheck(cm, cm->tree, 0, f);
	714	end = CDEND(cm);
	715	for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++) /* skip 0 */
	716	if (!UNUSEDCOLOR(cd))
	717	{
	718	assert(cd->nchrs > 0);
	719	has = (cd->block != NULL) ? "#" : "";
	720	if (cd->flags & PSEUDO)
	721	fprintf(f, "#%2ld%s(ps): ", (long) co, has);
	722	else
	723	fprintf(f, "#%2ld%s(%2d): ", (long) co,
	724	has, cd->nchrs);
	725	/* it's hard to do this more efficiently */
	726	for (c = CHR_MIN; c < CHR_MAX; c++)
	727	if (GETCOLOR(cm, c) == co)
	728	dumpchr(c, f);
	729	assert(c == CHR_MAX);
	730	if (GETCOLOR(cm, c) == co)
	731	dumpchr(c, f);
	732	fprintf(f, "\n");
	733	}
	734	}
	735
	736	/*
	737	* fillcheck - check proper filling of a tree
	738	*/
	739	static void
	740	fillcheck(struct colormap * cm,
	741	union tree * tree,
	742	int level, /* level number (top == 0) of this block */
	743	FILE *f)
	744	{
	745	int i;
	746	union tree *t;
	747	union tree *fillt = &cm->tree[level + 1];
	748
	749	assert(level < NBYTS - 1); /* this level has pointers */
	750	for (i = BYTTAB - 1; i >= 0; i--)
	751	{
	752	t = tree->tptr[i];
	753	if (t == NULL)
	754	fprintf(f, "NULL found in filled tree!\n");
	755	else if (t == fillt)
	756	{
	757	}
	758	else if (level < NBYTS - 2) /* more pointer blocks below */
	759	fillcheck(cm, t, level + 1, f);
	760	}
	761	}
	762
	763	/*
	764	* dumpchr - print a chr
	765	*
	766	* Kind of char-centric but works well enough for debug use.
	767	*/
	768	static void
	769	dumpchr(chr c,
	770	FILE *f)
	771	{
	772	if (c == '\\')
	773	fprintf(f, "\\\\");
	774	else if (c > ' ' && c <= '~')
	775	putc((char) c, f);
	776	else
	777	fprintf(f, "\\u%04lx", (long) c);
	778	}
	779
	780	#endif /* REG_DEBUG */