v1/__functional/boyer_moore_searcher.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___FUNCTIONAL_BOYER_MOORE_SEARCHER_H
0010 #define _LIBCPP___FUNCTIONAL_BOYER_MOORE_SEARCHER_H
0011
0012 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0013 #  pragma GCC system_header
0014 #endif
0015
0016 #include <__algorithm/fill_n.h>
0017 #include <__config>
0018 #include <__functional/hash.h>
0019 #include <__functional/operations.h>
0020 #include <__iterator/distance.h>
0021 #include <__iterator/iterator_traits.h>
0022 #include <__memory/shared_ptr.h>
0023 #include <__type_traits/make_unsigned.h>
0024 #include <__utility/pair.h>
0025 #include <__vector/vector.h>
0026 #include <array>
0027 #include <limits>
0028 #include <unordered_map>
0029
0030 #if _LIBCPP_STD_VER >= 17
0031
0032 _LIBCPP_PUSH_MACROS
0033 #  include <__undef_macros>
0034
0035 _LIBCPP_BEGIN_NAMESPACE_STD
0036
0037 template <class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/>
0038 class _BMSkipTable;
0039
0040 // General case for BM data searching; use a map
0041 template <class _Key, class _Value, class _Hash, class _BinaryPredicate>
0042 class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> {
0043 private:
0044   using value_type = _Value;
0045   using key_type   = _Key;
0046
0047   const value_type __default_value_;
0048   unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table_;
0049
0050 public:
0051   _LIBCPP_HIDE_FROM_ABI explicit _BMSkipTable(
0052       size_t __sz, value_type __default_value, _Hash __hash, _BinaryPredicate __pred)
0053       : __default_value_(__default_value), __table_(__sz, __hash, __pred) {}
0054
0055   _LIBCPP_HIDE_FROM_ABI void insert(const key_type& __key, value_type __val) { __table_[__key] = __val; }
0056
0057   _LIBCPP_HIDE_FROM_ABI value_type operator[](const key_type& __key) const {
0058     auto __it = __table_.find(__key);
0059     return __it == __table_.end() ? __default_value_ : __it->second;
0060   }
0061 };
0062
0063 // Special case small numeric values; use an array
0064 template <class _Key, class _Value, class _Hash, class _BinaryPredicate>
0065 class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> {
0066 private:
0067   using value_type = _Value;
0068   using key_type   = _Key;
0069
0070   using unsigned_key_type = make_unsigned_t<key_type>;
0071   std::array<value_type, 256> __table_;
0072   static_assert(numeric_limits<unsigned_key_type>::max() < 256);
0073
0074 public:
0075   _LIBCPP_HIDE_FROM_ABI explicit _BMSkipTable(size_t, value_type __default_value, _Hash, _BinaryPredicate) {
0076     std::fill_n(__table_.data(), __table_.size(), __default_value);
0077   }
0078
0079   _LIBCPP_HIDE_FROM_ABI void insert(key_type __key, value_type __val) {
0080     __table_[static_cast<unsigned_key_type>(__key)] = __val;
0081   }
0082
0083   _LIBCPP_HIDE_FROM_ABI value_type operator[](key_type __key) const {
0084     return __table_[static_cast<unsigned_key_type>(__key)];
0085   }
0086 };
0087
0088 template <class _RandomAccessIterator1,
0089           class _Hash            = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
0090           class _BinaryPredicate = equal_to<>>
0091 class _LIBCPP_TEMPLATE_VIS boyer_moore_searcher {
0092 private:
0093   using difference_type = typename std::iterator_traits<_RandomAccessIterator1>::difference_type;
0094   using value_type      = typename std::iterator_traits<_RandomAccessIterator1>::value_type;
0095   using __skip_table_type _LIBCPP_NODEBUG =
0096       _BMSkipTable<value_type,
0097                    difference_type,
0098                    _Hash,
0099                    _BinaryPredicate,
0100                    is_integral_v<value_type> && sizeof(value_type) == 1 && is_same_v<_Hash, hash<value_type>> &&
0101                        is_same_v<_BinaryPredicate, equal_to<>>>;
0102
0103 public:
0104   _LIBCPP_HIDE_FROM_ABI boyer_moore_searcher(
0105       _RandomAccessIterator1 __first,
0106       _RandomAccessIterator1 __last,
0107       _Hash __hash            = _Hash(),
0108       _BinaryPredicate __pred = _BinaryPredicate())
0109       : __first_(__first),
0110         __last_(__last),
0111         __pred_(__pred),
0112         __pattern_length_(__last - __first),
0113         __skip_table_(std::make_shared<__skip_table_type>(__pattern_length_, -1, __hash, __pred_)),
0114         __suffix_(std::__allocate_shared_unbounded_array<difference_type[]>(
0115             allocator<difference_type>(), __pattern_length_ + 1)) {
0116     difference_type __i = 0;
0117     while (__first != __last) {
0118       __skip_table_->insert(*__first, __i);
0119       ++__first;
0120       ++__i;
0121     }
0122     __build_suffix_table(__first_, __last_, __pred_);
0123   }
0124
0125   template <class _RandomAccessIterator2>
0126   _LIBCPP_HIDE_FROM_ABI pair<_RandomAccessIterator2, _RandomAccessIterator2>
0127   operator()(_RandomAccessIterator2 __first, _RandomAccessIterator2 __last) const {
0128     static_assert(__is_same_uncvref<typename iterator_traits<_RandomAccessIterator1>::value_type,
0129                                     typename iterator_traits<_RandomAccessIterator2>::value_type>::value,
0130                   "Corpus and Pattern iterators must point to the same type");
0131     if (__first == __last)
0132       return std::make_pair(__last, __last);
0133     if (__first_ == __last_)
0134       return std::make_pair(__first, __first);
0135
0136     if (__pattern_length_ > (__last - __first))
0137       return std::make_pair(__last, __last);
0138     return __search(__first, __last);
0139   }
0140
0141 private:
0142   _RandomAccessIterator1 __first_;
0143   _RandomAccessIterator1 __last_;
0144   _BinaryPredicate __pred_;
0145   difference_type __pattern_length_;
0146   shared_ptr<__skip_table_type> __skip_table_;
0147   shared_ptr<difference_type[]> __suffix_;
0148
0149   template <class _RandomAccessIterator2>
0150   _LIBCPP_HIDE_FROM_ABI pair<_RandomAccessIterator2, _RandomAccessIterator2>
0151   __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const {
0152     _RandomAccessIterator2 __current      = __f;
0153     const _RandomAccessIterator2 __last   = __l - __pattern_length_;
0154     const __skip_table_type& __skip_table = *__skip_table_;
0155
0156     while (__current <= __last) {
0157       difference_type __j = __pattern_length_;
0158       while (__pred_(__first_[__j - 1], __current[__j - 1])) {
0159         --__j;
0160         if (__j == 0)
0161           return std::make_pair(__current, __current + __pattern_length_);
0162       }
0163
0164       difference_type __k = __skip_table[__current[__j - 1]];
0165       difference_type __m = __j - __k - 1;
0166       if (__k < __j && __m > __suffix_[__j])
0167         __current += __m;
0168       else
0169         __current += __suffix_[__j];
0170     }
0171     return std::make_pair(__l, __l);
0172   }
0173
0174   template <class _Iterator, class _Container>
0175   _LIBCPP_HIDE_FROM_ABI void
0176   __compute_bm_prefix(_Iterator __first, _Iterator __last, _BinaryPredicate __pred, _Container& __prefix) {
0177     const size_t __count = __last - __first;
0178
0179     __prefix[0] = 0;
0180     size_t __k  = 0;
0181
0182     for (size_t __i = 1; __i != __count; ++__i) {
0183       while (__k > 0 && !__pred(__first[__k], __first[__i]))
0184         __k = __prefix[__k - 1];
0185
0186       if (__pred(__first[__k], __first[__i]))
0187         ++__k;
0188       __prefix[__i] = __k;
0189     }
0190   }
0191
0192   _LIBCPP_HIDE_FROM_ABI void
0193   __build_suffix_table(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _BinaryPredicate __pred) {
0194     const size_t __count = __last - __first;
0195
0196     if (__count == 0)
0197       return;
0198
0199     vector<difference_type> __scratch(__count);
0200
0201     __compute_bm_prefix(__first, __last, __pred, __scratch);
0202     for (size_t __i = 0; __i <= __count; ++__i)
0203       __suffix_[__i] = __count - __scratch[__count - 1];
0204
0205     using _ReverseIter = reverse_iterator<_RandomAccessIterator1>;
0206     __compute_bm_prefix(_ReverseIter(__last), _ReverseIter(__first), __pred, __scratch);
0207
0208     for (size_t __i = 0; __i != __count; ++__i) {
0209       const size_t __j          = __count - __scratch[__i];
0210       const difference_type __k = __i - __scratch[__i] + 1;
0211
0212       if (__suffix_[__j] > __k)
0213         __suffix_[__j] = __k;
0214     }
0215   }
0216 };
0217 _LIBCPP_CTAD_SUPPORTED_FOR_TYPE(boyer_moore_searcher);
0218
0219 template <class _RandomAccessIterator1,
0220           class _Hash            = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
0221           class _BinaryPredicate = equal_to<>>
0222 class _LIBCPP_TEMPLATE_VIS boyer_moore_horspool_searcher {
0223 private:
0224   using difference_type = typename iterator_traits<_RandomAccessIterator1>::difference_type;
0225   using value_type      = typename iterator_traits<_RandomAccessIterator1>::value_type;
0226   using __skip_table_type _LIBCPP_NODEBUG =
0227       _BMSkipTable<value_type,
0228                    difference_type,
0229                    _Hash,
0230                    _BinaryPredicate,
0231                    is_integral_v<value_type> && sizeof(value_type) == 1 && is_same_v<_Hash, hash<value_type>> &&
0232                        is_same_v<_BinaryPredicate, equal_to<>>>;
0233
0234 public:
0235   _LIBCPP_HIDE_FROM_ABI boyer_moore_horspool_searcher(
0236       _RandomAccessIterator1 __first,
0237       _RandomAccessIterator1 __last,
0238       _Hash __hash            = _Hash(),
0239       _BinaryPredicate __pred = _BinaryPredicate())
0240       : __first_(__first),
0241         __last_(__last),
0242         __pred_(__pred),
0243         __pattern_length_(__last - __first),
0244         __skip_table_(std::make_shared<__skip_table_type>(__pattern_length_, __pattern_length_, __hash, __pred_)) {
0245     if (__first == __last)
0246       return;
0247     --__last;
0248     difference_type __i = 0;
0249     while (__first != __last) {
0250       __skip_table_->insert(*__first, __pattern_length_ - 1 - __i);
0251       ++__first;
0252       ++__i;
0253     }
0254   }
0255
0256   template <class _RandomAccessIterator2>
0257   _LIBCPP_HIDE_FROM_ABI pair<_RandomAccessIterator2, _RandomAccessIterator2>
0258   operator()(_RandomAccessIterator2 __first, _RandomAccessIterator2 __last) const {
0259     static_assert(__is_same_uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type,
0260                                     typename std::iterator_traits<_RandomAccessIterator2>::value_type>::value,
0261                   "Corpus and Pattern iterators must point to the same type");
0262     if (__first == __last)
0263       return std::make_pair(__last, __last);
0264     if (__first_ == __last_)
0265       return std::make_pair(__first, __first);
0266
0267     if (__pattern_length_ > __last - __first)
0268       return std::make_pair(__last, __last);
0269
0270     return __search(__first, __last);
0271   }
0272
0273 private:
0274   _RandomAccessIterator1 __first_;
0275   _RandomAccessIterator1 __last_;
0276   _BinaryPredicate __pred_;
0277   difference_type __pattern_length_;
0278   shared_ptr<__skip_table_type> __skip_table_;
0279
0280   template <class _RandomAccessIterator2>
0281   _LIBCPP_HIDE_FROM_ABI pair<_RandomAccessIterator2, _RandomAccessIterator2>
0282   __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const {
0283     _RandomAccessIterator2 __current      = __f;
0284     const _RandomAccessIterator2 __last   = __l - __pattern_length_;
0285     const __skip_table_type& __skip_table = *__skip_table_;
0286
0287     while (__current <= __last) {
0288       difference_type __j = __pattern_length_;
0289       while (__pred_(__first_[__j - 1], __current[__j - 1])) {
0290         --__j;
0291         if (__j == 0)
0292           return std::make_pair(__current, __current + __pattern_length_);
0293       }
0294       __current += __skip_table[__current[__pattern_length_ - 1]];
0295     }
0296     return std::make_pair(__l, __l);
0297   }
0298 };
0299 _LIBCPP_CTAD_SUPPORTED_FOR_TYPE(boyer_moore_horspool_searcher);
0300
0301 _LIBCPP_END_NAMESPACE_STD
0302
0303 _LIBCPP_POP_MACROS
0304
0305 #endif // _LIBCPP_STD_VER >= 17
0306
0307 #endif // _LIBCPP___FUNCTIONAL_BOYER_MOORE_SEARCHER_H