tests/test-memmem.c

   1 /*
   2  * Copyright (C) 2004, 2007, 2008 Free Software Foundation
   3  * Written by Bruno Haible and Eric Blake
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program 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 General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 #include <string.h>
  21
  22 #include <signal.h>
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <unistd.h>
  26
  27 #define ASSERT(expr) \
  28   do                                                                         \
  29     {                                                                        \
  30       if (!(expr))                                                           \
  31         {                                                                    \
  32           fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
  33           fflush (stderr);                                                   \
  34           abort ();                                                          \
  35         }                                                                    \
  36     }                                                                        \
  37   while (0)
  38
  39 int
  40 main (int argc, char *argv[])
  41 {
  42 #if HAVE_DECL_ALARM
  43   /* Declare failure if test takes too long, by using default abort
  44      caused by SIGALRM.  All known platforms that lack alarm also lack
  45      memmem, and the replacement memmem is known to not take too
  46      long.  */
  47   signal (SIGALRM, SIG_DFL);
  48   alarm (100);
  49 #endif
  50
  51   {
  52     const char input[] = "foo";
  53     const char *result = memmem (input, strlen (input), "", 0);
  54     ASSERT (result == input);
  55   }
  56
  57   {
  58     const char input[] = "foo";
  59     const char *result = memmem (input, strlen (input), "o", 1);
  60     ASSERT (result == input + 1);
  61   }
  62
  63   {
  64     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  65     const char *result = memmem (input, strlen (input), "ABCDABD", 7);
  66     ASSERT (result == input + 15);
  67   }
  68
  69   {
  70     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  71     const char *result = memmem (input, strlen (input), "ABCDABE", 7);
  72     ASSERT (result == NULL);
  73   }
  74
  75   {
  76     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  77     const char *result = memmem (input, strlen (input), "ABCDABCD", 8);
  78     ASSERT (result == input + 11);
  79   }
  80
  81   /* Check that length 0 does not dereference NULL.  */
  82   {
  83     const char *result = memmem (NULL, 0, "foo", 3);
  84     ASSERT (result == NULL);
  85   }
  86
  87   {
  88     const char input[] = "foo";
  89     const char *result = memmem (input, strlen (input), NULL, 0);
  90     ASSERT (result == input);
  91   }
  92
  93   /* Check that a very long haystack is handled quickly if the needle is
  94      short and occurs near the beginning.  */
  95   {
  96     size_t repeat = 10000;
  97     size_t m = 1000000;
  98     char *needle =
  99       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 100       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
 101     size_t n = strlen (needle);
 102     char *haystack = (char *) malloc (m + 1);
 103     if (haystack != NULL)
 104       {
 105         memset (haystack, 'A', m);
 106         haystack[0] = 'B';
 107
 108         for (; repeat > 0; repeat--)
 109           {
 110             ASSERT (memmem (haystack, m, needle, n) == haystack + 1);
 111           }
 112
 113         free (haystack);
 114       }
 115   }
 116
 117   /* Check that a very long needle is discarded quickly if the haystack is
 118      short.  */
 119   {
 120     size_t repeat = 10000;
 121     size_t m = 1000000;
 122     char *haystack =
 123       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 124       "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
 125     size_t n = strlen (haystack);
 126     char *needle = (char *) malloc (m + 1);
 127     if (needle != NULL)
 128       {
 129         memset (needle, 'A', m);
 130
 131         for (; repeat > 0; repeat--)
 132           {
 133             ASSERT (memmem (haystack, n, needle, m) == NULL);
 134           }
 135
 136         free (needle);
 137       }
 138   }
 139
 140   /* Check that the asymptotic worst-case complexity is not quadratic.  */
 141   {
 142     size_t m = 1000000;
 143     char *haystack = (char *) malloc (2 * m + 1);
 144     char *needle = (char *) malloc (m + 1);
 145     if (haystack != NULL && needle != NULL)
 146       {
 147         const char *result;
 148
 149         memset (haystack, 'A', 2 * m);
 150         haystack[2 * m] = 'B';
 151
 152         memset (needle, 'A', m);
 153         needle[m] = 'B';
 154
 155         result = memmem (haystack, 2 * m + 1, needle, m + 1);
 156         ASSERT (result == haystack + m);
 157       }
 158     free (needle);
 159     free (haystack);
 160   }
 161
 162   /* Check that long needles not present in a haystack can be handled
 163      with sublinear speed.  */
 164   {
 165     size_t repeat = 10000;
 166     size_t m = 1000000;
 167     size_t n = 1000;
 168     char *haystack = (char *) malloc (m);
 169     char *needle = (char *) malloc (n);
 170     if (haystack != NULL && needle != NULL)
 171       {
 172         const char *result;
 173
 174         memset (haystack, 'A', m);
 175         memset (needle, 'B', n);
 176
 177         for (; repeat > 0; repeat--)
 178           {
 179             result = memmem (haystack, m, needle, n);
 180             ASSERT (result == NULL);
 181           }
 182       }
 183     free (haystack);
 184     free (needle);
 185   }
 186
 187   return 0;
 188 }