diff options
Diffstat (limited to 'tcl8.6/generic/regc_color.c')
| -rw-r--r-- | tcl8.6/generic/regc_color.c | 856 |
1 files changed, 0 insertions, 856 deletions
diff --git a/tcl8.6/generic/regc_color.c b/tcl8.6/generic/regc_color.c deleted file mode 100644 index 92e0aad..0000000 --- a/tcl8.6/generic/regc_color.c +++ /dev/null @@ -1,856 +0,0 @@ -/* - * 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: - */ |