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