/[dtapublic]/projs/trunk/shared_source/c_tcl_base_7_5_w_mods/regc_color.c
ViewVC logotype

Diff of /projs/trunk/shared_source/c_tcl_base_7_5_w_mods/regc_color.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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

Legend:
Removed from v.70  
changed lines
  Added in v.71

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25