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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 71 - (hide annotations) (download)
Sat Nov 5 11:07:06 2016 UTC (7 years, 3 months ago) by dashley
File MIME type: text/plain
File size: 17860 byte(s)
Set EOL properties appropriately to facilitate simultaneous Linux and Windows development.
1 dashley 71 /* $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:eol-style native
svn:keywords Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25