![[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] / researchv9 / libc / gen|
Return to regexec.c CVS log | Up to [Research Unix] / researchv9 / 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: 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.