1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___FUNCTIONAL_BOYER_MOORE_SEARCHER_H
10#define _LIBCPP___FUNCTIONAL_BOYER_MOORE_SEARCHER_H
11
12#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
13# pragma GCC system_header
14#endif
15
16#include <__algorithm/fill_n.h>
17#include <__config>
18#include <__functional/hash.h>
19#include <__functional/operations.h>
20#include <__iterator/iterator_traits.h>
21#include <__memory/shared_ptr.h>
22#include <__type_traits/make_unsigned.h>
23#include <__utility/pair.h>
24#include <array>
25#include <limits>
26#include <unordered_map>
27
28#if _LIBCPP_STD_VER >= 17
29
30_LIBCPP_PUSH_MACROS
31# include <__undef_macros>
32
33_LIBCPP_BEGIN_NAMESPACE_STD
34
35template <class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/>
36class _BMSkipTable;
37
38// General case for BM data searching; use a map
39template <class _Key, class _Value, class _Hash, class _BinaryPredicate>
40class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> {
41private:
42 using value_type = _Value;
43 using key_type = _Key;
44
45 const value_type __default_value_;
46 unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table_;
47
48public:
49 explicit _BMSkipTable(size_t __sz, value_type __default_value, _Hash __hash, _BinaryPredicate __pred)
50 : __default_value_(__default_value), __table_(__sz, __hash, __pred) {}
51
52 void insert(const key_type& __key, value_type __val) { __table_[__key] = __val; }
53
54 value_type operator[](const key_type& __key) const {
55 auto __it = __table_.find(__key);
56 return __it == __table_.end() ? __default_value_ : __it->second;
57 }
58};
59
60// Special case small numeric values; use an array
61template <class _Key, class _Value, class _Hash, class _BinaryPredicate>
62class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> {
63private:
64 using value_type = _Value;
65 using key_type = _Key;
66
67 using unsigned_key_type = make_unsigned_t<key_type>;
68 std::array<value_type, 256> __table_;
69 static_assert(numeric_limits<unsigned_key_type>::max() < 256);
70
71public:
72 explicit _BMSkipTable(size_t, value_type __default_value, _Hash, _BinaryPredicate) {
73 _LIBCPP_DIAGNOSTIC_PUSH
74 _LIBCPP_GCC_DIAGNOSTIC_IGNORED("-Wmaybe-uninitialized")
75 std::fill_n(__table_.data(), __table_.size(), __default_value);
76 _LIBCPP_DIAGNOSTIC_POP
77 }
78
79 void insert(key_type __key, value_type __val) { __table_[static_cast<unsigned_key_type>(__key)] = __val; }
80
81 value_type operator[](key_type __key) const { return __table_[static_cast<unsigned_key_type>(__key)]; }
82};
83
84template <class _RandomAccessIterator1,
85 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
86 class _BinaryPredicate = equal_to<>>
87class boyer_moore_searcher {
88private:
89 using difference_type = typename std::iterator_traits<_RandomAccessIterator1>::difference_type;
90 using value_type = typename std::iterator_traits<_RandomAccessIterator1>::value_type;
91 using __skip_table_type _LIBCPP_NODEBUG =
92 _BMSkipTable<value_type,
93 difference_type,
94 _Hash,
95 _BinaryPredicate,
96 is_integral_v<value_type> && sizeof(value_type) == 1 && is_same_v<_Hash, hash<value_type>> &&
97 is_same_v<_BinaryPredicate, equal_to<>>>;
98
99public:
100 boyer_moore_searcher(_RandomAccessIterator1 __first,
101 _RandomAccessIterator1 __last,
102 _Hash __hash = _Hash(),
103 _BinaryPredicate __pred = _BinaryPredicate())
104 : __first_(__first),
105 __last_(__last),
106 __pred_(__pred),
107 __pattern_length_(__last - __first),
108 __skip_table_(std::make_shared<__skip_table_type>(__pattern_length_, -1, __hash, __pred_)),
109 __suffix_(std::__allocate_shared_unbounded_array<difference_type[]>(
110 allocator<difference_type>(), __pattern_length_ + 1)) {
111 difference_type __i = 0;
112 while (__first != __last) {
113 __skip_table_->insert(*__first, __i);
114 ++__first;
115 ++__i;
116 }
117 __build_suffix_table(first: __first_, last: __last_, pred: __pred_);
118 }
119
120 template <class _RandomAccessIterator2>
121 pair<_RandomAccessIterator2, _RandomAccessIterator2>
122 operator()(_RandomAccessIterator2 __first, _RandomAccessIterator2 __last) const {
123 static_assert(is_same_v<__remove_cvref_t<typename iterator_traits<_RandomAccessIterator1>::value_type>,
124 __remove_cvref_t<typename iterator_traits<_RandomAccessIterator2>::value_type>>,
125 "Corpus and Pattern iterators must point to the same type");
126 if (__first == __last)
127 return std::make_pair(__last, __last);
128 if (__first_ == __last_)
129 return std::make_pair(__first, __first);
130
131 if (__pattern_length_ > (__last - __first))
132 return std::make_pair(__last, __last);
133 return __search(__first, __last);
134 }
135
136private:
137 _RandomAccessIterator1 __first_;
138 _RandomAccessIterator1 __last_;
139 _BinaryPredicate __pred_;
140 difference_type __pattern_length_;
141 shared_ptr<__skip_table_type> __skip_table_;
142 shared_ptr<difference_type[]> __suffix_;
143
144 template <class _RandomAccessIterator2>
145 pair<_RandomAccessIterator2, _RandomAccessIterator2>
146 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const {
147 _RandomAccessIterator2 __current = __f;
148 const _RandomAccessIterator2 __last = __l - __pattern_length_;
149 const __skip_table_type& __skip_table = *__skip_table_;
150
151 while (__current <= __last) {
152 difference_type __j = __pattern_length_;
153 while (__pred_(__first_[__j - 1], __current[__j - 1])) {
154 --__j;
155 if (__j == 0)
156 return std::make_pair(__current, __current + __pattern_length_);
157 }
158
159 difference_type __k = __skip_table[__current[__j - 1]];
160 difference_type __m = __j - __k - 1;
161 if (__k < __j && __m > __suffix_[__j])
162 __current += __m;
163 else
164 __current += __suffix_[__j];
165 }
166 return std::make_pair(__l, __l);
167 }
168
169 template <class _Iterator, class _Container>
170 void __compute_bm_prefix(_Iterator __first, _Iterator __last, _BinaryPredicate __pred, _Container& __prefix) {
171 const size_t __count = __last - __first;
172
173 __prefix[0] = 0;
174 size_t __k = 0;
175
176 for (size_t __i = 1; __i != __count; ++__i) {
177 while (__k > 0 && !__pred(__first[__k], __first[__i]))
178 __k = __prefix[__k - 1];
179
180 if (__pred(__first[__k], __first[__i]))
181 ++__k;
182 __prefix[__i] = __k;
183 }
184 }
185
186 void __build_suffix_table(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _BinaryPredicate __pred) {
187 const size_t __count = __last - __first;
188
189 if (__count == 0)
190 return;
191
192 auto __scratch = std::make_unique<difference_type[]>(__count);
193
194 __compute_bm_prefix(__first, __last, __pred, __scratch);
195 for (size_t __i = 0; __i <= __count; ++__i)
196 __suffix_[__i] = __count - __scratch[__count - 1];
197
198 using _ReverseIter = reverse_iterator<_RandomAccessIterator1>;
199 __compute_bm_prefix(_ReverseIter(__last), _ReverseIter(__first), __pred, __scratch);
200
201 for (size_t __i = 0; __i != __count; ++__i) {
202 const size_t __j = __count - __scratch[__i];
203 const difference_type __k = __i - __scratch[__i] + 1;
204
205 if (__suffix_[__j] > __k)
206 __suffix_[__j] = __k;
207 }
208 }
209};
210_LIBCPP_CTAD_SUPPORTED_FOR_TYPE(boyer_moore_searcher);
211
212template <class _RandomAccessIterator1,
213 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
214 class _BinaryPredicate = equal_to<>>
215class boyer_moore_horspool_searcher {
216private:
217 using difference_type = typename iterator_traits<_RandomAccessIterator1>::difference_type;
218 using value_type = typename iterator_traits<_RandomAccessIterator1>::value_type;
219 using __skip_table_type _LIBCPP_NODEBUG =
220 _BMSkipTable<value_type,
221 difference_type,
222 _Hash,
223 _BinaryPredicate,
224 is_integral_v<value_type> && sizeof(value_type) == 1 && is_same_v<_Hash, hash<value_type>> &&
225 is_same_v<_BinaryPredicate, equal_to<>>>;
226
227public:
228 boyer_moore_horspool_searcher(_RandomAccessIterator1 __first,
229 _RandomAccessIterator1 __last,
230 _Hash __hash = _Hash(),
231 _BinaryPredicate __pred = _BinaryPredicate())
232 : __first_(__first),
233 __last_(__last),
234 __pred_(__pred),
235 __pattern_length_(__last - __first),
236 __skip_table_(std::make_shared<__skip_table_type>(__pattern_length_, __pattern_length_, __hash, __pred_)) {
237 if (__first == __last)
238 return;
239 --__last;
240 difference_type __i = 0;
241 while (__first != __last) {
242 __skip_table_->insert(*__first, __pattern_length_ - 1 - __i);
243 ++__first;
244 ++__i;
245 }
246 }
247
248 template <class _RandomAccessIterator2>
249 pair<_RandomAccessIterator2, _RandomAccessIterator2>
250 operator()(_RandomAccessIterator2 __first, _RandomAccessIterator2 __last) const {
251 static_assert(is_same_v<__remove_cvref_t<typename std::iterator_traits<_RandomAccessIterator1>::value_type>,
252 __remove_cvref_t<typename std::iterator_traits<_RandomAccessIterator2>::value_type>>,
253 "Corpus and Pattern iterators must point to the same type");
254 if (__first == __last)
255 return std::make_pair(__last, __last);
256 if (__first_ == __last_)
257 return std::make_pair(__first, __first);
258
259 if (__pattern_length_ > __last - __first)
260 return std::make_pair(__last, __last);
261
262 return __search(__first, __last);
263 }
264
265private:
266 _RandomAccessIterator1 __first_;
267 _RandomAccessIterator1 __last_;
268 _BinaryPredicate __pred_;
269 difference_type __pattern_length_;
270 shared_ptr<__skip_table_type> __skip_table_;
271
272 template <class _RandomAccessIterator2>
273 pair<_RandomAccessIterator2, _RandomAccessIterator2>
274 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const {
275 _RandomAccessIterator2 __current = __f;
276 const _RandomAccessIterator2 __last = __l - __pattern_length_;
277 const __skip_table_type& __skip_table = *__skip_table_;
278
279 while (__current <= __last) {
280 difference_type __j = __pattern_length_;
281 while (__pred_(__first_[__j - 1], __current[__j - 1])) {
282 --__j;
283 if (__j == 0)
284 return std::make_pair(__current, __current + __pattern_length_);
285 }
286 __current += __skip_table[__current[__pattern_length_ - 1]];
287 }
288 return std::make_pair(__l, __l);
289 }
290};
291_LIBCPP_CTAD_SUPPORTED_FOR_TYPE(boyer_moore_horspool_searcher);
292
293_LIBCPP_END_NAMESPACE_STD
294
295_LIBCPP_POP_MACROS
296
297#endif // _LIBCPP_STD_VER >= 17
298
299#endif // _LIBCPP___FUNCTIONAL_BOYER_MOORE_SEARCHER_H
300