From owner-freebsd-hackers  Tue Oct  9 18:27:46 2001
Delivered-To: freebsd-hackers@freebsd.org
Received: from rodney.cnchost.com (rodney.concentric.net [207.155.252.4])
	by hub.freebsd.org (Postfix) with ESMTP
	id 69D7637B406; Tue,  9 Oct 2001 18:27:39 -0700 (PDT)
Received: from bitblocks.com (adsl-209-204-185-216.sonic.net [209.204.185.216])
	by rodney.cnchost.com
	id VAA22073; Tue, 9 Oct 2001 21:27:38 -0400 (EDT)
	[ConcentricHost SMTP Relay 1.14]
Message-ID: <200110100127.VAA22073@rodney.cnchost.com>
To: Mike Barcroft <mike@FreeBSD.org>
Cc: freebsd-hackers@FreeBSD.org, audit@freebsd.org
Subject: Re: strnstr(3) - New libc function for review 
In-reply-to: Your message of "Thu, 04 Oct 2001 21:57:06 EDT."
             <20011004215706.B34530@coffee.q9media.com> 
Date: Tue, 09 Oct 2001 18:27:38 -0700
From: Bakul Shah <bakul@bitblocks.com>
Sender: owner-freebsd-hackers@FreeBSD.ORG
Precedence: bulk
List-ID: <freebsd-hackers.FreeBSD.ORG>
List-Archive: <http://docs.freebsd.org/mail/> (Web Archive)
List-Help: <mailto:majordomo@FreeBSD.ORG?subject=help> (List Instructions)
List-Subscribe: <mailto:majordomo@FreeBSD.ORG?subject=subscribe%20freebsd-hackers>
List-Unsubscribe: <mailto:majordomo@FreeBSD.ORG?subject=unsubscribe%20freebsd-hackers>
X-Loop: FreeBSD.ORG

> 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