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