util/src/TclTk/tcl8.6.12/generic/rege_dfa.c

   1 /*
   2  * DFA routines
   3  * This file is #included by regexec.c.
   4  *
   5  * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
   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  */
  32 \f
  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 */
  38 longest(
  39     struct vars *const v,       /* used only for debug and exec flags */
  40     struct dfa *const d,
  41     chr *const start,           /* where the match should start */
  42     chr *const stop,            /* match must end at or before here */
  43     int *const hitstopp)        /* record whether hit v->stop, if non-NULL */
  44 {
  45     chr *cp;
  46     chr *realstop = (stop == v->stop) ? stop : stop + 1;
  47     color co;
  48     struct sset *css, *ss;
  49     chr *post;
  50     int i;
  51     struct colormap *cm = d->cm;
  52
  53     /*
  54      * Initialize.
  55      */
  56
  57     css = initialize(v, d, start);
  58     cp = start;
  59     if (hitstopp != NULL) {
  60         *hitstopp = 0;
  61     }
  62
  63     /*
  64      * Startup.
  65      */
  66
  67     FDEBUG(("+++ startup +++\n"));
  68     if (cp == v->start) {
  69         co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];
  70         FDEBUG(("color %ld\n", (long)co));
  71     } else {
  72         co = GETCOLOR(cm, *(cp - 1));
  73         FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));
  74     }
  75     css = miss(v, d, css, co, cp, start);
  76     if (css == NULL) {
  77         return NULL;
  78     }
  79     css->lastseen = cp;
  80
  81     /*
  82      * Main loop.
  83      */
  84
  85     if (v->eflags&REG_FTRACE) {
  86         while (cp < realstop) {
  87             FDEBUG(("+++ at c%d +++\n", (int) (css - d->ssets)));
  88             co = GETCOLOR(cm, *cp);
  89             FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
  90             ss = css->outs[co];
  91             if (ss == NULL) {
  92                 ss = miss(v, d, css, co, cp+1, start);
  93                 if (ss == NULL) {
  94                     break;      /* NOTE BREAK OUT */
  95                 }
  96             }
  97             cp++;
  98             ss->lastseen = cp;
  99             css = ss;
 100         }
 101     } else {
 102         while (cp < realstop) {
 103             co = GETCOLOR(cm, *cp);
 104             ss = css->outs[co];
 105             if (ss == NULL) {
 106                 ss = miss(v, d, css, co, cp+1, start);
 107                 if (ss == NULL) {
 108                     break;      /* NOTE BREAK OUT */
 109                 }
 110             }
 111             cp++;
 112             ss->lastseen = cp;
 113             css = ss;
 114         }
 115     }
 116
 117     /*
 118      * Shutdown.
 119      */
 120
 121     FDEBUG(("+++ shutdown at c%d +++\n", (int) (css - d->ssets)));
 122     if (cp == v->stop && stop == v->stop) {
 123         if (hitstopp != NULL) {
 124             *hitstopp = 1;
 125         }
 126         co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];
 127         FDEBUG(("color %ld\n", (long)co));
 128         ss = miss(v, d, css, co, cp, start);
 129
 130         /*
 131          * Special case: match ended at eol?
 132          */
 133
 134         if (ss != NULL && (ss->flags&POSTSTATE)) {
 135             return cp;
 136         } else if (ss != NULL) {
 137             ss->lastseen = cp;  /* to be tidy */
 138         }
 139     }
 140
 141     /*
 142      * Find last match, if any.
 143      */
 144
 145     post = d->lastpost;
 146     for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--) {
 147         if ((ss->flags&POSTSTATE) && (post != ss->lastseen) &&
 148                 (post == NULL || post < ss->lastseen)) {
 149             post = ss->lastseen;
 150         }
 151     }
 152     if (post != NULL) {         /* found one */
 153         return post - 1;
 154     }
 155
 156     return NULL;
 157 }
 158 \f
 159 /*
 160  - shortest - shortest-preferred matching engine
 161  ^ static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *,
 162  ^      chr **, int *);
 163  */
 164 static chr *                    /* endpoint, or NULL */
 165 shortest(
 166     struct vars *const v,
 167     struct dfa *const d,
 168     chr *const start,           /* where the match should start */
 169     chr *const min,             /* match must end at or after here */
 170     chr *const max,             /* match must end at or before here */
 171     chr **const coldp,          /* store coldstart pointer here, if nonNULL */
 172     int *const hitstopp)        /* record whether hit v->stop, if non-NULL */
 173 {
 174     chr *cp;
 175     chr *realmin = (min == v->stop) ? min : min + 1;
 176     chr *realmax = (max == v->stop) ? max : max + 1;
 177     color co;
 178     struct sset *css, *ss;
 179     struct colormap *cm = d->cm;
 180
 181     /*
 182      * Initialize.
 183      */
 184
 185     css = initialize(v, d, start);
 186     cp = start;
 187     if (hitstopp != NULL) {
 188         *hitstopp = 0;
 189     }
 190
 191     /*
 192      * Startup.
 193      */
 194
 195     FDEBUG(("--- startup ---\n"));
 196     if (cp == v->start) {
 197         co = d->cnfa->bos[(v->eflags&REG_NOTBOL) ? 0 : 1];
 198         FDEBUG(("color %ld\n", (long)co));
 199     } else {
 200         co = GETCOLOR(cm, *(cp - 1));
 201         FDEBUG(("char %c, color %ld\n", (char)*(cp-1), (long)co));
 202     }
 203     css = miss(v, d, css, co, cp, start);
 204     if (css == NULL) {
 205         return NULL;
 206     }
 207     css->lastseen = cp;
 208     ss = css;
 209
 210     /*
 211      * Main loop.
 212      */
 213
 214     if (v->eflags&REG_FTRACE) {
 215         while (cp < realmax) {
 216             FDEBUG(("--- at c%d ---\n", (int) (css - d->ssets)));
 217             co = GETCOLOR(cm, *cp);
 218             FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co));
 219             ss = css->outs[co];
 220             if (ss == NULL) {
 221                 ss = miss(v, d, css, co, cp+1, start);
 222                 if (ss == NULL) {
 223                     break;      /* NOTE BREAK OUT */
 224                 }
 225             }
 226             cp++;
 227             ss->lastseen = cp;
 228             css = ss;
 229             if ((ss->flags&POSTSTATE) && cp >= realmin) {
 230                 break;          /* NOTE BREAK OUT */
 231             }
 232         }
 233     } else {
 234         while (cp < realmax) {
 235             co = GETCOLOR(cm, *cp);
 236             ss = css->outs[co];
 237             if (ss == NULL) {
 238                 ss = miss(v, d, css, co, cp+1, start);
 239                 if (ss == NULL) {
 240                     break;      /* NOTE BREAK OUT */
 241                 }
 242             }
 243             cp++;
 244             ss->lastseen = cp;
 245             css = ss;
 246             if ((ss->flags&POSTSTATE) && cp >= realmin) {
 247                 break;          /* NOTE BREAK OUT */
 248             }
 249         }
 250     }
 251
 252     if (ss == NULL) {
 253         return NULL;
 254     }
 255
 256     if (coldp != NULL) {        /* report last no-progress state set, if any */
 257         *coldp = lastCold(v, d);
 258     }
 259
 260     if ((ss->flags&POSTSTATE) && cp > min) {
 261         assert(cp >= realmin);
 262         cp--;
 263     } else if (cp == v->stop && max == v->stop) {
 264         co = d->cnfa->eos[(v->eflags&REG_NOTEOL) ? 0 : 1];
 265         FDEBUG(("color %ld\n", (long)co));
 266         ss = miss(v, d, css, co, cp, start);
 267
 268         /*
 269          * Match might have ended at eol.
 270          */
 271
 272         if ((ss == NULL || !(ss->flags&POSTSTATE)) && hitstopp != NULL) {
 273             *hitstopp = 1;
 274         }
 275     }
 276
 277     if (ss == NULL || !(ss->flags&POSTSTATE)) {
 278         return NULL;
 279     }
 280
 281     return cp;
 282 }
 283 \f
 284 /*
 285  - lastCold - determine last point at which no progress had been made
 286  ^ static chr *lastCold(struct vars *, struct dfa *);
 287  */
 288 static chr *                    /* endpoint, or NULL */
 289 lastCold(
 290     struct vars *const v,
 291     struct dfa *const d)
 292 {
 293     struct sset *ss;
 294     chr *nopr = d->lastnopr;
 295     int i;
 296
 297     if (nopr == NULL) {
 298         nopr = v->start;
 299     }
 300     for (ss = d->ssets, i = d->nssused; i > 0; ss++, i--) {
 301         if ((ss->flags&NOPROGRESS) && nopr < ss->lastseen) {
 302             nopr = ss->lastseen;
 303         }
 304     }
 305     return nopr;
 306 }
 307 \f
 308 /*
 309  - newDFA - set up a fresh DFA
 310  ^ static struct dfa *newDFA(struct vars *, struct cnfa *,
 311  ^      struct colormap *, struct smalldfa *);
 312  */
 313 static struct dfa *
 314 newDFA(
 315     struct vars *const v,
 316     struct cnfa *const cnfa,
 317     struct colormap *const cm,
 318     struct smalldfa *sml)       /* preallocated space, may be NULL */
 319 {
 320     struct dfa *d;
 321     size_t nss = cnfa->nstates * 2;
 322     int wordsper = (cnfa->nstates + UBITS - 1) / UBITS;
 323     struct smalldfa *smallwas = sml;
 324
 325     assert(cnfa != NULL && cnfa->nstates != 0);
 326
 327     if (nss <= FEWSTATES && cnfa->ncolors <= FEWCOLORS) {
 328         assert(wordsper == 1);
 329         if (sml == NULL) {
 330             sml = (struct smalldfa *) MALLOC(sizeof(struct smalldfa));
 331             if (sml == NULL) {
 332                 ERR(REG_ESPACE);
 333                 return NULL;
 334             }
 335         }
 336         d = &sml->dfa;
 337         d->ssets = sml->ssets;
 338         d->statesarea = sml->statesarea;
 339         d->work = &d->statesarea[nss];
 340         d->outsarea = sml->outsarea;
 341         d->incarea = sml->incarea;
 342         d->cptsmalloced = 0;
 343         d->mallocarea = (smallwas == NULL) ? (char *)sml : NULL;
 344     } else {
 345         d = (struct dfa *) MALLOC(sizeof(struct dfa));
 346         if (d == NULL) {
 347             ERR(REG_ESPACE);
 348             return NULL;
 349         }
 350         d->ssets = (struct sset *) MALLOC(nss * sizeof(struct sset));
 351         d->statesarea = (unsigned *)
 352                 MALLOC((nss+WORK) * wordsper * sizeof(unsigned));
 353         d->work = &d->statesarea[nss * wordsper];
 354         d->outsarea = (struct sset **)
 355                 MALLOC(nss * cnfa->ncolors * sizeof(struct sset *));
 356         d->incarea = (struct arcp *)
 357                 MALLOC(nss * cnfa->ncolors * sizeof(struct arcp));
 358         d->cptsmalloced = 1;
 359         d->mallocarea = (char *)d;
 360         if (d->ssets == NULL || d->statesarea == NULL ||
 361                 d->outsarea == NULL || d->incarea == NULL) {
 362             freeDFA(d);
 363             ERR(REG_ESPACE);
 364             return NULL;
 365         }
 366     }
 367
 368     d->nssets = (v->eflags&REG_SMALL) ? 7 : nss;
 369     d->nssused = 0;
 370     d->nstates = cnfa->nstates;
 371     d->ncolors = cnfa->ncolors;
 372     d->wordsper = wordsper;
 373     d->cnfa = cnfa;
 374     d->cm = cm;
 375     d->lastpost = NULL;
 376     d->lastnopr = NULL;
 377     d->search = d->ssets;
 378
 379     /*
 380      * Initialization of sset fields is done as needed.
 381      */
 382
 383     return d;
 384 }
 385 \f
 386 /*
 387  - freeDFA - free a DFA
 388  ^ static void freeDFA(struct dfa *);
 389  */
 390 static void
 391 freeDFA(
 392     struct dfa *const d)
 393 {
 394     if (d->cptsmalloced) {
 395         if (d->ssets != NULL) {
 396             FREE(d->ssets);
 397         }
 398         if (d->statesarea != NULL) {
 399             FREE(d->statesarea);
 400         }
 401         if (d->outsarea != NULL) {
 402             FREE(d->outsarea);
 403         }
 404         if (d->incarea != NULL) {
 405             FREE(d->incarea);
 406         }
 407     }
 408
 409     if (d->mallocarea != NULL) {
 410         FREE(d->mallocarea);
 411     }
 412 }
 413 \f
 414 /*
 415  - hash - construct a hash code for a bitvector
 416  * There are probably better ways, but they're more expensive.
 417  ^ static unsigned hash(unsigned *, int);
 418  */
 419 static unsigned
 420 hash(
 421     unsigned *const uv,
 422     const int n)
 423 {
 424     int i;
 425     unsigned h;
 426
 427     h = 0;
 428     for (i = 0; i < n; i++) {
 429         h ^= uv[i];
 430     }
 431     return h;
 432 }
 433 \f
 434 /*
 435  - initialize - hand-craft a cache entry for startup, otherwise get ready
 436  ^ static struct sset *initialize(struct vars *, struct dfa *, chr *);
 437  */
 438 static struct sset *
 439 initialize(
 440     struct vars *const v,       /* used only for debug flags */
 441     struct dfa *const d,
 442     chr *const start)
 443 {
 444     struct sset *ss;
 445     int i;
 446
 447     /*
 448      * Is previous one still there?
 449      */
 450
 451     if (d->nssused > 0 && (d->ssets[0].flags&STARTER)) {
 452         ss = &d->ssets[0];
 453     } else {                    /* no, must (re)build it */
 454         ss = getVacantSS(v, d, start, start);
 455         for (i = 0; i < d->wordsper; i++) {
 456             ss->states[i] = 0;
 457         }
 458         BSET(ss->states, d->cnfa->pre);
 459         ss->hash = HASH(ss->states, d->wordsper);
 460         assert(d->cnfa->pre != d->cnfa->post);
 461         ss->flags = STARTER|LOCKED|NOPROGRESS;
 462
 463         /*
 464          * lastseen dealt with below
 465          */
 466     }
 467
 468     for (i = 0; i < d->nssused; i++) {
 469         d->ssets[i].lastseen = NULL;
 470     }
 471     ss->lastseen = start;       /* maybe untrue, but harmless */
 472     d->lastpost = NULL;
 473     d->lastnopr = NULL;
 474     return ss;
 475 }
 476 \f
 477 /*
 478  - miss - handle a cache miss
 479  ^ static struct sset *miss(struct vars *, struct dfa *, struct sset *,
 480  ^      pcolor, chr *, chr *);
 481  */
 482 static struct sset *            /* NULL if goes to empty set */
 483 miss(
 484     struct vars *const v,       /* used only for debug flags */
 485     struct dfa *const d,
 486     struct sset *const css,
 487     const pcolor co,
 488     chr *const cp,              /* next chr */
 489     chr *const start)           /* where the attempt got started */
 490 {
 491     struct cnfa *cnfa = d->cnfa;
 492     unsigned h;
 493     struct carc *ca;
 494     struct sset *p;
 495     int i, isPost, noProgress, gotState, doLAConstraints, sawLAConstraints;
 496
 497     /*
 498      * For convenience, we can be called even if it might not be a miss.
 499      */
 500
 501     if (css->outs[co] != NULL) {
 502         FDEBUG(("hit\n"));
 503         return css->outs[co];
 504     }
 505     FDEBUG(("miss\n"));
 506
 507     /*
 508      * First, what set of states would we end up in?
 509      */
 510
 511     for (i = 0; i < d->wordsper; i++) {
 512         d->work[i] = 0;
 513     }
 514     isPost = 0;
 515     noProgress = 1;
 516     gotState = 0;
 517     for (i = 0; i < d->nstates; i++) {
 518         if (ISBSET(css->states, i)) {
 519             for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) {
 520                 if (ca->co == co) {
 521                     BSET(d->work, ca->to);
 522                     gotState = 1;
 523                     if (ca->to == cnfa->post) {
 524                         isPost = 1;
 525                     }
 526                     if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS)) {
 527                         noProgress = 0;
 528                     }
 529                     FDEBUG(("%d -> %d\n", i, ca->to));
 530                 }
 531             }
 532         }
 533     }
 534     doLAConstraints = (gotState ? (cnfa->flags&HASLACONS) : 0);
 535     sawLAConstraints = 0;
 536     while (doLAConstraints) {           /* transitive closure */
 537         doLAConstraints = 0;
 538         for (i = 0; i < d->nstates; i++) {
 539             if (ISBSET(d->work, i)) {
 540                 for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) {
 541                     if (ca->co < cnfa->ncolors) {
 542                         continue;       /* NOTE CONTINUE */
 543                     }
 544                     sawLAConstraints = 1;
 545                     if (ISBSET(d->work, ca->to)) {
 546                         continue;       /* NOTE CONTINUE */
 547                     }
 548                     if (!checkLAConstraint(v, cnfa, cp, ca->co)) {
 549                         continue;       /* NOTE CONTINUE */
 550                     }
 551                     BSET(d->work, ca->to);
 552                     doLAConstraints = 1;
 553                     if (ca->to == cnfa->post) {
 554                         isPost = 1;
 555                     }
 556                     if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS)) {
 557                         noProgress = 0;
 558                     }
 559                     FDEBUG(("%d :> %d\n", i, ca->to));
 560                 }
 561             }
 562         }
 563     }
 564     if (!gotState) {
 565         return NULL;
 566     }
 567     h = HASH(d->work, d->wordsper);
 568
 569     /*
 570      * Next, is that in the cache?
 571      */
 572
 573     for (p = d->ssets, i = d->nssused; i > 0; p++, i--) {
 574          if (HIT(h, d->work, p, d->wordsper)) {
 575              FDEBUG(("cached c%d\n", (int) (p - d->ssets)));
 576              break;                     /* NOTE BREAK OUT */
 577          }
 578     }
 579     if (i == 0) {               /* nope, need a new cache entry */
 580         p = getVacantSS(v, d, cp, start);
 581         assert(p != css);
 582         for (i = 0; i < d->wordsper; i++) {
 583             p->states[i] = d->work[i];
 584         }
 585         p->hash = h;
 586         p->flags = (isPost ? POSTSTATE : 0);
 587         if (noProgress) {
 588             p->flags |= NOPROGRESS;
 589         }
 590
 591         /*
 592          * lastseen to be dealt with by caller
 593          */
 594     }
 595
 596     if (!sawLAConstraints) {    /* lookahead conds. always cache miss */
 597         FDEBUG(("c%d[%d]->c%d\n",
 598                 (int) (css - d->ssets), co, (int) (p - d->ssets)));
 599         css->outs[co] = p;
 600         css->inchain[co] = p->ins;
 601         p->ins.ss = css;
 602         p->ins.co = (color) co;
 603     }
 604     return p;
 605 }
 606 \f
 607 /*
 608  - checkLAConstraint - lookahead-constraint checker for miss()
 609  ^ static int checkLAConstraint(struct vars *, struct cnfa *, chr *, pcolor);
 610  */
 611 static int                      /* predicate:  constraint satisfied? */
 612 checkLAConstraint(
 613     struct vars *const v,
 614     struct cnfa *const pcnfa,   /* parent cnfa */
 615     chr *const cp,
 616     const pcolor co)            /* "color" of the lookahead constraint */
 617 {
 618     int n;
 619     struct subre *sub;
 620     struct dfa *d;
 621     struct smalldfa sd;
 622     chr *end;
 623
 624     n = co - pcnfa->ncolors;
 625     assert(n < v->g->nlacons && v->g->lacons != NULL);
 626     FDEBUG(("=== testing lacon %d\n", n));
 627     sub = &v->g->lacons[n];
 628     d = newDFA(v, &sub->cnfa, &v->g->cmap, &sd);
 629     if (d == NULL) {
 630         ERR(REG_ESPACE);
 631         return 0;
 632     }
 633     end = longest(v, d, cp, v->stop, NULL);
 634     freeDFA(d);
 635     FDEBUG(("=== lacon %d match %d\n", n, (end != NULL)));
 636     return (sub->subno) ? (end != NULL) : (end == NULL);
 637 }
 638 \f
 639 /*
 640  - getVacantSS - get a vacant state set
 641  * This routine clears out the inarcs and outarcs, but does not otherwise
 642  * clear the innards of the state set -- that's up to the caller.
 643  ^ static struct sset *getVacantSS(struct vars *, struct dfa *, chr *, chr *);
 644  */
 645 static struct sset *
 646 getVacantSS(
 647     struct vars *const v,       /* used only for debug flags */
 648     struct dfa *const d,
 649     chr *const cp,
 650     chr *const start)
 651 {
 652     int i;
 653     struct sset *ss, *p;
 654     struct arcp ap, lastap = {NULL, 0}; /* silence gcc 4 warning */
 655     color co;
 656
 657     ss = pickNextSS(v, d, cp, start);
 658     assert(!(ss->flags&LOCKED));
 659
 660     /*
 661      * Clear out its inarcs, including self-referential ones.
 662      */
 663
 664     ap = ss->ins;
 665     while ((p = ap.ss) != NULL) {
 666         co = ap.co;
 667         FDEBUG(("zapping c%d's %ld outarc\n", (int) (p - d->ssets), (long)co));
 668         p->outs[co] = NULL;
 669         ap = p->inchain[co];
 670         p->inchain[co].ss = NULL; /* paranoia */
 671     }
 672     ss->ins.ss = NULL;
 673
 674     /*
 675      * Take it off the inarc chains of the ssets reached by its outarcs.
 676      */
 677
 678     for (i = 0; i < d->ncolors; i++) {
 679         p = ss->outs[i];
 680         assert(p != ss);        /* not self-referential */
 681         if (p == NULL) {
 682             continue;           /* NOTE CONTINUE */
 683         }
 684         FDEBUG(("del outarc %d from c%d's in chn\n", i, (int) (p - d->ssets)));
 685         if (p->ins.ss == ss && p->ins.co == i) {
 686             p->ins = ss->inchain[i];
 687         } else {
 688             assert(p->ins.ss != NULL);
 689             for (ap = p->ins; ap.ss != NULL && !(ap.ss == ss && ap.co == i);
 690                     ap = ap.ss->inchain[ap.co]) {
 691                 lastap = ap;
 692             }
 693             assert(ap.ss != NULL);
 694             lastap.ss->inchain[lastap.co] = ss->inchain[i];
 695         }
 696         ss->outs[i] = NULL;
 697         ss->inchain[i].ss = NULL;
 698     }
 699
 700     /*
 701      * If ss was a success state, may need to remember location.
 702      */
 703
 704     if ((ss->flags&POSTSTATE) && ss->lastseen != d->lastpost &&
 705             (d->lastpost == NULL || d->lastpost < ss->lastseen)) {
 706         d->lastpost = ss->lastseen;
 707     }
 708
 709     /*
 710      * Likewise for a no-progress state.
 711      */
 712
 713     if ((ss->flags&NOPROGRESS) && ss->lastseen != d->lastnopr &&
 714             (d->lastnopr == NULL || d->lastnopr < ss->lastseen)) {
 715         d->lastnopr = ss->lastseen;
 716     }
 717
 718     return ss;
 719 }
 720 \f
 721 /*
 722  - pickNextSS - pick the next stateset to be used
 723  ^ static struct sset *pickNextSS(struct vars *, struct dfa *, chr *, chr *);
 724  */
 725 static struct sset *
 726 pickNextSS(
 727     struct vars *const v,       /* used only for debug flags */
 728     struct dfa *const d,
 729     chr *const cp,
 730     chr *const start)
 731 {
 732     int i;
 733     struct sset *ss, *end;
 734     chr *ancient;
 735
 736     /*
 737      * Shortcut for cases where cache isn't full.
 738      */
 739
 740     if (d->nssused < d->nssets) {
 741         i = d->nssused;
 742         d->nssused++;
 743         ss = &d->ssets[i];
 744         FDEBUG(("new c%d\n", i));
 745
 746         /*
 747          * Set up innards.
 748          */
 749
 750         ss->states = &d->statesarea[i * d->wordsper];
 751         ss->flags = 0;
 752         ss->ins.ss = NULL;
 753         ss->ins.co = WHITE;     /* give it some value */
 754         ss->outs = &d->outsarea[i * d->ncolors];
 755         ss->inchain = &d->incarea[i * d->ncolors];
 756         for (i = 0; i < d->ncolors; i++) {
 757             ss->outs[i] = NULL;
 758             ss->inchain[i].ss = NULL;
 759         }
 760         return ss;
 761     }
 762
 763     /*
 764      * Look for oldest, or old enough anyway.
 765      */
 766
 767     if (cp - start > d->nssets*2/3) {   /* oldest 33% are expendable */
 768         ancient = cp - d->nssets*2/3;
 769     } else {
 770         ancient = start;
 771     }
 772     for (ss = d->search, end = &d->ssets[d->nssets]; ss < end; ss++) {
 773         if ((ss->lastseen == NULL || ss->lastseen < ancient)
 774                 && !(ss->flags&LOCKED)) {
 775             d->search = ss + 1;
 776             FDEBUG(("replacing c%d\n", (int) (ss - d->ssets)));
 777             return ss;
 778         }
 779     }
 780     for (ss = d->ssets, end = d->search; ss < end; ss++) {
 781         if ((ss->lastseen == NULL || ss->lastseen < ancient)
 782                 && !(ss->flags&LOCKED)) {
 783             d->search = ss + 1;
 784             FDEBUG(("replacing c%d\n", (int) (ss - d->ssets)));
 785             return ss;
 786         }
 787     }
 788
 789     /*
 790      * Nobody's old enough?!? -- something's really wrong.
 791      */
 792
 793     FDEBUG(("can't find victim to replace!\n"));
 794     assert(NOTREACHED);
 795     ERR(REG_ASSERT);
 796     return d->ssets;
 797 }
 798 \f
 799 /*
 800  * Local Variables:
 801  * mode: c
 802  * c-basic-offset: 4
 803  * fill-column: 78
 804  * End:
 805  */