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

Contents of /projs/trunk/shared_source/c_tcl_base_7_5_w_mods/rege_dfa.c

Parent Directory Parent Directory | Revision Log Revision Log


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

Properties

Name Value
svn:keywords Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25