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