src/backend/regex/regc_color.c - hawq - Git at Google

 /*
  * 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.
  *
  * $PostgreSQL: pgsql/src/backend/regex/regc_color.c,v 1.9 2008/02/14 17:33:37 tgl Exp $
  *
  *
  * 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;
 	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 */
 		struct colordesc *newCd;

 		n = cm->ncds * 2;
 		if (cm->cd == cm->cdspace)
 		{
 			newCd = (struct colordesc *) MALLOC(n * sizeof(struct colordesc));
 			if (newCd != NULL)
 				memcpy(VS(newCd), VS(cm->cdspace), cm->ncds *
 					   sizeof(struct colordesc));
 		}
 		else
 			newCd = (struct colordesc *)
 				REALLOC(cm->cd, n * sizeof(struct colordesc));
 		if (newCd == NULL)
 		{
 			CERR(REG_ESPACE);
 			return COLORLESS;
 		}
 		cm->cd = newCd;
 		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);
 				a->co = sco;
 				colorchain(cm, 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];

 	if (cd->arcs != NULL)
 		cd->arcs->colorchainRev = a;
 	a->colorchain = cd->arcs;
 	a->colorchainRev = NULL;
 	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 = a->colorchainRev;

 	if (aa == NULL)
 	{
 		assert(cd->arcs == a);
 		cd->arcs = a->colorchain;
 	}
 	else
 	{
 		assert(aa->colorchain == a);
 		aa->colorchain = a->colorchain;
 	}
 	if (a->colorchain != NULL)
 		a->colorchain->colorchainRev = aa;
 	a->colorchain = NULL;		/* paranoia */
 	a->colorchainRev = NULL;
 }

 /*
  * 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);

 			/*
 			 * Unfortunately, it's hard to do this next bit more efficiently.
 			 *
 			 * Spencer's original coding has the loop iterating from CHR_MIN
 			 * to CHR_MAX, but that's utterly unusable for 32-bit chr. For
 			 * debugging purposes it seems fine to print only chr codes up to
 			 * 1000 or so.
 			 */
 			for (c = CHR_MIN; c < 1000; c++)
 				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 */
	/*
	* 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.
	*
	* $PostgreSQL: pgsql/src/backend/regex/regc_color.c,v 1.9 2008/02/14 17:33:37 tgl Exp $
	*
	*
	* 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;
	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 */
	struct colordesc *newCd;

	n = cm->ncds * 2;
	if (cm->cd == cm->cdspace)
	{
	newCd = (struct colordesc ) MALLOC(n sizeof(struct colordesc));
	if (newCd != NULL)
	memcpy(VS(newCd), VS(cm->cdspace), cm->ncds *
	sizeof(struct colordesc));
	}
	else
	newCd = (struct colordesc *)
	REALLOC(cm->cd, n * sizeof(struct colordesc));
	if (newCd == NULL)
	{
	CERR(REG_ESPACE);
	return COLORLESS;
	}
	cm->cd = newCd;
	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);
	a->co = sco;
	colorchain(cm, 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];

	if (cd->arcs != NULL)
	cd->arcs->colorchainRev = a;
	a->colorchain = cd->arcs;
	a->colorchainRev = NULL;
	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 = a->colorchainRev;

	if (aa == NULL)
	{
	assert(cd->arcs == a);
	cd->arcs = a->colorchain;
	}
	else
	{
	assert(aa->colorchain == a);
	aa->colorchain = a->colorchain;
	}
	if (a->colorchain != NULL)
	a->colorchain->colorchainRev = aa;
	a->colorchain = NULL; /* paranoia */
	a->colorchainRev = NULL;
	}

	/*
	* 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);

	/*
	* Unfortunately, it's hard to do this next bit more efficiently.
	*
	* Spencer's original coding has the loop iterating from CHR_MIN
	* to CHR_MAX, but that's utterly unusable for 32-bit chr. For
	* debugging purposes it seems fine to print only chr codes up to
	* 1000 or so.
	*/
	for (c = CHR_MIN; c < 1000; c++)
	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 */