1*ef5ccd6cSJohn Marino /* Copyright (C) 1991-1994, 1996-1998, 2000, 2004, 2007-2012 Free Software
2*ef5ccd6cSJohn Marino Foundation, Inc.
3*ef5ccd6cSJohn Marino This file is part of the GNU C Library.
4*ef5ccd6cSJohn Marino
5*ef5ccd6cSJohn Marino This program is free software; you can redistribute it and/or modify
6*ef5ccd6cSJohn Marino it under the terms of the GNU General Public License as published by
7*ef5ccd6cSJohn Marino the Free Software Foundation; either version 3, or (at your option)
8*ef5ccd6cSJohn Marino any later version.
9*ef5ccd6cSJohn Marino
10*ef5ccd6cSJohn Marino This program is distributed in the hope that it will be useful,
11*ef5ccd6cSJohn Marino but WITHOUT ANY WARRANTY; without even the implied warranty of
12*ef5ccd6cSJohn Marino MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13*ef5ccd6cSJohn Marino GNU General Public License for more details.
14*ef5ccd6cSJohn Marino
15*ef5ccd6cSJohn Marino You should have received a copy of the GNU General Public License along
16*ef5ccd6cSJohn Marino with this program; if not, see <http://www.gnu.org/licenses/>. */
17*ef5ccd6cSJohn Marino
18*ef5ccd6cSJohn Marino /* This particular implementation was written by Eric Blake, 2008. */
19*ef5ccd6cSJohn Marino
20*ef5ccd6cSJohn Marino #ifndef _LIBC
21*ef5ccd6cSJohn Marino # include <config.h>
22*ef5ccd6cSJohn Marino #endif
23*ef5ccd6cSJohn Marino
24*ef5ccd6cSJohn Marino /* Specification of memmem. */
25*ef5ccd6cSJohn Marino #include <string.h>
26*ef5ccd6cSJohn Marino
27*ef5ccd6cSJohn Marino #ifndef _LIBC
28*ef5ccd6cSJohn Marino # define __builtin_expect(expr, val) (expr)
29*ef5ccd6cSJohn Marino #endif
30*ef5ccd6cSJohn Marino
31*ef5ccd6cSJohn Marino #define RETURN_TYPE void *
32*ef5ccd6cSJohn Marino #define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
33*ef5ccd6cSJohn Marino #include "str-two-way.h"
34*ef5ccd6cSJohn Marino
35*ef5ccd6cSJohn Marino /* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK
36*ef5ccd6cSJohn Marino if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
37*ef5ccd6cSJohn Marino HAYSTACK. */
38*ef5ccd6cSJohn Marino void *
memmem(const void * haystack_start,size_t haystack_len,const void * needle_start,size_t needle_len)39*ef5ccd6cSJohn Marino memmem (const void *haystack_start, size_t haystack_len,
40*ef5ccd6cSJohn Marino const void *needle_start, size_t needle_len)
41*ef5ccd6cSJohn Marino {
42*ef5ccd6cSJohn Marino /* Abstract memory is considered to be an array of 'unsigned char' values,
43*ef5ccd6cSJohn Marino not an array of 'char' values. See ISO C 99 section 6.2.6.1. */
44*ef5ccd6cSJohn Marino const unsigned char *haystack = (const unsigned char *) haystack_start;
45*ef5ccd6cSJohn Marino const unsigned char *needle = (const unsigned char *) needle_start;
46*ef5ccd6cSJohn Marino
47*ef5ccd6cSJohn Marino if (needle_len == 0)
48*ef5ccd6cSJohn Marino /* The first occurrence of the empty string is deemed to occur at
49*ef5ccd6cSJohn Marino the beginning of the string. */
50*ef5ccd6cSJohn Marino return (void *) haystack;
51*ef5ccd6cSJohn Marino
52*ef5ccd6cSJohn Marino /* Sanity check, otherwise the loop might search through the whole
53*ef5ccd6cSJohn Marino memory. */
54*ef5ccd6cSJohn Marino if (__builtin_expect (haystack_len < needle_len, 0))
55*ef5ccd6cSJohn Marino return NULL;
56*ef5ccd6cSJohn Marino
57*ef5ccd6cSJohn Marino /* Use optimizations in memchr when possible, to reduce the search
58*ef5ccd6cSJohn Marino size of haystack using a linear algorithm with a smaller
59*ef5ccd6cSJohn Marino coefficient. However, avoid memchr for long needles, since we
60*ef5ccd6cSJohn Marino can often achieve sublinear performance. */
61*ef5ccd6cSJohn Marino if (needle_len < LONG_NEEDLE_THRESHOLD)
62*ef5ccd6cSJohn Marino {
63*ef5ccd6cSJohn Marino haystack = memchr (haystack, *needle, haystack_len);
64*ef5ccd6cSJohn Marino if (!haystack || __builtin_expect (needle_len == 1, 0))
65*ef5ccd6cSJohn Marino return (void *) haystack;
66*ef5ccd6cSJohn Marino haystack_len -= haystack - (const unsigned char *) haystack_start;
67*ef5ccd6cSJohn Marino if (haystack_len < needle_len)
68*ef5ccd6cSJohn Marino return NULL;
69*ef5ccd6cSJohn Marino return two_way_short_needle (haystack, haystack_len, needle, needle_len);
70*ef5ccd6cSJohn Marino }
71*ef5ccd6cSJohn Marino else
72*ef5ccd6cSJohn Marino return two_way_long_needle (haystack, haystack_len, needle, needle_len);
73*ef5ccd6cSJohn Marino }
74*ef5ccd6cSJohn Marino
75*ef5ccd6cSJohn Marino #undef LONG_NEEDLE_THRESHOLD
76