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