Path: utzoo!utgpu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!rpi!batcomputer!munnari.oz.au!uniwa!DIALix!metapro!bernie From: bernie@metapro.DIALix.oz.au (Bernd Felsche) Newsgroups: alt.sources Subject: wildmat.c, with less bugs Summary: wildmat with another bug squashed Keywords: wildmat, repost Message-ID: <1991Feb25.092530.6885@metapro.DIALix.oz.au> Date: 25 Feb 91 09:25:30 GMT Organization: MetaPro Systems, Perth, Western Australia Lines: 281 Thanks to the vigilance of: Jim Dumser and Bernd Raichle another bug has been exterminated. Funny how these things crop up in source code one adopts. Jim pointed out that the routine didn't even work for the supplied examples, and Bernd (not me, the other one), pointed out the ?*? came up TRUE on matching with "a". Thanks guys. And again thanks to Rich Salz for posting the original bugs... oops, I mean, source :-) Bernd actually worked out how the routine works and suggested a fix which I had already implemented and sent to Jim for checking. Jim hasn't complained yet so ..... Here's the updated code. ______________________cut with diamond along here_______________________ /* ** Do shell-style pattern matching for ?, \, [], and * characters. ** Might not be robust in face of malformed patterns; e.g., "foo[a-" ** could cause a segmentation violation. It is 8bit clean. ** ** Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986. ** Special thanks to Lars Mathiesen for the ABORT code. This can greatly ** speed up failing wildcard patterns. For example: ** pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-* ** text 1: -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1 ** text 2: -adobe-courier-bold-o-normal--12-120-75-75-p-70-iso8859-1 ** Text 1 matches with 51 calls, while text 2 fails with 54 calls. Without ** the ABORT, then it takes 22310 calls to fail. Ugh. ** ** bernie 613-01 91/01/04 19:34 ** Fixed problem with terminating * not matching with (null) ** ** bernie 597-00 91/01/08 11:24 ** Fixed shell glob negate from '^' to '!' ** ** bernie 597-02 91/01/21 13:43 ** Fixed . matching * or ? on first char. ** * bernie 1-00 91/02/14 10:28 ** Fixed Star return on ABORT */ #define TRUE 1 #define FALSE 0 #define ABORT -1 static int count; static int Star(s, p) register char *s; register char *p; { register int stat; while ( (stat=DoMatch(s, p)) == FALSE) /* gobble up * match */ if (*++s == '\0') return ABORT; return stat; } static int DoMatch(s, p) /* match string "s" to pattern "p" */ register char *s; register char *p; { register int last; register int matched; register int reverse; count++; for ( ; *p; s++, p++) { /* parse the string to end */ if (*s == '\0') return *p == '*' && *++p == '\0' ? TRUE : ABORT; switch (*p) { /* parse pattern */ case '\\': /* Literal match with following character. */ p++; /* FALLTHROUGH */ default: /*literal match*/ if (*s != *p) return FALSE; continue; case '?': /* Match anything. */ continue; case '*': /* Trailing star matches everything. */ return( *++p ? Star(s, p) : TRUE ); case '[': /* [!....] means inverse character class. */ if (reverse = p[1] == '!') p++; for (last = 0400, matched = FALSE; *++p && *p != ']'; last = *p) /* This next line requires a good C compiler. */ /* range? (in bounds) (equal) */ if ( ( *p == '-' ) ? (*s <= *++p && *s >= last ) : (*s == *p) ) matched = TRUE; if (matched == reverse) return FALSE; continue; } } return *s == '\0'; } int wildmat(s, p) char *s; char *p; { if ( (*p == '?' || *p == '*' ) && *s == '.' ) { return FALSE; } else { return DoMatch(s, p) == TRUE; } } char pattern[] = "-*-*-*-*-*-*-12-*-*-*-m-*-*-*", text1[] = "-adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1", text2[] = "-adobe-courier-bold-o-normal--12-120-75-75-p-70-iso8859-1"; main() { int result; count= 0; result = wildmat(text1,pattern); printf("%s\n%s\n%s %d\n", text1, pattern, ( result ? "TRUE" : "FALSE" ), count); count = 0; result = wildmat(text2,pattern); printf("%s\n%s\n%s %d\n", text2, pattern, ( result ? "TRUE" : "FALSE" ), count); } /* ** Do shell-style pattern matching for ?, \, [], and * characters. ** Might not be robust in face of malformed patterns; e.g., "foo[a-" ** could cause a segmentation violation. It is 8bit clean. ** ** Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986. ** Special thanks to Lars Mathiesen for the ABORT code. This can greatly ** speed up failing wildcard patterns. For example: ** pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-* ** text 1: -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1 ** text 2: -adobe-courier-bold-o-normal--12-120-75-75-p-70-iso8859-1 ** Text 1 matches with 51 calls, while text 2 fails with 54 calls. Without ** the ABORT, then it takes 22310 calls to fail. Ugh. ** ** bernie 613-01 91/01/04 19:34 ** Fixed problem with terminating * not matching with (null) ** ** bernie 597-00 91/01/08 11:24 ** Fixed shell glob negate from '^' to '!' ** ** bernie 597-02 91/01/21 13:43 ** Fixed . matching * or ? on first char. */ #define TRUE 1 #define FALSE 0 #define ABORT -1 static int count; static int Star(s, p) register char *s; register char *p; { register int stat; while ( (stat=DoMatch(s, p)) == FALSE) /* gobble up * match */ if (*++s == '\0') return ABORT; return stat; } static int DoMatch(s, p) /* match string "s" to pattern "p" */ register char *s; register char *p; { register int last; register int matched; register int reverse; count++; for ( ; *p; s++, p++) { /* parse the string to end */ if (*s == '\0') return *p == '*' && *++p == '\0' ? TRUE : ABORT; switch (*p) { /* parse pattern */ case '\\': /* Literal match with following character. */ p++; /* FALLTHROUGH */ default: /*literal match*/ if (*s != *p) return FALSE; continue; case '?': /* Match anything. */ continue; case '*': /* Trailing star matches everything. */ return( *++p ? Star(s, p) : TRUE ); case '[': /* [!....] means inverse character class. */ if (reverse = p[1] == '!') p++; for (last = 0400, matched = FALSE; *++p && *p != ']'; last = *p) /* This next line requires a good C compiler. */ /* range? (in bounds) (equal) */ if ( ( *p == '-' ) ? (*s <= *++p && *s >= last ) : (*s == *p) ) matched = TRUE; if (matched == reverse) return FALSE; continue; } } return *s == '\0'; } int wildmat(s, p) char *s; char *p; { if ( (*p == '?' || *p == '*' ) && *s == '.' ) { return FALSE; } else { return DoMatch(s, p) == TRUE; } } /* here's the bonus test program */ char pattern[] = "-*-*-*-*-*-*-12-*-*-*-m-*-*-*", text1[] = "-adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1", text2[] = "-adobe-courier-bold-o-normal--12-120-75-75-p-70-iso8859-1"; main() { int result; count= 0; result = wildmat(text1,pattern); printf("%s\n%s\n%s %d\n", text1, pattern, ( result ? "TRUE" : "FALSE" ), count); count = 0; result = wildmat(text2,pattern); printf("%s\n%s\n%s %d\n", text2, pattern, ( result ? "TRUE" : "FALSE" ), count); } -- Bernd Felsche, _--_|\ #include Metapro Systems, / sale \ Fax: +61 9 472 3337 328 Albany Highway, \_.--._/ Phone: +61 9 362 9355 Victoria Park, Western Australia v Email: bernie@metapro.DIALix.oz.au Brought to you by Super Global Mega Corp .com