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

Sichen Zhao 1473996754@qq.com
Sat Aug 26 13:28:00 GMT 2017


> 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
Ok, but how to provide a test case? i dont understand that.






More information about the Newlib mailing list