Subversion Repositories openrisc_2011-10-31

/* 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 */

}