Return to regexec.c CVS log

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

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

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