src/regex/regc_color.c

   1 /*
   2  * colorings of characters
   3  * This file is #included by regcomp.c.
   4  *
   5  * Copyright (c) 1998, 1999 Henry Spencer.      All rights reserved.
   6  *
   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
  10  * thanks all of them.
  11  *
  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.
  16  *
  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.
  19  *
  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.
  30  *
  31  * $Header$
  32  *
  33  *
  34  * Note that there are some incestuous relationships between this code and
  35  * NFA arc maintenance, which perhaps ought to be cleaned up sometime.
  36  */
  37
  38
  39
  40 #define CISERR()        VISERR(cm->v)
  41 #define CERR(e)         VERR(cm->v, (e))
  42
  43
  44
  45 /*
  46  * initcm - set up new colormap
  47  */
  48 static void
  49 initcm(struct vars * v,
  50            struct colormap * cm)
  51 {
  52         int                     i;
  53         int                     j;
  54         union tree *t;
  55         union tree *nextt;
  56         struct colordesc *cd;
  57
  58         cm->magic = CMMAGIC;
  59         cm->v = v;
  60
  61         cm->ncds = NINLINECDS;
  62         cm->cd = cm->cdspace;
  63         cm->max = 0;
  64         cm->free = 0;
  65
  66         cd = cm->cd;                            /* cm->cd[WHITE] */
  67         cd->sub = NOSUB;
  68         cd->arcs = NULL;
  69         cd->flags = 0;
  70         cd->nchrs = CHR_MAX - CHR_MIN + 1;
  71
  72         /* upper levels of tree */
  73         for (t = &cm->tree[0], j = NBYTS - 1; j > 0; t = nextt, j--)
  74         {
  75                 nextt = t + 1;
  76                 for (i = BYTTAB - 1; i >= 0; i--)
  77                         t->tptr[i] = nextt;
  78         }
  79         /* bottom level is solid white */
  80         t = &cm->tree[NBYTS - 1];
  81         for (i = BYTTAB - 1; i >= 0; i--)
  82                 t->tcolor[i] = WHITE;
  83         cd->block = t;
  84 }
  85
  86 /*
  87  * freecm - free dynamically-allocated things in a colormap
  88  */
  89 static void
  90 freecm(struct colormap * cm)
  91 {
  92         size_t          i;
  93         union tree *cb;
  94
  95         cm->magic = 0;
  96         if (NBYTS > 1)
  97                 cmtreefree(cm, cm->tree, 0);
  98         for (i = 1; i <= cm->max; i++)          /* skip WHITE */
  99                 if (!UNUSEDCOLOR(&cm->cd[i]))
 100                 {
 101                         cb = cm->cd[i].block;
 102                         if (cb != NULL)
 103                                 FREE(cb);
 104                 }
 105         if (cm->cd != cm->cdspace)
 106                 FREE(cm->cd);
 107 }
 108
 109 /*
 110  * cmtreefree - free a non-terminal part of a colormap tree
 111  */
 112 static void
 113 cmtreefree(struct colormap * cm,
 114                    union tree * tree,
 115                    int level)                   /* level number (top == 0) of this block */
 116 {
 117         int                     i;
 118         union tree *t;
 119         union tree *fillt = &cm->tree[level + 1];
 120         union tree *cb;
 121
 122         assert(level < NBYTS - 1);      /* this level has pointers */
 123         for (i = BYTTAB - 1; i >= 0; i--)
 124         {
 125                 t = tree->tptr[i];
 126                 assert(t != NULL);
 127                 if (t != fillt)
 128                 {
 129                         if (level < NBYTS - 2)
 130                         {                                       /* more pointer blocks below */
 131                                 cmtreefree(cm, t, level + 1);
 132                                 FREE(t);
 133                         }
 134                         else
 135                         {                                       /* color block below */
 136                                 cb = cm->cd[t->tcolor[0]].block;
 137                                 if (t != cb)    /* not a solid block */
 138                                         FREE(t);
 139                         }
 140                 }
 141         }
 142 }
 143
 144 /*
 145  * setcolor - set the color of a character in a colormap
 146  */
 147 static color                                    /* previous color */
 148 setcolor(struct colormap * cm,
 149                  chr c,
 150                  pcolor co)
 151 {
 152         uchr            uc = c;
 153         int                     shift;
 154         int                     level;
 155         int                     b;
 156         int                     bottom;
 157         union tree *t;
 158         union tree *newt;
 159         union tree *fillt;
 160         union tree *lastt;
 161         union tree *cb;
 162         color           prev;
 163
 164         assert(cm->magic == CMMAGIC);
 165         if (CISERR() || co == COLORLESS)
 166                 return COLORLESS;
 167
 168         t = cm->tree;
 169         for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0;
 170                  level++, shift -= BYTBITS)
 171         {
 172                 b = (uc >> shift) & BYTMASK;
 173                 lastt = t;
 174                 t = lastt->tptr[b];
 175                 assert(t != NULL);
 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));
 183                         if (newt == NULL)
 184                         {
 185                                 CERR(REG_ESPACE);
 186                                 return COLORLESS;
 187                         }
 188                         if (bottom)
 189                                 memcpy(VS(newt->tcolor), VS(t->tcolor),
 190                                            BYTTAB * sizeof(color));
 191                         else
 192                                 memcpy(VS(newt->tptr), VS(t->tptr),
 193                                            BYTTAB * sizeof(union tree *));
 194                         t = newt;
 195                         lastt->tptr[b] = t;
 196                 }
 197         }
 198
 199         b = uc & BYTMASK;
 200         prev = t->tcolor[b];
 201         t->tcolor[b] = (color) co;
 202         return prev;
 203 }
 204
 205 /*
 206  * maxcolor - report largest color number in use
 207  */
 208 static color
 209 maxcolor(struct colormap * cm)
 210 {
 211         if (CISERR())
 212                 return COLORLESS;
 213
 214         return (color) cm->max;
 215 }
 216
 217 /*
 218  * newcolor - find a new color (must be subject of setcolor at once)
 219  * Beware:      may relocate the colordescs.
 220  */
 221 static color                                    /* COLORLESS for error */
 222 newcolor(struct colormap * cm)
 223 {
 224         struct colordesc *cd;
 225         struct colordesc *new;
 226         size_t          n;
 227
 228         if (CISERR())
 229                 return COLORLESS;
 230
 231         if (cm->free != 0)
 232         {
 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);
 238                 cm->free = cd->sub;
 239         }
 240         else if (cm->max < cm->ncds - 1)
 241         {
 242                 cm->max++;
 243                 cd = &cm->cd[cm->max];
 244         }
 245         else
 246         {
 247                 /* oops, must allocate more */
 248                 n = cm->ncds * 2;
 249                 if (cm->cd == cm->cdspace)
 250                 {
 251                         new = (struct colordesc *) MALLOC(n *
 252                                                                                           sizeof(struct colordesc));
 253                         if (new != NULL)
 254                                 memcpy(VS(new), VS(cm->cdspace), cm->ncds *
 255                                            sizeof(struct colordesc));
 256                 }
 257                 else
 258                         new = (struct colordesc *) REALLOC(cm->cd,
 259                                                                                    n * sizeof(struct colordesc));
 260                 if (new == NULL)
 261                 {
 262                         CERR(REG_ESPACE);
 263                         return COLORLESS;
 264                 }
 265                 cm->cd = new;
 266                 cm->ncds = n;
 267                 assert(cm->max < cm->ncds - 1);
 268                 cm->max++;
 269                 cd = &cm->cd[cm->max];
 270         }
 271
 272         cd->nchrs = 0;
 273         cd->sub = NOSUB;
 274         cd->arcs = NULL;
 275         cd->flags = 0;
 276         cd->block = NULL;
 277
 278         return (color) (cd - cm->cd);
 279 }
 280
 281 /*
 282  * freecolor - free a color (must have no arcs or subcolor)
 283  */
 284 static void
 285 freecolor(struct colormap * cm,
 286                   pcolor co)
 287 {
 288         struct colordesc *cd = &cm->cd[co];
 289         color           pco,
 290                                 nco;                    /* for freelist scan */
 291
 292         assert(co >= 0);
 293         if (co == WHITE)
 294                 return;
 295
 296         assert(cd->arcs == NULL);
 297         assert(cd->sub == NOSUB);
 298         assert(cd->nchrs == 0);
 299         cd->flags = FREECOL;
 300         if (cd->block != NULL)
 301         {
 302                 FREE(cd->block);
 303                 cd->block = NULL;               /* just paranoia */
 304         }
 305
 306         if ((size_t) co == cm->max)
 307         {
 308                 while (cm->max > WHITE && UNUSEDCOLOR(&cm->cd[cm->max]))
 309                         cm->max--;
 310                 assert(cm->free >= 0);
 311                 while ((size_t) cm->free > cm->max)
 312                         cm->free = cm->cd[cm->free].sub;
 313                 if (cm->free > 0)
 314                 {
 315                         assert(cm->free < cm->max);
 316                         pco = cm->free;
 317                         nco = cm->cd[pco].sub;
 318                         while (nco > 0)
 319                                 if ((size_t) nco > cm->max)
 320                                 {
 321                                         /* take this one out of freelist */
 322                                         nco = cm->cd[nco].sub;
 323                                         cm->cd[pco].sub = nco;
 324                                 }
 325                                 else
 326                                 {
 327                                         assert(nco < cm->max);
 328                                         pco = nco;
 329                                         nco = cm->cd[pco].sub;
 330                                 }
 331                 }
 332         }
 333         else
 334         {
 335                 cd->sub = cm->free;
 336                 cm->free = (color) (cd - cm->cd);
 337         }
 338 }
 339
 340 /*
 341  * pseudocolor - allocate a false color, to be managed by other means
 342  */
 343 static color
 344 pseudocolor(struct colormap * cm)
 345 {
 346         color           co;
 347
 348         co = newcolor(cm);
 349         if (CISERR())
 350                 return COLORLESS;
 351         cm->cd[co].nchrs = 1;
 352         cm->cd[co].flags = PSEUDO;
 353         return co;
 354 }
 355
 356 /*
 357  * subcolor - allocate a new subcolor (if necessary) to this chr
 358  */
 359 static color
 360 subcolor(struct colormap * cm, chr c)
 361 {
 362         color           co;                             /* current color of c */
 363         color           sco;                    /* new subcolor */
 364
 365         co = GETCOLOR(cm, c);
 366         sco = newsub(cm, co);
 367         if (CISERR())
 368                 return COLORLESS;
 369         assert(sco != COLORLESS);
 370
 371         if (co == sco)                          /* already in an open subcolor */
 372                 return co;                              /* rest is redundant */
 373         cm->cd[co].nchrs--;
 374         cm->cd[sco].nchrs++;
 375         setcolor(cm, c, sco);
 376         return sco;
 377 }
 378
 379 /*
 380  * newsub - allocate a new subcolor (if necessary) for a color
 381  */
 382 static color
 383 newsub(struct colormap * cm,
 384            pcolor co)
 385 {
 386         color           sco;                    /* new subcolor */
 387
 388         sco = cm->cd[co].sub;
 389         if (sco == NOSUB)
 390         {                                                       /* color has no open subcolor */
 391                 if (cm->cd[co].nchrs == 1)              /* optimization */
 392                         return co;
 393                 sco = newcolor(cm);             /* must create subcolor */
 394                 if (sco == COLORLESS)
 395                 {
 396                         assert(CISERR());
 397                         return COLORLESS;
 398                 }
 399                 cm->cd[co].sub = sco;
 400                 cm->cd[sco].sub = sco;  /* open subcolor points to self */
 401         }
 402         assert(sco != NOSUB);
 403
 404         return sco;
 405 }
 406
 407 /*
 408  * subrange - allocate new subcolors to this range of chrs, fill in arcs
 409  */
 410 static void
 411 subrange(struct vars * v,
 412                  chr from,
 413                  chr to,
 414                  struct state * lp,
 415                  struct state * rp)
 416 {
 417         uchr            uf;
 418         int                     i;
 419
 420         assert(from <= to);
 421
 422         /* first, align "from" on a tree-block boundary */
 423         uf = (uchr) from;
 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 */
 428                 return;
 429
 430         /* deal with whole blocks */
 431         for (; to - from >= BYTTAB; from += BYTTAB)
 432                 subblock(v, from, lp, rp);
 433
 434         /* clean up any remaining partial table */
 435         for (; from <= to; from++)
 436                 newarc(v->nfa, PLAIN, subcolor(v->cm, from), lp, rp);
 437 }
 438
 439 /*
 440  * subblock - allocate new subcolors for one tree block of chrs, fill in arcs
 441  */
 442 static void
 443 subblock(struct vars * v,
 444                  chr start,                             /* first of BYTTAB chrs */
 445                  struct state * lp,
 446                  struct state * rp)
 447 {
 448         uchr            uc = start;
 449         struct colormap *cm = v->cm;
 450         int                     shift;
 451         int                     level;
 452         int                     i;
 453         int                     b;
 454         union tree *t;
 455         union tree *cb;
 456         union tree *fillt;
 457         union tree *lastt;
 458         int                     previ;
 459         int                     ndone;
 460         color           co;
 461         color           sco;
 462
 463         assert((uc % BYTTAB) == 0);
 464
 465         /* find its color block, making new pointer blocks as needed */
 466         t = cm->tree;
 467         fillt = NULL;
 468         for (level = 0, shift = BYTBITS * (NBYTS - 1); shift > 0;
 469                  level++, shift -= BYTBITS)
 470         {
 471                 b = (uc >> shift) & BYTMASK;
 472                 lastt = t;
 473                 t = lastt->tptr[b];
 474                 assert(t != NULL);
 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));
 479                         if (t == NULL)
 480                         {
 481                                 CERR(REG_ESPACE);
 482                                 return;
 483                         }
 484                         memcpy(VS(t->tptr), VS(fillt->tptr),
 485                                    BYTTAB * sizeof(union tree *));
 486                         lastt->tptr[b] = t;
 487                 }
 488         }
 489
 490         /* special cases:  fill block or solid block */
 491         co = t->tcolor[0];
 492         cb = cm->cd[co].block;
 493         if (t == fillt || t == cb)
 494         {
 495                 /* either way, we want a subcolor solid block */
 496                 sco = newsub(cm, co);
 497                 t = cm->cd[sco].block;
 498                 if (t == NULL)
 499                 {                                               /* must set it up */
 500                         t = (union tree *) MALLOC(sizeof(struct colors));
 501                         if (t == NULL)
 502                         {
 503                                 CERR(REG_ESPACE);
 504                                 return;
 505                         }
 506                         for (i = 0; i < BYTTAB; i++)
 507                                 t->tcolor[i] = sco;
 508                         cm->cd[sco].block = t;
 509                 }
 510                 /* find loop must have run at least once */
 511                 lastt->tptr[b] = t;
 512                 newarc(v->nfa, PLAIN, sco, lp, rp);
 513                 cm->cd[co].nchrs -= BYTTAB;
 514                 cm->cd[sco].nchrs += BYTTAB;
 515                 return;
 516         }
 517
 518         /* general case, a mixed block to be altered */
 519         i = 0;
 520         while (i < BYTTAB)
 521         {
 522                 co = t->tcolor[i];
 523                 sco = newsub(cm, co);
 524                 newarc(v->nfa, PLAIN, sco, lp, rp);
 525                 previ = i;
 526                 do
 527                 {
 528                         t->tcolor[i++] = sco;
 529                 } while (i < BYTTAB && t->tcolor[i] == co);
 530                 ndone = i - previ;
 531                 cm->cd[co].nchrs -= ndone;
 532                 cm->cd[sco].nchrs += ndone;
 533         }
 534 }
 535
 536 /*
 537  * okcolors - promote subcolors to full colors
 538  */
 539 static void
 540 okcolors(struct nfa * nfa,
 541                  struct colormap * cm)
 542 {
 543         struct colordesc *cd;
 544         struct colordesc *end = CDEND(cm);
 545         struct colordesc *scd;
 546         struct arc *a;
 547         color           co;
 548         color           sco;
 549
 550         for (cd = cm->cd, co = 0; cd < end; cd++, co++)
 551         {
 552                 sco = cd->sub;
 553                 if (UNUSEDCOLOR(cd) || sco == NOSUB)
 554                 {
 555                         /* has no subcolor, no further action */
 556                 }
 557                 else if (sco == co)
 558                 {
 559                         /* is subcolor, let parent deal with it */
 560                 }
 561                 else if (cd->nchrs == 0)
 562                 {
 563                         /* parent empty, its arcs change color to subcolor */
 564                         cd->sub = NOSUB;
 565                         scd = &cm->cd[sco];
 566                         assert(scd->nchrs > 0);
 567                         assert(scd->sub == sco);
 568                         scd->sub = NOSUB;
 569                         while ((a = cd->arcs) != NULL)
 570                         {
 571                                 assert(a->co == co);
 572                                 /* uncolorchain(cm, a); */
 573                                 cd->arcs = a->colorchain;
 574                                 a->co = sco;
 575                                 /* colorchain(cm, a); */
 576                                 a->colorchain = scd->arcs;
 577                                 scd->arcs = a;
 578                         }
 579                         freecolor(cm, co);
 580                 }
 581                 else
 582                 {
 583                         /* parent's arcs must gain parallel subcolor arcs */
 584                         cd->sub = NOSUB;
 585                         scd = &cm->cd[sco];
 586                         assert(scd->nchrs > 0);
 587                         assert(scd->sub == sco);
 588                         scd->sub = NOSUB;
 589                         for (a = cd->arcs; a != NULL; a = a->colorchain)
 590                         {
 591                                 assert(a->co == co);
 592                                 newarc(nfa, a->type, sco, a->from, a->to);
 593                         }
 594                 }
 595         }
 596 }
 597
 598 /*
 599  * colorchain - add this arc to the color chain of its color
 600  */
 601 static void
 602 colorchain(struct colormap * cm,
 603                    struct arc * a)
 604 {
 605         struct colordesc *cd = &cm->cd[a->co];
 606
 607         a->colorchain = cd->arcs;
 608         cd->arcs = a;
 609 }
 610
 611 /*
 612  * uncolorchain - delete this arc from the color chain of its color
 613  */
 614 static void
 615 uncolorchain(struct colormap * cm,
 616                          struct arc * a)
 617 {
 618         struct colordesc *cd = &cm->cd[a->co];
 619         struct arc *aa;
 620
 621         aa = cd->arcs;
 622         if (aa == a)                            /* easy case */
 623                 cd->arcs = a->colorchain;
 624         else
 625         {
 626                 for (; aa != NULL && aa->colorchain != a; aa = aa->colorchain)
 627                         continue;
 628                 assert(aa != NULL);
 629                 aa->colorchain = a->colorchain;
 630         }
 631         a->colorchain = NULL;           /* paranoia */
 632 }
 633
 634 /*
 635  * singleton - is this character in its own color?
 636  */
 637 static int                                              /* predicate */
 638 singleton(struct colormap * cm,
 639                   chr c)
 640 {
 641         color           co;                             /* color of c */
 642
 643         co = GETCOLOR(cm, c);
 644         if (cm->cd[co].nchrs == 1 && cm->cd[co].sub == NOSUB)
 645                 return 1;
 646         return 0;
 647 }
 648
 649 /*
 650  * rainbow - add arcs of all full colors (but one) between specified states
 651  */
 652 static void
 653 rainbow(struct nfa * nfa,
 654                 struct colormap * cm,
 655                 int type,
 656                 pcolor but,                             /* COLORLESS if no exceptions */
 657                 struct state * from,
 658                 struct state * to)
 659 {
 660         struct colordesc *cd;
 661         struct colordesc *end = CDEND(cm);
 662         color           co;
 663
 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);
 668 }
 669
 670 /*
 671  * colorcomplement - add arcs of complementary colors
 672  *
 673  * The calling sequence ought to be reconciled with cloneouts().
 674  */
 675 static void
 676 colorcomplement(struct nfa * nfa,
 677                                 struct colormap * cm,
 678                                 int type,
 679                                 struct state * of,              /* complements of this guy's PLAIN
 680                                                                                  * outarcs */
 681                                 struct state * from,
 682                                 struct state * to)
 683 {
 684         struct colordesc *cd;
 685         struct colordesc *end = CDEND(cm);
 686         color           co;
 687
 688         assert(of != from);
 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);
 693 }
 694
 695
 696 #ifdef REG_DEBUG
 697
 698 /*
 699  * dumpcolors - debugging output
 700  */
 701 static void
 702 dumpcolors(struct colormap * cm,
 703                    FILE *f)
 704 {
 705         struct colordesc *cd;
 706         struct colordesc *end;
 707         color           co;
 708         chr                     c;
 709         char       *has;
 710
 711         fprintf(f, "max %ld\n", (long) cm->max);
 712         if (NBYTS > 1)
 713                 fillcheck(cm, cm->tree, 0, f);
 714         end = CDEND(cm);
 715         for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++) /* skip 0 */
 716                 if (!UNUSEDCOLOR(cd))
 717                 {
 718                         assert(cd->nchrs > 0);
 719                         has = (cd->block != NULL) ? "#" : "";
 720                         if (cd->flags & PSEUDO)
 721                                 fprintf(f, "#%2ld%s(ps): ", (long) co, has);
 722                         else
 723                                 fprintf(f, "#%2ld%s(%2d): ", (long) co,
 724                                                 has, cd->nchrs);
 725                         /* it's hard to do this more efficiently */
 726                         for (c = CHR_MIN; c < CHR_MAX; c++)
 727                                 if (GETCOLOR(cm, c) == co)
 728                                         dumpchr(c, f);
 729                         assert(c == CHR_MAX);
 730                         if (GETCOLOR(cm, c) == co)
 731                                 dumpchr(c, f);
 732                         fprintf(f, "\n");
 733                 }
 734 }
 735
 736 /*
 737  * fillcheck - check proper filling of a tree
 738  */
 739 static void
 740 fillcheck(struct colormap * cm,
 741                   union tree * tree,
 742                   int level,                    /* level number (top == 0) of this block */
 743                   FILE *f)
 744 {
 745         int                     i;
 746         union tree *t;
 747         union tree *fillt = &cm->tree[level + 1];
 748
 749         assert(level < NBYTS - 1);      /* this level has pointers */
 750         for (i = BYTTAB - 1; i >= 0; i--)
 751         {
 752                 t = tree->tptr[i];
 753                 if (t == NULL)
 754                         fprintf(f, "NULL found in filled tree!\n");
 755                 else if (t == fillt)
 756                 {
 757                 }
 758                 else if (level < NBYTS - 2)             /* more pointer blocks below */
 759                         fillcheck(cm, t, level + 1, f);
 760         }
 761 }
 762
 763 /*
 764  * dumpchr - print a chr
 765  *
 766  * Kind of char-centric but works well enough for debug use.
 767  */
 768 static void
 769 dumpchr(chr c,
 770                 FILE *f)
 771 {
 772         if (c == '\\')
 773                 fprintf(f, "\\\\");
 774         else if (c > ' ' && c <= '~')
 775                 putc((char) c, f);
 776         else
 777                 fprintf(f, "\\u%04lx", (long) c);
 778 }
 779
 780 #endif   /* REG_DEBUG */