src/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	dashley	71	/* $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 */