tests/test-memmem.c

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