1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_EXPERIMENTAL_FUNCTIONAL 11#define _LIBCPP_EXPERIMENTAL_FUNCTIONAL 12 13/* 14 experimental/functional synopsis 15 16#include <algorithm> 17 18namespace std { 19namespace experimental { 20inline namespace fundamentals_v1 { 21 // 4.3, Searchers 22 template<class ForwardIterator, class BinaryPredicate = equal_to<>> 23 class default_searcher; 24 25 template<class RandomAccessIterator, 26 class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 27 class BinaryPredicate = equal_to<>> 28 class boyer_moore_searcher; 29 30 template<class RandomAccessIterator, 31 class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 32 class BinaryPredicate = equal_to<>> 33 class boyer_moore_horspool_searcher; 34 35 template<class ForwardIterator, class BinaryPredicate = equal_to<>> 36 default_searcher<ForwardIterator, BinaryPredicate> 37 make_default_searcher(ForwardIterator pat_first, ForwardIterator pat_last, 38 BinaryPredicate pred = BinaryPredicate()); 39 40 template<class RandomAccessIterator, 41 class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 42 class BinaryPredicate = equal_to<>> 43 boyer_moore_searcher<RandomAccessIterator, Hash, BinaryPredicate> 44 make_boyer_moore_searcher( 45 RandomAccessIterator pat_first, RandomAccessIterator pat_last, 46 Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); 47 48 template<class RandomAccessIterator, 49 class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>, 50 class BinaryPredicate = equal_to<>> 51 boyer_moore_horspool_searcher<RandomAccessIterator, Hash, BinaryPredicate> 52 make_boyer_moore_horspool_searcher( 53 RandomAccessIterator pat_first, RandomAccessIterator pat_last, 54 Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); 55 56 } // namespace fundamentals_v1 57 } // namespace experimental 58 59} // namespace std 60 61*/ 62 63#include <__debug> 64#include <__memory/uses_allocator.h> 65#include <algorithm> 66#include <array> 67#include <experimental/__config> 68#include <functional> 69#include <type_traits> 70#include <unordered_map> 71#include <vector> 72 73#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 74# pragma GCC system_header 75#endif 76 77_LIBCPP_PUSH_MACROS 78#include <__undef_macros> 79 80_LIBCPP_BEGIN_NAMESPACE_LFTS 81 82#if _LIBCPP_STD_VER > 11 83// default searcher 84template<class _ForwardIterator, class _BinaryPredicate = equal_to<>> 85class _LIBCPP_TEMPLATE_VIS default_searcher { 86public: 87 _LIBCPP_INLINE_VISIBILITY 88 default_searcher(_ForwardIterator __f, _ForwardIterator __l, 89 _BinaryPredicate __p = _BinaryPredicate()) 90 : __first_(__f), __last_(__l), __pred_(__p) {} 91 92 template <typename _ForwardIterator2> 93 _LIBCPP_INLINE_VISIBILITY 94 pair<_ForwardIterator2, _ForwardIterator2> 95 operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const 96 { 97 return _VSTD::__search(__f, __l, __first_, __last_, __pred_, 98 typename iterator_traits<_ForwardIterator>::iterator_category(), 99 typename iterator_traits<_ForwardIterator2>::iterator_category()); 100 } 101 102private: 103 _ForwardIterator __first_; 104 _ForwardIterator __last_; 105 _BinaryPredicate __pred_; 106 }; 107 108template<class _ForwardIterator, class _BinaryPredicate = equal_to<>> 109_LIBCPP_INLINE_VISIBILITY 110default_searcher<_ForwardIterator, _BinaryPredicate> 111make_default_searcher( _ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate ()) 112{ 113 return default_searcher<_ForwardIterator, _BinaryPredicate>(__f, __l, __p); 114} 115 116template<class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/> class _BMSkipTable; 117 118// General case for BM data searching; use a map 119template<class _Key, typename _Value, class _Hash, class _BinaryPredicate> 120class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> { 121 typedef _Value value_type; 122 typedef _Key key_type; 123 124 const _Value __default_value_; 125 std::unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table; 126 127public: 128 _LIBCPP_INLINE_VISIBILITY 129 _BMSkipTable(size_t __sz, _Value __default, _Hash __hf, _BinaryPredicate __pred) 130 : __default_value_(__default), __table(__sz, __hf, __pred) {} 131 132 _LIBCPP_INLINE_VISIBILITY 133 void insert(const key_type &__key, value_type __val) 134 { 135 __table [__key] = __val; // Would skip_.insert (val) be better here? 136 } 137 138 _LIBCPP_INLINE_VISIBILITY 139 value_type operator [](const key_type & __key) const 140 { 141 auto __it = __table.find (__key); 142 return __it == __table.end() ? __default_value_ : __it->second; 143 } 144}; 145 146 147// Special case small numeric values; use an array 148template<class _Key, typename _Value, class _Hash, class _BinaryPredicate> 149class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> { 150private: 151 typedef _Value value_type; 152 typedef _Key key_type; 153 154 typedef typename make_unsigned<key_type>::type unsigned_key_type; 155 typedef std::array<value_type, numeric_limits<unsigned_key_type>::max()> skip_map; 156 skip_map __table; 157 158public: 159 _LIBCPP_INLINE_VISIBILITY 160 _BMSkipTable(size_t /*__sz*/, _Value __default, _Hash /*__hf*/, _BinaryPredicate /*__pred*/) 161 { 162 std::fill_n(__table.begin(), __table.size(), __default); 163 } 164 165 _LIBCPP_INLINE_VISIBILITY 166 void insert(key_type __key, value_type __val) 167 { 168 __table[static_cast<unsigned_key_type>(__key)] = __val; 169 } 170 171 _LIBCPP_INLINE_VISIBILITY 172 value_type operator [](key_type __key) const 173 { 174 return __table[static_cast<unsigned_key_type>(__key)]; 175 } 176}; 177 178 179template <class _RandomAccessIterator1, 180 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>, 181 class _BinaryPredicate = equal_to<>> 182class _LIBCPP_TEMPLATE_VIS boyer_moore_searcher { 183private: 184 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type; 185 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type; 186 typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate, 187 is_integral<value_type>::value && // what about enums? 188 sizeof(value_type) == 1 && 189 is_same<_Hash, hash<value_type>>::value && 190 is_same<_BinaryPredicate, equal_to<>>::value 191 > skip_table_type; 192 193public: 194 boyer_moore_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, 195 _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate()) 196 : __first_(__f), __last_(__l), __pred_(__pred), 197 __pattern_length_(_VSTD::distance(__first_, __last_)), 198 __skip_{make_shared<skip_table_type>(__pattern_length_, -1, __hf, __pred_)}, 199 __suffix_{make_shared<vector<difference_type>>(__pattern_length_ + 1)} 200 { 201 // build the skip table 202 for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i ) 203 __skip_->insert(*__f, __i); 204 205 this->__build_suffix_table ( __first_, __last_, __pred_ ); 206 } 207 208 template <typename _RandomAccessIterator2> 209 pair<_RandomAccessIterator2, _RandomAccessIterator2> 210 operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 211 { 212 static_assert ( std::is_same< 213 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type, 214 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type 215 >::value, 216 "Corpus and Pattern iterators must point to the same type" ); 217 218 if (__f == __l ) return make_pair(__l, __l); // empty corpus 219 if (__first_ == __last_) return make_pair(__f, __f); // empty pattern 220 221 // If the pattern is larger than the corpus, we can't find it! 222 if ( __pattern_length_ > _VSTD::distance(__f, __l)) 223 return make_pair(__l, __l); 224 225 // Do the search 226 return this->__search(__f, __l); 227 } 228 229private: 230 _RandomAccessIterator1 __first_; 231 _RandomAccessIterator1 __last_; 232 _BinaryPredicate __pred_; 233 difference_type __pattern_length_; 234 shared_ptr<skip_table_type> __skip_; 235 shared_ptr<vector<difference_type>> __suffix_; 236 237 template <typename _RandomAccessIterator2> 238 pair<_RandomAccessIterator2, _RandomAccessIterator2> 239 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 240 { 241 _RandomAccessIterator2 __cur = __f; 242 const _RandomAccessIterator2 __last = __l - __pattern_length_; 243 const skip_table_type & __skip = *__skip_.get(); 244 const vector<difference_type> & __suffix = *__suffix_.get(); 245 246 while (__cur <= __last) 247 { 248 249 // Do we match right where we are? 250 difference_type __j = __pattern_length_; 251 while (__pred_(__first_ [__j-1], __cur [__j-1])) { 252 __j--; 253 // We matched - we're done! 254 if ( __j == 0 ) 255 return make_pair(__cur, __cur + __pattern_length_); 256 } 257 258 // Since we didn't match, figure out how far to skip forward 259 difference_type __k = __skip[__cur [ __j - 1 ]]; 260 difference_type __m = __j - __k - 1; 261 if (__k < __j && __m > __suffix[ __j ]) 262 __cur += __m; 263 else 264 __cur += __suffix[ __j ]; 265 } 266 267 return make_pair(__l, __l); // We didn't find anything 268 } 269 270 271 template<typename _Iterator, typename _Container> 272 void __compute_bm_prefix ( _Iterator __f, _Iterator __l, _BinaryPredicate __pred, _Container &__prefix ) 273 { 274 const size_t __count = _VSTD::distance(__f, __l); 275 276 __prefix[0] = 0; 277 size_t __k = 0; 278 for ( size_t __i = 1; __i < __count; ++__i ) 279 { 280 while ( __k > 0 && !__pred ( __f[__k], __f[__i] )) 281 __k = __prefix [ __k - 1 ]; 282 283 if ( __pred ( __f[__k], __f[__i] )) 284 __k++; 285 __prefix [ __i ] = __k; 286 } 287 } 288 289 void __build_suffix_table(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, 290 _BinaryPredicate __pred) 291 { 292 const size_t __count = _VSTD::distance(__f, __l); 293 vector<difference_type> & __suffix = *__suffix_.get(); 294 if (__count > 0) 295 { 296 vector<value_type> __scratch(__count); 297 298 __compute_bm_prefix(__f, __l, __pred, __scratch); 299 for ( size_t __i = 0; __i <= __count; __i++ ) 300 __suffix[__i] = __count - __scratch[__count-1]; 301 302 typedef reverse_iterator<_RandomAccessIterator1> _RevIter; 303 __compute_bm_prefix(_RevIter(__l), _RevIter(__f), __pred, __scratch); 304 305 for ( size_t __i = 0; __i < __count; __i++ ) 306 { 307 const size_t __j = __count - __scratch[__i]; 308 const difference_type __k = __i - __scratch[__i] + 1; 309 310 if (__suffix[__j] > __k) 311 __suffix[__j] = __k; 312 } 313 } 314 } 315 316}; 317 318template<class _RandomAccessIterator, 319 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>, 320 class _BinaryPredicate = equal_to<>> 321_LIBCPP_INLINE_VISIBILITY 322boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> 323make_boyer_moore_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l, 324 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) 325{ 326 return boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); 327} 328 329// boyer-moore-horspool 330template <class _RandomAccessIterator1, 331 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>, 332 class _BinaryPredicate = equal_to<>> 333class _LIBCPP_TEMPLATE_VIS boyer_moore_horspool_searcher { 334private: 335 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type; 336 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type; 337 typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate, 338 is_integral<value_type>::value && // what about enums? 339 sizeof(value_type) == 1 && 340 is_same<_Hash, hash<value_type>>::value && 341 is_same<_BinaryPredicate, equal_to<>>::value 342 > skip_table_type; 343 344public: 345 boyer_moore_horspool_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, 346 _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate()) 347 : __first_(__f), __last_(__l), __pred_(__pred), 348 __pattern_length_(_VSTD::distance(__first_, __last_)), 349 __skip_{_VSTD::make_shared<skip_table_type>(__pattern_length_, __pattern_length_, __hf, __pred_)} 350 { 351 // build the skip table 352 if ( __f != __l ) 353 { 354 __l = __l - 1; 355 for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i ) 356 __skip_->insert(*__f, __pattern_length_ - 1 - __i); 357 } 358 } 359 360 template <typename _RandomAccessIterator2> 361 pair<_RandomAccessIterator2, _RandomAccessIterator2> 362 operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 363 { 364 static_assert ( std::is_same< 365 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type, 366 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type 367 >::value, 368 "Corpus and Pattern iterators must point to the same type" ); 369 370 if (__f == __l ) return make_pair(__l, __l); // empty corpus 371 if (__first_ == __last_) return make_pair(__f, __f); // empty pattern 372 373 // If the pattern is larger than the corpus, we can't find it! 374 if ( __pattern_length_ > _VSTD::distance(__f, __l)) 375 return make_pair(__l, __l); 376 377 // Do the search 378 return this->__search(__f, __l); 379 } 380 381private: 382 _RandomAccessIterator1 __first_; 383 _RandomAccessIterator1 __last_; 384 _BinaryPredicate __pred_; 385 difference_type __pattern_length_; 386 shared_ptr<skip_table_type> __skip_; 387 388 template <typename _RandomAccessIterator2> 389 pair<_RandomAccessIterator2, _RandomAccessIterator2> 390 __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const { 391 _RandomAccessIterator2 __cur = __f; 392 const _RandomAccessIterator2 __last = __l - __pattern_length_; 393 const skip_table_type & __skip = *__skip_.get(); 394 395 while (__cur <= __last) 396 { 397 // Do we match right where we are? 398 difference_type __j = __pattern_length_; 399 while (__pred_(__first_[__j-1], __cur[__j-1])) 400 { 401 __j--; 402 // We matched - we're done! 403 if ( __j == 0 ) 404 return make_pair(__cur, __cur + __pattern_length_); 405 } 406 __cur += __skip[__cur[__pattern_length_-1]]; 407 } 408 409 return make_pair(__l, __l); 410 } 411}; 412 413template<class _RandomAccessIterator, 414 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>, 415 class _BinaryPredicate = equal_to<>> 416_LIBCPP_INLINE_VISIBILITY 417boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> 418make_boyer_moore_horspool_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l, 419 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) 420{ 421 return boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); 422} 423 424#endif // _LIBCPP_STD_VER > 11 425 426_LIBCPP_END_NAMESPACE_LFTS 427 428_LIBCPP_POP_MACROS 429 430#endif /* _LIBCPP_EXPERIMENTAL_FUNCTIONAL */ 431