Commit | Line | Data |
---|---|---|
c0c3707f | 1 | /* Copyright (C) 1991-1994, 1996-1998, 2000, 2004, 2007-2019 Free Software |
63ce7108 TT |
2 | Foundation, Inc. |
3 | This file is part of the GNU C Library. | |
4 | ||
5 | This program is free software; you can redistribute it and/or modify | |
6 | it under the terms of the GNU General Public License as published by | |
7 | the Free Software Foundation; either version 3, or (at your option) | |
8 | any later version. | |
9 | ||
10 | This program is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
13 | GNU General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU General Public License along | |
c0c3707f | 16 | with this program; if not, see <https://www.gnu.org/licenses/>. */ |
63ce7108 TT |
17 | |
18 | /* This particular implementation was written by Eric Blake, 2008. */ | |
19 | ||
20 | #ifndef _LIBC | |
21 | # include <config.h> | |
22 | #endif | |
23 | ||
24 | /* Specification of strstr. */ | |
25 | #include <string.h> | |
26 | ||
27 | #include <stdbool.h> | |
28 | ||
63ce7108 TT |
29 | #define RETURN_TYPE char * |
30 | #define AVAILABLE(h, h_l, j, n_l) \ | |
31 | (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \ | |
32 | && ((h_l) = (j) + (n_l))) | |
33 | #include "str-two-way.h" | |
34 | ||
35 | /* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK | |
36 | if NEEDLE is empty, otherwise NULL if NEEDLE is not found in | |
37 | HAYSTACK. */ | |
38 | char * | |
39 | strstr (const char *haystack_start, const char *needle_start) | |
40 | { | |
41 | const char *haystack = haystack_start; | |
42 | const char *needle = needle_start; | |
43 | size_t needle_len; /* Length of NEEDLE. */ | |
44 | size_t haystack_len; /* Known minimum length of HAYSTACK. */ | |
45 | bool ok = true; /* True if NEEDLE is prefix of HAYSTACK. */ | |
46 | ||
47 | /* Determine length of NEEDLE, and in the process, make sure | |
48 | HAYSTACK is at least as long (no point processing all of a long | |
49 | NEEDLE if HAYSTACK is too short). */ | |
50 | while (*haystack && *needle) | |
51 | ok &= *haystack++ == *needle++; | |
52 | if (*needle) | |
53 | return NULL; | |
54 | if (ok) | |
55 | return (char *) haystack_start; | |
56 | ||
57 | /* Reduce the size of haystack using strchr, since it has a smaller | |
58 | linear coefficient than the Two-Way algorithm. */ | |
59 | needle_len = needle - needle_start; | |
60 | haystack = strchr (haystack_start + 1, *needle_start); | |
61 | if (!haystack || __builtin_expect (needle_len == 1, 0)) | |
62 | return (char *) haystack; | |
63 | needle -= needle_len; | |
64 | haystack_len = (haystack > haystack_start + needle_len ? 1 | |
65 | : needle_len + haystack_start - haystack); | |
66 | ||
67 | /* Perform the search. Abstract memory is considered to be an array | |
68 | of 'unsigned char' values, not an array of 'char' values. See | |
69 | ISO C 99 section 6.2.6.1. */ | |
70 | if (needle_len < LONG_NEEDLE_THRESHOLD) | |
71 | return two_way_short_needle ((const unsigned char *) haystack, | |
72 | haystack_len, | |
73 | (const unsigned char *) needle, needle_len); | |
74 | return two_way_long_needle ((const unsigned char *) haystack, haystack_len, | |
75 | (const unsigned char *) needle, needle_len); | |
76 | } | |
77 | ||
78 | #undef LONG_NEEDLE_THRESHOLD |