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

[Sichen Zhao]

> 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;
> }
Ok, So just modify the strnstr like that, right?