1 /* Test of uN_strstr() functions.
2 Copyright (C) 2004, 2007-2018 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 <https://www.gnu.org/licenses/>. */
16
17 static void
test_u_strstr(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 }
211