diff options
author | William Joye <wjoye@cfa.harvard.edu> | 2016-12-21 22:46:09 (GMT) |
---|---|---|
committer | William Joye <wjoye@cfa.harvard.edu> | 2016-12-21 22:46:09 (GMT) |
commit | 768f87f613cc9789fcf8073018fa02178c8c91df (patch) | |
tree | ec633f5608ef498bee52a5f42c12c49493ec8bf8 /tcl8.6/generic/regc_color.c | |
parent | 07e464099b99459d0a37757771791598ef3395d9 (diff) | |
parent | 05fa4c89f20e9769db0e6c0b429cef2590771ace (diff) | |
download | blt-768f87f613cc9789fcf8073018fa02178c8c91df.zip blt-768f87f613cc9789fcf8073018fa02178c8c91df.tar.gz blt-768f87f613cc9789fcf8073018fa02178c8c91df.tar.bz2 |
Merge commit '05fa4c89f20e9769db0e6c0b429cef2590771ace' as 'tcl8.6'
Diffstat (limited to 'tcl8.6/generic/regc_color.c')
-rw-r--r-- | tcl8.6/generic/regc_color.c | 856 |
1 files changed, 856 insertions, 0 deletions
diff --git a/tcl8.6/generic/regc_color.c b/tcl8.6/generic/regc_color.c new file mode 100644 index 0000000..92e0aad --- /dev/null +++ b/tcl8.6/generic/regc_color.c @@ -0,0 +1,856 @@ +/* + * 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( + 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( + 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( + 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( + 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(newt->tcolor, t->tcolor, BYTTAB*sizeof(color)); + } else { + memcpy(newt->tptr, 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( + 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( + 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 { + struct colordesc *newCd; + + /* + * Oops, must allocate more. + */ + + if (cm->max == MAX_COLOR) { + CERR(REG_ECOLORS); + return COLORLESS; /* too many colors */ + } + n = cm->ncds * 2; + if (n > MAX_COLOR + 1) { + n = MAX_COLOR + 1; + } + if (cm->cd == cm->cdspace) { + newCd = (struct colordesc *) MALLOC(n * sizeof(struct colordesc)); + if (newCd != NULL) { + memcpy(newCd, 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 *, pcolor); + */ +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((size_t)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((size_t)nco < cm->max); + pco = nco; + nco = cm->cd[pco].sub; + } + } + } + } else { + cd->sub = cm->free; + cm->free = (color) (cd - cm->cd); + } +} + +/* + - pseudocolor - allocate a false color, to be managed by other means + ^ static color pseudocolor(struct colormap *); + */ +static color +pseudocolor( + 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( + 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( + 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( + 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( + 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(t->tptr, 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( + 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 *, struct arc *); + */ +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 *, struct arc *); + */ +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 *, struct colormap *, int, pcolor, + ^ struct state *, struct state *); + */ +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 *, struct colormap *, int, + ^ struct state *, struct state *, struct state *); + */ +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 +/* + ^ #ifdef REG_DEBUG + */ + +/* + - dumpcolors - debugging output + ^ static void dumpcolors(struct colormap *, FILE *); + */ +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, or + * even 16-bit. 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 *, union tree *, int, FILE *); + */ +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) { + /* empty body */ + } 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( + 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 */ + +/* + * Local Variables: + * mode: c + * c-basic-offset: 4 + * fill-column: 78 + * End: + */ |