added cache for *

[tridge/junkcode.git] / fnmatch / ms_fnmatch.c

diff --git a/fnmatch/ms_fnmatch.c b/fnmatch/ms_fnmatch.c
index 8942bdb5faaa4fb91f71df878f3aa97ae1791efd..828547d7478044c0d0684c9755debd863026a960 100644 (file)
--- a/fnmatch/ms_fnmatch.c
+++ b/fnmatch/ms_fnmatch.c
@@ -98,46 +98,36 @@ static int min_p_chars(const char *p)
   the original, recursive function. Needs replacing, but with exactly
   the same output
 */
-static int fnmatch_test2(const char *p, const char *n)
+static int fnmatch_test2(const char *p, size_t ofs, const char *n, unsigned *cache)
 {
        char c;
+       int len;
 
-       if (min_p_chars(p) > strlen(n)) return -1;
+       if (strlen(n) == 1) {
+//             printf("p=%s n=%s\n", p+ofs, n);
+       }
 
-//     printf("p=%s   n=%s\n", p, n);
+//     printf("p=%s n=%s\n", p+ofs, n);
+                       
 
-       while ((c = *p++)) {
+       while ((c = p[ofs++])) {
                switch (c) {
-               case '?':
-                       if (! *n) {
-                               return -1;
-                       }
-                       n++;
-                       break;
-
-               case '>':
-                       if (n[0] == '.') {
-                               if (! n[1] && null_match(p) == 0) {
-                                       return 0;
-                               }
-                               break;
-                       }
-                       if (! *n) return null_match(p);
-                       n++;
-                       break;
-
                case '*':
+                       len = n;
                        for (; *n; n++) {
-                               if (fnmatch_test2(p, n) == 0) {
+                               if (cache[ofs] && cache[ofs] >= len) {
+                                       return null_match(p+ofs);
+                               }
+                               if (fnmatch_test2(p, ofs, n, cache) == 0) {
                                        return 0;
                                }
                        }
-                       if (! *n) return null_match(p);
-                       return -1;
+                       if (cache[ofs] < len) cache[ofs] = len;
+                       return null_match(p+ofs);
 
                case '<':
                        for (; *n; n++) {
-                               if (fnmatch_test2(p, n) == 0) {
+                               if (fnmatch_test2(p, ofs, n, cache) == 0) {
                                        return 0;
                                }
                                if (*n == '.' && 
@@ -148,9 +138,28 @@ static int fnmatch_test2(const char *p, const char *n)
                        }
                        break;
 
+
+               case '?':
+                       if (! *n) {
+                               return -1;
+                       }
+                       n++;
+                       break;
+
+               case '>':
+                       if (n[0] == '.') {
+                               if (! n[1] && null_match(p+ofs) == 0) {
+                                       return 0;
+                               }
+                               break;
+                       }
+                       if (! *n) return null_match(p+ofs);
+                       n++;
+                       break;
+
                case '"':
                        if (*n == 0 && 
-                           null_match(p) == 0) {
+                           null_match(p+ofs) == 0) {
                                return 0;
                        }
                        if (*n != '.') return -1;
@@ -164,6 +173,7 @@ static int fnmatch_test2(const char *p, const char *n)
                                return -1;
                        }
                        n++;
+                       break;
                }
        }
        
@@ -200,8 +210,14 @@ static int fnmatch_test(const char *p, const char *n)
 {
        char *new = compress_pattern(p);
        int ret;
+       unsigned *cache;
+
+       cache = calloc(sizeof(unsigned), strlen(p)+1);
+
+       ret = fnmatch_test2(p, 0, n, cache);
+
+       free(cache);
 
-       ret = fnmatch_test2(new, n);
        free(new);
        return ret;
 }
@@ -241,17 +257,19 @@ static double end_timer(void)
 int main(void)
 {
        int i;
+       double t1=0, t2=0;
        srandom(time(NULL));
 
        signal(SIGALRM, sig_alrm);
 
        start_timer();
-       alarm(2);
-       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";
-       n_used = "c.cccccccccccccccccccccccccccc";
+       alarm(0);
+       p_used ="*c*c*c";
+       n_used = "ccc.";
        fnmatch_test(p_used, n_used);
        alarm(0);
        printf("took %.7f seconds\n", end_timer());
+//     exit(0);
 
        for (i=0;i<100000;i++) {
                int len1 = random() % 20;
@@ -260,16 +278,20 @@ int main(void)
                char *n = malloc(len2+1);
                int ret1, ret2;
 
-               randstring(p, len1, "*?a");
+               randstring(p, len1, "*>\"?a.");
                randstring(n, len2, "a.");
 
                p_used = p;
                n_used = n;
 
                alarm(0);
+               start_timer();
                ret1 = fnmatch_orig(p, n);
+               t1 += end_timer();
                alarm(2);
+               start_timer();
                ret2 = fnmatch_test(p, n);
+               t2 += end_timer();
                alarm(0);
 
                if (ret1 != ret2) {
@@ -288,6 +310,6 @@ int main(void)
                fflush(stdout);
        }
 
-       printf("ALL OK\n");
+       printf("ALL OK t1=%.4f t2=%.4f\n", t1, t2);
        return 0;
 }