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