1 // Copyright (C) 2014-2018 Free Software Foundation, Inc.
2 //
3 // This file is part of the GNU ISO C++ Library. This library is free
4 // software; you can redistribute it and/or modify it under the
5 // terms of the GNU General Public License as published by the
6 // Free Software Foundation; either version 3, or (at your option)
7 // any later version.
8
9 // This library 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 along
15 // with this library; see the file COPYING3. If not see
16 // <http://www.gnu.org/licenses/>.
17
18 // { dg-options "-std=gnu++17" }
19
20 #include <functional>
21 #include <cstring>
22 #ifdef _GLIBCXX_USE_WCHAR_T
23 # include <cwchar>
24 #endif
25 #include <algorithm>
26 #include <testsuite_hooks.h>
27
28 #ifndef __cpp_lib_boyer_moore_searcher
29 # error "Feature-test macro for searchers missing"
30 #elif __cpp_lib_boyer_moore_searcher < 201603
31 # error "Feature-test macro for searchers has wrong value"
32 #endif
33
34 using std::default_searcher;
35 using std::boyer_moore_searcher;
36 using std::boyer_moore_horspool_searcher;
37
38 void
test01()39 test01()
40 {
41 const char s[] = { 'a', (char)-97, 'a', '\0' };
42 const char* needles[] = {
43 s, "", "a", "aa", "aaa", "ab", "cd", "abcd", "abcdabcd", "abcabcd"
44 };
45 const char* haystacks[] = {
46 s, "", "a", "aa", "aaa", "ab", "cd", "abcd", "abcdabcd", "abcabcd",
47 "aaaaaaa", "aabaa", "aaacab", "cdabcdab", "abcdabcd", "xyzabcdxyz"
48 };
49
50 for (auto n : needles)
51 {
52 auto nlen = std::strlen(n);
53 auto ne = n + nlen;
54 default_searcher d(n, ne);
55 boyer_moore_searcher bm(n, ne);
56 boyer_moore_horspool_searcher bmh(n, ne);
57 for (auto h : haystacks)
58 {
59 auto he = h + std::strlen(h);
60 auto res = std::search(h, he, n, ne);
61 auto d_res = d(h, he);
62 VERIFY( d_res.first == res );
63 if (res == he)
64 VERIFY( d_res.second == d_res.first );
65 else
66 VERIFY( d_res.second == (d_res.first + nlen) );
67 auto bm_res = bm(h, he);
68 VERIFY( bm_res.first == res );
69 if (res == he)
70 VERIFY( bm_res.second == bm_res.first );
71 else
72 VERIFY( bm_res.second == (bm_res.first + nlen) );
73 auto bmh_res = bmh(h, he);
74 VERIFY( bmh_res.first == res );
75 if (res == he)
76 VERIFY( bmh_res.second == bmh_res.first );
77 else
78 VERIFY( bmh_res.second == (bmh_res.first + nlen) );
79 }
80 }
81 }
82
83 void
test02()84 test02()
85 {
86 #ifdef _GLIBCXX_USE_WCHAR_T
87 const wchar_t s[] = { L'a', (wchar_t)-97, L'a', L'\0' };
88 const wchar_t* needles[] = {
89 s, L"", L"a", L"aa", L"aaa", L"ab", L"cd", L"abcd", L"abcdabcd", L"abcabcd"
90 };
91 const wchar_t* haystacks[] = {
92 s, L"", L"a", L"aa", L"aaa", L"ab", L"cd", L"abcd", L"abcdabcd", L"abcabcd",
93 L"aaaaaaa", L"aabaa", L"aaacab", L"cdabcdab", L"abcdabcd", L"xyzabcdxyz"
94 };
95
96 for (auto n : needles)
97 {
98 auto nlen = std::wcslen(n);
99 auto ne = n + nlen;
100 default_searcher d(n, ne);
101 boyer_moore_searcher bm(n, ne);
102 boyer_moore_horspool_searcher bmh(n, ne);
103 for (auto h : haystacks)
104 {
105 auto he = h + std::wcslen(h);
106 auto res = std::search(h, he, n, ne);
107 auto d_res = d(h, he);
108 VERIFY( d_res.first == res );
109 if (res == he)
110 VERIFY( d_res.second == d_res.first );
111 else
112 VERIFY( d_res.second == (d_res.first + nlen) );
113 auto bm_res = bm(h, he);
114 VERIFY( bm_res.first == res );
115 if (res == he)
116 VERIFY( bm_res.second == bm_res.first );
117 else
118 VERIFY( bm_res.second == (bm_res.first + nlen) );
119 auto bmh_res = bmh(h, he);
120 VERIFY( bmh_res.first == res );
121 if (res == he)
122 VERIFY( bmh_res.second == bmh_res.first );
123 else
124 VERIFY( bmh_res.second == (bmh_res.first + nlen) );
125 }
126 }
127 #endif
128 }
129
130 void
test03()131 test03()
132 {
133 // custom predicate
134 struct
135 {
136 static unsigned char
137 norm(unsigned char c) { return std::isalnum(c) ? c : '#'; }
138
139 // equality
140 bool operator()(char l, char r) const { return norm(l) == norm(r); }
141
142 // hash
143 std::size_t operator()(char c) const { return std::hash<char>{}(norm(c)); }
144 } eq;
145
146 const char* needle = " foo 123 ";
147 const char* haystack = "*****foo*123******";
148 auto nlen = std::strlen(needle);
149 const char* ne = needle + nlen;
150 const char* he = haystack + std::strlen(haystack);
151
152 default_searcher d(needle, ne, eq);
153 boyer_moore_searcher bm(needle, ne, eq, eq);
154 boyer_moore_horspool_searcher bmh(needle, ne, eq, eq);
155
156 auto res = std::search(haystack, he, needle, ne, eq);
157 auto d_res = d(haystack, he);
158 VERIFY( d_res.first == res );
159 if (res == he)
160 VERIFY( d_res.second == d_res.first );
161 else
162 VERIFY( d_res.second == (d_res.first + nlen) );
163 auto bm_res = bm(haystack, he);
164 VERIFY( bm_res.first == res );
165 if (res == he)
166 VERIFY( bm_res.second == bm_res.first );
167 else
168 VERIFY( bm_res.second == (bm_res.first + nlen) );
169 auto bmh_res = bmh(haystack, he);
170 VERIFY( bmh_res.first == res );
171 if (res == he)
172 VERIFY( bmh_res.second == bmh_res.first );
173 else
174 VERIFY( bmh_res.second == (bmh_res.first + nlen) );
175 }
176
177 int
main()178 main()
179 {
180 test01();
181 test02();
182 test03();
183 }
184