This is the mail archive of the newlib@sourceware.org mailing list for the newlib project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
Other format: | [Raw text] |
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
Attachment:
signature.asc
Description: OpenPGP digital signature
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |