minimise max_n size
[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   the original, recursive function. Needs replacing, but with exactly
82   the same output
83 */
84 static int fnmatch_test2(const char *p, const char *n, const char **max_n)
85 {
86         char c;
87         int i;
88
89         while ((c = *p++)) {
90                 switch (c) {
91                 case '*':
92                         if (*max_n && *max_n <= n) {
93                                 return null_match(p);
94                         }
95                         for (i=0; n[i]; i++) {
96                                 if (fnmatch_test2(p, n+i, max_n+1) == 0) {
97                                         return 0;
98                                 }
99                         }
100                         if (!*max_n || *max_n > n) *max_n = n;
101                         return null_match(p);
102
103                 case '<':
104                         if (*max_n && *max_n <= n) {
105                                 return null_match(p);
106                         }
107                         for (i=0; n[i]; i++) {
108                                 if (fnmatch_test2(p, n+i, max_n+1) == 0) return 0;
109                                 if (n[i] == '.' && !strchr(n+i+1,'.')) {
110                                         return fnmatch_test2(p, n+i+1, max_n+1);
111                                 }
112                         }
113                         if (!*max_n || *max_n > n) *max_n = n;
114                         return null_match(p);
115
116                 case '?':
117                         if (! *n) {
118                                 return -1;
119                         }
120                         n++;
121                         break;
122
123                 case '>':
124                         if (n[0] == '.') {
125                                 if (! n[1] && null_match(p) == 0) {
126                                         return 0;
127                                 }
128                                 break;
129                         }
130                         if (! *n) return null_match(p);
131                         n++;
132                         break;
133
134                 case '"':
135                         if (*n == 0 && null_match(p) == 0) {
136                                 return 0;
137                         }
138                         if (*n != '.') return -1;
139                         n++;
140                         break;
141
142                 default:
143                         if (c != *n && toupper(c) != toupper(*n)) {
144                                 return -1;
145                         }
146                         n++;
147                         break;
148                 }
149         }
150         
151         if (! *n) {
152                 return 0;
153         }
154         
155         return -1;
156 }
157
158 /*
159   the new, hopefully better function. Fiddle this until it works and is fast
160 */
161 static int fnmatch_test(const char *p, const char *n)
162 {
163         int ret, count, i;
164         const char **max_n = NULL;
165
166         for (count=i=0;p[i];i++) {
167                 if (p[i] == '*' || p[i] == '<') count++;
168         }
169
170         if (count) {
171                 max_n = calloc(sizeof(char *), count);
172         }
173
174         ret = fnmatch_test2(p, n, max_n);
175
176         if (max_n) {
177                 free(max_n);
178         }
179
180         return ret;
181 }
182
183 static void randstring(char *s, int len, const char *chars)
184 {
185         while (len--) {
186                 *s++ = chars[random() % strlen(chars)];
187         }
188         *s = 0;
189 }
190
191 static const char *p_used;
192 static const char *n_used;
193
194 static void sig_alrm(int sig)
195 {
196         printf("Too slow!!\np='%s'\ns='%s'\n", p_used, n_used);
197         exit(0);
198 }
199
200 static struct timeval tp1,tp2;
201
202 static void start_timer(void)
203 {
204         gettimeofday(&tp1,NULL);
205 }
206
207 static double end_timer(void)
208 {
209         gettimeofday(&tp2,NULL);
210         return((tp2.tv_sec - tp1.tv_sec) + 
211                (tp2.tv_usec - tp1.tv_usec)*1.0e-6);
212 }
213
214 int main(void)
215 {
216         int i;
217         double t1, w1=0, t2, w2=0;
218         srandom(time(NULL));
219
220         signal(SIGALRM, sig_alrm);
221
222         for (i=0;i<200000;i++) {
223                 int len1 = random() % 20;
224                 int len2 = random() % 20;
225                 char *p = malloc(len1+1);
226                 char *n = malloc(len2+1);
227                 int ret1, ret2;
228
229                 randstring(p, len1, "*<>\"?a.");
230                 randstring(n, len2, "a.");
231
232                 p_used = p;
233                 n_used = n;
234
235                 alarm(2);
236                 start_timer();
237                 ret1 = ret2 = fnmatch_test(p, n);
238                 t2 = end_timer();
239                 alarm(0);
240
241                 alarm(0);
242                 start_timer();
243                 ret1 = fnmatch_orig(p, n);
244                 t1 = end_timer();
245
246                 if (t1 > w1) w1 = t1;
247                 if (t2 > w2) w2 = t2;
248
249                 if (ret1 != ret2) {
250                         printf("mismatch: ret1=%d ret2=%d pattern='%s' string='%s'\n",
251                                ret1, ret2, p, n);
252                         free(p);
253                         free(n);
254                         exit(0);
255                 }
256
257                 free(p);
258                 free(n);
259                 printf("%7d worst1=%2.5f  worst2=%2.5f  (ratio=%5.2f)\r", 
260                        i, w1, w2, w1/w2);
261                 fflush(stdout);
262         }
263
264         printf("\nALL OK speedup=%.4f\n", w1/w2);
265         return 0;
266 }