Path: utzoo!utgpu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!think.com!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!dkuug!diku!thorinn
From: thorinn@diku.dk (Lars Henrik Mathiesen)
Newsgroups: alt.sources
Subject: Re: Revised C filename wildcard routine
Message-ID: <1991Jan4.184639.23407@odin.diku.dk>
Date: 4 Jan 91 18:46:39 GMT
References: <3154@litchi.bbn.com>
Sender: news@odin.diku.dk (Netnews System)
Organization: Institute of Computer Science, U of Copenhagen
Lines: 63

rsalz@bbn.com (Rich Salz) writes:
>This is a revised version of my pattern-matching routine.  It has been
>posted to the net several times, and shows up in several places including
>Gilmore's public domain TAR.  You might want to test this, but I did
>and it seems solid.
>	/r$

>X**  Special thanks to Lars Mathiesen for the ABORT code.  This can greatly
>X**  speed up failing wildcard patterns.  For example:

>Xstatic int
>XStar(s, p)
>X    register char	*s;
>X    register char	*p;
>X{
>X    while (wildmat(s, p) == FALSE)
>X	if (*++s == '\0')
>X	    return ABORT;
>X    return TRUE;
>X}

I just thought I'd mention that in the patch I sent to Rich, the body
of the Star routine read like this:

{
    register int ret;

    while ((ret = DoMatch(s, p)) == FALSE)
	if (*++s == '\0')
	    return ABORT;
    return ret;
}

(Except that I used wildmatch for DoMatch.) Rich's version gives the
correct results, but the recursion goes through the wildmat function
maps all returns of ABORT to FALSE --- so the time complexity is still
the same as for traditional versions, with double the function call
overhead. (The whole point of the ABORT return code is that it is
supposed to propagate through the Star function, aborting the loop.)

I have just noted that the test on *++s in Star is repeated (with the
same result) at the top of the loop in DoMatch, so I suggest that it
should be eliminated as in the following version of Star:

static int
Star(s, p)
    register char       *s;
    register char       *p;
{
    register int ret;

    do
	ret = DoMatch(s++, p);
    while (ret == FALSE);
    return ret;
}

It may cause one more call of DoMatch in the failing case, but I think
it is clearer.

--
Lars Mathiesen, DIKU, U of Copenhagen, Denmark      [uunet!]mcsun!diku!thorinn
Institute of Datalogy -- we're scientists, not engineers.      thorinn@diku.dk