- for (begin = (const char *) haystack; begin <= last_possible; ++begin)
- if (begin[0] == ((const char *) needle)[0] &&
- !memcmp ((const void *) &begin[1],
- (const void *) ((const char *) needle + 1),
- needle_len - 1))
- return (void *) begin;
-
- return NULL;
+ /* Use optimizations in memchr when possible, to reduce the search
+ size of haystack using a linear algorithm with a smaller
+ coefficient. However, avoid memchr for long needles, since we
+ can often achieve sublinear performance. */
+ if (needle_len < LONG_NEEDLE_THRESHOLD)
+ {
+ haystack = memchr (haystack, *needle, haystack_len);
+ if (!haystack || __builtin_expect (needle_len == 1, 0))
+ return (void *) haystack;
+ haystack_len -= haystack - (const unsigned char *) haystack_start;
+ if (haystack_len < needle_len)
+ return NULL;
+ return two_way_short_needle (haystack, haystack_len, needle, needle_len);
+ }
+ else
+ return two_way_long_needle (haystack, haystack_len, needle, needle_len);