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

[Eric Blake <eblake at redhat dot com>]

On 08/25/2017 01:07 PM, Eric Blake wrote:
> 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;
> }

Hmm, I guess you also have to double-check that there is no NUL byte in
haystack prior to the result returned by memmem(). But that is still O(n):

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]) {
    char *x = memmem(haystack, haystack_len, needle, needle_len);
    if (x && !memchr(haystack, 0, x - haystack))
      return x;
  }
  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