src/backend/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  * $PostgreSQL$
  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         size_t          n;
 226
 227         if (CISERR())
 228                 return COLORLESS;
 229
 230         if (cm->free != 0)
 231         {
 232                 assert(cm->free > 0);
 233                 assert((size_t) cm->free < cm->ncds);
 234                 cd = &cm->cd[cm->free];
 235                 assert(UNUSEDCOLOR(cd));
 236                 assert(cd->arcs == NULL);
 237                 cm->free = cd->sub;
 238         }
 239         else if (cm->max < cm->ncds - 1)
 240         {
 241                 cm->max++;
 242                 cd = &cm->cd[cm->max];
 243         }
 244         else
 245         {
 246                 /* oops, must allocate more */
 247                 struct colordesc *newCd;
 248
 249                 n = cm->ncds * 2;
 250                 if (cm->cd == cm->cdspace)
 251                 {
 252                         newCd = (struct colordesc *) MALLOC(n * sizeof(struct colordesc));
 253                         if (newCd != NULL)
 254                                 memcpy(VS(newCd), VS(cm->cdspace), cm->ncds *
 255                                            sizeof(struct colordesc));
 256                 }
 257                 else
 258                         newCd = (struct colordesc *)
 259                                 REALLOC(cm->cd, n * sizeof(struct colordesc));
 260                 if (newCd == NULL)
 261                 {
 262                         CERR(REG_ESPACE);
 263                         return COLORLESS;
 264                 }
 265                 cm->cd = newCd;
 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                                 a->co = sco;
 574                                 colorchain(cm, a);
 575                         }
 576                         freecolor(cm, co);
 577                 }
 578                 else
 579                 {
 580                         /* parent's arcs must gain parallel subcolor arcs */
 581                         cd->sub = NOSUB;
 582                         scd = &cm->cd[sco];
 583                         assert(scd->nchrs > 0);
 584                         assert(scd->sub == sco);
 585                         scd->sub = NOSUB;
 586                         for (a = cd->arcs; a != NULL; a = a->colorchain)
 587                         {
 588                                 assert(a->co == co);
 589                                 newarc(nfa, a->type, sco, a->from, a->to);
 590                         }
 591                 }
 592         }
 593 }
 594
 595 /*
 596  * colorchain - add this arc to the color chain of its color
 597  */
 598 static void
 599 colorchain(struct colormap * cm,
 600                    struct arc * a)
 601 {
 602         struct colordesc *cd = &cm->cd[a->co];
 603
 604         if (cd->arcs != NULL)
 605                 cd->arcs->colorchainRev = a;
 606         a->colorchain = cd->arcs;
 607         a->colorchainRev = NULL;
 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 = a->colorchainRev;
 620
 621         if (aa == NULL)
 622         {
 623                 assert(cd->arcs == a);
 624                 cd->arcs = a->colorchain;
 625         }
 626         else
 627         {
 628                 assert(aa->colorchain == a);
 629                 aa->colorchain = a->colorchain;
 630         }
 631         if (a->colorchain != NULL)
 632                 a->colorchain->colorchainRev = aa;
 633         a->colorchain = NULL;           /* paranoia */
 634         a->colorchainRev = NULL;
 635 }
 636
 637 /*
 638  * rainbow - add arcs of all full colors (but one) between specified states
 639  */
 640 static void
 641 rainbow(struct nfa * nfa,
 642                 struct colormap * cm,
 643                 int type,
 644                 pcolor but,                             /* COLORLESS if no exceptions */
 645                 struct state * from,
 646                 struct state * to)
 647 {
 648         struct colordesc *cd;
 649         struct colordesc *end = CDEND(cm);
 650         color           co;
 651
 652         for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
 653                 if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but &&
 654                         !(cd->flags & PSEUDO))
 655                         newarc(nfa, type, co, from, to);
 656 }
 657
 658 /*
 659  * colorcomplement - add arcs of complementary colors
 660  *
 661  * The calling sequence ought to be reconciled with cloneouts().
 662  */
 663 static void
 664 colorcomplement(struct nfa * nfa,
 665                                 struct colormap * cm,
 666                                 int type,
 667                                 struct state * of,              /* complements of this guy's PLAIN
 668                                                                                  * outarcs */
 669                                 struct state * from,
 670                                 struct state * to)
 671 {
 672         struct colordesc *cd;
 673         struct colordesc *end = CDEND(cm);
 674         color           co;
 675
 676         assert(of != from);
 677         for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++)
 678                 if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO))
 679                         if (findarc(of, PLAIN, co) == NULL)
 680                                 newarc(nfa, type, co, from, to);
 681 }
 682
 683
 684 #ifdef REG_DEBUG
 685
 686 /*
 687  * dumpcolors - debugging output
 688  */
 689 static void
 690 dumpcolors(struct colormap * cm,
 691                    FILE *f)
 692 {
 693         struct colordesc *cd;
 694         struct colordesc *end;
 695         color           co;
 696         chr                     c;
 697         char       *has;
 698
 699         fprintf(f, "max %ld\n", (long) cm->max);
 700         if (NBYTS > 1)
 701                 fillcheck(cm, cm->tree, 0, f);
 702         end = CDEND(cm);
 703         for (cd = cm->cd + 1, co = 1; cd < end; cd++, co++) /* skip 0 */
 704                 if (!UNUSEDCOLOR(cd))
 705                 {
 706                         assert(cd->nchrs > 0);
 707                         has = (cd->block != NULL) ? "#" : "";
 708                         if (cd->flags & PSEUDO)
 709                                 fprintf(f, "#%2ld%s(ps): ", (long) co, has);
 710                         else
 711                                 fprintf(f, "#%2ld%s(%2d): ", (long) co,
 712                                                 has, cd->nchrs);
 713
 714                         /*
 715                          * Unfortunately, it's hard to do this next bit more efficiently.
 716                          *
 717                          * Spencer's original coding has the loop iterating from CHR_MIN
 718                          * to CHR_MAX, but that's utterly unusable for 32-bit chr. For
 719                          * debugging purposes it seems fine to print only chr codes up to
 720                          * 1000 or so.
 721                          */
 722                         for (c = CHR_MIN; c < 1000; c++)
 723                                 if (GETCOLOR(cm, c) == co)
 724                                         dumpchr(c, f);
 725                         fprintf(f, "\n");
 726                 }
 727 }
 728
 729 /*
 730  * fillcheck - check proper filling of a tree
 731  */
 732 static void
 733 fillcheck(struct colormap * cm,
 734                   union tree * tree,
 735                   int level,                    /* level number (top == 0) of this block */
 736                   FILE *f)
 737 {
 738         int                     i;
 739         union tree *t;
 740         union tree *fillt = &cm->tree[level + 1];
 741
 742         assert(level < NBYTS - 1);      /* this level has pointers */
 743         for (i = BYTTAB - 1; i >= 0; i--)
 744         {
 745                 t = tree->tptr[i];
 746                 if (t == NULL)
 747                         fprintf(f, "NULL found in filled tree!\n");
 748                 else if (t == fillt)
 749                 {
 750                 }
 751                 else if (level < NBYTS - 2)             /* more pointer blocks below */
 752                         fillcheck(cm, t, level + 1, f);
 753         }
 754 }
 755
 756 /*
 757  * dumpchr - print a chr
 758  *
 759  * Kind of char-centric but works well enough for debug use.
 760  */
 761 static void
 762 dumpchr(chr c,
 763                 FILE *f)
 764 {
 765         if (c == '\\')
 766                 fprintf(f, "\\\\");
 767         else if (c > ' ' && c <= '~')
 768                 putc((char) c, f);
 769         else
 770                 fprintf(f, "\\u%04lx", (long) c);
 771 }
 772
 773 #endif   /* REG_DEBUG */