0,0 → 1,102 |
/* 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. |
*/ |
|
/* |
FUNCTION |
<<memmem>>---find memory segment |
|
INDEX |
memmem |
|
ANSI_SYNOPSIS |
#include <string.h> |
char *memmem(const void *<[s1]>, size_t <[l1]>, const void *<[s2]>, |
size_t <[l2]>); |
|
DESCRIPTION |
|
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 |
Returns a pointer to the located segment, or a null pointer if |
<[s2]> is not found. If <[l2]> is 0, <[s1]> is returned. |
|
PORTABILITY |
<<memmem>> is a newlib extension. |
|
<<memmem>> requires no supporting OS subroutines. |
|
QUICKREF |
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" |
#endif |
|
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 6.2.6.1. */ |
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; |
haystack++; |
haystack_len--; |
} |
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 */ |
} |