Commit | Line | Data |
---|---|---|
48bf5def RN |
1 | /* |
2 | * DFA routines | |
3 | * This file is #included by regexec.c. | |
4 | * | |
5 | * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved. | |
6 | * | |
7 | * Development of this software was funded, in part, by Cray Research Inc., | |
8 | * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics | |
9 | * Corporation, none of whom are responsible for the results. The author | |
10 | * thanks all of them. | |
11 | * | |
12 | * Redistribution and use in source and binary forms -- with or without | |
13 | * modification -- are permitted for any purpose, provided that | |
14 | * redistributions in source form retain this entire copyright notice and | |
15 | * indicate the origin and nature of any modifications. | |
16 | * | |
17 | * I'd appreciate being given credit for this package in the documentation | |
18 | * of software which uses it, but that is not a requirement. | |
19 | * | |
20 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, | |
21 | * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY | |
22 | * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL | |
23 | * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | |
24 | * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | |
25 | * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; | |
26 | * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, | |
27 | * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR | |
28 | * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF | |
29 | * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
30 | * | |
31 | * $Header$ | |
32 | * | |
33 | */ | |
34 | ||
35 | /* | |
36 | * longest - longest-preferred matching engine | |
37 | */ | |
38 | static chr * /* endpoint, or NULL */ | |
39 | longest(struct vars * v, /* used only for debug and exec flags */ | |
40 | struct dfa * d, | |
41 | chr *start, /* where the match should start */ | |
42 | chr *stop, /* match must end at or before here */ | |
43 | int *hitstopp) /* record whether hit v->stop, if non-NULL */ | |
44 | { | |
45 | chr *cp; | |
46 | chr *realstop = (stop == v->stop) ? stop : stop + 1; | |
47 | color co; | |
48 | struct sset *css; | |
49 | struct sset *ss; | |
50 | chr *post; | |
51 | int i; | |
52 | struct colormap *cm = d->cm; | |
53 | ||
54 | /* initialize */ | |
55 | css = initialize(v, d, start); | |
56 | cp = start; | |
57 | if (hitstopp != NULL) | |
58 | *hitstopp = 0; | |
59 | ||
60 | /* startup */ | |
61 | FDEBUG(("+++ startup +++\n")); | |
62 | if (cp == v->start) | |
63 | { | |
64 | co = d->cnfa->bos[(v->eflags & REG_NOTBOL) ? 0 : 1]; | |
65 | FDEBUG(("color %ld\n", (long) co)); | |
66 | } | |
67 | else | |
68 | { | |
69 | co = GETCOLOR(cm, *(cp - 1)); | |
70 | FDEBUG(("char %c, color %ld\n", (char) *(cp - 1), (long) co)); | |
71 | } | |
72 | css = miss(v, d, css, co, cp, start); | |
73 | if (css == NULL) | |
74 | return NULL; | |
75 | css->lastseen = cp; | |
76 | ||
77 | /* main loop */ | |
78 | if (v->eflags & REG_FTRACE) | |
79 | while (cp < realstop) | |
80 | { | |
81 | FDEBUG(("+++ at c%d +++\n", css - d->ssets)); | |
82 | co = GETCOLOR(cm, *cp); | |
83 | FDEBUG(("char %c, color %ld\n", (char) *cp, (long) co)); | |
84 | ss = css->outs[co]; | |
85 | if (ss == NULL) | |
86 | { | |
87 | ss = miss(v, d, css, co, cp + 1, start); | |
88 | if (ss == NULL) | |
89 | break; /* NOTE BREAK OUT */ | |
90 | } | |
91 | cp++; | |
92 | ss->lastseen = cp; | |
93 | css = ss; | |
94 | } | |
95 | else | |
96 | while (cp < realstop) | |
97 | { | |
98 | co = GETCOLOR(cm, *cp); | |
99 | ss = css->outs[co]; | |
100 | if (ss == NULL) | |
101 | { | |
102 | ss = miss(v, d, css, co, cp + 1, start); | |
103 | if (ss == NULL) | |
104 | break; /* NOTE BREAK OUT */ | |
105 | } | |
106 | cp++; | |
107 | ss->lastseen = cp; | |
108 | css = ss; | |
109 | } | |
110 | ||
111 | /* shutdown */ | |
112 | FDEBUG(("+++ shutdown at c%d +++\n", css - d->ssets)); | |
113 | if (cp == v->stop && stop == v->stop) | |
114 | { | |
115 | if (hitstopp != NULL) | |
116 | *hitstopp = 1; | |
117 | co = d->cnfa->eos[(v->eflags & REG_NOTEOL) ? 0 : 1]; | |
118 | FDEBUG(("color %ld\n", (long) co)); | |
119 | ss = miss(v, d, css, co, cp, start); | |
120 | /* special case: match ended at eol? */ | |
121 | if (ss != NULL && (ss->flags & POSTSTATE)) | |
122 | return cp; | |
123 | else if (ss != NULL) | |
124 | ss->lastseen = cp; /* to be tidy */ | |
125 | } | |
126 | ||
127 | /* find last match, if any */ | |
128 | post = d->lastpost; | |
129 | for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--) | |
130 | if ((ss->flags & POSTSTATE) && post != ss->lastseen && | |
131 | (post == NULL || post < ss->lastseen)) | |
132 | post = ss->lastseen; | |
133 | if (post != NULL) /* found one */ | |
134 | return post - 1; | |
135 | ||
136 | return NULL; | |
137 | } | |
138 | ||
139 | /* | |
140 | * shortest - shortest-preferred matching engine | |
141 | */ | |
142 | static chr * /* endpoint, or NULL */ | |
143 | shortest(struct vars * v, | |
144 | struct dfa * d, | |
145 | chr *start, /* where the match should start */ | |
146 | chr *min, /* match must end at or after here */ | |
147 | chr *max, /* match must end at or before here */ | |
148 | chr **coldp, /* store coldstart pointer here, if | |
149 | * nonNULL */ | |
150 | int *hitstopp) /* record whether hit v->stop, if non-NULL */ | |
151 | { | |
152 | chr *cp; | |
153 | chr *realmin = (min == v->stop) ? min : min + 1; | |
154 | chr *realmax = (max == v->stop) ? max : max + 1; | |
155 | color co; | |
156 | struct sset *css; | |
157 | struct sset *ss; | |
158 | struct colormap *cm = d->cm; | |
159 | ||
160 | /* initialize */ | |
161 | css = initialize(v, d, start); | |
162 | cp = start; | |
163 | if (hitstopp != NULL) | |
164 | *hitstopp = 0; | |
165 | ||
166 | /* startup */ | |
167 | FDEBUG(("--- startup ---\n")); | |
168 | if (cp == v->start) | |
169 | { | |
170 | co = d->cnfa->bos[(v->eflags & REG_NOTBOL) ? 0 : 1]; | |
171 | FDEBUG(("color %ld\n", (long) co)); | |
172 | } | |
173 | else | |
174 | { | |
175 | co = GETCOLOR(cm, *(cp - 1)); | |
176 | FDEBUG(("char %c, color %ld\n", (char) *(cp - 1), (long) co)); | |
177 | } | |
178 | css = miss(v, d, css, co, cp, start); | |
179 | if (css == NULL) | |
180 | return NULL; | |
181 | css->lastseen = cp; | |
182 | ss = css; | |
183 | ||
184 | /* main loop */ | |
185 | if (v->eflags & REG_FTRACE) | |
186 | while (cp < realmax) | |
187 | { | |
188 | FDEBUG(("--- at c%d ---\n", css - d->ssets)); | |
189 | co = GETCOLOR(cm, *cp); | |
190 | FDEBUG(("char %c, color %ld\n", (char) *cp, (long) co)); | |
191 | ss = css->outs[co]; | |
192 | if (ss == NULL) | |
193 | { | |
194 | ss = miss(v, d, css, co, cp + 1, start); | |
195 | if (ss == NULL) | |
196 | break; /* NOTE BREAK OUT */ | |
197 | } | |
198 | cp++; | |
199 | ss->lastseen = cp; | |
200 | css = ss; | |
201 | if ((ss->flags & POSTSTATE) && cp >= realmin) | |
202 | break; /* NOTE BREAK OUT */ | |
203 | } | |
204 | else | |
205 | while (cp < realmax) | |
206 | { | |
207 | co = GETCOLOR(cm, *cp); | |
208 | ss = css->outs[co]; | |
209 | if (ss == NULL) | |
210 | { | |
211 | ss = miss(v, d, css, co, cp + 1, start); | |
212 | if (ss == NULL) | |
213 | break; /* NOTE BREAK OUT */ | |
214 | } | |
215 | cp++; | |
216 | ss->lastseen = cp; | |
217 | css = ss; | |
218 | if ((ss->flags & POSTSTATE) && cp >= realmin) | |
219 | break; /* NOTE BREAK OUT */ | |
220 | } | |
221 | ||
222 | if (ss == NULL) | |
223 | return NULL; | |
224 | ||
225 | if (coldp != NULL) /* report last no-progress state set, if | |
226 | * any */ | |
227 | *coldp = lastcold(v, d); | |
228 | ||
229 | if ((ss->flags & POSTSTATE) && cp > min) | |
230 | { | |
231 | assert(cp >= realmin); | |
232 | cp--; | |
233 | } | |
234 | else if (cp == v->stop && max == v->stop) | |
235 | { | |
236 | co = d->cnfa->eos[(v->eflags & REG_NOTEOL) ? 0 : 1]; | |
237 | FDEBUG(("color %ld\n", (long) co)); | |
238 | ss = miss(v, d, css, co, cp, start); | |
239 | /* match might have ended at eol */ | |
240 | if ((ss == NULL || !(ss->flags & POSTSTATE)) && hitstopp != NULL) | |
241 | *hitstopp = 1; | |
242 | } | |
243 | ||
244 | if (ss == NULL || !(ss->flags & POSTSTATE)) | |
245 | return NULL; | |
246 | ||
247 | return cp; | |
248 | } | |
249 | ||
250 | /* | |
251 | * lastcold - determine last point at which no progress had been made | |
252 | */ | |
253 | static chr * /* endpoint, or NULL */ | |
254 | lastcold(struct vars * v, | |
255 | struct dfa * d) | |
256 | { | |
257 | struct sset *ss; | |
258 | chr *nopr; | |
259 | int i; | |
260 | ||
261 | nopr = d->lastnopr; | |
262 | if (nopr == NULL) | |
263 | nopr = v->start; | |
264 | for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--) | |
265 | if ((ss->flags & NOPROGRESS) && nopr < ss->lastseen) | |
266 | nopr = ss->lastseen; | |
267 | return nopr; | |
268 | } | |
269 | ||
270 | /* | |
271 | * newdfa - set up a fresh DFA | |
272 | */ | |
273 | static struct dfa * | |
274 | newdfa(struct vars * v, | |
275 | struct cnfa * cnfa, | |
276 | struct colormap * cm, | |
277 | struct smalldfa * small) /* preallocated space, may be NULL */ | |
278 | { | |
279 | struct dfa *d; | |
280 | size_t nss = cnfa->nstates * 2; | |
281 | int wordsper = (cnfa->nstates + UBITS - 1) / UBITS; | |
282 | struct smalldfa *smallwas = small; | |
283 | ||
284 | assert(cnfa != NULL && cnfa->nstates != 0); | |
285 | ||
286 | if (nss <= FEWSTATES && cnfa->ncolors <= FEWCOLORS) | |
287 | { | |
288 | assert(wordsper == 1); | |
289 | if (small == NULL) | |
290 | { | |
291 | small = (struct smalldfa *) MALLOC( | |
292 | sizeof(struct smalldfa)); | |
293 | if (small == NULL) | |
294 | { | |
295 | ERR(REG_ESPACE); | |
296 | return NULL; | |
297 | } | |
298 | } | |
299 | d = &small->dfa; | |
300 | d->ssets = small->ssets; | |
301 | d->statesarea = small->statesarea; | |
302 | d->work = &d->statesarea[nss]; | |
303 | d->outsarea = small->outsarea; | |
304 | d->incarea = small->incarea; | |
305 | d->cptsmalloced = 0; | |
306 | d->mallocarea = (smallwas == NULL) ? (char *) small : NULL; | |
307 | } | |
308 | else | |
309 | { | |
310 | d = (struct dfa *) MALLOC(sizeof(struct dfa)); | |
311 | if (d == NULL) | |
312 | { | |
313 | ERR(REG_ESPACE); | |
314 | return NULL; | |
315 | } | |
316 | d->ssets = (struct sset *) MALLOC(nss * sizeof(struct sset)); | |
317 | d->statesarea = (unsigned *) MALLOC((nss + WORK) * wordsper * | |
318 | sizeof(unsigned)); | |
319 | d->work = &d->statesarea[nss * wordsper]; | |
320 | d->outsarea = (struct sset **) MALLOC(nss * cnfa->ncolors * | |
321 | sizeof(struct sset *)); | |
322 | d->incarea = (struct arcp *) MALLOC(nss * cnfa->ncolors * | |
323 | sizeof(struct arcp)); | |
324 | d->cptsmalloced = 1; | |
325 | d->mallocarea = (char *) d; | |
326 | if (d->ssets == NULL || d->statesarea == NULL || | |
327 | d->outsarea == NULL || d->incarea == NULL) | |
328 | { | |
329 | freedfa(d); | |
330 | ERR(REG_ESPACE); | |
331 | return NULL; | |
332 | } | |
333 | } | |
334 | ||
335 | d->nssets = (v->eflags & REG_SMALL) ? 7 : nss; | |
336 | d->nssused = 0; | |
337 | d->nstates = cnfa->nstates; | |
338 | d->ncolors = cnfa->ncolors; | |
339 | d->wordsper = wordsper; | |
340 | d->cnfa = cnfa; | |
341 | d->cm = cm; | |
342 | d->lastpost = NULL; | |
343 | d->lastnopr = NULL; | |
344 | d->search = d->ssets; | |
345 | ||
346 | /* initialization of sset fields is done as needed */ | |
347 | ||
348 | return d; | |
349 | } | |
350 | ||
351 | /* | |
352 | * freedfa - free a DFA | |
353 | */ | |
354 | static void | |
355 | freedfa(struct dfa * d) | |
356 | { | |
357 | if (d->cptsmalloced) | |
358 | { | |
359 | if (d->ssets != NULL) | |
360 | FREE(d->ssets); | |
361 | if (d->statesarea != NULL) | |
362 | FREE(d->statesarea); | |
363 | if (d->outsarea != NULL) | |
364 | FREE(d->outsarea); | |
365 | if (d->incarea != NULL) | |
366 | FREE(d->incarea); | |
367 | } | |
368 | ||
369 | if (d->mallocarea != NULL) | |
370 | FREE(d->mallocarea); | |
371 | } | |
372 | ||
373 | /* | |
374 | * hash - construct a hash code for a bitvector | |
375 | * | |
376 | * There are probably better ways, but they're more expensive. | |
377 | */ | |
378 | static unsigned | |
379 | hash(unsigned *uv, | |
380 | int n) | |
381 | { | |
382 | int i; | |
383 | unsigned h; | |
384 | ||
385 | h = 0; | |
386 | for (i = 0; i < n; i++) | |
387 | h ^= uv[i]; | |
388 | return h; | |
389 | } | |
390 | ||
391 | /* | |
392 | * initialize - hand-craft a cache entry for startup, otherwise get ready | |
393 | */ | |
394 | static struct sset * | |
395 | initialize(struct vars * v, /* used only for debug flags */ | |
396 | struct dfa * d, | |
397 | chr *start) | |
398 | { | |
399 | struct sset *ss; | |
400 | int i; | |
401 | ||
402 | /* is previous one still there? */ | |
403 | if (d->nssused > 0 && (d->ssets[0].flags & STARTER)) | |
404 | ss = &d->ssets[0]; | |
405 | else | |
406 | { /* no, must (re)build it */ | |
407 | ss = getvacant(v, d, start, start); | |
408 | for (i = 0; i < d->wordsper; i++) | |
409 | ss->states[i] = 0; | |
410 | BSET(ss->states, d->cnfa->pre); | |
411 | ss->hash = HASH(ss->states, d->wordsper); | |
412 | assert(d->cnfa->pre != d->cnfa->post); | |
413 | ss->flags = STARTER | LOCKED | NOPROGRESS; | |
414 | /* lastseen dealt with below */ | |
415 | } | |
416 | ||
417 | for (i = 0; i < d->nssused; i++) | |
418 | d->ssets[i].lastseen = NULL; | |
419 | ss->lastseen = start; /* maybe untrue, but harmless */ | |
420 | d->lastpost = NULL; | |
421 | d->lastnopr = NULL; | |
422 | return ss; | |
423 | } | |
424 | ||
425 | /* | |
426 | * miss - handle a cache miss | |
427 | */ | |
428 | static struct sset * /* NULL if goes to empty set */ | |
429 | miss(struct vars * v, /* used only for debug flags */ | |
430 | struct dfa * d, | |
431 | struct sset * css, | |
432 | pcolor co, | |
433 | chr *cp, /* next chr */ | |
434 | chr *start) /* where the attempt got started */ | |
435 | { | |
436 | struct cnfa *cnfa = d->cnfa; | |
437 | int i; | |
438 | unsigned h; | |
439 | struct carc *ca; | |
440 | struct sset *p; | |
441 | int ispost; | |
442 | int noprogress; | |
443 | int gotstate; | |
444 | int dolacons; | |
445 | int sawlacons; | |
446 | ||
447 | /* for convenience, we can be called even if it might not be a miss */ | |
448 | if (css->outs[co] != NULL) | |
449 | { | |
450 | FDEBUG(("hit\n")); | |
451 | return css->outs[co]; | |
452 | } | |
453 | FDEBUG(("miss\n")); | |
454 | ||
455 | /* first, what set of states would we end up in? */ | |
456 | for (i = 0; i < d->wordsper; i++) | |
457 | d->work[i] = 0; | |
458 | ispost = 0; | |
459 | noprogress = 1; | |
460 | gotstate = 0; | |
461 | for (i = 0; i < d->nstates; i++) | |
462 | if (ISBSET(css->states, i)) | |
463 | for (ca = cnfa->states[i] + 1; ca->co != COLORLESS; ca++) | |
464 | if (ca->co == co) | |
465 | { | |
466 | BSET(d->work, ca->to); | |
467 | gotstate = 1; | |
468 | if (ca->to == cnfa->post) | |
469 | ispost = 1; | |
470 | if (!cnfa->states[ca->to]->co) | |
471 | noprogress = 0; | |
472 | FDEBUG(("%d -> %d\n", i, ca->to)); | |
473 | } | |
474 | dolacons = (gotstate) ? (cnfa->flags & HASLACONS) : 0; | |
475 | sawlacons = 0; | |
476 | while (dolacons) | |
477 | { /* transitive closure */ | |
478 | dolacons = 0; | |
479 | for (i = 0; i < d->nstates; i++) | |
480 | if (ISBSET(d->work, i)) | |
481 | for (ca = cnfa->states[i] + 1; ca->co != COLORLESS; | |
482 | ca++) | |
483 | { | |
484 | if (ca->co <= cnfa->ncolors) | |
485 | continue; /* NOTE CONTINUE */ | |
486 | sawlacons = 1; | |
487 | if (ISBSET(d->work, ca->to)) | |
488 | continue; /* NOTE CONTINUE */ | |
489 | if (!lacon(v, cnfa, cp, ca->co)) | |
490 | continue; /* NOTE CONTINUE */ | |
491 | BSET(d->work, ca->to); | |
492 | dolacons = 1; | |
493 | if (ca->to == cnfa->post) | |
494 | ispost = 1; | |
495 | if (!cnfa->states[ca->to]->co) | |
496 | noprogress = 0; | |
497 | FDEBUG(("%d :> %d\n", i, ca->to)); | |
498 | } | |
499 | } | |
500 | if (!gotstate) | |
501 | return NULL; | |
502 | h = HASH(d->work, d->wordsper); | |
503 | ||
504 | /* next, is that in the cache? */ | |
505 | for (p = d->ssets, i = d->nssused; i > 0; p++, i--) | |
506 | if (HIT(h, d->work, p, d->wordsper)) | |
507 | { | |
508 | FDEBUG(("cached c%d\n", p - d->ssets)); | |
509 | break; /* NOTE BREAK OUT */ | |
510 | } | |
511 | if (i == 0) | |
512 | { /* nope, need a new cache entry */ | |
513 | p = getvacant(v, d, cp, start); | |
514 | assert(p != css); | |
515 | for (i = 0; i < d->wordsper; i++) | |
516 | p->states[i] = d->work[i]; | |
517 | p->hash = h; | |
518 | p->flags = (ispost) ? POSTSTATE : 0; | |
519 | if (noprogress) | |
520 | p->flags |= NOPROGRESS; | |
521 | /* lastseen to be dealt with by caller */ | |
522 | } | |
523 | ||
524 | if (!sawlacons) | |
525 | { /* lookahead conds. always cache miss */ | |
526 | FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, p - d->ssets)); | |
527 | css->outs[co] = p; | |
528 | css->inchain[co] = p->ins; | |
529 | p->ins.ss = css; | |
530 | p->ins.co = (color) co; | |
531 | } | |
532 | return p; | |
533 | } | |
534 | ||
535 | /* | |
536 | * lacon - lookahead-constraint checker for miss() | |
537 | */ | |
538 | static int /* predicate: constraint satisfied? */ | |
539 | lacon(struct vars * v, | |
540 | struct cnfa * pcnfa, /* parent cnfa */ | |
541 | chr *cp, | |
542 | pcolor co) /* "color" of the lookahead constraint */ | |
543 | { | |
544 | int n; | |
545 | struct subre *sub; | |
546 | struct dfa *d; | |
547 | struct smalldfa sd; | |
548 | chr *end; | |
549 | ||
550 | n = co - pcnfa->ncolors; | |
551 | assert(n < v->g->nlacons && v->g->lacons != NULL); | |
552 | FDEBUG(("=== testing lacon %d\n", n)); | |
553 | sub = &v->g->lacons[n]; | |
554 | d = newdfa(v, &sub->cnfa, &v->g->cmap, &sd); | |
555 | if (d == NULL) | |
556 | { | |
557 | ERR(REG_ESPACE); | |
558 | return 0; | |
559 | } | |
560 | end = longest(v, d, cp, v->stop, (int *) NULL); | |
561 | freedfa(d); | |
562 | FDEBUG(("=== lacon %d match %d\n", n, (end != NULL))); | |
563 | return (sub->subno) ? (end != NULL) : (end == NULL); | |
564 | } | |
565 | ||
566 | /* | |
567 | * getvacant - get a vacant state set | |
568 | * This routine clears out the inarcs and outarcs, but does not otherwise | |
569 | * clear the innards of the state set -- that's up to the caller. | |
570 | */ | |
571 | static struct sset * | |
572 | getvacant(struct vars * v, /* used only for debug flags */ | |
573 | struct dfa * d, | |
574 | chr *cp, | |
575 | chr *start) | |
576 | { | |
577 | int i; | |
578 | struct sset *ss; | |
579 | struct sset *p; | |
580 | struct arcp ap; | |
581 | struct arcp lastap; | |
582 | color co; | |
583 | ||
584 | ss = pickss(v, d, cp, start); | |
585 | assert(!(ss->flags & LOCKED)); | |
586 | ||
587 | /* clear out its inarcs, including self-referential ones */ | |
588 | ap = ss->ins; | |
589 | while ((p = ap.ss) != NULL) | |
590 | { | |
591 | co = ap.co; | |
592 | FDEBUG(("zapping c%d's %ld outarc\n", p - d->ssets, (long) co)); | |
593 | p->outs[co] = NULL; | |
594 | ap = p->inchain[co]; | |
595 | p->inchain[co].ss = NULL; /* paranoia */ | |
596 | } | |
597 | ss->ins.ss = NULL; | |
598 | ||
599 | /* take it off the inarc chains of the ssets reached by its outarcs */ | |
600 | for (i = 0; i < d->ncolors; i++) | |
601 | { | |
602 | p = ss->outs[i]; | |
603 | assert(p != ss); /* not self-referential */ | |
604 | if (p == NULL) | |
605 | continue; /* NOTE CONTINUE */ | |
606 | FDEBUG(("del outarc %d from c%d's in chn\n", i, p - d->ssets)); | |
607 | if (p->ins.ss == ss && p->ins.co == i) | |
608 | p->ins = ss->inchain[i]; | |
609 | else | |
610 | { | |
611 | assert(p->ins.ss != NULL); | |
612 | for (ap = p->ins; ap.ss != NULL && | |
613 | !(ap.ss == ss && ap.co == i); | |
614 | ap = ap.ss->inchain[ap.co]) | |
615 | lastap = ap; | |
616 | assert(ap.ss != NULL); | |
617 | lastap.ss->inchain[lastap.co] = ss->inchain[i]; | |
618 | } | |
619 | ss->outs[i] = NULL; | |
620 | ss->inchain[i].ss = NULL; | |
621 | } | |
622 | ||
623 | /* if ss was a success state, may need to remember location */ | |
624 | if ((ss->flags & POSTSTATE) && ss->lastseen != d->lastpost && | |
625 | (d->lastpost == NULL || d->lastpost < ss->lastseen)) | |
626 | d->lastpost = ss->lastseen; | |
627 | ||
628 | /* likewise for a no-progress state */ | |
629 | if ((ss->flags & NOPROGRESS) && ss->lastseen != d->lastnopr && | |
630 | (d->lastnopr == NULL || d->lastnopr < ss->lastseen)) | |
631 | d->lastnopr = ss->lastseen; | |
632 | ||
633 | return ss; | |
634 | } | |
635 | ||
636 | /* | |
637 | * pickss - pick the next stateset to be used | |
638 | */ | |
639 | static struct sset * | |
640 | pickss(struct vars * v, /* used only for debug flags */ | |
641 | struct dfa * d, | |
642 | chr *cp, | |
643 | chr *start) | |
644 | { | |
645 | int i; | |
646 | struct sset *ss; | |
647 | struct sset *end; | |
648 | chr *ancient; | |
649 | ||
650 | /* shortcut for cases where cache isn't full */ | |
651 | if (d->nssused < d->nssets) | |
652 | { | |
653 | i = d->nssused; | |
654 | d->nssused++; | |
655 | ss = &d->ssets[i]; | |
656 | FDEBUG(("new c%d\n", i)); | |
657 | /* set up innards */ | |
658 | ss->states = &d->statesarea[i * d->wordsper]; | |
659 | ss->flags = 0; | |
660 | ss->ins.ss = NULL; | |
661 | ss->ins.co = WHITE; /* give it some value */ | |
662 | ss->outs = &d->outsarea[i * d->ncolors]; | |
663 | ss->inchain = &d->incarea[i * d->ncolors]; | |
664 | for (i = 0; i < d->ncolors; i++) | |
665 | { | |
666 | ss->outs[i] = NULL; | |
667 | ss->inchain[i].ss = NULL; | |
668 | } | |
669 | return ss; | |
670 | } | |
671 | ||
672 | /* look for oldest, or old enough anyway */ | |
673 | if (cp - start > d->nssets * 2 / 3) /* oldest 33% are expendable */ | |
674 | ancient = cp - d->nssets * 2 / 3; | |
675 | else | |
676 | ancient = start; | |
677 | for (ss = d->search, end = &d->ssets[d->nssets]; ss < end; ss++) | |
678 | if ((ss->lastseen == NULL || ss->lastseen < ancient) && | |
679 | !(ss->flags & LOCKED)) | |
680 | { | |
681 | d->search = ss + 1; | |
682 | FDEBUG(("replacing c%d\n", ss - d->ssets)); | |
683 | return ss; | |
684 | } | |
685 | for (ss = d->ssets, end = d->search; ss < end; ss++) | |
686 | if ((ss->lastseen == NULL || ss->lastseen < ancient) && | |
687 | !(ss->flags & LOCKED)) | |
688 | { | |
689 | d->search = ss + 1; | |
690 | FDEBUG(("replacing c%d\n", ss - d->ssets)); | |
691 | return ss; | |
692 | } | |
693 | ||
694 | /* nobody's old enough?!? -- something's really wrong */ | |
695 | FDEBUG(("can't find victim to replace!\n")); | |
696 | assert(NOTREACHED); | |
697 | ERR(REG_ASSERT); | |
698 | return d->ssets; | |
699 | } |