Header And Logo

PostgreSQL
| The world's most advanced open source database.

regc_color.c

Go to the documentation of this file.
00001 /*
00002  * colorings of characters
00003  * This file is #included by regcomp.c.
00004  *
00005  * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
00006  *
00007  * Development of this software was funded, in part, by Cray Research Inc.,
00008  * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
00009  * Corporation, none of whom are responsible for the results.  The author
00010  * thanks all of them.
00011  *
00012  * Redistribution and use in source and binary forms -- with or without
00013  * modification -- are permitted for any purpose, provided that
00014  * redistributions in source form retain this entire copyright notice and
00015  * indicate the origin and nature of any modifications.
00016  *
00017  * I'd appreciate being given credit for this package in the documentation
00018  * of software which uses it, but that is not a requirement.
00019  *
00020  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
00021  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
00022  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
00023  * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00024  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00025  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
00026  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
00027  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
00028  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
00029  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00030  *
00031  * src/backend/regex/regc_color.c
00032  *
00033  *
00034  * Note that there are some incestuous relationships between this code and
00035  * NFA arc maintenance, which perhaps ought to be cleaned up sometime.
00036  */
00037 
00038 
00039 
00040 #define CISERR()    VISERR(cm->v)
00041 #define CERR(e)     VERR(cm->v, (e))
00042 
00043 
00044 
00045 /*
00046  * initcm - set up new colormap
00047  */
00048 static void
00049 initcm(struct vars * v,
00050        struct colormap * cm)
00051 {
00052     int         i;
00053     int         j;
00054     union tree *t;
00055     union tree *nextt;
00056     struct colordesc *cd;
00057 
00058     cm->magic = CMMAGIC;
00059     cm->v = v;
00060 
00061     cm->ncds = NINLINECDS;
00062     cm->cd = cm->cdspace;
00063     cm->max = 0;
00064     cm->free = 0;
00065 
00066     cd = cm->cd;                /* cm->cd[WHITE] */
00067     cd->sub = NOSUB;
00068     cd->arcs = NULL;
00069     cd->firstchr = CHR_MIN;
00070     cd->nchrs = CHR_MAX - CHR_MIN + 1;
00071     cd->flags = 0;
00072 
00073     /* upper levels of tree */
00074     for (t = &cm->tree[0], j = NBYTS - 1; j > 0; t = nextt, j--)
00075     {
00076         nextt = t + 1;
00077         for (i = BYTTAB - 1; i >= 0; i--)
00078             t->tptr[i] = nextt;
00079     }
00080     /* bottom level is solid white */
00081     t = &cm->tree[NBYTS - 1];
00082     for (i = BYTTAB - 1; i >= 0; i--)
00083         t->tcolor[i] = WHITE;
00084     cd->block = t;
00085 }
00086 
00087 /*
00088  * freecm - free dynamically-allocated things in a colormap
00089  */
00090 static void
00091 freecm(struct colormap * cm)
00092 {
00093     size_t      i;
00094     union tree *cb;
00095 
00096     cm->magic = 0;
00097     if (NBYTS > 1)
00098         cmtreefree(cm, cm->tree, 0);
00099     for (i = 1; i <= cm->max; i++)      /* skip WHITE */
00100         if (!UNUSEDCOLOR(&cm->cd[i]))
00101         {
00102             cb = cm->cd[i].block;
00103             if (cb != NULL)
00104                 FREE(cb);
00105         }
00106     if (cm->cd != cm->cdspace)
00107         FREE(cm->cd);
00108 }
00109 
00110 /*
00111  * cmtreefree - free a non-terminal part of a colormap tree
00112  */
00113 static void
00114 cmtreefree(struct colormap * cm,
00115            union tree * tree,
00116            int level)           /* level number (top == 0) of this block */
00117 {
00118     int         i;
00119     union tree *t;
00120     union tree *fillt = &cm->tree[level + 1];
00121     union tree *cb;
00122 
00123     assert(level < NBYTS - 1);  /* this level has pointers */
00124     for (i = BYTTAB - 1; i >= 0; i--)
00125     {
00126         t = tree->tptr[i];
00127         assert(t != NULL);
00128         if (t != fillt)
00129         {
00130             if (level < NBYTS - 2)
00131             {                   /* more pointer blocks below */
00132                 cmtreefree(cm, t, level + 1);
00133                 FREE(t);
00134             }
00135             else
00136             {                   /* color block below */
00137                 cb = cm->cd[t->tcolor[0]].block;
00138                 if (t != cb)    /* not a solid block */
00139                     FREE(t);
00140             }
00141         }
00142     }
00143 }
00144 
00145 /*
00146  * setcolor - set the color of a character in a colormap
00147  */
00148 static color                    /* previous color */
00149 setcolor(struct colormap * cm,
00150          chr c,
00151          pcolor co)
00152 {
00153     uchr        uc = c;
00154     int         shift;
00155     int         level;
00156     int         b;
00157     int         bottom;
00158     union tree *t;
00159     union tree *newt;
00160     union tree *fillt;
00161     union tree *lastt;
00162     union tree *cb;
00163     color       prev;
00164 
00165     assert(cm->magic == CMMAGIC);
00166     if (CISERR() || co == COLORLESS)
00167         return COLORLESS;
00168 
00169     t = cm->tree;
00170     for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0;
00171          level++, shift -= BYTBITS)
00172     {
00173         b = (uc >> shift) & BYTMASK;
00174         lastt = t;
00175         t = lastt->tptr[b];
00176         assert(t != NULL);
00177         fillt = &cm->tree[level + 1];
00178         bottom = (shift <= BYTBITS) ? 1 : 0;
00179         cb = (bottom) ? cm->cd[t->tcolor[0]].block : fillt;
00180         if (t == fillt || t == cb)
00181         {                       /* must allocate a new block */
00182             newt = (union tree *) MALLOC((bottom) ?
00183                                 sizeof(struct colors) : sizeof(struct ptrs));
00184             if (newt == NULL)
00185             {
00186                 CERR(REG_ESPACE);
00187                 return COLORLESS;
00188             }
00189             if (bottom)
00190                 memcpy(VS(newt->tcolor), VS(t->tcolor),
00191                        BYTTAB * sizeof(color));
00192             else
00193                 memcpy(VS(newt->tptr), VS(t->tptr),
00194                        BYTTAB * sizeof(union tree *));
00195             t = newt;
00196             lastt->tptr[b] = t;
00197         }
00198     }
00199 
00200     b = uc & BYTMASK;
00201     prev = t->tcolor[b];
00202     t->tcolor[b] = (color) co;
00203     return prev;
00204 }
00205 
00206 /*
00207  * maxcolor - report largest color number in use
00208  */
00209 static color
00210 maxcolor(struct colormap * cm)
00211 {
00212     if (CISERR())
00213         return COLORLESS;
00214 
00215     return (color) cm->max;
00216 }
00217 
00218 /*
00219  * newcolor - find a new color (must be subject of setcolor at once)
00220  * Beware:  may relocate the colordescs.
00221  */
00222 static color                    /* COLORLESS for error */
00223 newcolor(struct colormap * cm)
00224 {
00225     struct colordesc *cd;
00226     size_t      n;
00227 
00228     if (CISERR())
00229         return COLORLESS;
00230 
00231     if (cm->free != 0)
00232     {
00233         assert(cm->free > 0);
00234         assert((size_t) cm->free < cm->ncds);
00235         cd = &cm->cd[cm->free];
00236         assert(UNUSEDCOLOR(cd));
00237         assert(cd->arcs == NULL);
00238         cm->free = cd->sub;
00239     }
00240     else if (cm->max < cm->ncds - 1)
00241     {
00242         cm->max++;
00243         cd = &cm->cd[cm->max];
00244     }
00245     else
00246     {
00247         /* oops, must allocate more */
00248         struct colordesc *newCd;
00249 
00250         if (cm->max == MAX_COLOR)
00251         {
00252             CERR(REG_ECOLORS);
00253             return COLORLESS;   /* too many colors */
00254         }
00255 
00256         n = cm->ncds * 2;
00257         if (n > MAX_COLOR + 1)
00258             n = MAX_COLOR + 1;
00259         if (cm->cd == cm->cdspace)
00260         {
00261             newCd = (struct colordesc *) MALLOC(n * sizeof(struct colordesc));
00262             if (newCd != NULL)
00263                 memcpy(VS(newCd), VS(cm->cdspace), cm->ncds *
00264                        sizeof(struct colordesc));
00265         }
00266         else
00267             newCd = (struct colordesc *)
00268                 REALLOC(cm->cd, n * sizeof(struct colordesc));
00269         if (newCd == NULL)
00270         {
00271             CERR(REG_ESPACE);
00272             return COLORLESS;
00273         }
00274         cm->cd = newCd;
00275         cm->ncds = n;
00276         assert(cm->max < cm->ncds - 1);
00277         cm->max++;
00278         cd = &cm->cd[cm->max];
00279     }
00280 
00281     cd->nchrs = 0;
00282     cd->sub = NOSUB;
00283     cd->arcs = NULL;
00284     cd->firstchr = CHR_MIN;     /* in case never set otherwise */
00285     cd->flags = 0;
00286     cd->block = NULL;
00287 
00288     return (color) (cd - cm->cd);
00289 }
00290 
00291 /*
00292  * freecolor - free a color (must have no arcs or subcolor)
00293  */
00294 static void
00295 freecolor(struct colormap * cm,
00296           pcolor co)
00297 {
00298     struct colordesc *cd = &cm->cd[co];
00299     color       pco,
00300                 nco;            /* for freelist scan */
00301 
00302     assert(co >= 0);
00303     if (co == WHITE)
00304         return;
00305 
00306     assert(cd->arcs == NULL);
00307     assert(cd->sub == NOSUB);
00308     assert(cd->nchrs == 0);
00309     cd->flags = FREECOL;
00310     if (cd->block != NULL)
00311     {
00312         FREE(cd->block);
00313         cd->block = NULL;       /* just paranoia */
00314     }
00315 
00316     if ((size_t) co == cm->max)
00317     {
00318         while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max]))
00319             cm->max--;
00320         assert(cm->free >= 0);
00321         while ((size_t) cm->free > cm->max)
00322             cm->free = cm->cd[cm->free].sub;
00323         if (cm->free > 0)
00324         {
00325             assert(cm->free < cm->max);
00326             pco = cm->free;
00327             nco = cm->cd[pco].sub;
00328             while (nco > 0)
00329                 if ((size_t) nco > cm->max)
00330                 {
00331                     /* take this one out of freelist */
00332                     nco = cm->cd[nco].sub;
00333                     cm->cd[pco].sub = nco;
00334                 }
00335                 else
00336                 {
00337                     assert(nco < cm->max);
00338                     pco = nco;
00339                     nco = cm->cd[pco].sub;
00340                 }
00341         }
00342     }
00343     else
00344     {
00345         cd->sub = cm->free;
00346         cm->free = (color) (cd - cm->cd);
00347     }
00348 }
00349 
00350 /*
00351  * pseudocolor - allocate a false color, to be managed by other means
00352  */
00353 static color
00354 pseudocolor(struct colormap * cm)
00355 {
00356     color       co;
00357 
00358     co = newcolor(cm);
00359     if (CISERR())
00360         return COLORLESS;
00361     cm->cd[co].nchrs = 1;
00362     cm->cd[co].flags = PSEUDO;
00363     return co;
00364 }
00365 
00366 /*
00367  * subcolor - allocate a new subcolor (if necessary) to this chr
00368  */
00369 static color
00370 subcolor(struct colormap * cm, chr c)
00371 {
00372     color       co;             /* current color of c */
00373     color       sco;            /* new subcolor */
00374 
00375     co = GETCOLOR(cm, c);
00376     sco = newsub(cm, co);
00377     if (CISERR())
00378         return COLORLESS;
00379     assert(sco != COLORLESS);
00380 
00381     if (co == sco)              /* already in an open subcolor */
00382         return co;              /* rest is redundant */
00383     cm->cd[co].nchrs--;
00384     if (cm->cd[sco].nchrs == 0)
00385         cm->cd[sco].firstchr = c;
00386     cm->cd[sco].nchrs++;
00387     setcolor(cm, c, sco);
00388     return sco;
00389 }
00390 
00391 /*
00392  * newsub - allocate a new subcolor (if necessary) for a color
00393  */
00394 static color
00395 newsub(struct colormap * cm,
00396        pcolor co)
00397 {
00398     color       sco;            /* new subcolor */
00399 
00400     sco = cm->cd[co].sub;
00401     if (sco == NOSUB)
00402     {                           /* color has no open subcolor */
00403         if (cm->cd[co].nchrs == 1)      /* optimization */
00404             return co;
00405         sco = newcolor(cm);     /* must create subcolor */
00406         if (sco == COLORLESS)
00407         {
00408             assert(CISERR());
00409             return COLORLESS;
00410         }
00411         cm->cd[co].sub = sco;
00412         cm->cd[sco].sub = sco;  /* open subcolor points to self */
00413     }
00414     assert(sco != NOSUB);
00415 
00416     return sco;
00417 }
00418 
00419 /*
00420  * subrange - allocate new subcolors to this range of chrs, fill in arcs
00421  */
00422 static void
00423 subrange(struct vars * v,
00424          chr from,
00425          chr to,
00426          struct state * lp,
00427          struct state * rp)
00428 {
00429     uchr        uf;
00430     int         i;
00431 
00432     assert(from <= to);
00433 
00434     /* first, align "from" on a tree-block boundary */
00435     uf = (uchr) from;
00436     i = (int) (((uf + BYTTAB - 1) & (uchr) ~BYTMASK) - uf);
00437     for (; from <= to && i > 0; i--, from++)
00438         newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
00439     if (from > to)              /* didn't reach a boundary */
00440         return;
00441 
00442     /* deal with whole blocks */
00443     for (; to - from >= BYTTAB; from += BYTTAB)
00444         subblock(v, from, lp, rp);
00445 
00446     /* clean up any remaining partial table */
00447     for (; from <= to; from++)
00448         newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
00449 }
00450 
00451 /*
00452  * subblock - allocate new subcolors for one tree block of chrs, fill in arcs
00453  *
00454  * Note: subcolors that are created during execution of this function
00455  * will not be given a useful value of firstchr; it'll be left as CHR_MIN.
00456  * For the current usage of firstchr in pg_regprefix, this does not matter
00457  * because such subcolors won't occur in the common prefix of a regex.
00458  */
00459 static void
00460 subblock(struct vars * v,
00461          chr start,             /* first of BYTTAB chrs */
00462          struct state * lp,
00463          struct state * rp)
00464 {
00465     uchr        uc = start;
00466     struct colormap *cm = v->cm;
00467     int         shift;
00468     int         level;
00469     int         i;
00470     int         b;
00471     union tree *t;
00472     union tree *cb;
00473     union tree *fillt;
00474     union tree *lastt;
00475     int         previ;
00476     int         ndone;
00477     color       co;
00478     color       sco;
00479 
00480     assert((uc % BYTTAB) == 0);
00481 
00482     /* find its color block, making new pointer blocks as needed */
00483     t = cm->tree;
00484     fillt = NULL;
00485     for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0;
00486          level++, shift -= BYTBITS)
00487     {
00488         b = (uc >> shift) & BYTMASK;
00489         lastt = t;
00490         t = lastt->tptr[b];
00491         assert(t != NULL);
00492         fillt = &cm->tree[level + 1];
00493         if (t == fillt && shift > BYTBITS)
00494         {                       /* need new ptr block */
00495             t = (union tree *) MALLOC(sizeof(struct ptrs));
00496             if (t == NULL)
00497             {
00498                 CERR(REG_ESPACE);
00499                 return;
00500             }
00501             memcpy(VS(t->tptr), VS(fillt->tptr),
00502                    BYTTAB * sizeof(union tree *));
00503             lastt->tptr[b] = t;
00504         }
00505     }
00506 
00507     /* special cases:  fill block or solid block */
00508     co = t->tcolor[0];
00509     cb = cm->cd[co].block;
00510     if (t == fillt || t == cb)
00511     {
00512         /* either way, we want a subcolor solid block */
00513         sco = newsub(cm, co);
00514         t = cm->cd[sco].block;
00515         if (t == NULL)
00516         {                       /* must set it up */
00517             t = (union tree *) MALLOC(sizeof(struct colors));
00518             if (t == NULL)
00519             {
00520                 CERR(REG_ESPACE);
00521                 return;
00522             }
00523             for (i = 0; i < BYTTAB; i++)
00524                 t->tcolor[i] = sco;
00525             cm->cd[sco].block = t;
00526         }
00527         /* find loop must have run at least once */
00528         lastt->tptr[b] = t;
00529         newarc(v->nfa, PLAIN, sco, lp, rp);
00530         cm->cd[co].nchrs -= BYTTAB;
00531         cm->cd[sco].nchrs += BYTTAB;
00532         return;
00533     }
00534 
00535     /* general case, a mixed block to be altered */
00536     i = 0;
00537     while (i < BYTTAB)
00538     {
00539         co = t->tcolor[i];
00540         sco = newsub(cm, co);
00541         newarc(v->nfa, PLAIN, sco, lp, rp);
00542         previ = i;
00543         do
00544         {
00545             t->tcolor[i++] = sco;
00546         } while (i < BYTTAB && t->tcolor[i] == co);
00547         ndone = i - previ;
00548         cm->cd[co].nchrs -= ndone;
00549         cm->cd[sco].nchrs += ndone;
00550     }
00551 }
00552 
00553 /*
00554  * okcolors - promote subcolors to full colors
00555  */
00556 static void
00557 okcolors(struct nfa * nfa,
00558          struct colormap * cm)
00559 {
00560     struct colordesc *cd;
00561     struct colordesc *end = CDEND(cm);
00562     struct colordesc *scd;
00563     struct arc *a;
00564     color       co;
00565     color       sco;
00566 
00567     for (cd = cm->cd, co = 0; cd < end; cd++, co++)
00568     {
00569         sco = cd->sub;
00570         if (UNUSEDCOLOR(cd) || sco == NOSUB)
00571         {
00572             /* has no subcolor, no further action */
00573         }
00574         else if (sco == co)
00575         {
00576             /* is subcolor, let parent deal with it */
00577         }
00578         else if (cd->nchrs == 0)
00579         {
00580             /* parent empty, its arcs change color to subcolor */
00581             cd->sub = NOSUB;
00582             scd = &cm->cd[sco];
00583             assert(scd->nchrs > 0);
00584             assert(scd->sub == sco);
00585             scd->sub = NOSUB;
00586             while ((a = cd->arcs) != NULL)
00587             {
00588                 assert(a->co == co);
00589                 uncolorchain(cm, a);
00590                 a->co = sco;
00591                 colorchain(cm, a);
00592             }
00593             freecolor(cm, co);
00594         }
00595         else
00596         {
00597             /* parent's arcs must gain parallel subcolor arcs */
00598             cd->sub = NOSUB;
00599             scd = &cm->cd[sco];
00600             assert(scd->nchrs > 0);
00601             assert(scd->sub == sco);
00602             scd->sub = NOSUB;
00603             for (a = cd->arcs; a != NULL; a = a->colorchain)
00604             {
00605                 assert(a->co == co);
00606                 newarc(nfa, a->type, sco, a->from, a->to);
00607             }
00608         }
00609     }
00610 }
00611 
00612 /*
00613  * colorchain - add this arc to the color chain of its color
00614  */
00615 static void
00616 colorchain(struct colormap * cm,
00617            struct arc * a)
00618 {
00619     struct colordesc *cd = &cm->cd[a->co];
00620 
00621     if (cd->arcs != NULL)
00622         cd->arcs->colorchainRev = a;
00623     a->colorchain = cd->arcs;
00624     a->colorchainRev = NULL;
00625     cd->arcs = a;
00626 }
00627 
00628 /*
00629  * uncolorchain - delete this arc from the color chain of its color
00630  */
00631 static void
00632 uncolorchain(struct colormap * cm,
00633              struct arc * a)
00634 {
00635     struct colordesc *cd = &cm->cd[a->co];
00636     struct arc *aa = a->colorchainRev;
00637 
00638     if (aa == NULL)
00639     {
00640         assert(cd->arcs == a);
00641         cd->arcs = a->colorchain;
00642     }
00643     else
00644     {
00645         assert(aa->colorchain == a);
00646         aa->colorchain = a->colorchain;
00647     }
00648     if (a->colorchain != NULL)
00649         a->colorchain->colorchainRev = aa;
00650     a->colorchain = NULL;       /* paranoia */
00651     a->colorchainRev = NULL;
00652 }
00653 
00654 /*
00655  * rainbow - add arcs of all full colors (but one) between specified states
00656  */
00657 static void
00658 rainbow(struct nfa * nfa,
00659         struct colormap * cm,
00660         int type,
00661         pcolor but,             /* COLORLESS if no exceptions */
00662         struct state * from,
00663         struct state * to)
00664 {
00665     struct colordesc *cd;
00666     struct colordesc *end = CDEND(cm);
00667     color       co;
00668 
00669     for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
00670         if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but &&
00671             !(cd->flags & PSEUDO))
00672             newarc(nfa, type, co, from, to);
00673 }
00674 
00675 /*
00676  * colorcomplement - add arcs of complementary colors
00677  *
00678  * The calling sequence ought to be reconciled with cloneouts().
00679  */
00680 static void
00681 colorcomplement(struct nfa * nfa,
00682                 struct colormap * cm,
00683                 int type,
00684                 struct state * of,      /* complements of this guy's PLAIN
00685                                          * outarcs */
00686                 struct state * from,
00687                 struct state * to)
00688 {
00689     struct colordesc *cd;
00690     struct colordesc *end = CDEND(cm);
00691     color       co;
00692 
00693     assert(of != from);
00694     for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
00695         if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO))
00696             if (findarc(of, PLAIN, co) == NULL)
00697                 newarc(nfa, type, co, from, to);
00698 }
00699 
00700 
00701 #ifdef REG_DEBUG
00702 
00703 /*
00704  * dumpcolors - debugging output
00705  */
00706 static void
00707 dumpcolors(struct colormap * cm,
00708            FILE *f)
00709 {
00710     struct colordesc *cd;
00711     struct colordesc *end;
00712     color       co;
00713     chr         c;
00714     char       *has;
00715 
00716     fprintf(f, "max %ld\n", (long) cm->max);
00717     if (NBYTS > 1)
00718         fillcheck(cm, cm->tree, 0, f);
00719     end = CDEND(cm);
00720     for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++) /* skip 0 */
00721         if (!UNUSEDCOLOR(cd))
00722         {
00723             assert(cd->nchrs > 0);
00724             has = (cd->block != NULL) ? "#" : "";
00725             if (cd->flags & PSEUDO)
00726                 fprintf(f, "#%2ld%s(ps): ", (long) co, has);
00727             else
00728                 fprintf(f, "#%2ld%s(%2d): ", (long) co,
00729                         has, cd->nchrs);
00730 
00731             /*
00732              * Unfortunately, it's hard to do this next bit more efficiently.
00733              *
00734              * Spencer's original coding has the loop iterating from CHR_MIN
00735              * to CHR_MAX, but that's utterly unusable for 32-bit chr. For
00736              * debugging purposes it seems fine to print only chr codes up to
00737              * 1000 or so.
00738              */
00739             for (c = CHR_MIN; c < 1000; c++)
00740                 if (GETCOLOR(cm, c) == co)
00741                     dumpchr(c, f);
00742             fprintf(f, "\n");
00743         }
00744 }
00745 
00746 /*
00747  * fillcheck - check proper filling of a tree
00748  */
00749 static void
00750 fillcheck(struct colormap * cm,
00751           union tree * tree,
00752           int level,            /* level number (top == 0) of this block */
00753           FILE *f)
00754 {
00755     int         i;
00756     union tree *t;
00757     union tree *fillt = &cm->tree[level + 1];
00758 
00759     assert(level < NBYTS - 1);  /* this level has pointers */
00760     for (i = BYTTAB - 1; i >= 0; i--)
00761     {
00762         t = tree->tptr[i];
00763         if (t == NULL)
00764             fprintf(f, "NULL found in filled tree!\n");
00765         else if (t == fillt)
00766         {
00767         }
00768         else if (level < NBYTS - 2)     /* more pointer blocks below */
00769             fillcheck(cm, t, level + 1, f);
00770     }
00771 }
00772 
00773 /*
00774  * dumpchr - print a chr
00775  *
00776  * Kind of char-centric but works well enough for debug use.
00777  */
00778 static void
00779 dumpchr(chr c,
00780         FILE *f)
00781 {
00782     if (c == '\\')
00783         fprintf(f, "\\\\");
00784     else if (c > ' ' && c <= '~')
00785         putc((char) c, f);
00786     else
00787         fprintf(f, "\\u%04lx", (long) c);
00788 }
00789 
00790 #endif   /* REG_DEBUG */