Date: Tue, 09 Oct 2001 18:27:38 -0700 From: Bakul Shah <bakul@bitblocks.com> To: Mike Barcroft <mike@FreeBSD.org> Cc: freebsd-hackers@FreeBSD.org, audit@freebsd.org Subject: Re: strnstr(3) - New libc function for review Message-ID: <200110100127.VAA22073@rodney.cnchost.com> In-Reply-To: Your message of "Thu, 04 Oct 2001 21:57:06 EDT." <20011004215706.B34530@coffee.q9media.com>
next in thread | previous in thread | raw e-mail | index | archive | help
> I would appreciate comments/reviews of the following new addition to
> libc. It is largely based off the current strstr(3) implementation.
Sorry for not getting to this sooner.
> /*
> * Find the first occurrence of find in s, where the search is limited to the
> * first slen characters of s.
> */
> char *
> strnstr(s, find, slen)
> const char *s;
> const char *find;
> size_t slen;
> {
> char c, sc;
> size_t len;
>
> if ((c = *find++) != '\0') {
> len = strlen(find);
> do {
> do {
> if ((sc = *s++) == '\0' || slen-- < 1)
> return (NULL);
> } while (sc != c);
> if (len > slen)
> return (NULL);
> } while (strncmp(s, find, len) != 0);
> s--;
> }
> return ((char *)s);
> }
Why not pass the length of the pattern as well? Regardless,
why not use simpler code that is easier to prove right?
char*
strnstr(const char *s, size_t slen, const chat *p, size_t plen)
{
while (slen >= plen) {
if (strncmp(s, p, plen) == 0)
return (char*)s;
s++, slen--;
}
return 0;
}
Another reason for passing in both string lengths is to allow
switching to a more efficient algorithm. The above algorithm
runs in slen*plen time. Other more efficient algorithms have
a startup cost that can be hiddne for a fairly moderate value
of slen*plen. So you'd insert something like
if (worth_it_to_run_KMP_algo(splen, plen))
return kmp_strnstr(s, slen, p, plen);
right above the while loop. This makes such functions
useful for much larger strings (e.g. when you have
mmapped in the whole file).
-- bakul
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200110100127.VAA22073>