home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume7 / read-vms-backs / match.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-01-19  |  6.6 KB  |  313 lines
  1. #include <stdio.h>
  2. #include <sys/types.h>
  3.  
  4. #define ASTERISK '*'        /* The '*' metacharacter */
  5. #define QUESTION '?'        /* The '?' metacharacter */
  6. #define LEFT_BRACKET '['    /* The '[' metacharacter */
  7. #define RIGHT_BRACKET ']'    /* The ']' metacharacter */
  8.  
  9. #define IS_OCTAL(ch) (ch >= '0' && ch <= '7')
  10.  
  11. typedef int BOOLEAN;
  12. #define VOID void
  13. #define TRUE 1
  14. #define FALSE 0
  15. #define EOS '\000'
  16.  
  17. static BOOLEAN do_list ();
  18. static char nextch ();
  19. static VOID list_parse ();
  20.  
  21.  
  22. /*
  23.  *  FUNCTION
  24.  *
  25.  *    match    test string for wildcard match
  26.  *
  27.  *  SYNOPSIS
  28.  *
  29.  *    BOOLEAN match (string, pattern)
  30.  *    register char *string;
  31.  *    register char *pattern;
  32.  *
  33.  *  DESCRIPTION
  34.  *
  35.  *    Test string for match using pattern.  The pattern may
  36.  *    contain the normal shell metacharacters for pattern
  37.  *    matching.  The '*' character matches any string,
  38.  *    including the null string.  The '?' character matches
  39.  *    any single character.  A list of characters enclosed
  40.  *    in '[' and ']' matches any character in the list.
  41.  *    If the first character following the beginning '['
  42.  *    is a '!' then any character not in the list is matched.
  43.  *
  44.  */
  45.  
  46.  
  47. /*
  48.  *  PSEUDO CODE
  49.  *
  50.  *    Begin match
  51.  *        Switch on type of pattern character
  52.  *        Case ASTERISK:
  53.  *            Attempt to match asterisk
  54.  *            Break
  55.  *        Case QUESTION MARK:
  56.  *            Attempt to match question mark
  57.  *            Break
  58.  *        Case EOS:
  59.  *            Match is result of EOS on string test
  60.  *            Break
  61.  *        Case default:
  62.  *            If explicit match then
  63.  *            Match is result of submatch
  64.  *            Else
  65.  *            Match is FALSE
  66.  *            End if
  67.  *            Break
  68.  *        End switch
  69.  *        Return result of match test
  70.  *    End match
  71.  *
  72.  */
  73.  
  74. BOOLEAN match (string, pattern)
  75. register char *string;
  76. register char *pattern;
  77. {
  78.     register BOOLEAN ismatch;
  79.  
  80.     ismatch = FALSE;
  81.     switch (*pattern) {
  82.     case ASTERISK:
  83.         pattern++;
  84.         do {
  85.         ismatch = match (string, pattern);
  86.         } while (!ismatch && *string++ != EOS);
  87.         break;
  88.     case QUESTION:
  89.         if (*string != EOS) {
  90.         ismatch = match (++string, ++pattern);
  91.         }
  92.         break;
  93.     case EOS:
  94.         if (*string == EOS) {
  95.         ismatch = TRUE;
  96.         }
  97.         break;
  98.     case LEFT_BRACKET:
  99.         if (*string != EOS) {
  100.         ismatch = do_list (string, pattern);
  101.         }
  102.         break;
  103.     default:
  104.         if (*string++ == *pattern++) {
  105.         ismatch = match (string, pattern);
  106.         } else {
  107.         ismatch = FALSE;
  108.         }
  109.         break;
  110.     }
  111.     return (ismatch);
  112. }
  113.  
  114.  
  115. /*
  116.  *  FUNCTION
  117.  *
  118.  *    do_list    process a list and following substring
  119.  *
  120.  *  SYNOPSIS
  121.  *
  122.  *    static BOOLEAN do_list (string, pattern)
  123.  *    register char *string;
  124.  *    register char *pattern;
  125.  *
  126.  *  DESCRIPTION
  127.  *
  128.  *    Called when a list is found in the pattern.  Returns
  129.  *    TRUE if the current character matches the list and
  130.  *    the remaining substring matches the remaining pattern.
  131.  *
  132.  *    Returns FALSE if either the current character fails to
  133.  *    match the list or the list matches but the remaining
  134.  *    substring and subpattern's don't.
  135.  *
  136.  *  RESTRICTIONS
  137.  *
  138.  *    The mechanism used to match characters in an inclusive
  139.  *    pair (I.E. [a-d]) may not be portable to machines
  140.  *    in which the native character set is not ASCII.
  141.  *
  142.  *    The rules implemented here are:
  143.  *
  144.  *        (1)    The backslash character may be
  145.  *            used to quote any special character.
  146.  *            I.E.  "\]" and "\-" anywhere in list,
  147.  *            or "\!" at start of list.
  148.  *
  149.  *        (2)    The sequence \nnn becomes the character
  150.  *            given by nnn (in octal).
  151.  *
  152.  *        (3)    Any non-escaped ']' marks the end of list.
  153.  *
  154.  *        (4)    A list beginning with the special character
  155.  *            '!' matches any character NOT in list.
  156.  *            The '!' character is only special if it
  157.  *            is the first character in the list.
  158.  *
  159.  */
  160.  
  161.  
  162. /*
  163.  *  PSEUDO CODE
  164.  *
  165.  *    Begin do_list
  166.  *        Default result is no match
  167.  *        Skip over the opening left bracket
  168.  *        If the next pattern character is a '!' then
  169.  *        List match gives FALSE
  170.  *        Skip over the '!' character
  171.  *        Else
  172.  *        List match gives TRUE
  173.  *        End if
  174.  *        While not at closing bracket or EOS
  175.  *        Get lower and upper bounds
  176.  *        If character in bounds then
  177.  *            Result is same as sense flag.
  178.  *            Skip over rest of list
  179.  *        End if
  180.  *        End while
  181.  *        If match found then
  182.  *        If not at end of pattern then
  183.  *            Call match with rest of pattern
  184.  *        End if
  185.  *        End if
  186.  *        Return match result
  187.  *    End do_list
  188.  *
  189.  */
  190.  
  191. static BOOLEAN do_list (string, pattern)
  192. register char *string;
  193. char *pattern;
  194. {
  195.     register BOOLEAN ismatch;
  196.     register BOOLEAN if_found;
  197.     register BOOLEAN if_not_found;
  198.     auto char lower;
  199.     auto char upper;
  200.  
  201.     pattern++;
  202.     if (*pattern == '!') {
  203.     if_found = FALSE;
  204.     if_not_found = TRUE;
  205.     pattern++;
  206.     } else {
  207.     if_found = TRUE;
  208.     if_not_found = FALSE;
  209.     }
  210.     ismatch = if_not_found;
  211.     while (*pattern != ']' && *pattern != EOS) {
  212.     list_parse (&pattern, &lower, &upper);
  213.     if (*string >= lower && *string <= upper) {
  214.         ismatch = if_found;
  215.         while (*pattern != ']' && *pattern != EOS) {pattern++;}
  216.     }
  217.     }
  218.     if (*pattern++ != ']') {
  219.     fprintf (stderr, "warning - character class error\n");
  220.     } else {
  221.     if (ismatch) {
  222.         ismatch = match (++string, pattern);
  223.     }
  224.     }
  225.     return (ismatch);
  226. }
  227.  
  228.  
  229. /*
  230.  *  FUNCTION
  231.  *
  232.  *    list_parse    parse part of list into lower and upper bounds
  233.  *
  234.  *  SYNOPSIS
  235.  *
  236.  *    static VOID list_parse (patp, lowp, highp)
  237.  *    char **patp;
  238.  *    char *lowp;
  239.  *    char *highp;
  240.  *
  241.  *  DESCRIPTION
  242.  *
  243.  *    Given pointer to a pattern pointer (patp), pointer to
  244.  *    a place to store lower bound (lowp), and pointer to a
  245.  *    place to store upper bound (highp), parses part of
  246.  *    the list, updating the pattern pointer in the process.
  247.  *
  248.  *    For list characters which are not part of a range,
  249.  *    the lower and upper bounds are set to that character.
  250.  *
  251.  */
  252.  
  253. static VOID list_parse (patp, lowp, highp)
  254. char **patp;
  255. char *lowp;
  256. char *highp;
  257. {
  258.     *lowp = nextch (patp);
  259.     if (**patp == '-') {
  260.     (*patp)++;
  261.     *highp = nextch (patp);
  262.     } else {
  263.     *highp = *lowp;
  264.     }
  265. }
  266.  
  267.  
  268. /*
  269.  *  FUNCTION
  270.  *
  271.  *    nextch      determine next character in a pattern
  272.  *
  273.  *  SYNOPSIS
  274.  *
  275.  *    static char nextch (patp)
  276.  *    char **patp;
  277.  *
  278.  *  DESCRIPTION
  279.  *
  280.  *    Given pointer to a pointer to a pattern, uses the pattern
  281.  *    pointer to determine the next character in the pattern,
  282.  *    subject to translation of backslash-char and backslash-octal
  283.  *    sequences.
  284.  *
  285.  *    The character pointer is updated to point at the next pattern
  286.  *    character to be processed.
  287.  *
  288.  */
  289.  
  290. static char nextch (patp)
  291. char **patp;
  292. {
  293.     register char ch;
  294.     register char chsum;
  295.     register int count;
  296.  
  297.     ch = *(*patp)++;
  298.     if (ch == '\\') {
  299.     ch = *(*patp)++;
  300.     if (IS_OCTAL (ch)) {
  301.         chsum = 0;
  302.         for (count = 0; count < 3 && IS_OCTAL (ch); count++) {
  303.         chsum *= 8;
  304.         chsum += ch - '0';
  305.         ch = *(*patp)++;
  306.         }
  307.         (*patp)--;
  308.         ch = chsum;
  309.     }
  310.     }
  311.     return (ch);
  312. }
  313.