Commit | Line | Data |
---|---|---|
49e4877c | 1 | /* Copyright (C) 1991-1994, 1996-1998, 2000, 2004, 2007-2016 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 | |
16 | with this program; if not, see <http://www.gnu.org/licenses/>. */ | |
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 | ||
29 | #ifndef _LIBC | |
30 | # define __builtin_expect(expr, val) (expr) | |
31 | #endif | |
32 | ||
33 | #define RETURN_TYPE char * | |
34 | #define AVAILABLE(h, h_l, j, n_l) \ | |
35 | (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \ | |
36 | && ((h_l) = (j) + (n_l))) | |
37 | #include "str-two-way.h" | |
38 | ||
39 | /* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK | |
40 | if NEEDLE is empty, otherwise NULL if NEEDLE is not found in | |
41 | HAYSTACK. */ | |
42 | char * | |
43 | strstr (const char *haystack_start, const char *needle_start) | |
44 | { | |
45 | const char *haystack = haystack_start; | |
46 | const char *needle = needle_start; | |
47 | size_t needle_len; /* Length of NEEDLE. */ | |
48 | size_t haystack_len; /* Known minimum length of HAYSTACK. */ | |
49 | bool ok = true; /* True if NEEDLE is prefix of HAYSTACK. */ | |
50 | ||
51 | /* Determine length of NEEDLE, and in the process, make sure | |
52 | HAYSTACK is at least as long (no point processing all of a long | |
53 | NEEDLE if HAYSTACK is too short). */ | |
54 | while (*haystack && *needle) | |
55 | ok &= *haystack++ == *needle++; | |
56 | if (*needle) | |
57 | return NULL; | |
58 | if (ok) | |
59 | return (char *) haystack_start; | |
60 | ||
61 | /* Reduce the size of haystack using strchr, since it has a smaller | |
62 | linear coefficient than the Two-Way algorithm. */ | |
63 | needle_len = needle - needle_start; | |
64 | haystack = strchr (haystack_start + 1, *needle_start); | |
65 | if (!haystack || __builtin_expect (needle_len == 1, 0)) | |
66 | return (char *) haystack; | |
67 | needle -= needle_len; | |
68 | haystack_len = (haystack > haystack_start + needle_len ? 1 | |
69 | : needle_len + haystack_start - haystack); | |
70 | ||
71 | /* Perform the search. Abstract memory is considered to be an array | |
72 | of 'unsigned char' values, not an array of 'char' values. See | |
73 | ISO C 99 section 6.2.6.1. */ | |
74 | if (needle_len < LONG_NEEDLE_THRESHOLD) | |
75 | return two_way_short_needle ((const unsigned char *) haystack, | |
76 | haystack_len, | |
77 | (const unsigned char *) needle, needle_len); | |
78 | return two_way_long_needle ((const unsigned char *) haystack, haystack_len, | |
79 | (const unsigned char *) needle, needle_len); | |
80 | } | |
81 | ||
82 | #undef LONG_NEEDLE_THRESHOLD |