home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 2 / 2857 < prev    next >
Encoding:
Internet Message Format  |  1991-02-26  |  7.3 KB
  1. From: bernie@metapro.DIALix.oz.au (Bernd Felsche)
  2. Newsgroups: alt.sources
  3. Subject: wildmat.c, with less bugs
  4. Message-ID: <1991Feb25.092530.6885@metapro.DIALix.oz.au>
  5. Date: 25 Feb 91 09:25:30 GMT
  6.  
  7. Thanks to the vigilance of:
  8.     Jim Dumser <jmd@ee.umr.edu>
  9. and
  10.     Bernd Raichle <raichle@azu.informatik.uni-stuttgart.de>
  11.  
  12. another bug has been exterminated. Funny how these things crop up in
  13. source code one adopts.
  14.  
  15. Jim pointed out that the routine didn't even work for the supplied
  16. examples, and Bernd (not me, the other one), pointed out the ?*? came
  17. up TRUE on matching with "a".
  18.  
  19. Thanks guys. And again thanks to Rich Salz for posting the original
  20. bugs... oops, I mean, source :-)
  21.  
  22. Bernd actually worked out how the routine works and suggested a fix
  23. which I had already implemented and sent to Jim for checking. Jim
  24. hasn't complained yet so .....
  25.  
  26. Here's the updated code.
  27.  
  28. ______________________cut with diamond along here_______________________
  29.  
  30. /*
  31. **  Do shell-style pattern matching for ?, \, [], and * characters.
  32. **  Might not be robust in face of malformed patterns; e.g., "foo[a-"
  33. **  could cause a segmentation violation.  It is 8bit clean.
  34. **
  35. **  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
  36. **  Special thanks to Lars Mathiesen for the ABORT code.  This can greatly
  37. **  speed up failing wildcard patterns.  For example:
  38. **    pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
  39. **    text 1:     -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
  40. **    text 2:     -adobe-courier-bold-o-normal--12-120-75-75-p-70-iso8859-1
  41. **  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
  42. **  the ABORT, then it takes 22310 calls to fail.  Ugh.
  43. **
  44. **  bernie    613-01 91/01/04 19:34 
  45. **  Fixed problem with terminating * not matching with (null)
  46. **
  47. **  bernie    597-00 91/01/08 11:24 
  48. **  Fixed shell glob negate from '^' to '!'
  49. **
  50. **  bernie    597-02 91/01/21 13:43 
  51. **    Fixed . matching * or ? on first char.
  52. **
  53.  *  bernie      1-00 91/02/14 10:28 
  54. **    Fixed Star return on ABORT
  55. */
  56.  
  57. #define TRUE        1
  58. #define FALSE        0
  59. #define ABORT        -1
  60.  
  61. static int count;
  62.  
  63. static int
  64. Star(s, p)
  65.     register char    *s;
  66.     register char    *p;
  67. {
  68.     register int stat;
  69.  
  70.     while ( (stat=DoMatch(s, p)) == FALSE) /* gobble up * match */
  71.     if (*++s == '\0') return ABORT;
  72.     return stat;
  73. }
  74.  
  75.  
  76. static int
  77. DoMatch(s, p)    /* match string "s" to pattern "p" */
  78.     register char    *s;
  79.     register char    *p;
  80. {
  81.     register int      last;
  82.     register int      matched;
  83.     register int      reverse;
  84.  
  85.     count++;
  86.  
  87.     for ( ; *p; s++, p++) { /* parse the string to end */
  88.     if (*s == '\0')
  89.         return *p == '*' && *++p == '\0' ? TRUE : ABORT;
  90.  
  91.     switch (*p) { /* parse pattern */
  92.  
  93.     case '\\':
  94.         /* Literal match with following character. */
  95.         p++;
  96.         /* FALLTHROUGH */
  97.  
  98.     default: /*literal match*/
  99.         if (*s != *p)
  100.         return FALSE;
  101.         continue;
  102.  
  103.     case '?':
  104.         /* Match anything. */
  105.         continue;
  106.  
  107.     case '*':
  108.         /* Trailing star matches everything. */
  109.         return( *++p ? Star(s, p) : TRUE );
  110.  
  111.     case '[':
  112.         /* [!....] means inverse character class. */
  113.         if (reverse = p[1] == '!') p++;
  114.  
  115.         for (last = 0400, matched = FALSE; *++p && *p != ']'; last = *p)
  116.         /* This next line requires a good C compiler. */
  117.         /*     range?        (in bounds)                  (equal) */
  118.         if ( ( *p == '-' ) ? (*s <= *++p && *s >= last ) : (*s == *p) )
  119.             matched = TRUE;
  120.  
  121.         if (matched == reverse) return FALSE;
  122.         continue;
  123.     }
  124.     }
  125.     return *s == '\0';
  126. }
  127.  
  128.  
  129. int wildmat(s, p)
  130.     char    *s;
  131.     char    *p;
  132. {
  133.     if ( (*p == '?' || *p == '*' ) && *s == '.' ) {
  134.         return FALSE;
  135.     } else {
  136.         return DoMatch(s, p) == TRUE;
  137.     }
  138. }
  139.  
  140.  
  141. char pattern[] = "-*-*-*-*-*-*-12-*-*-*-m-*-*-*",
  142.      text1[] = "-adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1",
  143.      text2[] = "-adobe-courier-bold-o-normal--12-120-75-75-p-70-iso8859-1";
  144.  
  145. main()
  146. {
  147.     int result;
  148.  
  149.     count= 0; result = wildmat(text1,pattern);
  150.     printf("%s\n%s\n%s %d\n",
  151.         text1, pattern, ( result ? "TRUE" : "FALSE" ), count);
  152.  
  153.     count = 0; result = wildmat(text2,pattern);
  154.     printf("%s\n%s\n%s %d\n",
  155.         text2, pattern, ( result ? "TRUE" : "FALSE" ), count);
  156. }
  157.  
  158. /*
  159. **  Do shell-style pattern matching for ?, \, [], and * characters.
  160. **  Might not be robust in face of malformed patterns; e.g., "foo[a-"
  161. **  could cause a segmentation violation.  It is 8bit clean.
  162. **
  163. **  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
  164. **  Special thanks to Lars Mathiesen for the ABORT code.  This can greatly
  165. **  speed up failing wildcard patterns.  For example:
  166. **    pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
  167. **    text 1:     -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
  168. **    text 2:     -adobe-courier-bold-o-normal--12-120-75-75-p-70-iso8859-1
  169. **  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
  170. **  the ABORT, then it takes 22310 calls to fail.  Ugh.
  171. **
  172. **  bernie    613-01 91/01/04 19:34 
  173. **  Fixed problem with terminating * not matching with (null)
  174. **
  175. **  bernie    597-00 91/01/08 11:24 
  176. **  Fixed shell glob negate from '^' to '!'
  177. **
  178. **  bernie    597-02 91/01/21 13:43 
  179. **    Fixed . matching * or ? on first char.
  180. */
  181.  
  182. #define TRUE        1
  183. #define FALSE        0
  184. #define ABORT        -1
  185.  
  186. static int count;
  187.  
  188. static int
  189. Star(s, p)
  190.     register char    *s;
  191.     register char    *p;
  192. {
  193.     register int stat;
  194.  
  195.     while ( (stat=DoMatch(s, p)) == FALSE) /* gobble up * match */
  196.     if (*++s == '\0') return ABORT;
  197.     return stat;
  198. }
  199.  
  200.  
  201. static int
  202. DoMatch(s, p)    /* match string "s" to pattern "p" */
  203.     register char    *s;
  204.     register char    *p;
  205. {
  206.     register int      last;
  207.     register int      matched;
  208.     register int      reverse;
  209.  
  210.     count++;
  211.  
  212.     for ( ; *p; s++, p++) { /* parse the string to end */
  213.     if (*s == '\0')
  214.         return *p == '*' && *++p == '\0' ? TRUE : ABORT;
  215.  
  216.     switch (*p) { /* parse pattern */
  217.  
  218.     case '\\':
  219.         /* Literal match with following character. */
  220.         p++;
  221.         /* FALLTHROUGH */
  222.  
  223.     default: /*literal match*/
  224.         if (*s != *p)
  225.         return FALSE;
  226.         continue;
  227.  
  228.     case '?':
  229.         /* Match anything. */
  230.         continue;
  231.  
  232.     case '*':
  233.         /* Trailing star matches everything. */
  234.         return( *++p ? Star(s, p) : TRUE );
  235.  
  236.     case '[':
  237.         /* [!....] means inverse character class. */
  238.         if (reverse = p[1] == '!') p++;
  239.  
  240.         for (last = 0400, matched = FALSE; *++p && *p != ']'; last = *p)
  241.         /* This next line requires a good C compiler. */
  242.         /*     range?        (in bounds)                  (equal) */
  243.         if ( ( *p == '-' ) ? (*s <= *++p && *s >= last ) : (*s == *p) )
  244.             matched = TRUE;
  245.  
  246.         if (matched == reverse) return FALSE;
  247.         continue;
  248.     }
  249.     }
  250.     return *s == '\0';
  251. }
  252.  
  253.  
  254. int wildmat(s, p)
  255.     char    *s;
  256.     char    *p;
  257. {
  258.     if ( (*p == '?' || *p == '*' ) && *s == '.' ) {
  259.         return FALSE;
  260.     } else {
  261.         return DoMatch(s, p) == TRUE;
  262.     }
  263. }
  264.  
  265. /* here's the bonus test program */
  266.  
  267. char pattern[] = "-*-*-*-*-*-*-12-*-*-*-m-*-*-*",
  268.      text1[] = "-adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1",
  269.      text2[] = "-adobe-courier-bold-o-normal--12-120-75-75-p-70-iso8859-1";
  270.  
  271. main()
  272. {
  273.     int result;
  274.  
  275.     count= 0; result = wildmat(text1,pattern);
  276.     printf("%s\n%s\n%s %d\n",
  277.         text1, pattern, ( result ? "TRUE" : "FALSE" ), count);
  278.  
  279.     count = 0; result = wildmat(text2,pattern);
  280.     printf("%s\n%s\n%s %d\n",
  281.         text2, pattern, ( result ? "TRUE" : "FALSE" ), count);
  282. }
  283. -- 
  284. Bernd Felsche,                 _--_|\   #include <std/disclaimer.h>
  285. Metapro Systems,              / sale \  Fax:   +61 9 472 3337
  286. 328 Albany Highway,           \_.--._/  Phone: +61 9 362 9355
  287. Victoria Park,  Western Australia   v   Email: bernie@metapro.DIALix.oz.au
  288.