blob: 25704e467decff5971b34f4189ddfff04ac5fa8e [file] [log] [blame]
/* Byte-wise substring search, using the Two-Way algorithm.
* Copyright (C) 2008 Eric Blake
* Permission to use, copy, modify, and distribute this software
* is freely granted, provided that this notice is preserved.
<<memmem>>---find memory segment
#include <string.h>
char *memmem(const void *<[s1]>, size_t <[l1]>, const void *<[s2]>,
size_t <[l2]>);
Locates the first occurrence in the memory region pointed to
by <[s1]> with length <[l1]> of the sequence of bytes pointed
to by <[s2]> of length <[l2]>. If you already know the
lengths of your haystack and needle, <<memmem>> can be much
faster than <<strstr>>.
Returns a pointer to the located segment, or a null pointer if
<[s2]> is not found. If <[l2]> is 0, <[s1]> is returned.
<<memmem>> is a newlib extension.
<<memmem>> requires no supporting OS subroutines.
memmem pure
#include <string.h>
#if !defined(PREFER_SIZE_OVER_SPEED) && !defined(__OPTIMIZE_SIZE__)
# define RETURN_TYPE void *
# define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
# include "str-two-way.h"
void *
_DEFUN (memmem, (haystack_start, haystack_len, needle_start, needle_len),
const void *haystack_start _AND
size_t haystack_len _AND
const void *needle_start _AND
size_t needle_len)
/* Abstract memory is considered to be an array of 'unsigned char' values,
not an array of 'char' values. See ISO C 99 section */
const unsigned char *haystack = (const unsigned char *) haystack_start;
const unsigned char *needle = (const unsigned char *) needle_start;
if (needle_len == 0)
/* The first occurrence of the empty string is deemed to occur at
the beginning of the string. */
return (void *) haystack;
#if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
/* Less code size, but quadratic performance in the worst case. */
while (needle_len <= haystack_len)
if (!memcmp (haystack, needle, needle_len))
return (void *) haystack;
return NULL;
#else /* compilation for speed */
/* Larger code size, but guaranteed linear performance. */
/* Sanity check, otherwise the loop might search through the whole
memory. */
if (haystack_len < needle_len)
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 || needle_len == 1)
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);
return two_way_long_needle (haystack, haystack_len, needle, needle_len);
#endif /* compilation for speed */