/[dtapublic]/projs/trunk/shared_source/c_tcl_base_7_5_w_mods/rege_dfa.c
ViewVC logotype

Diff of /projs/trunk/shared_source/c_tcl_base_7_5_w_mods/rege_dfa.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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

Legend:
Removed from v.29  
changed lines
  Added in v.71

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25