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 ( std::is_same< 212 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type, 213 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type 214 >::value, 215 "Corpus and Pattern iterators must point to the same type" ); 216 217 if (__f == __l ) return make_pair(__l, __l); // empty corpus 218 if (__first_ == __last_) return make_pair(__f, __f); // empty pattern 219 220 // If the pattern is larger than the corpus, we can't find it! 221 if ( __pattern_length_ > _VSTD::distance(__f, __l)) 222 return make_pair(__l, __l); 223 224 // Do the search 225 return this->__search(__f, __l); 226 } 227 228private: 229 _RandomAccessIterator1 __first_; 230 _RandomAccessIterator1 __last_; 231 _BinaryPredicate __pred_; 232 difference_type __pattern_length_; 233 shared_ptr<skip_table_type> __skip_; 234 shared_ptr<vector<difference_type>> __suffix_; 235 236 template <typename _RandomAccessIterator2> 237 pair<_RandomAccessIterator2, _RandomAccessIterator2> 238 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 239 { 240 _RandomAccessIterator2 __cur = __f; 241 const _RandomAccessIterator2 __last = __l - __pattern_length_; 242 const skip_table_type & __skip = *__skip_.get(); 243 const vector<difference_type> & __suffix = *__suffix_.get(); 244 245 while (__cur <= __last) 246 { 247 248 // Do we match right where we are? 249 difference_type __j = __pattern_length_; 250 while (__pred_(__first_ [__j-1], __cur [__j-1])) { 251 __j--; 252 // We matched - we're done! 253 if ( __j == 0 ) 254 return make_pair(__cur, __cur + __pattern_length_); 255 } 256 257 // Since we didn't match, figure out how far to skip forward 258 difference_type __k = __skip[__cur [ __j - 1 ]]; 259 difference_type __m = __j - __k - 1; 260 if (__k < __j && __m > __suffix[ __j ]) 261 __cur += __m; 262 else 263 __cur += __suffix[ __j ]; 264 } 265 266 return make_pair(__l, __l); // We didn't find anything 267 } 268 269 270 template<typename _Iterator, typename _Container> 271 void __compute_bm_prefix ( _Iterator __f, _Iterator __l, _BinaryPredicate __pred, _Container &__prefix ) 272 { 273 const size_t __count = _VSTD::distance(__f, __l); 274 275 __prefix[0] = 0; 276 size_t __k = 0; 277 for ( size_t __i = 1; __i < __count; ++__i ) 278 { 279 while ( __k > 0 && !__pred ( __f[__k], __f[__i] )) 280 __k = __prefix [ __k - 1 ]; 281 282 if ( __pred ( __f[__k], __f[__i] )) 283 __k++; 284 __prefix [ __i ] = __k; 285 } 286 } 287 288 void __build_suffix_table(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, 289 _BinaryPredicate __pred) 290 { 291 const size_t __count = _VSTD::distance(__f, __l); 292 vector<difference_type> & __suffix = *__suffix_.get(); 293 if (__count > 0) 294 { 295 vector<value_type> __scratch(__count); 296 297 __compute_bm_prefix(__f, __l, __pred, __scratch); 298 for ( size_t __i = 0; __i <= __count; __i++ ) 299 __suffix[__i] = __count - __scratch[__count-1]; 300 301 typedef reverse_iterator<_RandomAccessIterator1> _RevIter; 302 __compute_bm_prefix(_RevIter(__l), _RevIter(__f), __pred, __scratch); 303 304 for ( size_t __i = 0; __i < __count; __i++ ) 305 { 306 const size_t __j = __count - __scratch[__i]; 307 const difference_type __k = __i - __scratch[__i] + 1; 308 309 if (__suffix[__j] > __k) 310 __suffix[__j] = __k; 311 } 312 } 313 } 314 315}; 316 317template<class _RandomAccessIterator, 318 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>, 319 class _BinaryPredicate = equal_to<>> 320_LIBCPP_INLINE_VISIBILITY 321boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> 322make_boyer_moore_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l, 323 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) 324{ 325 return boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); 326} 327 328// boyer-moore-horspool 329template <class _RandomAccessIterator1, 330 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>, 331 class _BinaryPredicate = equal_to<>> 332class _LIBCPP_TEMPLATE_VIS boyer_moore_horspool_searcher { 333private: 334 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type; 335 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type; 336 typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate, 337 is_integral<value_type>::value && // what about enums? 338 sizeof(value_type) == 1 && 339 is_same<_Hash, hash<value_type>>::value && 340 is_same<_BinaryPredicate, equal_to<>>::value 341 > skip_table_type; 342 343public: 344 boyer_moore_horspool_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, 345 _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate()) 346 : __first_(__f), __last_(__l), __pred_(__pred), 347 __pattern_length_(_VSTD::distance(__first_, __last_)), 348 __skip_{_VSTD::make_shared<skip_table_type>(__pattern_length_, __pattern_length_, __hf, __pred_)} 349 { 350 // build the skip table 351 if ( __f != __l ) 352 { 353 __l = __l - 1; 354 for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i ) 355 __skip_->insert(*__f, __pattern_length_ - 1 - __i); 356 } 357 } 358 359 template <typename _RandomAccessIterator2> 360 pair<_RandomAccessIterator2, _RandomAccessIterator2> 361 operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const 362 { 363 static_assert ( std::is_same< 364 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type>::type, 365 typename std::__uncvref<typename std::iterator_traits<_RandomAccessIterator2>::value_type>::type 366 >::value, 367 "Corpus and Pattern iterators must point to the same type" ); 368 369 if (__f == __l ) return make_pair(__l, __l); // empty corpus 370 if (__first_ == __last_) return make_pair(__f, __f); // empty pattern 371 372 // If the pattern is larger than the corpus, we can't find it! 373 if ( __pattern_length_ > _VSTD::distance(__f, __l)) 374 return make_pair(__l, __l); 375 376 // Do the search 377 return this->__search(__f, __l); 378 } 379 380private: 381 _RandomAccessIterator1 __first_; 382 _RandomAccessIterator1 __last_; 383 _BinaryPredicate __pred_; 384 difference_type __pattern_length_; 385 shared_ptr<skip_table_type> __skip_; 386 387 template <typename _RandomAccessIterator2> 388 pair<_RandomAccessIterator2, _RandomAccessIterator2> 389 __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const { 390 _RandomAccessIterator2 __cur = __f; 391 const _RandomAccessIterator2 __last = __l - __pattern_length_; 392 const skip_table_type & __skip = *__skip_.get(); 393 394 while (__cur <= __last) 395 { 396 // Do we match right where we are? 397 difference_type __j = __pattern_length_; 398 while (__pred_(__first_[__j-1], __cur[__j-1])) 399 { 400 __j--; 401 // We matched - we're done! 402 if ( __j == 0 ) 403 return make_pair(__cur, __cur + __pattern_length_); 404 } 405 __cur += __skip[__cur[__pattern_length_-1]]; 406 } 407 408 return make_pair(__l, __l); 409 } 410}; 411 412template<class _RandomAccessIterator, 413 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>, 414 class _BinaryPredicate = equal_to<>> 415_LIBCPP_INLINE_VISIBILITY 416boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> 417make_boyer_moore_horspool_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l, 418 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) 419{ 420 return boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); 421} 422 423#endif // _LIBCPP_STD_VER > 11 424 425_LIBCPP_END_NAMESPACE_LFTS 426 427_LIBCPP_POP_MACROS 428 429#endif /* _LIBCPP_EXPERIMENTAL_FUNCTIONAL */ 430