Return to regexec.c CVS log

Up to [Research Unix] / researchv10no / cmd / nupas / libc

Annotation of researchv10no/cmd/nupas/libc/regexec.c, revision 1.1

1.1     ! root        1: #include "regprog.h"
        !             2: 
        !             3: /*
        !             4:  *     Machine state
        !             5:  */
        !             6: #define LISTINCREMENT 8
        !             7: typedef struct List{
        !             8:        Inst    *inst;          /* Instruction of the thread */
        !             9:        Subexp  se;             /* matched subexpressions in this thread */
        !            10: }List;
        !            11: static List    *tl, *nl;       /* This list, next list */
        !            12: static List    *tle, *nle;     /* ends of this and next list */
        !            13: static List    *list[2];
        !            14: static List    *liste[2];
        !            15: static int     listsize = LISTINCREMENT;
        !            16: 
        !            17: static Subexp sempty;          /* empty set of matches */
        !            18: static int match;              /* true if match is found */
        !            19: 
        !            20: /*
        !            21:  * Note optimization in addinst:
        !            22:  *     *lp must be pending when addinst called; if *l has been looked
        !            23:  *             at already, the optimization is a bug.
        !            24:  */
        !            25: static List *
        !            26: newthread(lp, ip, sep)
        !            27:        List *lp;       /* list to add to */
        !            28:        Inst *ip;       /* instruction to add */
        !            29:        register Subexp *sep;   /* pointers to subexpressions */
        !            30: {
        !            31:        register List *p;
        !            32: 
        !            33:        for(p=lp; p->inst != NULL; p++){
        !            34:                if(p->inst==ip){
        !            35:                        if((sep)->m[0].sp < p->se.m[0].sp)
        !            36:                                p->se = *sep;
        !            37:                        return NULL;
        !            38:                }
        !            39:        }
        !            40:        p->inst = ip;
        !            41:        p->se = *sep;
        !            42:        (++p)->inst = NULL;
        !            43:        return p;
        !            44: }
        !            45: 
        !            46: static void
        !            47: newmatch(mp, ms, sp)
        !            48:        regsubexp *mp;
        !            49:        int ms; 
        !            50:        register Subexp *sp;
        !            51: {
        !            52:        register int i;
        !            53: 
        !            54:        if (mp==NULL || ms <=0)
        !            55:                return;
        !            56:        if(mp[0].sp==0 || sp->m[0].sp<mp[0].sp ||
        !            57:           (sp->m[0].sp==mp[0].sp && sp->m[0].ep>mp[0].ep)) {
        !            58:                for (i=0; i < ms; i++)
        !            59:                        mp[i] = sp->m[i];
        !            60:        }
        !            61: }
        !            62: 
        !            63: extern int
        !            64: regexec(progp, starts, mp, ms)
        !            65:        Prog *progp;    /* program to run */
        !            66:        char *starts;   /* string to run machine on */
        !            67:        regsubexp *mp;  /* subexpression elements */
        !            68:        int ms;         /* number of elements pointed to by mp */
        !            69: {
        !            70:        register flag=0;
        !            71:        register Inst *inst;
        !            72:        register List *tlp;
        !            73:        register char *s;
        !            74:        int startchar=progp->startinst->type<OPERATOR? progp->startinst->type : 0;
        !            75:        int i, checkstart;
        !            76: 
        !            77: restart:
        !            78:        match = 0;
        !            79:        checkstart = startchar;
        !            80:        sempty.m[0].sp = NULL;
        !            81:        if (mp!=NULL && ms >0)
        !            82:                mp[0].sp = mp[0].ep = NULL;
        !            83:        if (list[0] == NULL) {
        !            84:                list[0] = (List *)malloc(2*listsize*sizeof(List));
        !            85:                list[1] = list[0] + listsize;
        !            86:                liste[0] = list[0] + listsize - 1;
        !            87:                liste[1] = list[1] + listsize - 1;
        !            88:                if (list[0] == NULL)
        !            89:                        regerror("list overflow");
        !            90:        }
        !            91:        list[0][0].inst = list[1][0].inst = NULL;
        !            92: 
        !            93:        /* Execute machine once for each character, including terminal NUL */
        !            94:        s=starts;
        !            95:        do{
        !            96:                /* fast check for first char */
        !            97:                if(checkstart && *s!=startchar)
        !            98:                        continue;
        !            99:                tl=list[flag];
        !           100:                tle=liste[flag];
        !           101:                nl=list[flag^=1];
        !           102:                nle=liste[flag];
        !           103:                nl->inst=0;
        !           104:                /* Add first instruction to this list */
        !           105:                sempty.m[0].sp = s;
        !           106:                (void)newthread(tl, progp->startinst, &sempty);
        !           107:                /* Execute machine until this list is empty */
        !           108:                for(tlp=tl; inst=tlp->inst; tlp++){     /* assignment = */
        !           109:        Switchstmt:
        !           110:                        switch(inst->type){
        !           111:                        default:        /* regular character */
        !           112:                                if(inst->type == *s){
        !           113:        Addinst:
        !           114:                                        if(newthread(nl, inst->next, &tlp->se)==nle)
        !           115:                                                goto realloc;
        !           116:                                }
        !           117:                                break;
        !           118:                        case LBRA:
        !           119:                                tlp->se.m[inst->subid].sp = s;
        !           120:                                inst=inst->next;
        !           121:                                goto Switchstmt;
        !           122:                        case RBRA:
        !           123:                                tlp->se.m[inst->subid].ep = s;
        !           124:                                inst=inst->next;
        !           125:                                goto Switchstmt;
        !           126:                        case ANY:
        !           127:                                goto Addinst;
        !           128:                        case BOL:
        !           129:                                if(s == starts){
        !           130:                                        inst=inst->next;
        !           131:                                        goto Switchstmt;
        !           132:                                }
        !           133:                                break;
        !           134:                        case EOL:
        !           135:                                if(*s=='\0'){
        !           136:                                        inst=inst->next;
        !           137:                                        goto Switchstmt;
        !           138:                                }
        !           139:                                break;
        !           140:                        case CCLASS:
        !           141:                                if(((char *)inst->right)[*s/8]&(1<<(*s&07)))
        !           142:                                        goto Addinst;
        !           143:                                break;
        !           144:                        case OR:
        !           145:                                /* evaluate right choice later */
        !           146:                                if (newthread(tlp, inst->right, &tlp->se) == tle)
        !           147:                                        goto realloc;
        !           148:                                /* efficiency: advance and re-evaluate */
        !           149:                                inst=inst->left;
        !           150:                                goto Switchstmt;
        !           151:                        case END:       /* Match! */
        !           152:                                match = 1;
        !           153:                                tlp->se.m[0].ep = s;
        !           154:                                if (mp != NULL && ms > 0)                                                                       newmatch(mp, ms, &tlp->se);
        !           155:                                break;
        !           156:                        }
        !           157:                }
        !           158:                checkstart = startchar && nl->inst==NULL;
        !           159:        }while(*s++);
        !           160:        return match;
        !           161: realloc:
        !           162:        free(list[0]);
        !           163:        list[0] = NULL;
        !           164:        listsize += LISTINCREMENT;
        !           165:        goto restart;
        !           166: }
        !           167: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.