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

[Gedare Bloom <gedare at rtems dot org>]

On Fri, Aug 25, 2017 at 10:18 PM, Sichen Zhao <1473996754@qq.com> wrote:
>> 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?
>
Sichen,

Yes, you can optimize the algorithm in this function to utilize memmem
and memchr. This is a good idea, and nice catch on the NUL byte.
Please also provide a test case in RTEMS.

-Gedare