git.saurik.com Git - wxWidgets.git/blob

1 /*

2 * DFA routines

3 * This file is #included by regexec.c.

4 *

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 */

33 /*

34 - longest - longest-preferred matching engine

35 ^ static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *);

36 */

37 static chr * /* endpoint, or NULL */

 longest(v, d, start, stop, hitstopp)

39 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;

         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;

         struct colormap *cm = d->cm;

54 /* initialize */

         css = initialize(v, d, start);

56 cp = start;

57 if (hitstopp != NULL)

58 *hitstopp = 0;

60 /* startup */

         FDEBUG(("+++ startup +++\n"));

         if (cp == v->start) {

                 co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];

                 FDEBUG(("color %ld\n", (long)co));

65 } else {

                 co = GETCOLOR(cm, *(cp - 1));

                 FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));

68 }

         css = miss(v, d, css, co, cp, start);

70 if (css == NULL)

71 return NULL;

72 css->lastseen = cp;

74 /* main loop */

         if (v->eflags&REG_FTRACE)

76 while (cp < realstop) {

                         FDEBUG(("+++ at c%d +++\n", css - d->ssets));

                         co = GETCOLOR(cm, *cp);

                         FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));

80 ss = css->outs[co];

81 if (ss == NULL) {

                                 ss = miss(v, d, css, co, cp+1, start);

83 if (ss == NULL)

84 break; /* NOTE BREAK OUT */

85 }

86 cp++;

87 ss->lastseen = cp;

88 css = ss;

89 }

90 else

91 while (cp < realstop) {

                         co = GETCOLOR(cm, *cp);

93 ss = css->outs[co];

94 if (ss == NULL) {

                                 ss = miss(v, d, css, co, cp+1, start);

96 if (ss == NULL)

97 break; /* NOTE BREAK OUT */

98 }

99 cp++;

100 ss->lastseen = cp;

101 css = ss;

102 }

103

104 /* shutdown */

         FDEBUG(("+++ shutdown at c%d +++\n", css - d->ssets));

         if (cp == v->stop && stop == v->stop) {

107 if (hitstopp != NULL)

108 *hitstopp = 1;

                 co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];

                 FDEBUG(("color %ld\n", (long)co));

                 ss = miss(v, d, css, co, cp, start);

112 /* special case: match ended at eol? */

                 if (ss != NULL && (ss->flags&POSTSTATE))

114 return cp;

115 else if (ss != NULL)

116 ss->lastseen = cp; /* to be tidy */

117 }

118

119 /* find last match, if any */

120 post = d->lastpost;

         for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)

                 if ((ss->flags&POSTSTATE) && post != ss->lastseen &&

                                         (post == NULL || post < ss->lastseen))

124 post = ss->lastseen;

         if (post != NULL)               /* found one */

126 return post - 1;

127

128 return NULL;

129 }

130

131 /*

132 - shortest - shortest-preferred matching engine

133 ^ static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *,

134 ^ chr **, int *);

135 */

136 static chr * /* endpoint, or NULL */

 shortest(v, d, start, min, max, coldp, hitstopp)

138 struct vars *v;

139 struct dfa *d;

140 chr *start; /* where the match should start */

141 chr *min; /* match must end at or after here */

142 chr *max; /* match must end at or before here */

143 chr **coldp; /* store coldstart pointer here, if nonNULL */

144 int *hitstopp; /* record whether hit v->stop, if non-NULL */

145 {

146 chr *cp;

         chr *realmin = (min == v->stop) ? min : min + 1;

         chr *realmax = (max == v->stop) ? max : max + 1;

149 color co;

150 struct sset *css;

151 struct sset *ss;

         struct colormap *cm = d->cm;

153

154 /* initialize */

         css = initialize(v, d, start);

156 cp = start;

157 if (hitstopp != NULL)

158 *hitstopp = 0;

159

160 /* startup */

         FDEBUG(("--- startup ---\n"));

         if (cp == v->start) {

                 co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];

                 FDEBUG(("color %ld\n", (long)co));

165 } else {

                 co = GETCOLOR(cm, *(cp - 1));

                 FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));

168 }

         css = miss(v, d, css, co, cp, start);

170 if (css == NULL)

171 return NULL;

172 css->lastseen = cp;

173 ss = css;

174

175 /* main loop */

         if (v->eflags&REG_FTRACE)

177 while (cp < realmax) {

                         FDEBUG(("--- at c%d ---\n", css - d->ssets));

                         co = GETCOLOR(cm, *cp);

                         FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));

181 ss = css->outs[co];

182 if (ss == NULL) {

                                 ss = miss(v, d, css, co, cp+1, start);

184 if (ss == NULL)

185 break; /* NOTE BREAK OUT */

186 }

187 cp++;

188 ss->lastseen = cp;

189 css = ss;

                         if ((ss->flags&POSTSTATE) && cp >= realmin)

191 break; /* NOTE BREAK OUT */

192 }

193 else

194 while (cp < realmax) {

                         co = GETCOLOR(cm, *cp);

196 ss = css->outs[co];

197 if (ss == NULL) {

                                 ss = miss(v, d, css, co, cp+1, start);

199 if (ss == NULL)

200 break; /* NOTE BREAK OUT */

201 }

202 cp++;

203 ss->lastseen = cp;

204 css = ss;

                         if ((ss->flags&POSTSTATE) && cp >= realmin)

206 break; /* NOTE BREAK OUT */

207 }

208

209 if (ss == NULL)

210 return NULL;

211

         if (coldp != NULL)      /* report last no-progress state set, if any */

                 *coldp = lastcold(v, d);

214

         if ((ss->flags&POSTSTATE) && cp > min) {

216 assert(cp >= realmin);

217 cp--;

         } else if (cp == v->stop && max == v->stop) {

                 co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];

                 FDEBUG(("color %ld\n", (long)co));

                 ss = miss(v, d, css, co, cp, start);

222 /* match might have ended at eol */

                 if ((ss == NULL || !(ss->flags&POSTSTATE)) && hitstopp != NULL)

224 *hitstopp = 1;

225 }

226

         if (ss == NULL || !(ss->flags&POSTSTATE))

228 return NULL;

229

230 return cp;

231 }

232

233 /*

234 - lastcold - determine last point at which no progress had been made

235 ^ static chr *lastcold(struct vars *, struct dfa *);

236 */

237 static chr * /* endpoint, or NULL */

238 lastcold(v, d)

239 struct vars *v;

240 struct dfa *d;

241 {

242 struct sset *ss;

243 chr *nopr;

244 int i;

245

246 nopr = d->lastnopr;

247 if (nopr == NULL)

248 nopr = v->start;

         for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--)

                 if ((ss->flags&NOPROGRESS) && nopr < ss->lastseen)

251 nopr = ss->lastseen;

252 return nopr;

253 }

254

255 /*

256 - newdfa - set up a fresh DFA

257 ^ static struct dfa *newdfa(struct vars *, struct cnfa *,

258 ^ struct colormap *, struct smalldfa *);

259 */

260

261 /* FIXME Required for CW 8 on Mac since it's not in limits.h */

262 #ifndef __CHAR_BIT__

263 #define __CHAR_BIT__ 8

264 #endif

265

266 static struct dfa *

 newdfa(v, cnfa, cm, small)

268 struct vars *v;

269 struct cnfa *cnfa;

270 struct colormap *cm;

271 struct smalldfa *small; /* preallocated space, may be NULL */

272 {

273 struct dfa *d;

         size_t nss = cnfa->nstates * 2;

         int wordsper = (cnfa->nstates + UBITS - 1) / UBITS;

276 struct smalldfa *smallwas = small;

277

         assert(cnfa != NULL && cnfa->nstates != 0);

279

         if (nss <= FEWSTATES && cnfa->ncolors <= FEWCOLORS) {

                 assert(wordsper == 1);

282 if (small == NULL) {

                         small = (struct smalldfa *)MALLOC(

284 sizeof(struct smalldfa));

285 if (small == NULL) {

286 ERR(REG_ESPACE);

287 return NULL;

288 }

289 }

290 d = &small->dfa;

291 d->ssets = small->ssets;

292 d->statesarea = small->statesarea;

                 d->work = &d->statesarea[nss];

294 d->outsarea = small->outsarea;

295 d->incarea = small->incarea;

296 d->cptsmalloced = 0;

                 d->mallocarea = (smallwas == NULL) ? (char *)small : NULL;

298 } else {

                 d = (struct dfa *)MALLOC(sizeof(struct dfa));

300 if (d == NULL) {

301 ERR(REG_ESPACE);

302 return NULL;

303 }

                 d->ssets = (struct sset *)MALLOC(nss * sizeof(struct sset));

                 d->statesarea = (unsigned *)MALLOC((nss+WORK) * wordsper *

306 sizeof(unsigned));

                 d->work = &d->statesarea[nss * wordsper];

                 d->outsarea = (struct sset **)MALLOC(nss * cnfa->ncolors *

309 sizeof(struct sset *));

                 d->incarea = (struct arcp *)MALLOC(nss * cnfa->ncolors *

311 sizeof(struct arcp));

312 d->cptsmalloced = 1;

                 d->mallocarea = (char *)d;

                 if (d->ssets == NULL || d->statesarea == NULL ||

                                 d->outsarea == NULL || d->incarea == NULL) {

316 freedfa(d);

317 ERR(REG_ESPACE);

318 return NULL;

319 }

320 }

321

         d->nssets = (v->eflags&REG_SMALL) ? 7 : nss;

323 d->nssused = 0;

324 d->nstates = cnfa->nstates;

325 d->ncolors = cnfa->ncolors;

326 d->wordsper = wordsper;

327 d->cnfa = cnfa;

328 d->cm = cm;

329 d->lastpost = NULL;

330 d->lastnopr = NULL;

331 d->search = d->ssets;

332

333 /* initialization of sset fields is done as needed */

334

335 return d;

336 }

337

338 /*

339 - freedfa - free a DFA

340 ^ static VOID freedfa(struct dfa *);

341 */

342 static VOID

343 freedfa(d)

344 struct dfa *d;

345 {

346 if (d->cptsmalloced) {

                 if (d->ssets != NULL)

348 FREE(d->ssets);

                 if (d->statesarea != NULL)

350 FREE(d->statesarea);

                 if (d->outsarea != NULL)

352 FREE(d->outsarea);

                 if (d->incarea != NULL)

354 FREE(d->incarea);

355 }

356

         if (d->mallocarea != NULL)

358 FREE(d->mallocarea);

359 }

360

361 /*

362 - hash - construct a hash code for a bitvector

363 * There are probably better ways, but they're more expensive.

364 ^ static unsigned hash(unsigned *, int);

365 */

366 static unsigned

367 hash(uv, n)

368 unsigned *uv;

369 int n;

370 {

371 int i;

372 unsigned h;

373

374 h = 0;

         for (i = 0; i < n; i++)

376 h ^= uv[i];

377 return h;

378 }

379

380 /*

381 - initialize - hand-craft a cache entry for startup, otherwise get ready

382 ^ static struct sset *initialize(struct vars *, struct dfa *, chr *);

383 */

384 static struct sset *

 initialize(v, d, start)

386 struct vars *v; /* used only for debug flags */

387 struct dfa *d;

388 chr *start;

389 {

390 struct sset *ss;

391 int i;

392

393 /* is previous one still there? */

         if (d->nssused > 0 && (d->ssets[0].flags&STARTER))

                 ss = &d->ssets[0];

396 else { /* no, must (re)build it */

                 ss = getvacant(v, d, start, start);

                 for (i = 0; i < d->wordsper; i++)

                         ss->states[i] = 0;

                 BSET(ss->states, d->cnfa->pre);

                 ss->hash = HASH(ss->states, d->wordsper);

                 assert(d->cnfa->pre != d->cnfa->post);

                 ss->flags = STARTER|LOCKED|NOPROGRESS;

404 /* lastseen dealt with below */

405 }

406

         for (i = 0; i < d->nssused; i++)

                 d->ssets[i].lastseen = NULL;

409 ss->lastseen = start; /* maybe untrue, but harmless */

410 d->lastpost = NULL;

411 d->lastnopr = NULL;

412 return ss;

413 }

414

415 /*

416 - miss - handle a cache miss

417 ^ static struct sset *miss(struct vars *, struct dfa *, struct sset *,

418 ^ pcolor, chr *, chr *);

419 */

420 static struct sset * /* NULL if goes to empty set */

 miss(v, d, css, co, cp, start)

422 struct vars *v; /* used only for debug flags */

423 struct dfa *d;

424 struct sset *css;

425 pcolor co;

426 chr *cp; /* next chr */

427 chr *start; /* where the attempt got started */

428 {

         struct cnfa *cnfa = d->cnfa;

430 int i;

431 unsigned h;

432 struct carc *ca;

433 struct sset *p;

434 int ispost;

435 int noprogress;

436 int gotstate;

437 int dolacons;

438 int sawlacons;

439

440 /* for convenience, we can be called even if it might not be a miss */

         if (css->outs[co] != NULL) {

                 FDEBUG(("hit\n"));

443 return css->outs[co];

444 }

         FDEBUG(("miss\n"));

446

447 /* first, what set of states would we end up in? */

         for (i = 0; i < d->wordsper; i++)

                 d->work[i] = 0;

450 ispost = 0;

451 noprogress = 1;

452 gotstate = 0;

         for (i = 0; i < d->nstates; i++)

                 if (ISBSET(css->states, i))

                         for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++)

                                 if (ca->co == co) {

                                         BSET(d->work, ca->to);

458 gotstate = 1;

                                         if (ca->to == cnfa->post)

460 ispost = 1;

                                         if (!cnfa->states[ca->to]->co)

462 noprogress = 0;

                                         FDEBUG(("%d -> %d\n", i, ca->to));

464 }

         dolacons = (gotstate) ? (cnfa->flags&HASLACONS) : 0;

466 sawlacons = 0;

467 while (dolacons) { /* transitive closure */

468 dolacons = 0;

                 for (i = 0; i < d->nstates; i++)

                         if (ISBSET(d->work, i))

                                 for (ca = cnfa->states[i]+1; ca->co != COLORLESS;

472 ca++) {

                                         if (ca->co <= cnfa->ncolors)

474 continue; /* NOTE CONTINUE */

475 sawlacons = 1;

                                         if (ISBSET(d->work, ca->to))

477 continue; /* NOTE CONTINUE */

                                         if (!lacon(v, cnfa, cp, ca->co))

479 continue; /* NOTE CONTINUE */

                                         BSET(d->work, ca->to);

481 dolacons = 1;

                                         if (ca->to == cnfa->post)

483 ispost = 1;

                                         if (!cnfa->states[ca->to]->co)

485 noprogress = 0;

                                         FDEBUG(("%d :> %d\n", i, ca->to));

487 }

488 }

489 if (!gotstate)

490 return NULL;

         h = HASH(d->work, d->wordsper);

492

493 /* next, is that in the cache? */

         for (p = d->ssets, i = d->nssused; i > 0; p++, i--)

                 if (HIT(h, d->work, p, d->wordsper)) {

                         FDEBUG(("cached c%d\n", p - d->ssets));

497 break; /* NOTE BREAK OUT */

498 }

         if (i == 0) {           /* nope, need a new cache entry */

                 p = getvacant(v, d, cp, start);

501 assert(p != css);

                 for (i = 0; i < d->wordsper; i++)

                         p->states[i] = d->work[i];

504 p->hash = h;

                 p->flags = (ispost) ? POSTSTATE : 0;

506 if (noprogress)

507 p->flags |= NOPROGRESS;

508 /* lastseen to be dealt with by caller */

509 }

510

511 if (!sawlacons) { /* lookahead conds. always cache miss */

                 FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, p - d->ssets));

513 css->outs[co] = p;

                 css->inchain[co] = p->ins;

515 p->ins.ss = css;

                 p->ins.co = (color)co;

517 }

518 return p;

519 }

520

521 /*

522 - lacon - lookahead-constraint checker for miss()

523 ^ static int lacon(struct vars *, struct cnfa *, chr *, pcolor);

524 */

525 static int /* predicate: constraint satisfied? */

 lacon(v, pcnfa, cp, co)

527 struct vars *v;

528 struct cnfa *pcnfa; /* parent cnfa */

529 chr *cp;

530 pcolor co; /* "color" of the lookahead constraint */

531 {

532 int n;

533 struct subre *sub;

534 struct dfa *d;

535 struct smalldfa sd;

536 chr *end;

537

538 n = co - pcnfa->ncolors;

         assert(n < v->g->nlacons && v->g->lacons != NULL);

         FDEBUG(("=== testing lacon %d\n", n));

         sub = &v->g->lacons[n];

         d = newdfa(v, &sub->cnfa, &v->g->cmap, &sd);

543 if (d == NULL) {

544 ERR(REG_ESPACE);

545 return 0;

546 }

         end = longest(v, d, cp, v->stop, (int *)NULL);

548 freedfa(d);

         FDEBUG(("=== lacon %d match %d\n", n, (end != NULL)));

         return (sub->subno) ? (end != NULL) : (end == NULL);

551 }

552

553 /*

554 - getvacant - get a vacant state set

555 * This routine clears out the inarcs and outarcs, but does not otherwise

556 * clear the innards of the state set -- that's up to the caller.

557 ^ static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);

558 */

559 static struct sset *

 getvacant(v, d, cp, start)

561 struct vars *v; /* used only for debug flags */

562 struct dfa *d;

563 chr *cp;

564 chr *start;

565 {

566 int i;

567 struct sset *ss;

568 struct sset *p;

569 struct arcp ap;

570 struct arcp lastap;

571 color co;

     lastap.ss = NULL; lastap.co = 0; // WX: suppress dummy gcc warnings

         ss = pickss(v, d, cp, start);

         assert(!(ss->flags&LOCKED));

575

576 /* clear out its inarcs, including self-referential ones */

577 ap = ss->ins;

         while ((p = ap.ss) != NULL) {

579 co = ap.co;

                 FDEBUG(("zapping c%d's %ld outarc\n", p - d->ssets, (long)co));

581 p->outs[co] = NULL;

582 ap = p->inchain[co];

                 p->inchain[co].ss = NULL;       /* paranoia */

584 }

585 ss->ins.ss = NULL;

586

587 /* take it off the inarc chains of the ssets reached by its outarcs */

         for (i = 0; i < d->ncolors; i++) {

589 p = ss->outs[i];

                 assert(p != ss);                /* not self-referential */

591 if (p == NULL)

592 continue; /* NOTE CONTINUE */

                 FDEBUG(("del outarc %d from c%d's in chn\n", i, p - d->ssets));

                 if (p->ins.ss == ss && p->ins.co == i)

                         p->ins = ss->inchain[i];

596 else {

                         assert(p->ins.ss != NULL);

                         for (ap = p->ins; ap.ss != NULL &&

                                                 !(ap.ss == ss && ap.co == i);

                                                 ap = ap.ss->inchain[ap.co])

601 lastap = ap;

                         assert(ap.ss != NULL);

                         lastap.ss->inchain[lastap.co] = ss->inchain[i];

604 }

605 ss->outs[i] = NULL;

                 ss->inchain[i].ss = NULL;

607 }

608

609 /* if ss was a success state, may need to remember location */

         if ((ss->flags&POSTSTATE) && ss->lastseen != d->lastpost &&

                         (d->lastpost == NULL || d->lastpost < ss->lastseen))

612 d->lastpost = ss->lastseen;

613

614 /* likewise for a no-progress state */

         if ((ss->flags&NOPROGRESS) && ss->lastseen != d->lastnopr &&

                         (d->lastnopr == NULL || d->lastnopr < ss->lastseen))

617 d->lastnopr = ss->lastseen;

618

619 return ss;

620 }

621

622 /*

623 - pickss - pick the next stateset to be used

624 ^ static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);

625 */

626 static struct sset *

 pickss(v, d, cp, start)

628 struct vars *v; /* used only for debug flags */

629 struct dfa *d;

630 chr *cp;

631 chr *start;

632 {

633 int i;

634 struct sset *ss;

635 struct sset *end;

636 chr *ancient;

637

638 /* shortcut for cases where cache isn't full */

         if (d->nssused < d->nssets) {

640 i = d->nssused;

641 d->nssused++;

642 ss = &d->ssets[i];

                 FDEBUG(("new c%d\n", i));

644 /* set up innards */

                 ss->states = &d->statesarea[i * d->wordsper];

646 ss->flags = 0;

647 ss->ins.ss = NULL;

                 ss->ins.co = WHITE;             /* give it some value */

                 ss->outs = &d->outsarea[i * d->ncolors];

                 ss->inchain = &d->incarea[i * d->ncolors];

                 for (i = 0; i < d->ncolors; i++) {

652 ss->outs[i] = NULL;

                         ss->inchain[i].ss = NULL;

654 }

655 return ss;

656 }

657

658 /* look for oldest, or old enough anyway */

         if (cp - start > d->nssets*2/3)         /* oldest 33% are expendable */

                 ancient = cp - d->nssets*2/3;

661 else

662 ancient = start;

         for (ss = d->search, end = &d->ssets[d->nssets]; ss < end; ss++)

                 if ((ss->lastseen == NULL || ss->lastseen < ancient) &&

665 !(ss->flags&LOCKED)) {

                         d->search = ss + 1;

                         FDEBUG(("replacing c%d\n", ss - d->ssets));

668 return ss;

669 }

         for (ss = d->ssets, end = d->search; ss < end; ss++)

                 if ((ss->lastseen == NULL || ss->lastseen < ancient) &&

672 !(ss->flags&LOCKED)) {

                         d->search = ss + 1;

                         FDEBUG(("replacing c%d\n", ss - d->ssets));

675 return ss;

676 }

677

678 /* nobody's old enough?!? -- something's really wrong */

         FDEBUG(("can't find victim to replace!\n"));

680 assert(NOTREACHED);

681 ERR(REG_ASSERT);

682 return d->ssets;

683 }