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