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
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 
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:
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 
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())
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>
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>
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>
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 
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 
227 template <class _RandomAccessIterator1,
228           class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
229           class _BinaryPredicate = equal_to<>>
230 class _LIBCPP_TEMPLATE_VIS boyer_moore_horspool_searcher {
231 private:
232   using difference_type = typename iterator_traits<_RandomAccessIterator1>::difference_type;
233   using value_type = typename iterator_traits<_RandomAccessIterator1>::value_type;
234   using __skip_table_type = _BMSkipTable<value_type,
235                                          difference_type,
236                                          _Hash,
237                                          _BinaryPredicate,
238                                          is_integral_v<value_type>
239                                       && sizeof(value_type) == 1
240                                       && is_same_v<_Hash, hash<value_type>>
241                                       && is_same_v<_BinaryPredicate, equal_to<>>>;
242 public:
243   boyer_moore_horspool_searcher(_RandomAccessIterator1 __first,
244                                 _RandomAccessIterator1 __last,
245                                 _Hash __hash = _Hash(),
246                                 _BinaryPredicate __pred = _BinaryPredicate())
247     : __first_(__first),
248       __last_(__last),
249       __pred_(__pred),
250       __pattern_length_(__last - __first),
251       __skip_table_(std::make_shared<__skip_table_type>(__pattern_length_, __pattern_length_, __hash, __pred_)) {
252     if (__first == __last)
253       return;
254     --__last;
255     difference_type __i = 0;
256     while (__first != __last) {
257       __skip_table_->insert(*__first, __pattern_length_ - 1 - __i);
258       ++__first;
259       ++__i;
260     }
261   }
262 
263   template <class _RandomAccessIterator2>
264   pair<_RandomAccessIterator2, _RandomAccessIterator2>
265   operator()(_RandomAccessIterator2 __first, _RandomAccessIterator2 __last) const {
266     static_assert(__is_same_uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type,
267                                     typename std::iterator_traits<_RandomAccessIterator2>::value_type>::value,
268                   "Corpus and Pattern iterators must point to the same type");
269     if (__first == __last)
270       return std::make_pair(__last, __last);
271     if (__first_ == __last_)
272       return std::make_pair(__first, __first);
273 
274     if (__pattern_length_ > __last - __first)
275       return std::make_pair(__last, __last);
276 
277     return __search(__first, __last);
278   }
279 
280 private:
281   _RandomAccessIterator1 __first_;
282   _RandomAccessIterator1 __last_;
283   _BinaryPredicate __pred_;
284   difference_type __pattern_length_;
285   shared_ptr<__skip_table_type> __skip_table_;
286 
287   template <class _RandomAccessIterator2>
288   pair<_RandomAccessIterator2, _RandomAccessIterator2>
289   __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const {
290     _RandomAccessIterator2 __current = __f;
291     const _RandomAccessIterator2 __last = __l - __pattern_length_;
292     const __skip_table_type& __skip_table = *__skip_table_;
293 
294     while (__current <= __last) {
295       difference_type __j = __pattern_length_;
296       while (__pred_(__first_[__j - 1], __current[__j - 1])) {
297         --__j;
298         if (__j == 0)
299           return std::make_pair(__current, __current + __pattern_length_);
300       }
301       __current += __skip_table[__current[__pattern_length_ - 1]];
302     }
303     return std::make_pair(__l, __l);
304   }
305 };
306 
307 _LIBCPP_END_NAMESPACE_STD
308 
309 _LIBCPP_POP_MACROS
310 
311 #endif // _LIBCPP_STD_VER > 14
312 
313 #endif // _LIBCPP___FUNCTIONAL_BOYER_MOORE_SEARCHER_H
314