tests/unistr/test-u-strstr.h

   1 /* Test of uN_strstr() functions.
   2    Copyright (C) 2004, 2007-2017 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 <http://www.gnu.org/licenses/>.  */
  16
  17 static void
  18 test_u_strstr (void)
  19 {
  20   {
  21     const UNIT input[] = { 'f', 'o', 'o', 0 };
  22     const UNIT needle[] = { 0 };
  23     const UNIT *result = U_STRSTR (input, needle);
  24     ASSERT (result == input);
  25   }
  26
  27   {
  28     const UNIT input[] = { 'f', 'o', 'o', 0 };
  29     const UNIT needle[] = { 'o', 0 };
  30     const UNIT *result = U_STRSTR (input, needle);
  31     ASSERT (result == input + 1);
  32   }
  33
  34   {
  35     const UNIT input[] =
  36       { 'A', 'B', 'C', ' ', 'A', 'B', 'C', 'D', 'A', 'B', ' ', 'A', 'B', 'C',
  37         'D', 'A', 'B', 'C', 'D', 'A', 'B', 'D', 'E', 0
  38       };
  39     const UNIT needle[] = { 'A', 'B', 'C', 'D', 'A', 'B', 'D', 0 };
  40     const UNIT *result = U_STRSTR (input, needle);
  41     ASSERT (result == input + 15);
  42   }
  43
  44   {
  45     const UNIT input[] =
  46       { 'A', 'B', 'C', ' ', 'A', 'B', 'C', 'D', 'A', 'B', ' ', 'A', 'B', 'C',
  47         'D', 'A', 'B', 'C', 'D', 'A', 'B', 'D', 'E', 0
  48       };
  49     const UNIT needle[] = { 'A', 'B', 'C', 'D', 'A', 'B', 'E', 0 };
  50     const UNIT *result = U_STRSTR (input, needle);
  51     ASSERT (result == NULL);
  52   }
  53
  54   {
  55     const UNIT input[] =
  56       { 'A', 'B', 'C', ' ', 'A', 'B', 'C', 'D', 'A', 'B', ' ', 'A', 'B', 'C',
  57         'D', 'A', 'B', 'C', 'D', 'A', 'B', 'D', 'E', 0
  58       };
  59     const UNIT needle[] = { 'A', 'B', 'C', 'D', 'A', 'B', 'C', 'D', 0 };
  60     const UNIT *result = U_STRSTR (input, needle);
  61     ASSERT (result == input + 11);
  62   }
  63
  64   /* Check that a long periodic needle does not cause false positives.  */
  65   {
  66     const UNIT input[] =
  67       { 'F', '_', 'B', 'D', '_', 'C', 'E', '_', 'B', 'D', '_', 'E', 'F',
  68         '_', 'B', 'F', '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F',
  69         '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D',
  70         '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D', '_', 'C', '3',
  71         '_', '8', '8', '_', '2', '0', '_', 'E', 'F', '_', 'B', 'F',
  72         '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D',
  73         '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D', '_', 'C', '3',
  74         '_', 'A', '7', '_', '2', '0', '_', 'E', 'F', '_', 'B', 'F',
  75         '_', 'B', 'D', 0
  76       };
  77     const UNIT needle[] =
  78       { '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D', '_', 'E', 'F',
  79         '_', 'B', 'F', '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F',
  80         '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D',
  81         '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D', 0
  82       };
  83     const UNIT *result = U_STRSTR (input, needle);
  84     ASSERT (result == NULL);
  85   }
  86   {
  87     const UNIT input[] =
  88       { 'F', '_', 'B', 'D', '_', 'C', 'E', '_', 'B', 'D', '_', 'E', 'F',
  89         '_', 'B', 'F', '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F',
  90         '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D',
  91         '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D', '_', 'C', '3',
  92         '_', '8', '8', '_', '2', '0', '_', 'E', 'F', '_', 'B', 'F',
  93         '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D',
  94         '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D', '_', 'C', '3',
  95         '_', 'A', '7', '_', '2', '0', '_', 'E', 'F', '_', 'B', 'F',
  96         '_', 'B', 'D', '_', 'D', 'A', '_', 'B', '5', '_', 'C', '2',
  97         '_', 'A', '6', '_', '2', '0', '_', 'E', 'F', '_', 'B', 'F',
  98         '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D',
  99         '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D', '_', 'E', 'F',
 100         '_', 'B', 'F', '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F',
 101         '_', 'B', 'D', 0
 102       };
 103     const UNIT needle[] =
 104       { '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D', '_', 'E', 'F',
 105         '_', 'B', 'F', '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F',
 106         '_', 'B', 'D', '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D',
 107         '_', 'E', 'F', '_', 'B', 'F', '_', 'B', 'D', 0
 108       };
 109     const UNIT *result = U_STRSTR (input, needle);
 110     ASSERT (result == input + 115);
 111   }
 112
 113   /* Check that a very long haystack is handled quickly if the needle is
 114      short and occurs near the beginning.  */
 115   {
 116     size_t repeat = 10000;
 117     size_t m = 1000000;
 118     const UNIT needle[] =
 119       { 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 120         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 121         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 122         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 123         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 124         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 125         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 126         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 127         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 128         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 0
 129       };
 130     UNIT *haystack = (UNIT *) malloc ((m + 1) * sizeof (UNIT));
 131     if (haystack != NULL)
 132       {
 133         size_t i;
 134
 135         haystack[0] = 'B';
 136         for (i = 1; i < m; i++)
 137           haystack[i] = 'A';
 138         haystack[m] = '\0';
 139
 140         for (; repeat > 0; repeat--)
 141           {
 142             ASSERT (U_STRSTR (haystack, needle) == haystack + 1);
 143           }
 144
 145         free (haystack);
 146       }
 147   }
 148
 149   /* Check that a very long needle is discarded quickly if the haystack is
 150      short.  */
 151   {
 152     size_t repeat = 10000;
 153     size_t m = 1000000;
 154     const UNIT haystack[] =
 155       { 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 156         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 157         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 158         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A',
 159         'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'B',
 160         'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B',
 161         'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B',
 162         'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B',
 163         'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B',
 164         'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 'A', 'B', 0
 165       };
 166     UNIT *needle = (UNIT *) malloc ((m + 1) * sizeof (UNIT));
 167     if (needle != NULL)
 168       {
 169         size_t i;
 170
 171         for (i = 0; i < m; i++)
 172           needle[i] = 'A';
 173         needle[m] = '\0';
 174
 175         for (; repeat > 0; repeat--)
 176           {
 177             ASSERT (U_STRSTR (haystack, needle) == NULL);
 178           }
 179
 180         free (needle);
 181       }
 182   }
 183
 184   /* Check that the asymptotic worst-case complexity is not quadratic.  */
 185   {
 186     size_t m = 1000000;
 187     UNIT *haystack = (UNIT *) malloc ((2 * m + 2) * sizeof (UNIT));
 188     UNIT *needle = (UNIT *) malloc ((m + 2) * sizeof (UNIT));
 189     if (haystack != NULL && needle != NULL)
 190       {
 191         size_t i;
 192         const UNIT *result;
 193
 194         for (i = 0; i < 2 * m; i++)
 195           haystack[i] = 'A';
 196         haystack[2 * m] = 'B';
 197         haystack[2 * m + 1] = 0;
 198
 199         for (i = 0; i < m; i++)
 200           needle[i] = 'A';
 201         needle[m] = 'B';
 202         needle[m + 1] = 0;
 203
 204         result = U_STRSTR (haystack, needle);
 205         ASSERT (result == haystack + m);
 206       }
 207     free (needle);
 208     free (haystack);
 209   }
 210 }