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