shared_source/c_tcl_base_7_5_w_mods/regc_color.c

/* $Header$ */
/*
 * 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 < (signed int)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 < (signed int)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;
                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;
        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 *, 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 */

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