/[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 42 - (show annotations) (download)
Fri Oct 14 01:50:00 2016 UTC (8 years ago) by dashley
Original Path: projs/trunk/shared_source/tcl_base/rege_dfa.c
File MIME type: text/plain
File size: 18866 byte(s)
Move shared source code to commonize.
1 /* $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