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