summaryrefslogtreecommitdiffstats
path: root/generic/regc_color.c
diff options
context:
space:
mode:
Diffstat (limited to 'generic/regc_color.c')
-rw-r--r--generic/regc_color.c619
1 files changed, 619 insertions, 0 deletions
diff --git a/generic/regc_color.c b/generic/regc_color.c
new file mode 100644
index 0000000..4a8a87c
--- /dev/null
+++ b/generic/regc_color.c
@@ -0,0 +1,619 @@
+/*
+ * colorings of characters
+ * This file is #included by regcomp.c.
+ *
+ * Note that there are some incestuous relationships between this code and
+ * NFA arc maintenance, which perhaps ought to be cleaned up sometime.
+ */
+
+
+
+/*
+ * If this declaration draws a complaint about a negative array size,
+ * then CHRBITS is defined incorrectly for the chr type.
+ */
+static char isCHRBITSright[NEGIFNOT(sizeof(chr)*CHAR_BIT == CHRBITS)];
+
+
+
+#define CISERR() VISERR(cm->v)
+#define CERR(e) VERR(cm->v, (e))
+
+
+
+/*
+ - newcm - get new colormap
+ ^ static struct colormap *newcm(struct vars *);
+ */
+static struct colormap * /* NULL for allocation failure */
+newcm(v)
+struct vars *v;
+{
+ struct colormap *cm;
+ int i;
+ int j;
+ union tree *t;
+ union tree *nextt;
+ struct colordesc *cd;
+
+ cm = (struct colormap *)MALLOC(sizeof(struct colormap));
+ if (cm == NULL) {
+ ERR(REG_ESPACE);
+ return NULL;
+ }
+ cm->magic = CMMAGIC;
+ cm->v = v;
+ cm->rest = WHITE;
+ cm->filled = 0;
+
+ cm->ncds = NINLINECDS;
+ cm->cd = cm->cds;
+ for (cd = cm->cd; cd < CDEND(cm); cd++) {
+ cd->nchrs = 0;
+ cd->sub = NOSUB;
+ cd->arcs = NULL;
+ cd->flags = 0;
+ }
+ cm->cd[WHITE].nchrs = CHR_MAX - CHR_MIN + 1;
+
+ /* treetop starts as NULLs if there are lower levels */
+ t = cm->tree;
+ if (NBYTS > 1)
+ for (i = BYTTAB-1; i >= 0; i--)
+ t->tptr[i] = NULL;
+ /* if no lower levels, treetop and last fill block are the same */
+
+ /* fill blocks point to next fill block... */
+ for (t = &cm->tree[1], j = NBYTS-2; j > 0; t = nextt, j--) {
+ nextt = t + 1;
+ for (i = BYTTAB-1; i >= 0; i--)
+ t->tptr[i] = t + 1;
+ }
+ /* ...except last which is solid white */
+ t = &cm->tree[NBYTS-1];
+ for (i = BYTTAB-1; i >= 0; i--)
+ t->tcolor[i] = WHITE;
+
+
+ return cm;
+}
+
+/*
+ - freecm - free a colormap
+ ^ static VOID freecm(struct colormap *);
+ */
+static VOID
+freecm(cm)
+struct colormap *cm;
+{
+ cm->magic = 0;
+ if (NBYTS > 1)
+ cmtreefree(cm, cm->tree, 0);
+ if (cm->cd != cm->cds)
+ FREE(cm->cd);
+ FREE(cm);
+}
+
+/*
+ - 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];
+
+ assert(level < NBYTS-1); /* this level has pointers */
+ for (i = BYTTAB-1; i >= 0; i--) {
+ t = tree->tptr[i];
+ if (t != NULL && t != fillt) {
+ if (level < NBYTS-2) /* more pointer blocks below */
+ cmtreefree(cm, t, level+1);
+ FREE(t);
+ }
+ }
+}
+
+/*
+ - fillcm - fill in a colormap, so no NULLs remain
+ * The point of this is that the tree traversal can then be a fixed set
+ * of table lookups with no conditional branching. It might be better
+ * to do reallocation for a more compacted structure, on the order of
+ * what's done for NFAs, but the colormap can be quite large and a total
+ * rebuild of it could be costly.
+ ^ static VOID fillcm(struct colormap *);
+ */
+static VOID
+fillcm(cm)
+struct colormap *cm;
+{
+ if (!cm->filled && NBYTS > 1)
+ cmtreefill(cm, cm->tree, 0);
+ cm->filled = 1;
+}
+
+/*
+ - cmtreefill - fill a non-terminal part of a colormap tree
+ ^ static VOID cmtreefill(struct colormap *, union tree *, int);
+ */
+static VOID
+cmtreefill(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];
+
+ assert(level < NBYTS-1); /* this level has pointers */
+ for (i = BYTTAB-1; i >= 0; i--) {
+ t = tree->tptr[i];
+ if (t == fillt) /* oops */
+ {}
+ else if (t == NULL)
+ tree->tptr[i] = fillt;
+ else if (level < NBYTS-2) /* more pointer blocks below */
+ cmtreefill(cm, t, level+1);
+ }
+}
+
+/*
+ - getcolor - get the color of a character from a colormap
+ ^ static color getcolor(struct colormap *, pchr);
+ */
+static color
+getcolor(cm, c)
+struct colormap *cm;
+pchr c;
+{
+ uchr uc = c;
+ int shift;
+ int b;
+ union tree *t;
+
+ assert(cm->magic == CMMAGIC);
+
+ t = cm->tree;
+ for (shift = BYTBITS * (NBYTS - 1); t != NULL; shift -= BYTBITS) {
+ b = (uc >> shift) & BYTMASK;
+ if (shift == 0) /* reached the bottom */
+ return t->tcolor[b];
+ t = t->tptr[b];
+ }
+
+ /* we fell off an incomplete part of the tree */
+ assert(!cm->filled);
+ return cm->rest;
+}
+
+/*
+ - 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 i;
+ int b;
+ int bottom;
+ union tree *t;
+ union tree *lastt;
+ color prev;
+
+ assert(cm->magic == CMMAGIC);
+ if (CISERR() || co == COLORLESS)
+ return COLORLESS;
+
+ t = cm->tree;
+ for (shift = BYTBITS * (NBYTS - 1); shift > 0; shift -= BYTBITS) {
+ b = (uc >> shift) & BYTMASK;
+ lastt = t;
+ t = t->tptr[b];
+ if (t == NULL) { /* fell off an incomplete part */
+ bottom = (shift <= BYTBITS) ? 1 : 0;
+ t = (union tree *)MALLOC((bottom) ?
+ sizeof(struct colors) : sizeof(struct ptrs));
+ if (t == NULL) {
+ CERR(REG_ESPACE);
+ return COLORLESS;
+ }
+ if (bottom)
+ for (i = BYTTAB-1; i >= 0; i--)
+ t->tcolor[i] = cm->rest;
+ else
+ for (i = BYTTAB-1; i >= 0; i--)
+ t->tptr[i] = NULL;
+ lastt->tptr[b] = t;
+ }
+ }
+ assert(shift == 0 && t != NULL); /* we hit bottom; it's there */
+
+ 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;
+{
+ struct colordesc *cd;
+ struct colordesc *end;
+ struct colordesc *lastused;
+
+ if (CISERR())
+ return COLORLESS;
+
+ lastused = NULL;
+ end = CDEND(cm);
+ for (cd = cm->cd; cd < end; cd++)
+ if (!UNUSEDCOLOR(cd))
+ lastused = cd;
+ assert(lastused != NULL);
+ return (color)(lastused - cm->cd);
+}
+
+/*
+ - 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 *end;
+ struct colordesc *firstnew;
+ size_t n;
+
+ if (CISERR())
+ return COLORLESS;
+
+ end = CDEND(cm);
+ for (cd = cm->cd; cd < end; cd++)
+ if (UNUSEDCOLOR(cd)) {
+ assert(cd->arcs == NULL);
+ return (color)(cd - cm->cd);
+ }
+
+ /* oops, must allocate more */
+ n = cm->ncds * 2;
+ if (cm->cd == cm->cds) {
+ cd = (struct colordesc *)MALLOC(sizeof(struct colordesc) * n);
+ if (cd != NULL)
+ memcpy(VS(cd), VS(cm->cds), cm->ncds *
+ sizeof(struct colordesc));
+ } else {
+ cd = (struct colordesc *)REALLOC(cm->cd,
+ n * sizeof(struct colordesc));
+ }
+ if (cd == NULL) {
+ CERR(REG_ESPACE);
+ return COLORLESS;
+ }
+ cm->cd = cd;
+ firstnew = CDEND(cm);
+ cm->ncds = n;
+ end = CDEND(cm);
+ for (cd = firstnew; cd < end; cd++) {
+ cd->nchrs = 0;
+ cd->sub = NOSUB;
+ cd->arcs = NULL;
+ cd->flags = 0;
+ }
+ assert(firstnew < CDEND(cm) && UNUSEDCOLOR(firstnew));
+ return (color)(firstnew - 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 = cm->cd[co].sub;
+ if (sco == NOSUB) { /* must create subcolor */
+ if (cm->cd[co].nchrs == 1) /* shortcut */
+ return co;
+ sco = newcolor(cm);
+ if (sco == COLORLESS)
+ return COLORLESS;
+ cm->cd[co].sub = sco;
+ cm->cd[sco].sub = sco; /* self-referential subcolor ptr */
+ }
+
+ if (co == sco) /* repeated character */
+ return co; /* no further action needed */
+ cm->cd[co].nchrs--;
+ cm->cd[sco].nchrs++;
+ setcolor(cm, c, sco);
+ return sco;
+}
+
+/*
+ - 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 (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;
+ }
+ } 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
+
+/*
+ - 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;
+
+ if (cm->filled) {
+ fprintf(f, "filled\n");
+ 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 (cd->nchrs > 0) {
+ if (cd->flags&PSEUDO)
+ fprintf(f, "#%2ld(ps): ", (long)co);
+ else
+ fprintf(f, "#%2ld(%2d): ", (long)co, cd->nchrs);
+ 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, "\\0%lo", (long)c);
+}
+
+#endif /* ifdef REG_DEBUG */
generated by cgit v0.12 at 2024-08-21 06:59:36 (GMT)