Return to regexec.c CVS log

Up to [Research Unix] / researchv9 / libc / gen

Annotation of researchv9/libc/gen/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<NSUBEXP; i++)
        !            59:                        mp[i] = sp->m[i];
        !            60:                for (; i<ms; i++)
        !            61:                        mp[i].sp = mp[i].ep = NULL;
        !            62:        }
        !            63: }
        !            64: 
        !            65: extern int
        !            66: regexec(progp, starts, mp, ms)
        !            67:        Prog *progp;    /* program to run */
        !            68:        char *starts;   /* string to run machine on */
        !            69:        regsubexp *mp;  /* subexpression elements */
        !            70:        int ms;         /* number of elements pointed to by mp */
        !            71: {
        !            72:        register flag=0;
        !            73:        register Inst *inst;
        !            74:        register List *tlp;
        !            75:        register char *s;
        !            76:        int startchar=progp->startinst->type<OPERATOR? progp->startinst->type : 0;
        !            77:        int i, checkstart;
        !            78: 
        !            79: restart:
        !            80:        match = 0;
        !            81:        checkstart = startchar;
        !            82:        sempty.m[0].sp = NULL;
        !            83:        if (mp!=NULL && ms >0)
        !            84:                mp[0].sp = mp[0].ep = NULL;
        !            85:        if (list[0] == NULL) {
        !            86:                list[0] = (List *)malloc(2*listsize*sizeof(List));
        !            87:                list[1] = list[0] + listsize;
        !            88:                liste[0] = list[0] + listsize - 1;
        !            89:                liste[1] = list[1] + listsize - 1;
        !            90:                if (list[0] == NULL)
        !            91:                        regerror("list overflow");
        !            92:        }
        !            93:        list[0][0].inst = list[1][0].inst = NULL;
        !            94: 
        !            95:        /* Execute machine once for each character, including terminal NUL */
        !            96:        s=starts;
        !            97:        do{
        !            98:                /* fast check for first char */
        !            99:                if(checkstart && *s!=startchar)
        !           100:                        continue;
        !           101:                tl=list[flag];
        !           102:                tle=liste[flag];
        !           103:                nl=list[flag^=1];
        !           104:                nle=liste[flag];
        !           105:                nl->inst=0;
        !           106:                /* Add first instruction to this list */
        !           107:                sempty.m[0].sp = s;
        !           108:                (void)newthread(tl, progp->startinst, &sempty);
        !           109:                /* Execute machine until this list is empty */
        !           110:                for(tlp=tl; inst=tlp->inst; tlp++){     /* assignment = */
        !           111:        Switchstmt:
        !           112:                        switch(inst->type){
        !           113:                        default:        /* regular character */
        !           114:                                if(inst->type == *s){
        !           115:        Addinst:
        !           116:                                        if(newthread(nl, inst->next, &tlp->se)==nle)
        !           117:                                                goto realloc;
        !           118:                                }
        !           119:                                break;
        !           120:                        case LBRA:
        !           121:                                tlp->se.m[inst->subid].sp = s;
        !           122:                                inst=inst->next;
        !           123:                                goto Switchstmt;
        !           124:                        case RBRA:
        !           125:                                tlp->se.m[inst->subid].ep = s;
        !           126:                                inst=inst->next;
        !           127:                                goto Switchstmt;
        !           128:                        case ANY:
        !           129:                                goto Addinst;
        !           130:                        case BOL:
        !           131:                                if(s == starts){
        !           132:                                        inst=inst->next;
        !           133:                                        goto Switchstmt;
        !           134:                                }
        !           135:                                break;
        !           136:                        case EOL:
        !           137:                                if(*s=='\0'){
        !           138:                                        inst=inst->next;
        !           139:                                        goto Switchstmt;
        !           140:                                }
        !           141:                                break;
        !           142:                        case CCLASS:
        !           143:                                if(((char *)inst->right)[*s/8]&(1<<(*s&07)))
        !           144:                                        goto Addinst;
        !           145:                                break;
        !           146:                        case OR:
        !           147:                                /* evaluate right choice later */
        !           148:                                if (newthread(tlp, inst->right, &tlp->se) == tle)
        !           149:                                        goto realloc;
        !           150:                                /* efficiency: advance and re-evaluate */
        !           151:                                inst=inst->left;
        !           152:                                goto Switchstmt;
        !           153:                        case END:       /* Match! */
        !           154:                                match = 1;
        !           155:                                tlp->se.m[0].ep = s;
        !           156:                                if (mp != NULL && ms > 0)                                                                       newmatch(mp, ms, &tlp->se);
        !           157:                                break;
        !           158:                        }
        !           159:                }
        !           160:                checkstart = startchar && nl->inst==NULL;
        !           161:        }while(*s++);
        !           162:        return match;
        !           163: realloc:
        !           164:        free(list[0]);
        !           165:        list[0] = NULL;
        !           166:        listsize += LISTINCREMENT;
        !           167:        goto restart;
        !           168: }
        !           169: 

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