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

Eric Blake eblake@redhat.com
Fri Aug 25 19:18:00 GMT 2017


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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 619 bytes
Desc: OpenPGP digital signature
URL: <http://sourceware.org/pipermail/newlib/attachments/20170825/4d1c9d99/attachment.sig>


More information about the Newlib mailing list