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 _LIBCPP_HIDE_FROM_ABI explicit _BMSkipTable(
50 size_t __sz, value_type __default_value, _Hash __hash, _BinaryPredicate __pred)
51 : __default_value_(__default_value), __table_(__sz, __hash, __pred) {}
52
53 _LIBCPP_HIDE_FROM_ABI void insert(const key_type& __key, value_type __val) { __table_[__key] = __val; }
54
55 _LIBCPP_HIDE_FROM_ABI value_type operator[](const key_type& __key) const {
56 auto __it = __table_.find(__key);
57 return __it == __table_.end() ? __default_value_ : __it->second;
58 }
59};
60
61// Special case small numeric values; use an array
62template <class _Key, class _Value, class _Hash, class _BinaryPredicate>
63class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> {
64private:
65 using value_type = _Value;
66 using key_type = _Key;
67
68 using unsigned_key_type = make_unsigned_t<key_type>;
69 std::array<value_type, 256> __table_;
70 static_assert(numeric_limits<unsigned_key_type>::max() < 256);
71
72public:
73 _LIBCPP_HIDE_FROM_ABI explicit _BMSkipTable(size_t, value_type __default_value, _Hash, _BinaryPredicate) {
74 _LIBCPP_DIAGNOSTIC_PUSH
75 _LIBCPP_GCC_DIAGNOSTIC_IGNORED("-Wmaybe-uninitialized")
76 std::fill_n(__table_.data(), __table_.size(), __default_value);
77 _LIBCPP_DIAGNOSTIC_POP
78 }
79
80 _LIBCPP_HIDE_FROM_ABI void insert(key_type __key, value_type __val) {
81 __table_[static_cast<unsigned_key_type>(__key)] = __val;
82 }
83
84 _LIBCPP_HIDE_FROM_ABI value_type operator[](key_type __key) const {
85 return __table_[static_cast<unsigned_key_type>(__key)];
86 }
87};
88
89template <class _RandomAccessIterator1,
90 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
91 class _BinaryPredicate = equal_to<>>
92class boyer_moore_searcher {
93private:
94 using difference_type = typename std::iterator_traits<_RandomAccessIterator1>::difference_type;
95 using value_type = typename std::iterator_traits<_RandomAccessIterator1>::value_type;
96 using __skip_table_type _LIBCPP_NODEBUG =
97 _BMSkipTable<value_type,
98 difference_type,
99 _Hash,
100 _BinaryPredicate,
101 is_integral_v<value_type> && sizeof(value_type) == 1 && is_same_v<_Hash, hash<value_type>> &&
102 is_same_v<_BinaryPredicate, equal_to<>>>;
103
104public:
105 _LIBCPP_HIDE_FROM_ABI boyer_moore_searcher(
106 _RandomAccessIterator1 __first,
107 _RandomAccessIterator1 __last,
108 _Hash __hash = _Hash(),
109 _BinaryPredicate __pred = _BinaryPredicate())
110 : __first_(__first),
111 __last_(__last),
112 __pred_(__pred),
113 __pattern_length_(__last - __first),
114 __skip_table_(std::make_shared<__skip_table_type>(__pattern_length_, -1, __hash, __pred_)),
115 __suffix_(std::__allocate_shared_unbounded_array<difference_type[]>(
116 allocator<difference_type>(), __pattern_length_ + 1)) {
117 difference_type __i = 0;
118 while (__first != __last) {
119 __skip_table_->insert(*__first, __i);
120 ++__first;
121 ++__i;
122 }
123 __build_suffix_table(first: __first_, last: __last_, pred: __pred_);
124 }
125
126 template <class _RandomAccessIterator2>
127 _LIBCPP_HIDE_FROM_ABI pair<_RandomAccessIterator2, _RandomAccessIterator2>
128 operator()(_RandomAccessIterator2 __first, _RandomAccessIterator2 __last) const {
129 static_assert(is_same_v<__remove_cvref_t<typename iterator_traits<_RandomAccessIterator1>::value_type>,
130 __remove_cvref_t<typename iterator_traits<_RandomAccessIterator2>::value_type>>,
131 "Corpus and Pattern iterators must point to the same type");
132 if (__first == __last)
133 return std::make_pair(__last, __last);
134 if (__first_ == __last_)
135 return std::make_pair(__first, __first);
136
137 if (__pattern_length_ > (__last - __first))
138 return std::make_pair(__last, __last);
139 return __search(__first, __last);
140 }
141
142private:
143 _RandomAccessIterator1 __first_;
144 _RandomAccessIterator1 __last_;
145 _BinaryPredicate __pred_;
146 difference_type __pattern_length_;
147 shared_ptr<__skip_table_type> __skip_table_;
148 shared_ptr<difference_type[]> __suffix_;
149
150 template <class _RandomAccessIterator2>
151 _LIBCPP_HIDE_FROM_ABI pair<_RandomAccessIterator2, _RandomAccessIterator2>
152 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const {
153 _RandomAccessIterator2 __current = __f;
154 const _RandomAccessIterator2 __last = __l - __pattern_length_;
155 const __skip_table_type& __skip_table = *__skip_table_;
156
157 while (__current <= __last) {
158 difference_type __j = __pattern_length_;
159 while (__pred_(__first_[__j - 1], __current[__j - 1])) {
160 --__j;
161 if (__j == 0)
162 return std::make_pair(__current, __current + __pattern_length_);
163 }
164
165 difference_type __k = __skip_table[__current[__j - 1]];
166 difference_type __m = __j - __k - 1;
167 if (__k < __j && __m > __suffix_[__j])
168 __current += __m;
169 else
170 __current += __suffix_[__j];
171 }
172 return std::make_pair(__l, __l);
173 }
174
175 template <class _Iterator, class _Container>
176 _LIBCPP_HIDE_FROM_ABI void
177 __compute_bm_prefix(_Iterator __first, _Iterator __last, _BinaryPredicate __pred, _Container& __prefix) {
178 const size_t __count = __last - __first;
179
180 __prefix[0] = 0;
181 size_t __k = 0;
182
183 for (size_t __i = 1; __i != __count; ++__i) {
184 while (__k > 0 && !__pred(__first[__k], __first[__i]))
185 __k = __prefix[__k - 1];
186
187 if (__pred(__first[__k], __first[__i]))
188 ++__k;
189 __prefix[__i] = __k;
190 }
191 }
192
193 _LIBCPP_HIDE_FROM_ABI void
194 __build_suffix_table(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _BinaryPredicate __pred) {
195 const size_t __count = __last - __first;
196
197 if (__count == 0)
198 return;
199
200 auto __scratch = std::make_unique<difference_type[]>(__count);
201
202 __compute_bm_prefix(__first, __last, __pred, __scratch);
203 for (size_t __i = 0; __i <= __count; ++__i)
204 __suffix_[__i] = __count - __scratch[__count - 1];
205
206 using _ReverseIter = reverse_iterator<_RandomAccessIterator1>;
207 __compute_bm_prefix(_ReverseIter(__last), _ReverseIter(__first), __pred, __scratch);
208
209 for (size_t __i = 0; __i != __count; ++__i) {
210 const size_t __j = __count - __scratch[__i];
211 const difference_type __k = __i - __scratch[__i] + 1;
212
213 if (__suffix_[__j] > __k)
214 __suffix_[__j] = __k;
215 }
216 }
217};
218_LIBCPP_CTAD_SUPPORTED_FOR_TYPE(boyer_moore_searcher);
219
220template <class _RandomAccessIterator1,
221 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
222 class _BinaryPredicate = equal_to<>>
223class boyer_moore_horspool_searcher {
224private:
225 using difference_type = typename iterator_traits<_RandomAccessIterator1>::difference_type;
226 using value_type = typename iterator_traits<_RandomAccessIterator1>::value_type;
227 using __skip_table_type _LIBCPP_NODEBUG =
228 _BMSkipTable<value_type,
229 difference_type,
230 _Hash,
231 _BinaryPredicate,
232 is_integral_v<value_type> && sizeof(value_type) == 1 && is_same_v<_Hash, hash<value_type>> &&
233 is_same_v<_BinaryPredicate, equal_to<>>>;
234
235public:
236 _LIBCPP_HIDE_FROM_ABI boyer_moore_horspool_searcher(
237 _RandomAccessIterator1 __first,
238 _RandomAccessIterator1 __last,
239 _Hash __hash = _Hash(),
240 _BinaryPredicate __pred = _BinaryPredicate())
241 : __first_(__first),
242 __last_(__last),
243 __pred_(__pred),
244 __pattern_length_(__last - __first),
245 __skip_table_(std::make_shared<__skip_table_type>(__pattern_length_, __pattern_length_, __hash, __pred_)) {
246 if (__first == __last)
247 return;
248 --__last;
249 difference_type __i = 0;
250 while (__first != __last) {
251 __skip_table_->insert(*__first, __pattern_length_ - 1 - __i);
252 ++__first;
253 ++__i;
254 }
255 }
256
257 template <class _RandomAccessIterator2>
258 _LIBCPP_HIDE_FROM_ABI pair<_RandomAccessIterator2, _RandomAccessIterator2>
259 operator()(_RandomAccessIterator2 __first, _RandomAccessIterator2 __last) const {
260 static_assert(is_same_v<__remove_cvref_t<typename std::iterator_traits<_RandomAccessIterator1>::value_type>,
261 __remove_cvref_t<typename std::iterator_traits<_RandomAccessIterator2>::value_type>>,
262 "Corpus and Pattern iterators must point to the same type");
263 if (__first == __last)
264 return std::make_pair(__last, __last);
265 if (__first_ == __last_)
266 return std::make_pair(__first, __first);
267
268 if (__pattern_length_ > __last - __first)
269 return std::make_pair(__last, __last);
270
271 return __search(__first, __last);
272 }
273
274private:
275 _RandomAccessIterator1 __first_;
276 _RandomAccessIterator1 __last_;
277 _BinaryPredicate __pred_;
278 difference_type __pattern_length_;
279 shared_ptr<__skip_table_type> __skip_table_;
280
281 template <class _RandomAccessIterator2>
282 _LIBCPP_HIDE_FROM_ABI pair<_RandomAccessIterator2, _RandomAccessIterator2>
283 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const {
284 _RandomAccessIterator2 __current = __f;
285 const _RandomAccessIterator2 __last = __l - __pattern_length_;
286 const __skip_table_type& __skip_table = *__skip_table_;
287
288 while (__current <= __last) {
289 difference_type __j = __pattern_length_;
290 while (__pred_(__first_[__j - 1], __current[__j - 1])) {
291 --__j;
292 if (__j == 0)
293 return std::make_pair(__current, __current + __pattern_length_);
294 }
295 __current += __skip_table[__current[__pattern_length_ - 1]];
296 }
297 return std::make_pair(__l, __l);
298 }
299};
300_LIBCPP_CTAD_SUPPORTED_FOR_TYPE(boyer_moore_horspool_searcher);
301
302_LIBCPP_END_NAMESPACE_STD
303
304_LIBCPP_POP_MACROS
305
306#endif // _LIBCPP_STD_VER >= 17
307
308#endif // _LIBCPP___FUNCTIONAL_BOYER_MOORE_SEARCHER_H
309