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