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