2.11BSD#431 - /usr/src/new/vmsbackup/match.c

   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: }

Defined functions

Defined typedef's

Defined macros