- /* Use optimizations in memchr when possible. */
- if (__builtin_expect (needle_len == 1, 0))
- return memchr (haystack, (unsigned char) *Needle, haystack_len);
-
- /* Minimizing the worst-case complexity:
- Let n = haystack_len, m = needle_len.
- The naïve algorithm is O(n*m) worst-case.
- The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a
- memory allocation.
- To achieve linear complexity and yet amortize the cost of the
- memory allocation, we activate the Knuth-Morris-Pratt algorithm
- only once the naïve algorithm has already run for some time; more
- precisely, when
- - the outer loop count is >= 10,
- - the average number of comparisons per outer loop is >= 5,
- - the total number of comparisons is >= m.
- But we try it only once. If the memory allocation attempt failed,
- we don't retry it. */
- {
- bool try_kmp = true;
- size_t outer_loop_count = 0;
- size_t comparison_count = 0;
-
- /* Speed up the following searches of needle by caching its first
- character. */
- char b = *Needle++;
-
- for (;; Haystack++)
- {
- if (Haystack == last_haystack)
- /* No match. */
- return NULL;
-
- /* See whether it's advisable to use an asymptotically faster
- algorithm. */
- if (try_kmp
- && outer_loop_count >= 10
- && comparison_count >= 5 * outer_loop_count)
- {
- /* See if needle + comparison_count now reaches the end of
- needle. */
- if (comparison_count >= needle_len)
- {
- /* Try the Knuth-Morris-Pratt algorithm. */
- const char *result;
- if (knuth_morris_pratt (Haystack, last_haystack,
- Needle - 1, needle_len, &result))
- return (void *) result;
- try_kmp = false;
- }
- }
-
- outer_loop_count++;
- comparison_count++;
- if (*Haystack == b)
- /* The first character matches. */
- {
- const char *rhaystack = Haystack + 1;
- const char *rneedle = Needle;
-
- for (;; rhaystack++, rneedle++)
- {
- if (rneedle == last_needle)
- /* Found a match. */
- return (void *) Haystack;
- if (rhaystack == last_haystack)
- /* No match. */
- return NULL;
- comparison_count++;
- if (*rhaystack != *rneedle)
- /* Nothing in this round. */
- break;
- }
- }
- }
- }
-
- 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);