home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume30 / tin / part10 / wildmat.c < prev   
C/C++ Source or Header  |  1992-05-20  |  5KB  |  176 lines
  1. /*  $Revision: 1.5 $
  2. **
  3. **  Do shell-style pattern matching for ?, \, [], and * characters.
  4. **  Might not be robust in face of malformed patterns; e.g., "foo[a-"
  5. **  could cause a segmentation violation.  It is 8bit clean.
  6. **
  7. **  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
  8. **  Rich $alz is now <rsalz@bbn.com>.
  9. **  April, 1991:  Replaced mutually-recursive calls with in-line code
  10. **  for the star character.
  11. **
  12. **  Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
  13. **  This can greatly speed up failing wildcard patterns.  For example:
  14. **    pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
  15. **    text 1:     -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
  16. **    text 2:     -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
  17. **  Text 1 matches with 51 calls, while text 2 fails with 54 calls.  Without
  18. **  the ABORT, then it takes 22310 calls to fail.  Ugh.  The following
  19. **  explanation is from Lars:
  20. **  The precondition that must be fulfilled is that DoMatch will consume
  21. **  at least one character in text.  This is true if *p is neither '*' nor
  22. **  '\0'.)  The last return has ABORT instead of FALSE to avoid quadratic
  23. **  behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx".  With
  24. **  FALSE, each star-loop has to run to the end of the text; with ABORT
  25. **  only the last one does.
  26. **
  27. **  Once the control of one instance of DoMatch enters the star-loop, that
  28. **  instance will return either TRUE or ABORT, and any calling instance
  29. **  will therefore return immediately after (without calling recursively
  30. **  again).  In effect, only one star-loop is ever active.  It would be
  31. **  possible to modify the code to maintain this context explicitly,
  32. **  eliminating all recursive calls at the cost of some complication and
  33. **  loss of clarity (and the ABORT stuff seems to be unclear enough by
  34. **  itself).  I think it would be unwise to try to get this into a
  35. **  released version unless you have a good test data base to try it out
  36. **  on.
  37. */
  38.  
  39. #define TRUE            1
  40. #define FALSE            0
  41. #define ABORT            -1
  42.  
  43.  
  44.     /* What character marks an inverted character class? */
  45. #define NEGATE_CLASS        '^'
  46.     /* Is "*" a common pattern? */
  47. #define OPTIMIZE_JUST_STAR
  48.     /* Do tar(1) matching rules, which ignore a trailing slash? */
  49. #undef MATCH_TAR_PATTERN
  50.  
  51.  
  52. /*
  53. **  Match text and p, return TRUE, FALSE, or ABORT.
  54. */
  55. static int
  56. DoMatch(text, p)
  57.     register char    *text;
  58.     register char    *p;
  59. {
  60. #ifndef INDEX_DAEMON
  61.  
  62.     register int    last;
  63.     register int    matched;
  64.     register int    reverse;
  65.  
  66.     for ( ; *p; text++, p++) {
  67.     if (*text == '\0' && *p != '*')
  68.         return ABORT;
  69.     switch (*p) {
  70.     case '\\':
  71.         /* Literal match with following character. */
  72.         p++;
  73.         /* FALLTHROUGH */
  74.     default:
  75.         if (*text != *p)
  76.         return FALSE;
  77.         continue;
  78.     case '?':
  79.         /* Match anything. */
  80.         continue;
  81.     case '*':
  82.         while (*++p == '*')
  83.         /* Consecutive stars act just like one. */
  84.         continue;
  85.         if (*p == '\0')
  86.         /* Trailing star matches everything. */
  87.         return TRUE;
  88.         while (*text)
  89.         if ((matched = DoMatch(text++, p)) != FALSE)
  90.             return matched;
  91.         return ABORT;
  92.     case '[':
  93.         reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
  94.         if (reverse)
  95.         /* Inverted character class. */
  96.         p++;
  97.         matched = FALSE;
  98.         if (p[1] == ']' || p[1] == '-')
  99.         if (*++p == *text)
  100.             matched = TRUE;
  101.         for (last = *p; *++p && *p != ']'; last = *p)
  102.         /* This next line requires a good C compiler. */
  103.         if (*p == '-' && p[1] != ']'
  104.             ? *text <= *++p && *text >= last : *text == *p)
  105.             matched = TRUE;
  106.         if (matched == reverse)
  107.         return FALSE;
  108.         continue;
  109.     }
  110.     }
  111.  
  112. #ifdef    MATCH_TAR_PATTERN
  113.     if (*text == '/')
  114.     return TRUE;
  115. #endif    /* MATCH_TAR_ATTERN */
  116.     return *text == '\0';
  117.  
  118. #endif    /* INDEX_DAEMON */
  119. }
  120.  
  121.  
  122. /*
  123. **  User-level routine.  Returns TRUE or FALSE.
  124. */
  125. int
  126. wildmat(text, p)
  127.     char    *text;
  128.     char    *p;
  129. {
  130. #ifdef    OPTIMIZE_JUST_STAR
  131.     if (p[0] == '*' && p[1] == '\0')
  132.     return TRUE;
  133. #endif    /* OPTIMIZE_JUST_STAR */
  134.     return DoMatch(text, p) == TRUE;
  135. }
  136.  
  137.  
  138.  
  139. #ifdef    TEST
  140. #include <stdio.h>
  141.  
  142. /* Yes, we use gets not fgets.  Sue me. */
  143. extern char    *gets();
  144.  
  145.  
  146. main()
  147. {
  148.     char     p[80];
  149.     char     text[80];
  150.  
  151.     printf("Wildmat tester.  Enter pattern, then strings to test.\n");
  152.     printf("A blank line gets prompts for a new pattern; a blank pattern\n");
  153.     printf("exits the program.\n");
  154.  
  155.     for ( ; ; ) {
  156.     printf("\nEnter pattern:  ");
  157.     (void)fflush(stdout);
  158.     if (gets(p) == NULL || p[0] == '\0')
  159.         break;
  160.     for ( ; ; ) {
  161.         printf("Enter text:  ");
  162.         (void)fflush(stdout);
  163.         if (gets(text) == NULL)
  164.         exit(0);
  165.         if (text[0] == '\0')
  166.         /* Blank line; go back and get a new pattern. */
  167.         break;
  168.         printf("      %s\n", wildmat(text, p) ? "YES" : "NO");
  169.     }
  170.     }
  171.  
  172.     exit(0);
  173.     /* NOTREACHED */
  174. }
  175. #endif    /* TEST */
  176.