Power-Programmierung/CD2.mdf/c/tools/getf/match.c

C/C++ Source or Header | 1993-03-14 | 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
                <[e-mail]>

    character set code courtesy of:

                Gary S. Moss
                U. S. Army Ballistic Research Laboratory
                Aberdeen Proving Ground
                Maryland 21005-5066
                [phone] 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