now seems to really work
[tridge/junkcode.git] / fnmatch / ms_fnmatch.c
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <unistd.h>
5 #include <sys/time.h>
6 #include <time.h>
7 #include <signal.h>
8 #include <ctype.h>
9
10 /*
11   the original, recursive function. Needs replacing, but with exactly
12   the same output
13 */
14 static int fnmatch_orig(const char *p, const char *n)
15 {
16         char c;
17
18         while ((c = *p++)) {
19                 switch (c) {
20                 case '?':
21                         if (! *n) return -1;
22                         n++;
23                         break;
24
25                 case '>':
26                         if (n[0] == '.') {
27                                 if (! n[1] && fnmatch_orig(p, n+1) == 0) return 0;
28                                 if (fnmatch_orig(p, n) == 0) return 0;
29                                 return -1;
30                         }
31                         if (! *n) return fnmatch_orig(p, n);
32                         n++;
33                         break;
34
35                 case '*':
36                         for (; *n; n++) {
37                                 if (fnmatch_orig(p, n) == 0) return 0;
38                         }
39                         break;
40
41                 case '<':
42                         for (; *n; n++) {
43                                 if (fnmatch_orig(p, n) == 0) return 0;
44                                 if (*n == '.' && !strchr(n+1,'.')) {
45                                         n++;
46                                         break;
47                                 }
48                         }
49                         break;
50
51                 case '"':
52                         if (*n == 0 && fnmatch_orig(p, n) == 0) return 0;
53                         if (*n != '.') return -1;
54                         n++;
55                         break;
56
57                 default:
58                         if (c != *n && toupper(c) != toupper(*n)) return -1;
59                         n++;
60                 }
61         }
62         
63         if (! *n) return 0;
64         
65         return -1;
66 }
67
68
69 static int null_match(const char *p)
70 {
71         for (;*p;p++) {
72                 if (*p != '*' &&
73                     *p != '<' &&
74                     *p != '"' &&
75                     *p != '>') return -1;
76         }
77         return 0;
78 }
79
80
81 struct max_n {
82         const char *predot;
83         const char *postdot;
84 };
85
86 /*
87   the test function
88 */
89 static int fnmatch_test2(const char *p, const char *n, struct max_n *max_n, const char *ldot)
90 {
91         char c;
92         int i;
93
94         while ((c = *p++)) {
95                 switch (c) {
96                 case '*':
97                         if (max_n->predot && max_n->predot <= n) {
98                                 return null_match(p);
99                         }
100                         for (i=0; n[i]; i++) {
101                                 if (fnmatch_test2(p, n+i, max_n+1, ldot) == 0) {
102                                         return 0;
103                                 }
104                         }
105                         if (!max_n->predot || max_n->predot > n) max_n->predot = n;
106                         return null_match(p);
107
108                 case '<':
109                         if (max_n->predot && max_n->predot <= n) {
110                                 return null_match(p);
111                         }
112                         if (max_n->postdot && max_n->postdot <= n && n < ldot) {
113                                 return -1;
114                         }
115                         for (i=0; n[i]; i++) {
116                                 if (fnmatch_test2(p, n+i, max_n+1, ldot) == 0) return 0;
117                                 if (n+i == ldot) {
118                                         if (fnmatch_test2(p, n+i+1, max_n+1, ldot) == 0) return 0;
119                                         if (!max_n->postdot || max_n->postdot > n) max_n->postdot = n;
120                                         return -1;
121                                 }
122                         }
123                         if (!max_n->predot || max_n->predot > n) max_n->predot = n;
124                         return null_match(p);
125
126                 case '?':
127                         if (! *n) {
128                                 return -1;
129                         }
130                         n++;
131                         break;
132
133                 case '>':
134                         if (n[0] == '.') {
135                                 if (! n[1] && null_match(p) == 0) {
136                                         return 0;
137                                 }
138                                 break;
139                         }
140                         if (! *n) return null_match(p);
141                         n++;
142                         break;
143
144                 case '"':
145                         if (*n == 0 && null_match(p) == 0) {
146                                 return 0;
147                         }
148                         if (*n != '.') return -1;
149                         n++;
150                         break;
151
152                 default:
153                         if (c != *n && toupper(c) != toupper(*n)) {
154                                 return -1;
155                         }
156                         n++;
157                         break;
158                 }
159         }
160         
161         if (! *n) {
162                 return 0;
163         }
164         
165         return -1;
166 }
167
168 /*
169   the new, hopefully better function. Fiddle this until it works and is fast
170 */
171 static int fnmatch_test(const char *p, const char *n)
172 {
173         int ret, count, i;
174         struct max_n *max_n = NULL;
175
176         for (count=i=0;p[i];i++) {
177                 if (p[i] == '*' || p[i] == '<') count++;
178         }
179
180         if (count) {
181                 max_n = calloc(sizeof(struct max_n), count);
182         }
183
184         ret = fnmatch_test2(p, n, max_n, strrchr(n, '.'));
185
186         if (max_n) {
187                 free(max_n);
188         }
189
190         return ret;
191 }
192
193 static void randstring(char *s, int len, const char *chars)
194 {
195         while (len--) {
196                 *s++ = chars[random() % strlen(chars)];
197         }
198         *s = 0;
199 }
200
201 static const char *p_used;
202 static const char *n_used;
203
204 static void sig_alrm(int sig)
205 {
206         printf("\nToo slow!!\np='%s'\ns='%s'\n", p_used, n_used);
207         exit(0);
208 }
209
210 static struct timeval tp1,tp2;
211
212 static void start_timer(void)
213 {
214         gettimeofday(&tp1,NULL);
215 }
216
217 static double end_timer(void)
218 {
219         gettimeofday(&tp2,NULL);
220         return((tp2.tv_sec - tp1.tv_sec) + 
221                (tp2.tv_usec - tp1.tv_usec)*1.0e-6);
222 }
223
224 int main(void)
225 {
226         int i;
227         double t1, w1=0, t2, w2=0;
228         srandom(time(NULL));
229
230         signal(SIGALRM, sig_alrm);
231
232         for (i=0;i<200000;i++) {
233                 int len1 = random() % 25;
234                 int len2 = random() % 25;
235                 char *p = malloc(len1+1);
236                 char *n = malloc(len2+1);
237                 int ret1, ret2;
238
239                 randstring(p, len1, "*<>\"?a.");
240 //              randstring(p, len1, "<a.");
241                 randstring(n, len2, "a.");
242
243                 p_used = p;
244                 n_used = n;
245
246                 alarm(2);
247                 start_timer();
248                 ret1 = ret2 = fnmatch_test(p, n);
249                 t2 = end_timer();
250                 alarm(0);
251
252                 alarm(0);
253                 start_timer();
254                 ret1 = fnmatch_orig(p, n);
255                 t1 = end_timer();
256
257                 if (t1 > w1) w1 = t1;
258                 if (t2 > w2) w2 = t2;
259
260                 if (ret1 != ret2) {
261                         printf("\nmismatch: ret1=%d ret2=%d pattern='%s' string='%s'\n",
262                                ret1, ret2, p, n);
263                         free(p);
264                         free(n);
265                         exit(0);
266                 }
267
268                 free(p);
269                 free(n);
270                 printf("%7d worst1=%2.5f  worst2=%2.5f  (ratio=%5.2f)\r", 
271                        i, w1, w2, w1/w2);
272                 fflush(stdout);
273         }
274
275         printf("\nALL OK speedup=%.4f\n", w1/w2);
276         return 0;
277 }