filename pattern matching

Here's a function that matches a filter (like *.c) to a filename (like hippo.c).

Code:

---

int match(char *f, char *s) {
    char *t;

    while(1) {
        if(*f == '?' || *s == '?') ;
        else if(*f == '*') {
            t = s;
            while(1) {
                if(match(f+1, t)) return 1;
                if(!*t++) break;
            }

            return 0;
        }
        else if(*s == '*') {
            t = f;
            while(1) {
                if(match(s+1, t)) return 1;
                if(!*t++) break;
            }

            return 0;
        }
        else if(*f != *s) return 0;

        if(!*s || !*f) break;
        s++, f++;
    }

    return *f || *s ? 0 : 1;
}

---

It returns 1 if there's a match, 0 otherwise.

There's nothing wrong with it (as far as I can see), I was just wondering how it could be improved. It's a little too slow for me.

Before anyone points it out, the * matching could be removed from one of the arguments.

Here's a quick lazy way:

Code:

---

int match( char *f, char *s )
{
    char *fend, *send;
    fend = f + strlen( f ) - 1;
    send = s + strlen( s ) - 1;

    while( *fend == *send && fend > f && send > s )
    {
        fend--;
        send--;
    }

    if( *fend == '*' )
        return 1;
    return 0;
}

---

Something like that? Or do you want stuff like this to work too?

Code:

---

int restult = match ( "hip*.c", "hippo.c" ); /* returns 1 */

---

Quzah.

I want everything to work - like hi??o.exe matches hippo.*

So what are all of your matching rules? You'll need to actually list what you consider a match first. Define the rules for matching and wild cards.


Quzah.

All DOS pattern matching . . . Like ? matches any one character, and * matches zero or more characters.

Code:

---

#include <windows.h>
#include <shlwapi.h>

int match(char *f, char *s)
{
    return PathMatchSpec(f, s);
}

---

That's sort of what I'm trying to duplicate . . . but I don't have <windows.h>.

you may want to check the boost libraries... I think they have libraries for what's called regular expressions (or REGEX for short)

note: their site seems to be not working ATM...

edit: it works, but it's slow as anything... (>2 minute load time)

Aren't the Boost libraries for C++? At any rate, yours fails a few tests it should pass. At least from what I can gather by your rules. Maybe not? Any way, mine's a bit different. Perhaps not better. Either way, they don't always give the same results, so one of us is wrong. :P

Code:

---

#include<stdio.h>
#include<string.h>

int match(char *f, char *s) {
    char *t;

    while(1) {
        if(*f == '?' || *s == '?') ;
        else if(*f == '*') {
            t = s;
            while(1) {
                if(match(f+1, t)) return 1;
                if(!*t++) break;
            }

            return 0;
        }
        else if(*s == '*') {
            t = f;
            while(1) {
                if(match(s+1, t)) return 1;
                if(!*t++) break;
            }

            return 0;
        }
        else if(*f != *s) return 0;

        if(!*s || !*f) break;
        s++, f++;
    }

    return *f || *s ? 0 : 1;
}

int qmatch( char *f, char *s )
{
    while( *f && *s )
    {
        if( *f == '*' )
        {
            while( *f && (*f == '*' || *f == '?') ) f++;
            while( *s && *s != *f )*s++;
        }
        if( !*s || !*f ) break;
        if( *s == '*' )
        {
            while( *s && (*s == '*' || *s == '?') ) s++;
            while( *f && *f != *s )*f++;
        }
        if( !*s || !*f ) break;
        if( *f == *s || *f == '?' || *s == '?' )
        {
            f++;
            s++;
        }
        else
            return 0;
    }
    return (*f || *s) || (*f==*s) ? 1 : 0;

}

int main( void )
{
    char *s[] =
    {
        "foo.c",
        "?oo.c",
        "*.c",
        "f?*",
        "?*?",
        "*",
        "?.*",
        "foo.*"
    };

    char *f[] =
    {
        "foo.c",
        "?oo.c",
        "*.c",
        "?*.c",
        "*?.?",
        "foo.?",
        "foo.*",
        "f?o?c",
        "f*o*"
        "*",
        "?????"
    };

    int x,y;

    for( y = 0; y < sizeof f / sizeof f[0]; y++ )
    {
        for( x = 0; x < sizeof s / sizeof s[0]; x++ )
        {
            printf("%8s vs %8s = %d, %d\n", f[ y ], s[ x ],
                match( f[ y ], s[ x ] ),
                qmatch( f[ y ], s[ x ] )
            );
        }

    }

    return 0;
}
/*
  foo.c vs    foo.c = 1, 1
  foo.c vs    ?oo.c = 1, 1
  foo.c vs      *.c = 1, 1
  foo.c vs      f?* = 1, 1
  foo.c vs      ?*? = 1, 1
  foo.c vs        * = 1, 1
  foo.c vs      ?.* = 0, 0
  foo.c vs    foo.* = 1, 1
  ?oo.c vs    foo.c = 1, 1
  ?oo.c vs    ?oo.c = 1, 1
  ?oo.c vs      *.c = 0, 1
  ?oo.c vs      f?* = 1, 1
  ?oo.c vs      ?*? = 1, 1
  ?oo.c vs        * = 0, 1
  ?oo.c vs      ?.* = 0, 0
  ?oo.c vs    foo.* = 1, 1
    *.c vs    foo.c = 1, 1
    *.c vs    ?oo.c = 0, 1
    *.c vs      *.c = 1, 1
    *.c vs      f?* = 1, 1
    *.c vs      ?*? = 1, 1
    *.c vs        * = 1, 1
    *.c vs      ?.* = 1, 1
    *.c vs    foo.* = 1, 1
    ?*.c vs    foo.c = 1, 1
    ?*.c vs    ?oo.c = 1, 1
    ?*.c vs      *.c = 1, 1
    ?*.c vs      f?* = 1, 1
    ?*.c vs      ?*? = 1, 1
    ?*.c vs        * = 0, 1
    ?*.c vs      ?.* = 1, 1
    ?*.c vs    foo.* = 1, 1
    *?.? vs    foo.c = 1, 1
    *?.? vs    ?oo.c = 0, 1
    *?.? vs      *.c = 1, 1
    *?.? vs      f?* = 1, 1
    *?.? vs      ?*? = 0, 1
    *?.? vs        * = 0, 1
    *?.? vs      ?.* = 1, 1
    *?.? vs    foo.* = 1, 1
  foo.? vs    foo.c = 1, 1
  foo.? vs    ?oo.c = 1, 1
  foo.? vs      *.c = 1, 1
  foo.? vs      f?* = 1, 1
  foo.? vs      ?*? = 1, 1
  foo.? vs        * = 1, 1
  foo.? vs      ?.* = 0, 0
  foo.? vs    foo.* = 1, 1
  foo.* vs    foo.c = 1, 1
  foo.* vs    ?oo.c = 1, 1
  foo.* vs      *.c = 1, 1
  foo.* vs      f?* = 1, 1
  foo.* vs      ?*? = 1, 1
  foo.* vs        * = 1, 1
  foo.* vs      ?.* = 0, 0
  foo.* vs    foo.* = 1, 1
  f?o?c vs    foo.c = 1, 1
  f?o?c vs    ?oo.c = 1, 1
  f?o?c vs      *.c = 1, 1
  f?o?c vs      f?* = 1, 1
  f?o?c vs      ?*? = 0, 1
  f?o?c vs        * = 1, 1
  f?o?c vs      ?.* = 1, 1
  f?o?c vs    foo.* = 1, 1
  f*o** vs    foo.c = 1, 1
  f*o** vs    ?oo.c = 1, 1
  f*o** vs      *.c = 1, 1
  f*o** vs      f?* = 1, 1
  f*o** vs      ?*? = 1, 1
  f*o** vs        * = 1, 1
  f*o** vs      ?.* = 1, 1
  f*o** vs    foo.* = 1, 1
  ????? vs    foo.c = 1, 1
  ????? vs    ?oo.c = 1, 1
  ????? vs      *.c = 0, 1
  ????? vs      f?* = 0, 1
  ????? vs      ?*? = 0, 1
  ????? vs        * = 0, 1
  ????? vs      ?.* = 0, 1
  ????? vs    foo.* = 1, 1
*/

---

Mine was an attempt to really cover all the cases I could think up for valid matching. I don't know if they fit all of your rules, but that's my take on it.

Quzah.

Let's stop this madness; only one string should be parsed for wildcards; the filename should not.

That wasn't a requirement given. Thus, I matched his code, except mine works. As I recall, you weren't the one setting the rules for this little event.


Quzah.

Quzah, you're right: mine was wrong. The if(*s=='?' || *f=='?') was in the wrong place.

Code:

---

int match(char *f, char *s) {
    char *t;

    while(1) {
        if(*f == '*') {
            t = s;
            while(1) {
                if(match(f+1, t)) return 1;
                if(!*t++) break;
            }

            return 0;
        }
        else if(*s == '*') {
            t = f;
            while(1) {
                if(match(s+1, t)) return 1;
                if(!*t++) break;
            }

            return 0;
        }
        else if(*f == '?' || *s == '?') ;
        else if(*f != *s) return 0;

        if(!*s || !*f) break;
        s++, f++;
    }

    return *f || *s ? 0 : 1;
}

---

If there was a ?, it ignored the other character - even if it was a *. This should work - run it through your test again.