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