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