-h- match.c Thu May 30 19:20:13 1985 MATCH.C;1 /* SCCS id: @(#) match.c 1.3 Last edit: 1/16/85 at 21:18:57 Retrieved: 1/16/85 at 21:19:58 SCCS archive: /vld/moss/work/libWIND/s.match.c Author: Gary S. Moss U. S. Army Ballistic Research Laboratory Aberdeen Proving Ground Maryland 21005-5066 (301)278-6647 or AV-283-6647 */ static char sccsTag[] = "@(#) match.c 1.3 last edit 1/16/85 at 21:18:57"; #include #include #include "./ascii.h" extern void prnt1Err(); /* m a t c h ( ) if string matches pattern, return 1, else return 0 special characters: * Matches any string including the null string. ? Matches any single character. [...] Matches any one of the characters enclosed. [!..] Matchea any character NOT enclosed. - May be used inside brackets to specify range (i.e. str[1-58] matches str1, str2, ... str5, str8) \ Escapes special characters. */ match( pattern, string ) register char *pattern, *string; { do { switch( pattern[0] ) { case '*': /* Match any string including null string. */ if( pattern[1] == NUL || string[0] == NUL ) return 1; while( string[0] != NUL ) { if( match( &pattern[1], string ) ) return 1; ++string; } return 0; case '?': /* Match any character. */ break; case '[': /* Match one of the characters in brackets unless first is a '!', then match any character not inside brackets. */ { register char *rgtBracket; static int negation; ++pattern; /* Skip over left bracket. */ /* Find matching right bracket. */ if( (rgtBracket = strchr( pattern, ']' )) == NULL ) { prnt1Err( "Unmatched '['." ); return 0; } /* Check for negation operator. */ if( pattern[0] == '!' ) { ++pattern; negation = 1; } else { negation = 0; } /* Traverse pattern inside brackets. */ for( ; pattern < rgtBracket && pattern[0] != string[0]; ++pattern ) { if( pattern[ 0] == '-' && pattern[-1] != '\\' ) { if( pattern[-1] <= string[0] && pattern[-1] != '[' && pattern[ 1] >= string[0] && pattern[ 1] != ']' ) break; } } if( pattern == rgtBracket ) { if( ! negation ) { return 0; } } else { if( negation ) { return 0; } } pattern = rgtBracket; /* Skip to right bracket. */ break; } case '\\': /* Escape special character. */ ++pattern; /* WARNING: falls through to default case. */ default: /* Compare characters. */ if( pattern[0] != string[0] ) return 0; } ++pattern; ++string; } while( pattern[0] != NUL && string[0] != NUL ); if( (pattern[0] == NUL || pattern[0] == '*' ) && string[0] == NUL ) { return 1; } else { return 0; } } -h- matchtest.c Thu May 30 19:20:13 1985 MATCHTEST.C;1 /* SCCS id: @(#) matchtest.c 1.2 Last edit: 1/16/85 at 21:19:12 Retrieved: 1/16/85 at 21:20:06 SCCS archive: /vld/moss/work/libWIND/s.matchtest.c Author: Gary S. Moss U. S. Army Ballistic Research Laboratory Aberdeen Proving Ground Maryland 21005-5066 (301)278-6647 or AV-283-6647 */ #if ! defined( lint ) static char sccsTag[] = "@(#) matchtest.c 1.2 last edit 1/16/85 at 21:19:12"; #endif #include extern int match(); char *usage[] = { "", "matchtest(1.2)", "", "Usage: matchtest [pattern string]", "", "If no arguments are given, the program reads words on its standard input.", "The program writes to its standard output.", 0 }; void prntUsage(), prnt1Err(); static char *pattern, *string; static char patbuf[BUFSIZ], strbuf[BUFSIZ]; /* m a i n ( ) */ main( argc, argv ) char *argv[]; { if( ! parsArgv( argc, argv ) ) { prntUsage(); exit( 1 ); } if( pattern != NULL ) { if( match( pattern, string ) ) { (void) printf( "'%s' matches '%s'.\n", pattern, string ); exit( 0 ); } else { (void) printf( "'%s' does not match '%s'.\n", pattern, string ); exit( 1 ); } } while( scanf( "%s %s", patbuf, strbuf ) == 2 ) { if( match( patbuf, strbuf ) ) { (void) printf( "'%s' matches '%s'.\n", patbuf, strbuf ); } else { (void) printf( "'%s' does not match '%s'.\n", patbuf, strbuf ); } } exit( 0 ); } /* p a r s A r g v ( ) */ parsArgv( argc, argv ) register char **argv; { register int c; extern int optind; extern char *optarg; /* Parse options. */ while( (c = getopt( argc, argv, "" )) != EOF ) { switch( c ) { case '?' : return 0; } } if( argc - optind != 2 ) { if( argc == optind ) { pattern = string = NULL; } else { (void) fprintf( stderr, "Arg count wrong!\n" ); return 0; } } else { pattern = argv[optind++]; string = argv[optind++]; } return 1; } /* p r n t U s a g e ( ) Print usage message. */ void prntUsage() { register char **p = usage; while( *p ) (void) fprintf( stderr, "%s\n", *p++ ); return; } -h- nmatch.c Thu May 30 19:20:13 1985 NMATCH.C;1 #include #include #define ASTERISK '*' /* The '*' metacharacter */ #define QUESTION '?' /* The '?' metacharacter */ #define LEFT_BRACKET '[' /* The '[' metacharacter */ #define RIGHT_BRACKET ']' /* The ']' metacharacter */ #define IS_OCTAL(ch) (ch >= '0' && ch <= '7') typedef int BOOLEAN; #define VOID void #define TRUE 1 #define FALSE 0 #define EOS '\000' static BOOLEAN do_list (); static char nextch (); static VOID list_parse (); /* * FUNCTION * * match test string for wildcard match * * SYNOPSIS * * BOOLEAN match (string, pattern) * register char *string; * register char *pattern; * * DESCRIPTION * * Test string for match using pattern. The pattern may * contain the normal shell metacharacters for pattern * matching. The '*' character matches any string, * including the null string. The '?' character matches * any single character. A list of characters enclosed * in '[' and ']' matches any character in the list. * If the first character following the beginning '[' * is a '!' then any character not in the list is matched. * */ /* * PSEUDO CODE * * Begin match * Switch on type of pattern character * Case ASTERISK: * Attempt to match asterisk * Break * Case QUESTION MARK: * Attempt to match question mark * Break * Case EOS: * Match is result of EOS on string test * Break * Case default: * If explicit match then * Match is result of submatch * Else * Match is FALSE * End if * Break * End switch * Return result of match test * End match * */ BOOLEAN match (string, pattern) register char *string; register char *pattern; { register BOOLEAN ismatch; ismatch = FALSE; switch (*pattern) { case ASTERISK: pattern++; do { ismatch = match (string, pattern); } while (!ismatch && *string++ != EOS); break; case QUESTION: if (*string != EOS) { ismatch = match (++string, ++pattern); } break; case EOS: if (*string == EOS) { ismatch = TRUE; } break; case LEFT_BRACKET: if (*string != EOS) { ismatch = do_list (string, pattern); } break; default: if (*string++ == *pattern++) { ismatch = match (string, pattern); } else { ismatch = FALSE; } break; } return (ismatch); } /* * FUNCTION * * do_list process a list and following substring * * SYNOPSIS * * static BOOLEAN do_list (string, pattern) * register char *string; * register char *pattern; * * DESCRIPTION * * Called when a list is found in the pattern. Returns * TRUE if the current character matches the list and * the remaining substring matches the remaining pattern. * * Returns FALSE if either the current character fails to * match the list or the list matches but the remaining * substring and subpattern's don't. * * RESTRICTIONS * * The mechanism used to match characters in an inclusive * pair (I.E. [a-d]) may not be portable to machines * in which the native character set is not ASCII. * * The rules implemented here are: * * (1) The backslash character may be * used to quote any special character. * I.E. "\]" and "\-" anywhere in list, * or "\!" at start of list. * * (2) The sequence \nnn becomes the character * given by nnn (in octal). * * (3) Any non-escaped ']' marks the end of list. * * (4) A list beginning with the special character * '!' matches any character NOT in list. * The '!' character is only special if it * is the first character in the list. * */ /* * PSEUDO CODE * * Begin do_list * Default result is no match * Skip over the opening left bracket * If the next pattern character is a '!' then * List match gives FALSE * Skip over the '!' character * Else * List match gives TRUE * End if * While not at closing bracket or EOS * Get lower and upper bounds * If character in bounds then * Result is same as sense flag. * Skip over rest of list * End if * End while * If match found then * If not at end of pattern then * Call match with rest of pattern * End if * End if * Return match result * End do_list * */ static BOOLEAN do_list (string, pattern) register char *string; char *pattern; { register BOOLEAN ismatch; register BOOLEAN if_found; register BOOLEAN if_not_found; auto char lower; auto char upper; pattern++; if (*pattern == '!') { if_found = FALSE; if_not_found = TRUE; pattern++; } else { if_found = TRUE; if_not_found = FALSE; } ismatch = if_not_found; while (*pattern != ']' && *pattern != EOS) { list_parse (&pattern, &lower, &upper); if (*string >= lower && *string <= upper) { ismatch = if_found; while (*pattern != ']' && *pattern != EOS) {pattern++;} } } if (*pattern++ != ']') { fprintf (stderr, "warning - character class error\n"); } else { if (ismatch) { ismatch = match (++string, pattern); } } return (ismatch); } /* * FUNCTION * * list_parse parse part of list into lower and upper bounds * * SYNOPSIS * * static VOID list_parse (patp, lowp, highp) * char **patp; * char *lowp; * char *highp; * * DESCRIPTION * * Given pointer to a pattern pointer (patp), pointer to * a place to store lower bound (lowp), and pointer to a * place to store upper bound (highp), parses part of * the list, updating the pattern pointer in the process. * * For list characters which are not part of a range, * the lower and upper bounds are set to that character. * */ static VOID list_parse (patp, lowp, highp) char **patp; char *lowp; char *highp; { *lowp = nextch (patp); if (**patp == '-') { (*patp)++; *highp = nextch (patp); } else { *highp = *lowp; } } /* * FUNCTION * * nextch determine next character in a pattern * * SYNOPSIS * * static char nextch (patp) * char **patp; * * DESCRIPTION * * Given pointer to a pointer to a pattern, uses the pattern * pointer to determine the next character in the pattern, * subject to translation of backslash-char and backslash-octal * sequences. * * The character pointer is updated to point at the next pattern * character to be processed. * */ static char nextch (patp) char **patp; { register char ch; register char chsum; register int count; ch = *(*patp)++; if (ch == '\\') { ch = *(*patp)++; if (IS_OCTAL (ch)) { chsum = 0; for (count = 0; count < 3 && IS_OCTAL (ch); count++) { chsum *= 8; chsum += ch - '0'; ch = *(*patp)++; } (*patp)--; ch = chsum; } } return (ch); }