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