fnmatch/ms_fnmatch.c

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