2 * colorings of characters
3 * This file is #included by regcomp.c.
5 * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved.
7 * Development of this software was funded, in part, by Cray Research Inc.,
8 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
9 * Corporation, none of whom are responsible for the results. The author
12 * Redistribution and use in source and binary forms -- with or without
13 * modification -- are permitted for any purpose, provided that
14 * redistributions in source form retain this entire copyright notice and
15 * indicate the origin and nature of any modifications.
17 * I'd appreciate being given credit for this package in the documentation
18 * of software which uses it, but that is not a requirement.
20 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
21 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
22 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
23 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 * $PostgreSQL: pgsql/src/backend/regex/regc_color.c,v 1.5 2005/10/15 02:49:24 momjian Exp $
34 * Note that there are some incestuous relationships between this code and
35 * NFA arc maintenance, which perhaps ought to be cleaned up sometime.
40 #define CISERR() VISERR(cm->v)
41 #define CERR(e) VERR(cm->v, (e))
46 * initcm - set up new colormap
49 initcm(struct vars * v,
61 cm->ncds = NINLINECDS;
66 cd = cm->cd; /* cm->cd[WHITE] */
70 cd->nchrs = CHR_MAX - CHR_MIN + 1;
72 /* upper levels of tree */
73 for (t = &cm->tree[0], j = NBYTS - 1; j > 0; t = nextt, j--)
76 for (i = BYTTAB - 1; i >= 0; i--)
79 /* bottom level is solid white */
80 t = &cm->tree[NBYTS - 1];
81 for (i = BYTTAB - 1; i >= 0; i--)
87 * freecm - free dynamically-allocated things in a colormap
90 freecm(struct colormap * cm)
97 cmtreefree(cm, cm->tree, 0);
98 for (i = 1; i <= cm->max; i++) /* skip WHITE */
99 if (!UNUSEDCOLOR(&cm->cd[i]))
101 cb = cm->cd[i].block;
105 if (cm->cd != cm->cdspace)
110 * cmtreefree - free a non-terminal part of a colormap tree
113 cmtreefree(struct colormap * cm,
115 int level) /* level number (top == 0) of this block */
119 union tree *fillt = &cm->tree[level + 1];
122 assert(level < NBYTS - 1); /* this level has pointers */
123 for (i = BYTTAB - 1; i >= 0; i--)
129 if (level < NBYTS - 2)
130 { /* more pointer blocks below */
131 cmtreefree(cm, t, level + 1);
135 { /* color block below */
136 cb = cm->cd[t->tcolor[0]].block;
137 if (t != cb) /* not a solid block */
145 * setcolor - set the color of a character in a colormap
147 static color /* previous color */
148 setcolor(struct colormap * cm,
164 assert(cm->magic == CMMAGIC);
165 if (CISERR() || co == COLORLESS)
169 for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0;
170 level++, shift -= BYTBITS)
172 b = (uc >> shift) & BYTMASK;
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)
180 { /* must allocate a new block */
181 newt = (union tree *) MALLOC((bottom) ?
182 sizeof(struct colors) : sizeof(struct ptrs));
189 memcpy(VS(newt->tcolor), VS(t->tcolor),
190 BYTTAB * sizeof(color));
192 memcpy(VS(newt->tptr), VS(t->tptr),
193 BYTTAB * sizeof(union tree *));
201 t->tcolor[b] = (color) co;
206 * maxcolor - report largest color number in use
209 maxcolor(struct colormap * cm)
214 return (color) cm->max;
218 * newcolor - find a new color (must be subject of setcolor at once)
219 * Beware: may relocate the colordescs.
221 static color /* COLORLESS for error */
222 newcolor(struct colormap * cm)
224 struct colordesc *cd;
225 struct colordesc *new;
233 assert(cm->free > 0);
234 assert((size_t) cm->free < cm->ncds);
235 cd = &cm->cd[cm->free];
236 assert(UNUSEDCOLOR(cd));
237 assert(cd->arcs == NULL);
240 else if (cm->max < cm->ncds - 1)
243 cd = &cm->cd[cm->max];
247 /* oops, must allocate more */
249 if (cm->cd == cm->cdspace)
251 new = (struct colordesc *) MALLOC(n *
252 sizeof(struct colordesc));
254 memcpy(VS(new), VS(cm->cdspace), cm->ncds *
255 sizeof(struct colordesc));
258 new = (struct colordesc *) REALLOC(cm->cd,
259 n * sizeof(struct colordesc));
267 assert(cm->max < cm->ncds - 1);
269 cd = &cm->cd[cm->max];
278 return (color) (cd - cm->cd);
282 * freecolor - free a color (must have no arcs or subcolor)
285 freecolor(struct colormap * cm,
288 struct colordesc *cd = &cm->cd[co];
290 nco; /* for freelist scan */
296 assert(cd->arcs == NULL);
297 assert(cd->sub == NOSUB);
298 assert(cd->nchrs == 0);
300 if (cd->block != NULL)
303 cd->block = NULL; /* just paranoia */
306 if ((size_t) co == cm->max)
308 while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max]))
310 assert(cm->free >= 0);
311 while ((size_t) cm->free > cm->max)
312 cm->free = cm->cd[cm->free].sub;
315 assert(cm->free < cm->max);
317 nco = cm->cd[pco].sub;
319 if ((size_t) nco > cm->max)
321 /* take this one out of freelist */
322 nco = cm->cd[nco].sub;
323 cm->cd[pco].sub = nco;
327 assert(nco < cm->max);
329 nco = cm->cd[pco].sub;
336 cm->free = (color) (cd - cm->cd);
341 * pseudocolor - allocate a false color, to be managed by other means
344 pseudocolor(struct colormap * cm)
351 cm->cd[co].nchrs = 1;
352 cm->cd[co].flags = PSEUDO;
357 * subcolor - allocate a new subcolor (if necessary) to this chr
360 subcolor(struct colormap * cm, chr c)
362 color co; /* current color of c */
363 color sco; /* new subcolor */
365 co = GETCOLOR(cm, c);
366 sco = newsub(cm, co);
369 assert(sco != COLORLESS);
371 if (co == sco) /* already in an open subcolor */
372 return co; /* rest is redundant */
375 setcolor(cm, c, sco);
380 * newsub - allocate a new subcolor (if necessary) for a color
383 newsub(struct colormap * cm,
386 color sco; /* new subcolor */
388 sco = cm->cd[co].sub;
390 { /* color has no open subcolor */
391 if (cm->cd[co].nchrs == 1) /* optimization */
393 sco = newcolor(cm); /* must create subcolor */
394 if (sco == COLORLESS)
399 cm->cd[co].sub = sco;
400 cm->cd[sco].sub = sco; /* open subcolor points to self */
402 assert(sco != NOSUB);
408 * subrange - allocate new subcolors to this range of chrs, fill in arcs
411 subrange(struct vars * v,
422 /* first, align "from" on a tree-block boundary */
424 i = (int) (((uf + BYTTAB - 1) & (uchr) ~BYTMASK) - uf);
425 for (; from <= to && i > 0; i--, from++)
426 newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
427 if (from > to) /* didn't reach a boundary */
430 /* deal with whole blocks */
431 for (; to - from >= BYTTAB; from += BYTTAB)
432 subblock(v, from, lp, rp);
434 /* clean up any remaining partial table */
435 for (; from <= to; from++)
436 newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
440 * subblock - allocate new subcolors for one tree block of chrs, fill in arcs
443 subblock(struct vars * v,
444 chr start, /* first of BYTTAB chrs */
449 struct colormap *cm = v->cm;
463 assert((uc % BYTTAB) == 0);
465 /* find its color block, making new pointer blocks as needed */
468 for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0;
469 level++, shift -= BYTBITS)
471 b = (uc >> shift) & BYTMASK;
475 fillt = &cm->tree[level + 1];
476 if (t == fillt && shift > BYTBITS)
477 { /* need new ptr block */
478 t = (union tree *) MALLOC(sizeof(struct ptrs));
484 memcpy(VS(t->tptr), VS(fillt->tptr),
485 BYTTAB * sizeof(union tree *));
490 /* special cases: fill block or solid block */
492 cb = cm->cd[co].block;
493 if (t == fillt || t == cb)
495 /* either way, we want a subcolor solid block */
496 sco = newsub(cm, co);
497 t = cm->cd[sco].block;
499 { /* must set it up */
500 t = (union tree *) MALLOC(sizeof(struct colors));
506 for (i = 0; i < BYTTAB; i++)
508 cm->cd[sco].block = t;
510 /* find loop must have run at least once */
512 newarc(v->nfa, PLAIN, sco, lp, rp);
513 cm->cd[co].nchrs -= BYTTAB;
514 cm->cd[sco].nchrs += BYTTAB;
518 /* general case, a mixed block to be altered */
523 sco = newsub(cm, co);
524 newarc(v->nfa, PLAIN, sco, lp, rp);
528 t->tcolor[i++] = sco;
529 } while (i < BYTTAB && t->tcolor[i] == co);
531 cm->cd[co].nchrs -= ndone;
532 cm->cd[sco].nchrs += ndone;
537 * okcolors - promote subcolors to full colors
540 okcolors(struct nfa * nfa,
541 struct colormap * cm)
543 struct colordesc *cd;
544 struct colordesc *end = CDEND(cm);
545 struct colordesc *scd;
550 for (cd = cm->cd, co = 0; cd < end; cd++, co++)
553 if (UNUSEDCOLOR(cd) || sco == NOSUB)
555 /* has no subcolor, no further action */
559 /* is subcolor, let parent deal with it */
561 else if (cd->nchrs == 0)
563 /* parent empty, its arcs change color to subcolor */
566 assert(scd->nchrs > 0);
567 assert(scd->sub == sco);
569 while ((a = cd->arcs) != NULL)
572 /* uncolorchain(cm, a); */
573 cd->arcs = a->colorchain;
575 /* colorchain(cm, a); */
576 a->colorchain = scd->arcs;
583 /* parent's arcs must gain parallel subcolor arcs */
586 assert(scd->nchrs > 0);
587 assert(scd->sub == sco);
589 for (a = cd->arcs; a != NULL; a = a->colorchain)
592 newarc(nfa, a->type, sco, a->from, a->to);
599 * colorchain - add this arc to the color chain of its color
602 colorchain(struct colormap * cm,
605 struct colordesc *cd = &cm->cd[a->co];
607 a->colorchain = cd->arcs;
612 * uncolorchain - delete this arc from the color chain of its color
615 uncolorchain(struct colormap * cm,
618 struct colordesc *cd = &cm->cd[a->co];
622 if (aa == a) /* easy case */
623 cd->arcs = a->colorchain;
626 for (; aa != NULL && aa->colorchain != a; aa = aa->colorchain)
629 aa->colorchain = a->colorchain;
631 a->colorchain = NULL; /* paranoia */
635 * singleton - is this character in its own color?
637 static int /* predicate */
638 singleton(struct colormap * cm,
641 color co; /* color of c */
643 co = GETCOLOR(cm, c);
644 if (cm->cd[co].nchrs == 1 && cm->cd[co].sub == NOSUB)
650 * rainbow - add arcs of all full colors (but one) between specified states
653 rainbow(struct nfa * nfa,
654 struct colormap * cm,
656 pcolor but, /* COLORLESS if no exceptions */
660 struct colordesc *cd;
661 struct colordesc *end = CDEND(cm);
664 for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
665 if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but &&
666 !(cd->flags & PSEUDO))
667 newarc(nfa, type, co, from, to);
671 * colorcomplement - add arcs of complementary colors
673 * The calling sequence ought to be reconciled with cloneouts().
676 colorcomplement(struct nfa * nfa,
677 struct colormap * cm,
679 struct state * of, /* complements of this guy's PLAIN
684 struct colordesc *cd;
685 struct colordesc *end = CDEND(cm);
689 for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
690 if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO))
691 if (findarc(of, PLAIN, co) == NULL)
692 newarc(nfa, type, co, from, to);
699 * dumpcolors - debugging output
702 dumpcolors(struct colormap * cm,
705 struct colordesc *cd;
706 struct colordesc *end;
711 fprintf(f, "max %ld\n", (long) cm->max);
713 fillcheck(cm, cm->tree, 0, f);
715 for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++) /* skip 0 */
716 if (!UNUSEDCOLOR(cd))
718 assert(cd->nchrs > 0);
719 has = (cd->block != NULL) ? "#" : "";
720 if (cd->flags & PSEUDO)
721 fprintf(f, "#%2ld%s(ps): ", (long) co, has);
723 fprintf(f, "#%2ld%s(%2d): ", (long) co,
725 /* it's hard to do this more efficiently */
726 for (c = CHR_MIN; c < CHR_MAX; c++)
727 if (GETCOLOR(cm, c) == co)
729 assert(c == CHR_MAX);
730 if (GETCOLOR(cm, c) == co)
737 * fillcheck - check proper filling of a tree
740 fillcheck(struct colormap * cm,
742 int level, /* level number (top == 0) of this block */
747 union tree *fillt = &cm->tree[level + 1];
749 assert(level < NBYTS - 1); /* this level has pointers */
750 for (i = BYTTAB - 1; i >= 0; i--)
754 fprintf(f, "NULL found in filled tree!\n");
758 else if (level < NBYTS - 2) /* more pointer blocks below */
759 fillcheck(cm, t, level + 1, f);
764 * dumpchr - print a chr
766 * Kind of char-centric but works well enough for debug use.
774 else if (c > ' ' && c <= '~')
777 fprintf(f, "\\u%04lx", (long) c);
780 #endif /* REG_DEBUG */