home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programming
/
powerprogramming1994.iso
/
progtool
/
c
/
getf.arc
/
MATCH.C
< prev
next >
Wrap
C/C++ Source or Header
|
1987-11-05
|
6KB
|
205 lines
/*
match - test whether a file name matches a pattern
usage...
char pattern[10]="*alloc.c*";
char string[10]="malloc.c";
okay = match(pattern, string);
value is nonzero if the pattern matches the string.
* Matches any string including the null string.
? Matches any single character.
[...] Matches any one of the characters enclosed.
[~...] Matches 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.
Other characters match themselves.
Unlike the wild card characters in CP/M and MS-DOS command line
interpreters, the '*' may usefully appear at the beginning of the
name...
pattern: *alloc
means: any name ending in "alloc"
matches: alloc
malloc
myalloc
doesn't match: allo
allok
allocate
The pattern can usefully contain more than one '*'...
pattern: *ll*
means: any name containing "ll"
matches: ll
alloc
llama
all
doesn't match: aloc
Another difference is that the '.' no longer has a special meaning...
pattern: alloc*
means: any name beginning with "alloc"
matches: alloc
alloc.c <-- different
allocate.c <-- different
A stressing case: pattern <*bbbbbbbbb>
string <bbbbbbbbbbbbbbb>
...uses space proportional to pattern_length and time proportional
to pattern_length*string_length. (However, a conventional backup
type match uses time proportional to string_length**pattern_length.)
Author: James R. Van Zandt
27 Spencer Dr.
Nashua NH 03062
<jrv@mitre-bedford.arpa>
character set code courtesy of:
Gary S. Moss
U. S. Army Ballistic Research Laboratory
Aberdeen Proving Ground
Maryland 21005-5066
(301)278-6647 or AV-283-6647
*/
/*
If the pattern is no longer than MAX_PATTERN, the work arrays are
guaranteed to be long enough. An uncomplicated pattern may be much
longer. If the pattern is too long MATCH may fail to recognize
a matching string.
*/
#define MAX_PATTERN 30
#include <stdio.h>
match(pat, nam) char *pat, *nam;
{
char **q, **a, **n, *s, *rightbrkt;
int negation;
static char
*alive[MAX_PATTERN+2], /* array of pointers to pattern characters which
may correspond to *nam */
*next[MAX_PATTERN+2]; /* subset of above array - the pattern character
after a '*' has to be added */
/* alive[] and next[] are sorted by pointer value, have no duplicate entries, and
are terminated by zeros (null pointers) */
/* printf("pattern: <%s >\n", pat);********/
next[0]=pat;
next[1]=0;
while(next[0]) /* there are some pattern characters that may match *nam */
{a=alive;
n=next;
/********
printf("active pattern characters: ", pat);
for (q=n, s=pat; *s || s[-1]; s++)
if(s==*q){q++; putchar('*');}
else putchar(' ');
printf("\n");
printf("pattern pointers before expansion...\n");
for (q=n; *q; q++) printf(" %5u -> %c\n", *q, **q);
*******/
while(a<=alive+MAX_PATTERN && (*a++=*n))
{/* for each '*', add the normal character which follows it
in the pattern */
/*******
printf("a=%u, checking pattern character %c\n", a, **n);
********/
if(**n=='*')
{for (s=*n; *++s=='*'; ) {}
if (s != n[1] && a<=alive+MAX_PATTERN)
*a++ = s;
}
n++;
}
/**********
printf("expanded pattern characters: ", pat);
for (q=alive, s=pat; *s || s[-1]; s++)
if(s==*q){q++; putchar('*');}
else putchar(' ');
printf(" =? %c\n",*nam);
printf("matching %c in name with...", *nam);
for(q=alive; *q; q++) printf("\n %5u -> %5u -> %c", q, *q, **q);
printf(" ...%d pointers\n", q-alive);
***********/
if(*nam==0)
{/* have reached end of name... pattern matches only
if a[-2], the last entry in alive[], points to the null
which terminates the pattern. (Note that a[-1] is zero.)
*/
/***********
printf("reached end of name, last entry is %u -> %u -> %c\n",
a-2,a[-2], *a[-2]);
***********/
return *a[-2]==0;
}
a=alive;
n=next;
while(*a) /* no need to limit # entries in next[], since
there can be no more than were in alive[] */
{switch(**a)
{case '?': *n++ = *a+1; break;
case '*': if(n[-1]!=*a) *n++ = *a; break;
case '[':
(*a)++;
rightbrkt=index(*a,']');
if(!rightbrkt){fprintf(stderr,"missing ]\n"); return 0;}
if(**a=='~') {negation=1; (*a)++;}
else negation=0;
while(*a<rightbrkt)
{if(**a=='-'
&& (*a)[-1] != '['
&& (*a)[ 1] != ']') /* range is given */
{if( (*a)[-1] <= *nam
&& (*a)[ 1] >= *nam) break;
}
else
{if(**a=='\\') (*a)++;
if(**a==*nam) break;
}
(*a)++;
}
if(*a!=rightbrkt ^ negation) *n++ = rightbrkt+1;
break;
case '\\': (*a)++; /* escape the following character */
default: if(**a==*nam) *n++ = *a+1;
}
a++;
}
*n=0;
nam++;
}
/*************
printf("no pointers alive\n");
**************/
return 0; /* no match */
}
#ifdef MAIN
char r[90], s[90];
main(argc, argv) int argc; char **argv;
{ int dif;
while(1)
{printf("pattern > "); gets(r);
printf("name > "); gets(s);
dif=!match(r, s);
printf("<%s> and <%s> ", r, s);
if(dif) printf("are different\n");
else printf("match\n");
if(s[0]=='q') exit();
}
}
#endif