Re: [PATCH 1/2] Import strnstr.c from FreeBSD.

[Eric Blake <eblake at redhat dot com>]

On 08/23/2017 09:14 PM, Sichen Zhao wrote:

> +/*
> + * Find the first occurrence of find in s, where the search is limited to the
> + * first slen characters of s.
> + */
> +char *
> +strnstr(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 (slen-- < 1 || (sc = *s++) == '\0')
> +					return (NULL);
> +			} while (sc != c);
> +			if (len > slen)
> +				return (NULL);
> +		} while (strncmp(s, find, len) != 0);
> +		s--;
> +	}

This is a poor algorithm (O(n^2) because it is is calling an O(n)
strncmp() over every byte of haystack).  It also calls strlen() instead
of strnlen(), which (when the needle is bigger than the haystack, and
therefore the function must return NULL) is wasted effort.

Instead of copying the poor BSD implementation, why not just open-code
it yourself to take advantage of our O(n) memmem(), which has already
been optimized to take advantage of a better algorithm that is not
quadratic?

char *
strnstr(const char *haystack, const char *needle, size_t haystack_len)
{
  size_t needle_len = strnlen(needle, slen);
  if (needle_len < slen || !needle[needle_len])
    return memmem(haystack, haystack_len, needle, needle_len);
  return NULL;
}

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org

Attachment: signature.asc
Description: OpenPGP digital signature