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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25