1  /* Test of searching in a string.
       2     Copyright (C) 2007-2021 Free Software Foundation, Inc.
       3  
       4     This program is free software: you can redistribute it and/or modify
       5     it under the terms of the GNU General Public License as published by
       6     the Free Software Foundation; either version 3 of the License, or
       7     (at your option) any later version.
       8  
       9     This program is distributed in the hope that it will be useful,
      10     but WITHOUT ANY WARRANTY; without even the implied warranty of
      11     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      12     GNU General Public License for more details.
      13  
      14     You should have received a copy of the GNU General Public License
      15     along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
      16  
      17  /* Written by Bruno Haible <bruno@clisp.org>, 2007.  */
      18  
      19  #include <config.h>
      20  
      21  #include <string.h>
      22  
      23  #include <locale.h>
      24  #include <stdlib.h>
      25  
      26  #include "macros.h"
      27  
      28  int
      29  main ()
      30  {
      31    /* configure should already have checked that the locale is supported.  */
      32    if (setlocale (LC_ALL, "") == NULL)
      33      return 1;
      34  
      35    {
      36      const char input[] = "f\303\266\303\266";
      37      const char *result = mbsstr (input, "");
      38      ASSERT (result == input);
      39    }
      40  
      41    {
      42      const char input[] = "f\303\266\303\266";
      43      const char *result = mbsstr (input, "\303\266");
      44      ASSERT (result == input + 1);
      45    }
      46  
      47    {
      48      const char input[] = "f\303\266\303\266";
      49      const char *result = mbsstr (input, "\266\303");
      50      ASSERT (result == NULL);
      51    }
      52  
      53    {
      54      const char input[] = "\303\204BC \303\204BCD\303\204B \303\204BCD\303\204BCD\303\204BDE"; /* "ÄBC ÄBCDÄB ÄBCDÄBCDÄBDE" */
      55      const char *result = mbsstr (input, "\303\204BCD\303\204BD"); /* "ÄBCDÄBD" */
      56      ASSERT (result == input + 19);
      57    }
      58  
      59    {
      60      const char input[] = "\303\204BC \303\204BCD\303\204B \303\204BCD\303\204BCD\303\204BDE"; /* "ÄBC ÄBCDÄB ÄBCDÄBCDÄBDE" */
      61      const char *result = mbsstr (input, "\303\204BCD\303\204BE"); /* "ÄBCDÄBE" */
      62      ASSERT (result == NULL);
      63    }
      64  
      65    /* Check that a very long haystack is handled quickly if the needle is
      66       short and occurs near the beginning.  */
      67    {
      68      size_t repeat = 10000;
      69      size_t m = 1000000;
      70      const char *needle =
      71        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
      72        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
      73      char *haystack = (char *) malloc (m + 1);
      74      if (haystack != NULL)
      75        {
      76          memset (haystack, 'A', m);
      77          haystack[0] = '\303'; haystack[1] = '\204';
      78          haystack[m] = '\0';
      79  
      80          for (; repeat > 0; repeat--)
      81            {
      82              ASSERT (mbsstr (haystack, needle) == haystack + 2);
      83            }
      84  
      85          free (haystack);
      86        }
      87    }
      88  
      89    /* Check that a very long needle is discarded quickly if the haystack is
      90       short.  */
      91    {
      92      size_t repeat = 10000;
      93      size_t m = 1000000;
      94      const char *haystack =
      95        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
      96        "A\303\207A\303\207A\303\207A\303\207A\303\207A\303\207A\303\207"
      97        "A\303\207A\303\207A\303\207A\303\207A\303\207A\303\207A\303\207"
      98        "A\303\207A\303\207A\303\207A\303\207A\303\207A\303\207A\303\207"
      99        "A\303\207A\303\207A\303\207A\303\207A\303\207A\303\207A\303\207"
     100        "A\303\207A\303\207A\303\207A\303\207A\303\207A\303\207";
     101      char *needle = (char *) malloc (m + 1);
     102      if (needle != NULL)
     103        {
     104          memset (needle, 'A', m);
     105          needle[m] = '\0';
     106  
     107          for (; repeat > 0; repeat--)
     108            {
     109              ASSERT (mbsstr (haystack, needle) == NULL);
     110            }
     111  
     112          free (needle);
     113        }
     114    }
     115  
     116    /* Check that the asymptotic worst-case complexity is not quadratic.  */
     117    {
     118      size_t m = 1000000;
     119      char *haystack = (char *) malloc (2 * m + 3);
     120      char *needle = (char *) malloc (m + 3);
     121      if (haystack != NULL && needle != NULL)
     122        {
     123          const char *result;
     124  
     125          memset (haystack, 'A', 2 * m);
     126          haystack[2 * m] = '\303'; haystack[2 * m + 1] = '\207';
     127          haystack[2 * m + 2] = '\0';
     128  
     129          memset (needle, 'A', m);
     130          needle[m] = '\303'; needle[m + 1] = '\207';
     131          needle[m + 2] = '\0';
     132  
     133          result = mbsstr (haystack, needle);
     134          ASSERT (result == haystack + m);
     135        }
     136      free (needle);
     137      free (haystack);
     138    }
     139  
     140    return 0;
     141  }