Mercurial > gnulib
annotate tests/test-memmem.c @ 40246:c34f677e6117 default tip master
_Noreturn: GCC 4.7 does not support [[noreturn]] in C++11 mode
* lib/_Noreturn.h, m4/gnulib-common.m4: Don't use [[noreturn]] before
GCC 4.8.
author | Akim Demaille <akim.demaille@gmail.com> |
---|---|
date | Sun, 17 Mar 2019 19:27:20 +0100 |
parents | 452ab00796c7 |
children |
rev | line source |
---|---|
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
1 /* |
40057
b06060465f09
maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents:
39838
diff
changeset
|
2 * Copyright (C) 2004, 2007-2019 Free Software Foundation, Inc. |
9542 | 3 * Written by Bruno Haible and Eric Blake |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
4 * |
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
8891
diff
changeset
|
5 * This program is free software: you can redistribute it and/or modify |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
6 * it under the terms of the GNU General Public License as published by |
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
8891
diff
changeset
|
7 * the Free Software Foundation; either version 3 of the License, or |
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
8891
diff
changeset
|
8 * (at your option) any later version. |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
9 * |
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
10 * This program is distributed in the hope that it will be useful, |
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
13 * GNU General Public License for more details. |
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
14 * |
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
15 * You should have received a copy of the GNU General Public License |
19190 | 16 * along with this program. If not, see <https://www.gnu.org/licenses/>. */ |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
17 |
8891
633babea5f62
Unconditionally include <config.h> in unit tests.
Eric Blake <ebb9@byu.net>
parents:
7944
diff
changeset
|
18 #include <config.h> |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
19 |
9542 | 20 #include <string.h> |
21 | |
12489 | 22 #include "signature.h" |
23 SIGNATURE_CHECK (memmem, void *, (void const *, size_t, void const *, size_t)); | |
24 | |
10195 | 25 #include <signal.h> |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
26 #include <stdlib.h> |
9569
c5dc234b375e
Shorten duration of memmem test.
Eric Blake <ebb9@byu.net>
parents:
9542
diff
changeset
|
27 #include <unistd.h> |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
28 |
11570
1e84e9b3384a
Make some tests ISO C 99 compliant.
Bruno Haible <bruno@clisp.org>
parents:
10195
diff
changeset
|
29 #include "zerosize-ptr.h" |
12496
a48d3d749ca5
Refactor common macros used in tests.
Bruno Haible <bruno@clisp.org>
parents:
12489
diff
changeset
|
30 #include "macros.h" |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
31 |
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
32 int |
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
33 main (int argc, char *argv[]) |
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
34 { |
9571 | 35 #if HAVE_DECL_ALARM |
9569
c5dc234b375e
Shorten duration of memmem test.
Eric Blake <ebb9@byu.net>
parents:
9542
diff
changeset
|
36 /* Declare failure if test takes too long, by using default abort |
9571 | 37 caused by SIGALRM. All known platforms that lack alarm also lack |
38 memmem, and the replacement memmem is known to not take too | |
39 long. */ | |
17356
639f60219717
tests: make it easier to bypass alarm time in debugger
Eric Blake <eblake@redhat.com>
parents:
17249
diff
changeset
|
40 int alarm_value = 100; |
10192
0553e4d56bcc
Work around environments that (stupidly) ignore SIGALRM.
Bruno Haible <bruno@clisp.org>
parents:
9889
diff
changeset
|
41 signal (SIGALRM, SIG_DFL); |
17356
639f60219717
tests: make it easier to bypass alarm time in debugger
Eric Blake <eblake@redhat.com>
parents:
17249
diff
changeset
|
42 alarm (alarm_value); |
9571 | 43 #endif |
44 | |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
45 { |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
46 const char input[] = "foo"; |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
47 const char *result = memmem (input, strlen (input), "", 0); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
48 ASSERT (result == input); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
49 } |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
50 |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
51 { |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
52 const char input[] = "foo"; |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
53 const char *result = memmem (input, strlen (input), "o", 1); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
54 ASSERT (result == input + 1); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
55 } |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
56 |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
57 { |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
58 const char input[] = "ABC ABCDAB ABCDABCDABDE"; |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
59 const char *result = memmem (input, strlen (input), "ABCDABD", 7); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
60 ASSERT (result == input + 15); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
61 } |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
62 |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
63 { |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
64 const char input[] = "ABC ABCDAB ABCDABCDABDE"; |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
65 const char *result = memmem (input, strlen (input), "ABCDABE", 7); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
66 ASSERT (result == NULL); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
67 } |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
68 |
9584
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
69 { |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
70 const char input[] = "ABC ABCDAB ABCDABCDABDE"; |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
71 const char *result = memmem (input, strlen (input), "ABCDABCD", 8); |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
72 ASSERT (result == input + 11); |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
73 } |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
74 |
11570
1e84e9b3384a
Make some tests ISO C 99 compliant.
Bruno Haible <bruno@clisp.org>
parents:
10195
diff
changeset
|
75 /* Check that length 0 does not dereference the pointer. */ |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
76 { |
11570
1e84e9b3384a
Make some tests ISO C 99 compliant.
Bruno Haible <bruno@clisp.org>
parents:
10195
diff
changeset
|
77 const char *result = memmem (zerosize_ptr (), 0, "foo", 3); |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
78 ASSERT (result == NULL); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
79 } |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
80 |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
81 { |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
82 const char input[] = "foo"; |
40214 | 83 const char *result = memmem (input, strlen (input), zerosize_ptr (), 0); |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
84 ASSERT (result == input); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
85 } |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
86 |
13772
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
87 /* Check that a long periodic needle does not cause false positives. */ |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
88 { |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
89 const char input[] = ("F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD" |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
90 "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD" |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
91 "_C3_A7_20_EF_BF_BD"); |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
92 const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"; |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
93 const char *result = memmem (input, strlen (input), need, strlen (need)); |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
94 ASSERT (result == NULL); |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
95 } |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
96 { |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
97 const char input[] = ("F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD" |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
98 "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD" |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
99 "_C3_A7_20_EF_BF_BD_DA_B5_C2_A6_20" |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
100 "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"); |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
101 const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"; |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
102 const char *result = memmem (input, strlen (input), need, strlen (need)); |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
103 ASSERT (result == input + 115); |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
104 } |
1d8a613275c6
memmem, strstr, strcasestr: fix bug with long periodic needle
Eric Blake <eblake@redhat.com>
parents:
13415
diff
changeset
|
105 |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
106 /* Check that a very long haystack is handled quickly if the needle is |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
107 short and occurs near the beginning. */ |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
108 { |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
109 size_t repeat = 10000; |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
110 size_t m = 1000000; |
13415
a884db63982b
Avoid some more warnings from "gcc -Wwrite-strings".
Bruno Haible <bruno@clisp.org>
parents:
12825
diff
changeset
|
111 const char *needle = |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
112 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
113 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"; |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
114 size_t n = strlen (needle); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
115 char *haystack = (char *) malloc (m + 1); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
116 if (haystack != NULL) |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
117 { |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
118 memset (haystack, 'A', m); |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
119 haystack[0] = 'B'; |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
120 |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
121 for (; repeat > 0; repeat--) |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
122 { |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
123 ASSERT (memmem (haystack, m, needle, n) == haystack + 1); |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
124 } |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
125 |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
126 free (haystack); |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
127 } |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
128 } |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
129 |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
130 /* Check that a very long needle is discarded quickly if the haystack is |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
131 short. */ |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
132 { |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
133 size_t repeat = 10000; |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
134 size_t m = 1000000; |
13415
a884db63982b
Avoid some more warnings from "gcc -Wwrite-strings".
Bruno Haible <bruno@clisp.org>
parents:
12825
diff
changeset
|
135 const char *haystack = |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
136 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA" |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
137 "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB"; |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
138 size_t n = strlen (haystack); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
139 char *needle = (char *) malloc (m + 1); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
140 if (needle != NULL) |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
141 { |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
142 memset (needle, 'A', m); |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
143 |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
144 for (; repeat > 0; repeat--) |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
145 { |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
146 ASSERT (memmem (haystack, n, needle, m) == NULL); |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
147 } |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
148 |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
149 free (needle); |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
150 } |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
151 } |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
152 |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
153 /* Check that the asymptotic worst-case complexity is not quadratic. */ |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
154 { |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
155 size_t m = 1000000; |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
156 char *haystack = (char *) malloc (2 * m + 1); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
157 char *needle = (char *) malloc (m + 1); |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
158 if (haystack != NULL && needle != NULL) |
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
159 { |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
160 const char *result; |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
161 |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
162 memset (haystack, 'A', 2 * m); |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
163 haystack[2 * m] = 'B'; |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
164 |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
165 memset (needle, 'A', m); |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
166 needle[m] = 'B'; |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
167 |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
168 result = memmem (haystack, 2 * m + 1, needle, m + 1); |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
169 ASSERT (result == haystack + m); |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
170 } |
9749
daf5ba9fe2d9
Remove useless "if" tests before free. Deprecate "free" module.
Jim Meyering <meyering@redhat.com>
parents:
9608
diff
changeset
|
171 free (needle); |
daf5ba9fe2d9
Remove useless "if" tests before free. Deprecate "free" module.
Jim Meyering <meyering@redhat.com>
parents:
9608
diff
changeset
|
172 free (haystack); |
9538
43d9769bf4d0
Fix memmem to avoid O(n^2) worst-case complexity.
Eric Blake <ebb9@byu.net>
parents:
9309
diff
changeset
|
173 } |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
174 |
9584
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
175 /* Check that long needles not present in a haystack can be handled |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
176 with sublinear speed. */ |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
177 { |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
178 size_t repeat = 10000; |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
179 size_t m = 1000000; |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
180 size_t n = 1000; |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
181 char *haystack = (char *) malloc (m); |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
182 char *needle = (char *) malloc (n); |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
183 if (haystack != NULL && needle != NULL) |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
184 { |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
185 const char *result; |
9584
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
186 |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
187 memset (haystack, 'A', m); |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
188 memset (needle, 'B', n); |
9584
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
189 |
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
190 for (; repeat > 0; repeat--) |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
191 { |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
192 result = memmem (haystack, m, needle, n); |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
193 ASSERT (result == NULL); |
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11570
diff
changeset
|
194 } |
9584
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
195 } |
9749
daf5ba9fe2d9
Remove useless "if" tests before free. Deprecate "free" module.
Jim Meyering <meyering@redhat.com>
parents:
9608
diff
changeset
|
196 free (haystack); |
daf5ba9fe2d9
Remove useless "if" tests before free. Deprecate "free" module.
Jim Meyering <meyering@redhat.com>
parents:
9608
diff
changeset
|
197 free (needle); |
9584
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
198 } |
f490fd6e4955
Rewrite memmem to guarantee linear complexity without malloc.
Eric Blake <ebb9@byu.net>
parents:
9571
diff
changeset
|
199 |
14395
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
200 { |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
201 /* Ensure that with a barely periodic "short" needle, memmem's |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
202 search does not mistakenly skip just past the match point. |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
203 This use of memmem would mistakenly return NULL before |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
204 gnulib v0.0-4927. */ |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
205 const char *haystack = |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
206 "\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
207 "with_build_libsubdir\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
208 "with_local_prefix\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
209 "with_gxx_include_dir\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
210 "with_cpp_install_dir\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
211 "enable_generated_files_in_srcdir\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
212 "with_gnu_ld\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
213 "with_ld\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
214 "with_demangler_in_ld\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
215 "with_gnu_as\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
216 "with_as\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
217 "enable_largefile\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
218 "enable_werror_always\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
219 "enable_checking\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
220 "enable_coverage\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
221 "enable_gather_detailed_mem_stats\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
222 "enable_build_with_cxx\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
223 "with_stabs\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
224 "enable_multilib\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
225 "enable___cxa_atexit\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
226 "enable_decimal_float\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
227 "enable_fixed_point\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
228 "enable_threads\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
229 "enable_tls\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
230 "enable_objc_gc\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
231 "with_dwarf2\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
232 "enable_shared\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
233 "with_build_sysroot\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
234 "with_sysroot\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
235 "with_specs\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
236 "with_pkgversion\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
237 "with_bugurl\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
238 "enable_languages\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
239 "with_multilib_list\n"; |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
240 const char *needle = "\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
241 "with_gnu_ld\n"; |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
242 const char* p = memmem (haystack, strlen (haystack), |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
243 needle, strlen (needle)); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
244 ASSERT (p - haystack == 114); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
245 } |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
246 |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
247 { |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
248 /* Same bug, shorter trigger. */ |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
249 const char *haystack = "..wi.d."; |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
250 const char *needle = ".d."; |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
251 const char* p = memmem (haystack, strlen (haystack), |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
252 needle, strlen (needle)); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
253 ASSERT (p - haystack == 4); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
254 } |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
255 |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
256 { |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
257 /* Like the above, but trigger the flaw in two_way_long_needle |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
258 by using a needle of length LONG_NEEDLE_THRESHOLD (32) or greater. |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
259 Rather than trying to find the right alignment manually, I've |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
260 arbitrarily chosen the following needle and template for the |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
261 haystack, and ensure that for each placement of the needle in |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
262 that haystack, memmem finds it. */ |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
263 const char *needle = "\nwith_gnu_ld-extend-to-len-32-b\n"; |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
264 const char *h = |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
265 "\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
266 "with_build_libsubdir\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
267 "with_local_prefix\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
268 "with_gxx_include_dir\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
269 "with_cpp_install_dir\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
270 "with_e_\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
271 "..............................\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
272 "with_FGHIJKLMNOPQRSTUVWXYZ\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
273 "with_567890123456789\n" |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
274 "with_multilib_list\n"; |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
275 size_t h_len = strlen (h); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
276 char *haystack = malloc (h_len + 1); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
277 size_t i; |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
278 ASSERT (haystack); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
279 for (i = 0; i < h_len - strlen (needle); i++) |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
280 { |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
281 const char *p; |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
282 memcpy (haystack, h, h_len + 1); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
283 memcpy (haystack + i, needle, strlen (needle) + 1); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
284 p = memmem (haystack, strlen (haystack), needle, strlen (needle)); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
285 ASSERT (p); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
286 ASSERT (p - haystack == i); |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
287 } |
39836
7e5ce9b777a1
Apply Jim Meyering's fix from 2015-01-11 to more tests.
Bruno Haible <bruno@clisp.org>
parents:
19484
diff
changeset
|
288 free (haystack); |
14395
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
289 } |
bf7bdef206dd
strstr: expand test coverage
Eric Blake <eblake@redhat.com>
parents:
14079
diff
changeset
|
290 |
39838
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
291 /* Test long needles. */ |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
292 { |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
293 size_t m = 1024; |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
294 char *haystack = (char *) malloc (2 * m + 1); |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
295 char *needle = (char *) malloc (m + 1); |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
296 if (haystack != NULL && needle != NULL) |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
297 { |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
298 const char *p; |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
299 haystack[0] = 'x'; |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
300 memset (haystack + 1, ' ', m - 1); |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
301 memset (haystack + m, 'x', m); |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
302 haystack[2 * m] = '\0'; |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
303 memset (needle, 'x', m); |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
304 needle[m] = '\0'; |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
305 p = memmem (haystack, strlen (haystack), needle, strlen (needle)); |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
306 ASSERT (p); |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
307 ASSERT (p - haystack == m); |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
308 } |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
309 free (needle); |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
310 free (haystack); |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
311 } |
92143bff3a3f
Add test case from a recent glibc bug.
Bruno Haible <bruno@clisp.org>
parents:
39836
diff
changeset
|
312 |
5310
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
313 return 0; |
26382eb5dbd2
New module 'memmem', from Simon Josefsson.
Bruno Haible <bruno@clisp.org>
parents:
diff
changeset
|
314 } |