![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to regexec.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv8dc / libc / gen|
Return to regexec.c CVS log | Up to [Research Unix] / researchv8dc / libc / gen |
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.