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