1  /* Copyright (C) 1991-1994, 1996-1998, 2000, 2004, 2007-2023 Free Software
       2     Foundation, Inc.
       3     This file is part of the GNU C Library.
       4  
       5     This file is free software: you can redistribute it and/or modify
       6     it under the terms of the GNU Lesser General Public License as
       7     published by the Free Software Foundation; either version 2.1 of the
       8     License, or (at your option) any later version.
       9  
      10     This file is distributed in the hope that it will be useful,
      11     but WITHOUT ANY WARRANTY; without even the implied warranty of
      12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      13     GNU Lesser General Public License for more details.
      14  
      15     You should have received a copy of the GNU Lesser General Public License
      16     along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
      17  
      18  /* This particular implementation was written by Eric Blake, 2008.  */
      19  
      20  #ifndef _LIBC
      21  # include <config.h>
      22  #endif
      23  
      24  /* Specification of memmem.  */
      25  #include <string.h>
      26  
      27  #define RETURN_TYPE void *
      28  #define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
      29  #include "str-two-way.h"
      30  
      31  /* Return the first occurrence of NEEDLE in HAYSTACK.  Return HAYSTACK
      32     if NEEDLE_LEN is 0, otherwise NULL if NEEDLE is not found in
      33     HAYSTACK.  */
      34  void *
      35  memmem (const void *haystack_start, size_t haystack_len,
      36          const void *needle_start, size_t needle_len)
      37  {
      38    /* Abstract memory is considered to be an array of 'unsigned char' values,
      39       not an array of 'char' values.  See ISO C 99 section 6.2.6.1.  */
      40    const unsigned char *haystack = (const unsigned char *) haystack_start;
      41    const unsigned char *needle = (const unsigned char *) needle_start;
      42  
      43    if (needle_len == 0)
      44      /* The first occurrence of the empty string is deemed to occur at
      45         the beginning of the string.  */
      46      return (void *) haystack;
      47  
      48    /* Sanity check, otherwise the loop might search through the whole
      49       memory.  */
      50    if (__builtin_expect (haystack_len < needle_len, 0))
      51      return NULL;
      52  
      53    /* Use optimizations in memchr when possible, to reduce the search
      54       size of haystack using a linear algorithm with a smaller
      55       coefficient.  However, avoid memchr for long needles, since we
      56       can often achieve sublinear performance.  */
      57    if (needle_len < LONG_NEEDLE_THRESHOLD)
      58      {
      59        haystack = memchr (haystack, *needle, haystack_len);
      60        if (!haystack || __builtin_expect (needle_len == 1, 0))
      61          return (void *) haystack;
      62        haystack_len -= haystack - (const unsigned char *) haystack_start;
      63        if (haystack_len < needle_len)
      64          return NULL;
      65        return two_way_short_needle (haystack, haystack_len, needle, needle_len);
      66      }
      67    else
      68      return two_way_long_needle (haystack, haystack_len, needle, needle_len);
      69  }
      70  
      71  #undef LONG_NEEDLE_THRESHOLD