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;
}