home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / news / cnews.tar / contrib / lib / wildmat.c < prev   
C/C++ Source or Header  |  1992-06-07  |  5KB  |  167 lines
  1. /*  $Revision: 1.1 $
  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.     register int    last;
  61.     register int    matched;
  62.     register int    reverse;
  63.  
  64.     for ( ; *p; text++, p++) {
  65.     if (*text == '\0' && *p != '*')
  66.         return ABORT;
  67.     switch (*p) {
  68.     case '\\':
  69.         /* Literal match with following character. */
  70.         p++;
  71.         /* FALLTHROUGH */
  72.     default:
  73.         if (*text != *p)
  74.         return FALSE;
  75.         continue;
  76.     case '?':
  77.         /* Match anything. */
  78.         continue;
  79.     case '*':
  80.         while (*++p == '*')
  81.         /* Consecutive stars act just like one. */
  82.         continue;
  83.         if (*p == '\0')
  84.         /* Trailing star matches everything. */
  85.         return TRUE;
  86.         while (*text)
  87.         if ((matched = DoMatch(text++, p)) != FALSE)
  88.             return matched;
  89.         return ABORT;
  90.     case '[':
  91.         reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
  92.         if (reverse)
  93.         /* Inverted character class. */
  94.         p++;
  95.         for (last = 0400, matched = FALSE; *++p && *p != ']'; last = *p)
  96.         /* This next line requires a good C compiler. */
  97.         if (*p == '-' ? *text <= *++p && *text >= last : *text == *p)
  98.             matched = TRUE;
  99.         if (matched == reverse)
  100.         return FALSE;
  101.         continue;
  102.     }
  103.     }
  104.  
  105. #ifdef    MATCH_TAR_PATTERN
  106.     if (*text == '/')
  107.     return TRUE;
  108. #endif    /* MATCH_TAR_ATTERN */
  109.     return *text == '\0';
  110. }
  111.  
  112.  
  113. /*
  114. **  User-level routine.  Returns TRUE or FALSE.
  115. */
  116. int
  117. wildmat(text, p)
  118.     char    *text;
  119.     char    *p;
  120. {
  121. #ifdef    OPTIMIZE_JUST_STAR
  122.     if (p[0] == '*' && p[1] == '\0')
  123.     return TRUE;
  124. #endif    /* OPTIMIZE_JUST_STAR */
  125.     return DoMatch(text, p) == TRUE;
  126. }
  127.  
  128.  
  129.  
  130. #ifdef    TEST
  131. #include <stdio.h>
  132.  
  133. /* Yes, we use gets not fgets.  Sue me. */
  134. extern char    *gets();
  135.  
  136.  
  137. main()
  138. {
  139.     char     p[80];
  140.     char     text[80];
  141.  
  142.     printf("Wildmat tester.  Enter pattern, then strings to test.\n");
  143.     printf("A blank line gets prompts for a new pattern; a blank pattern\n");
  144.     printf("exits the program.\n");
  145.  
  146.     for ( ; ; ) {
  147.     printf("\nEnter pattern:  ");
  148.     (void)fflush(stdout);
  149.     if (gets(p) == NULL || p[0] == '\0')
  150.         break;
  151.     for ( ; ; ) {
  152.         printf("Enter text:  ");
  153.         (void)fflush(stdout);
  154.         if (gets(text) == NULL)
  155.         exit(0);
  156.         if (text[0] == '\0')
  157.         /* Blank line; go back and get a new pattern. */
  158.         break;
  159.         printf("      %s\n", wildmat(text, p) ? "YES" : "NO");
  160.     }
  161.     }
  162.  
  163.     exit(0);
  164.     /* NOTREACHED */
  165. }
  166. #endif    /* TEST */
  167.