![[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] / researchv10no / games / word_clout|
Return to regexec.c CVS log | Up to [Research Unix] / researchv10no / games / word_clout |
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.