tests/test-memmem.c

   1 /*
   2  * Copyright (C) 2004, 2007-2009 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 "signature.h"
  23 SIGNATURE_CHECK (memmem, void *, (void const *, size_t, void const *, size_t));
  24
  25 #include <signal.h>
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <unistd.h>
  29
  30 #include "zerosize-ptr.h"
  31
  32 #define ASSERT(expr) \
  33   do                                                                         \
  34     {                                                                        \
  35       if (!(expr))                                                           \
  36         {                                                                    \
  37           fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
  38           fflush (stderr);                                                   \
  39           abort ();                                                          \
  40         }                                                                    \
  41     }                                                                        \
  42   while (0)
  43
  44 static void *
  45 null_ptr (void)
  46 {
  47   return NULL;
  48 }
  49
  50 int
  51 main (int argc, char *argv[])
  52 {
  53 #if HAVE_DECL_ALARM
  54   /* Declare failure if test takes too long, by using default abort
  55      caused by SIGALRM.  All known platforms that lack alarm also lack
  56      memmem, and the replacement memmem is known to not take too
  57      long.  */
  58   signal (SIGALRM, SIG_DFL);
  59   alarm (100);
  60 #endif
  61
  62   {
  63     const char input[] = "foo";
  64     const char *result = memmem (input, strlen (input), "", 0);
  65     ASSERT (result == input);
  66   }
  67
  68   {
  69     const char input[] = "foo";
  70     const char *result = memmem (input, strlen (input), "o", 1);
  71     ASSERT (result == input + 1);
  72   }
  73
  74   {
  75     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  76     const char *result = memmem (input, strlen (input), "ABCDABD", 7);
  77     ASSERT (result == input + 15);
  78   }
  79
  80   {
  81     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  82     const char *result = memmem (input, strlen (input), "ABCDABE", 7);
  83     ASSERT (result == NULL);
  84   }
  85
  86   {
  87     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  88     const char *result = memmem (input, strlen (input), "ABCDABCD", 8);
  89     ASSERT (result == input + 11);
  90   }
  91
  92   /* Check that length 0 does not dereference the pointer.  */
  93   {
  94     const char *result = memmem (zerosize_ptr (), 0, "foo", 3);
  95     ASSERT (result == NULL);
  96   }
  97
  98   {
  99     const char input[] = "foo";
 100     const char *result = memmem (input, strlen (input), null_ptr (), 0);
 101     ASSERT (result == input);
 102   }
 103
 104   /* Check that a very long haystack is handled quickly if the needle is
 105      short and occurs near the beginning.  */
 106   {
 107     size_t repeat = 10000;
 108     size_t m = 1000000;
 109     char *needle =
 110       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 111       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
 112     size_t n = strlen (needle);
 113     char *haystack = (char *) malloc (m + 1);
 114     if (haystack != NULL)
 115       {
 116         memset (haystack, 'A', m);
 117         haystack[0] = 'B';
 118
 119         for (; repeat > 0; repeat--)
 120           {
 121             ASSERT (memmem (haystack, m, needle, n) == haystack + 1);
 122           }
 123
 124         free (haystack);
 125       }
 126   }
 127
 128   /* Check that a very long needle is discarded quickly if the haystack is
 129      short.  */
 130   {
 131     size_t repeat = 10000;
 132     size_t m = 1000000;
 133     char *haystack =
 134       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 135       "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
 136     size_t n = strlen (haystack);
 137     char *needle = (char *) malloc (m + 1);
 138     if (needle != NULL)
 139       {
 140         memset (needle, 'A', m);
 141
 142         for (; repeat > 0; repeat--)
 143           {
 144             ASSERT (memmem (haystack, n, needle, m) == NULL);
 145           }
 146
 147         free (needle);
 148       }
 149   }
 150
 151   /* Check that the asymptotic worst-case complexity is not quadratic.  */
 152   {
 153     size_t m = 1000000;
 154     char *haystack = (char *) malloc (2 * m + 1);
 155     char *needle = (char *) malloc (m + 1);
 156     if (haystack != NULL && needle != NULL)
 157       {
 158         const char *result;
 159
 160         memset (haystack, 'A', 2 * m);
 161         haystack[2 * m] = 'B';
 162
 163         memset (needle, 'A', m);
 164         needle[m] = 'B';
 165
 166         result = memmem (haystack, 2 * m + 1, needle, m + 1);
 167         ASSERT (result == haystack + m);
 168       }
 169     free (needle);
 170     free (haystack);
 171   }
 172
 173   /* Check that long needles not present in a haystack can be handled
 174      with sublinear speed.  */
 175   {
 176     size_t repeat = 10000;
 177     size_t m = 1000000;
 178     size_t n = 1000;
 179     char *haystack = (char *) malloc (m);
 180     char *needle = (char *) malloc (n);
 181     if (haystack != NULL && needle != NULL)
 182       {
 183         const char *result;
 184
 185         memset (haystack, 'A', m);
 186         memset (needle, 'B', n);
 187
 188         for (; repeat > 0; repeat--)
 189           {
 190             result = memmem (haystack, m, needle, n);
 191             ASSERT (result == NULL);
 192           }
 193       }
 194     free (haystack);
 195     free (needle);
 196   }
 197
 198   return 0;
 199 }