/* 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 <>---find memory segment INDEX memmem ANSI_SYNOPSIS #include 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, <> can be much faster than <>. 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 <> is a newlib extension. <> requires no supporting OS subroutines. QUICKREF memmem pure */ #include #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 */ }