Wildcard string compare (globbing)

I read this article " ,its really amazing. I appreciate your efforts. I am student, I need help in defining the same kind of function according to my requirements. I hope, I 'll get good response.

Words are strings which are separated by dots. Two additional characters are also valid i.e:The *, which matches 1 word and the #, which matches 0..N words Example: *.stock.# matches the routing keys usd.stock and eur.stock.dsf but not stock.nasdaq.

Your help would be highly appreciated.

Sam

A very useful function!
Sign In·Permalink

First of all I like this code, it is small and fully stand-alone.
I have modified it, because I need an additional wildcard joker that represents digits. Finally the modified function accepts '*', '?' and '#' as joker characters.

int wildcmp_ex(const char *wild, const char *string) {
  const char *cp = NULL, *mp = NULL;
 
  while (*string) {
    if (*wild == '*') {
      if (!*++wild) {
        return 1;
      }
      mp = wild;
      cp = string+1;
    } else if (((*wild == *string) && (*wild != '#')) || (*wild == '?') || ((*wild == '#') && isdigit(*string))) {
      wild++;
      string++;
    } else {
      if (mp)
      {
        wild = mp;
        string = cp++;
      }
      else
      {
        return 0;
      }
    }
  }
 
  while (*wild == '*') {
    wild++;
  }
  return !*wild;
}

Thomas Haase

modified 29 Sep '11 - 8:26.

Hi Jack Handy, Is there a licence attached to this code? Thanks, Mark
Sign In·Permalink

Just for fun... a C# version with almost the same syntax as the original C version Smile | :)

public static bool wildcmp(string pattern, string text) {
 
  var wild = new StringScanner(pattern);
  var @string = new StringScanner(text);
 
  var mp = wild;
  var cp = @string;
 
  while (@string && wild != '*') {
    if (wild != @string && wild != '?') {
      return false;
    }
    wild++;
    @string++;
  }
 
  while (@string) {
    if (@wild == '*') {
      if (!++wild) {
        return true;
      }
      mp = wild;
      cp = @string + 1;
    } else if (wild == @string || wild == '?') {
      wild++;
      @string++;
    } else {
      wild = mp;
      @string = cp++;
    }
  }
 
  while (wild == '*') {
    wild++;
  }
  return !wild;
}
 
public struct StringScanner
{
    private string _string;
    private int _position;
    
    public StringScanner(string s)
    {
        _string = s;
        _position = 0;
    }
    
    public string String
    {
        get { return _string; }
    }
    
    public int Position
    {
        get { return _position; }
    }
        
    public bool Finished
    {
        get { return _position == _string.Length;}
    }
    
    public char Current
    {
        get { return Finished ? '\0' : _string[_position]; }
    }
    
    public bool MoveNext()
    {
        if (Finished)
            return false;
        _position++;
        return true;
    }
    
    public static StringScanner operator ++(StringScanner scanner)
    {
        scanner.MoveNext();
        return scanner;
    }
    
    public static StringScanner operator +(StringScanner scanner, int n)
    {
        return new StringScanner(scanner.String)
        {
            _position = Math.Min(scanner.Position + n, scanner.String.Length)
        };
    }
    
    public static implicit operator bool(StringScanner scanner)
    {
        return !scanner.Finished;
    }
    
    public static implicit operator char(StringScanner scanner)
    {
        return scanner.Current;
    }
    
    public static bool operator ==(StringScanner scanner1, StringScanner scanner2)
    {
        return scanner1.Current == scanner2.Current;
    }
    
    public static bool operator !=(StringScanner scanner1, StringScanner scanner2)
    {
        return scanner1.Current != scanner2.Current;
    }
}

My blog : in English - in French

I've been using this for years, just don't show it to your instructor.

// String match with wildcards.  Obtained from the Internet somewhere.  Case insensitive.

BOOL wm(const char *s, const char *t)
{
	return *t-'*' ? *s ? (*t=='?') | (toupper(*s)==toupper(*t)) && wm(s+1,t+1) : !*t : wm(s,t+1) || *s && wm(s+1,t);
}

If you want case sensitive, remove the toupper() calls.

This strikes me as an obvious place to use recursion. So here goes...

   public class MString
   {
      /// <summary>
      /// Function to compare two strings, where strA may contain wildcard characters '*' and 
      /// '?'. http://en.wikipedia.org/wiki/Wildcard_character
      /// </summary>
      /// <param name="strA">string which may contain wildcards, may be empty, must not be null</param>
      /// <param name="strB">string to compare to, no wildcard processing, may be empty, must not be null</param>
      /// <param name="ignoreCase">true = ignore upper/lower case, false = don't ignore case</param>
      /// <returns>true = match, false = non-match</returns>
      public static bool CompareWWc(string strA, string strB, bool ignoreCase)
      {
         if (ignoreCase)
            return CompareWWc(strA.ToLower(), strB.ToLower());
         else 
            return CompareWWc(strA, strB);
      }
 

      /// <summary>
      /// Recursive function to compare two strings, where strA may contain wildcard characters 
      /// '*' and '?'. http://en.wikipedia.org/wiki/Wildcard_character
      /// </summary>
      /// <param name="strA">string which may contain wildcards, may be empty, must not be null</param>
      /// <param name="strB">string to compare to, no wildcard processing, may be empty, must not be null</param>
      /// <returns>true = match, false = non-match</returns>
      public static bool CompareWWc(string strA, string strB)
      {
         // Top of loop to scan across strA (and strB)
         for (int i = 0; i < strA.Length; i++)
         {
            // Special processing when we hit a '*' in strA
            if (strA[i] == '*')
            {
               // If the '*' is at the end of strA then result = true irrespective of strB
               if (i == strA.Length - 1)
                  return true;  
 
               // Do recursive calls to try to find a match somewhere to the right in strB
               strA = strA.Substring(i + 1);  // The part of strA beyond the '*'
               for (int j = i; j < strB.Length; j++)
                  if (CompareWWc(strA, strB.Substring(j)))
                     return true;
               return false;
            }
 
            // Normal processing for non-'*' characters in strA
            if (i >= strB.Length || (strA[i] != strB[i] && strA[i] != '?'))
               return false;
         }
 
         // We've reached the end of strA and the last character is not '*'
         return strA.Length == strB.Length;
      }
 
   }

And here's a little test sequence:

         if (!MString.CompareWWc("", ""))
            Console.WriteLine("Something wrong!");
 

         if (!MString.CompareWWc("something", "something"))
            Console.WriteLine("Something wrong!");
 
         if (MString.CompareWWc("something", "zomething"))
            Console.WriteLine("Something wrong!");
         
         if (MString.CompareWWc("something", "some"))
            Console.WriteLine("Something wrong!");
         
         if (MString.CompareWWc("something", "something else"))
            Console.WriteLine("Something wrong!");
 

         if (!MString.CompareWWc("s?m?th???", "something"))
            Console.WriteLine("Something wrong!");
         
         if (MString.CompareWWc("s?m?th???", "somethin"))
            Console.WriteLine("Something wrong!");
 

         if (!MString.CompareWWc("*", ""))
            Console.WriteLine("Something wrong!");
         
         if (!MString.CompareWWc("*", "nonsense"))
            Console.WriteLine("Something wrong!");
         
         if (!MString.CompareWWc("non*", "nonsense"))
            Console.WriteLine("Something wrong!");
 

         if (!MString.CompareWWc("*nonsense", "nonsense"))
            Console.WriteLine("Something wrong!");
 
         if (!MString.CompareWWc("non*nse", "nonsense"))
            Console.WriteLine("Something wrong!");
         
         if (MString.CompareWWc("non*nse", "nonsenze"))
            Console.WriteLine("Something wrong!");
         
         if (!MString.CompareWWc("non*n?e", "nonsense"))
            Console.WriteLine("Something wrong!");
 

         if (!MString.CompareWWc("n*on*nse", "nonsense"))
            Console.WriteLine("Something wrong!");
 
         if (!MString.CompareWWc("n*n*nse", "nonsense"))
            Console.WriteLine("Something wrong!");
 
         if (MString.CompareWWc("*non*nse", "nonsenze"))
            Console.WriteLine("Something wrong!");
 
         if (!MString.CompareWWc("n*n*n?e", "nonsense"))
            Console.WriteLine("Something wrong!");
      }

By the way, the name CompareWWc means Compare With Wildcards.

Dear Jack,
Dear all,

I used this function in comparing two strings the first is Pattern(* KK *) and the second is Text(TT KK ZZ) and the function return pass. thats briliant,but my question how I can edit the function to be able to catch or handle the characters of matched * to save them in variables. for example:

X = TT
Y = ZZ

to deal with them later on in my system.

I tried many times but its not working well so far.

So please any one have an idea to do that please let me know and its will be appreciated.

Best Regards.

code in C# ?? AE
Sign In·Permalink

Great code, but when trying this I realized that the following pattern is a match:

Search: ????????
Text to search: ABC

The problem is that the pattern can be LONGER than the text searched, in which case it should return a not found, but instead returns found.

Also, this example succeeds:

Search: y*n
Text to search: yessir

But of course should fail, since I'm looking for a text that ends with n

So I re-wrote your program to this, to correctly handle this situation.

bool StrWildCmp(char* wildstring, char *matchstring){
 
	
	char stopstring[1];
	*stopstring = 0;
 
	while(*matchstring) {
		if (*wildstring == '*') {
		  if (!*++wildstring) {
			return true;
		  } else {
			  *stopstring = *wildstring;
		  }
		}
 
		if(*stopstring) {
			if(*stopstring == *matchstring ) {
				wildstring++;
				matchstring++;
				*stopstring = 0;
			} else {
				matchstring++;
			}
		} else if((*wildstring == *matchstring) || (*wildstring == '?')) {
				wildstring++;
				matchstring++;
		} else {
			return false;
		}
 
		if(!*matchstring && *wildstring && *wildstring != '*') {
			// matchstring too short
			return false;
		}
	}
 
  return true;
}

Thanks again for the inspiration. Cool | :cool:

If you have ability to use Windows code you can use PathMatchSpec: http://msdn.microsoft.com/en-us/library/bb773727(VS.85).aspx[^]
View the reply to this message Sign In·Permalink

Anyone tried converting this to using wchar_t* (essentially Unicode) instead of char*?
View the reply to this message Sign In·Permalink

This is the version of the wildcmp function in XBLite programming language:

FUNCTION SBYTE wildcmp( wildcard$, search$)
  ' wildcmp(const char *wild, const char *string)
  ' Written by Jack Handy - jakkhandy@hotmail.com
 
  ULONG cp
  ULONG mp
  
  STRING s_txt$
  ULONG  sp 
  
  STRING w_txt$
  ULONG  wp
 
  IFZ search$   THEN RETURN $$FALSE  
  IFZ wildcard$ THEN RETURN $$FALSE
  
  w_txt$ = wildcard$ + "\0\0"   ' Just to be sure
  s_txt$ = search$   + "\0\0"
  
  DO WHILE (s_txt${sp}) && (w_txt${wp} != '*') 
    IF (w_txt${wp} != s_txt${sp} )  && (w_txt${wp} != '?') THEN RETURN $$FALSE
    
    INC wp
    INC sp
  LOOP
    
  DO WHILE (s_txt${sp})
    IF ( w_txt${wp} == '*' ) THEN    
      INC wp
      IF !(w_txt${wp}) THEN RETURN $$TRUE      
      
      mp = wp     
      cp = sp + 1 
    ELSE 
      IF (w_txt${wp} == s_txt${sp} )  || (w_txt${wp} == '?') THEN    
        INC wp
        INC sp
      ELSE
        wp = mp
      
        sp = cp                   
        IF s_txt${sp} THEN INC cp 
       
      ENDIF
    ENDIF  
  LOOP
    
  DO WHILE (w_txt${wp} == '*' )    
    INC wp
  LOOP
  
  RETURN !w_txt${wp} 
 
END FUNCTION

I had converted the wildcmp to C#, it's very easy to wildcard string, thanks so much.

bool WildCompare(string strWild, string strEmail)
{
int cp = 0;
int mp = 0;

int wildIndex = 0;
int emailIndex = 0;

while ((!ValueIsNullOrEmpty(strEmail, emailIndex)) && (ValueAt(strWild, wildIndex) != '*'))
{
if ((ValueAt(strWild, wildIndex) != ValueAt(strEmail, emailIndex)) && (ValueAt(strWild, wildIndex) != '?'))
{
return false;
}
wildIndex++;
emailIndex++;
}

while (!ValueIsNullOrEmpty(strEmail,emailIndex))
{
if (ValueAt( strWild, wildIndex) == '*')
{
wildIndex++;
if (ValueIsNullOrEmpty(strWild,wildIndex ))
{
return true;
}
mp = wildIndex;
cp = emailIndex + 1;
}
else if ((ValueAt(strWild, wildIndex).Equals(ValueAt(strEmail, emailIndex)) || (ValueAt(strWild, wildIndex) == '?')))
{
wildIndex++;
emailIndex++;
}
else
{
wildIndex = mp;
emailIndex = cp++;
}
}

while (ValueAt(strWild, wildIndex) == '*')
{
wildIndex++;
}
return ValueIsNullOrEmpty(strWild, wildIndex);
}

Cry | :((

Well, as direct as I could come up with anyway. Makes use of unsafe to enable pointer arithmetic. Unfortunately, because fixed is required to prevent the GC from moving the pointers, I had to change it to use increment indexers instead of directly manipulating the pointers. Alternatively, you could use stackalloc to instantiate two native char[]'s and copy the values, but that seems contrary to this function's low-memory footprint, high performance goals.

Has been tested against every test case presented in the comments section as well as some additional cases I threw in.

public unsafe static bool GlobCompare( string glob, string path )
{
      fixed ( char* pGlob = glob, pPath = path )
      {
            int pGlobInc = 0;
            int pPathInc = 0;

            int mp = 0;
            int cp = 0;

            while ( ( *( pPath + pPathInc ) != 0 ) && ( *( pGlob + pGlobInc ) != '*' ) )
            {
                  if ( ( *( pGlob + pGlobInc ) != *( pPath + pPathInc ) ) && ( *( pGlob + pGlobInc ) != '?' ) )
                  {
                        return false;
                  }
                  pGlobInc++;
                  pPathInc++;
            }

            while ( *( pPath + pPathInc ) != 0 )
            {
                  if ( *( pGlob + pGlobInc ) == '*' )
                  {
                        if ( 0 == *( pGlob + ++pGlobInc ) )
                        {
                              return true;
                        }
                        mp = pGlobInc;
                        cp = pPathInc + 1;
                  }
                  else if ( ( *( pGlob + pGlobInc ) == *( pPath + pPathInc ) ) || ( *( pGlob + pGlobInc ) == '?' ) )
                  {
                        pGlobInc++;
                        pPathInc++;
                  }
                  else
                  {
                        pGlobInc = mp;
                        pPathInc = cp++;
                  }
            }

            while ( *( pGlob + pGlobInc ) == '*' )
            {
                  pGlobInc++;
            }
            return ( 0 == *( pGlob + pGlobInc ) );
      }
}

Spam message removed
Sign In·Permalink

I am using this in Artistic Style, a popular multi-platform code formatter available at SourceForge.

http://astyle.sourceforge.net/

Release 1.22 added directory recursion to the project. Wildcard processing was made internal to the program. Linux has a glob function but Windows doesn't. I just used this for both of them. It let me process both platforms in a similar manner.

A minor change was made for Windows to make the comparison case insensitive. Linux was left case sensitive.

Thanks for making it available. Using this was a lot easier than writing my own. I doubt that mine would have been this sophisticated.

Boy do I feel stupid. I worked on an algorithm like this for days, and never got it quite right. Then, I see the wonderful, and simplistic work of someone like this, and it reminds me that sometimes we all are guilty of 'over-engineering'... Thanks Mr. Handy!
Sign In·Permalink

How can this code be converted to do a replace? I need to provide a find/replace dialog in an application and I don't want to jump through the hoops of the Boost library. Can anyone help? Patrick
Sign In·Permalink

Here's RegExp version (may be easily ported to C++).
Pros: More readable, Relies on proven RegExp
Cons: Maybe slower?, If eval string contains RegExp keywords then it might result in unexpected result



public static bool Match(string eval, string pattern, bool caseSensitive)

{

	bool match = false;

 

	// Make input parameters lower-case if case is not an issue

	if (!caseSensitive)

	{

		eval = eval.ToLower();

		pattern = pattern.ToLower();

	}

 

	// Escape regexp special character in pattern

	pattern = pattern.Replace(".", @"\.");

 

	// Replace valid wildcards with regexp equivalents

	pattern = pattern.Replace('?', '.').Replace("*", ".*");

 

	// Add boundaries to pattern

	pattern = @"\A" + pattern + @"\z";

 

	// Search for a match

	try

	{

		match = Regex.IsMatch(eval, pattern);

	}

	catch /* (ArgumentException ex) */

	{

		// Syntax error in the regular expression

	}

 

	// Return result

	return match;

}

Sign In·Permalink

This is tight and clever. Thanks for sharing it.
View the reply to this message Sign In·Permalink

Hi, wildcmp("<>", "<field1><field2>") return 1 while I think it should return 0 (I maybe wrong, so please tell me). If someone knows how to fix it, I will appreciate. Regards
View the reply to this message Sign In·Permalink

I think it's better to make the function return a bool value. Anyway, many string comparision functions return 0 when the strings equal.
Sign In·Permalink

if wild = "?.abc", str = "abc.abc" wildcmp(wild, str) not work but if wild = "?.abc", str = "abc.abc" wildcmp(wild, str) do work does anyone have any idea about the case?
View the 2 replies to this message Sign In·Permalink