codekingpro/portable-devtools
114k
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCUDACXX_EXPERIMENTAL_FUNCTIONAL11#define _LIBCUDACXX_EXPERIMENTAL_FUNCTIONAL12 13/*14 experimental/functional synopsis15 16#include <algorithm>17 18namespace std {19namespace experimental {20inline namespace fundamentals_v1 {21 22 // See C++14 20.9.9, Function object binders23 template <class T> constexpr bool is_bind_expression_v24 = is_bind_expression<T>::value;25 template <class T> constexpr int is_placeholder_v26 = is_placeholder<T>::value;27 28 // 4.2, Class template function29 template<class> class function; // undefined30 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, Searchers45 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_v180 } // namespace experimental81 82 template<class R, class... ArgTypes, class Alloc>83 struct uses_allocator<experimental::function<R(ArgTypes...)>, Alloc>;84 85} // namespace std86 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(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)100# pragma GCC system_header101#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)102# pragma clang system_header103#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)104# pragma system_header105#endif // no system header106 107_LIBCUDACXX_PUSH_MACROS108#include <__undef_macros>109 110 111_LIBCUDACXX_BEGIN_NAMESPACE_LFTS112 113#if _LIBCUDACXX_STD_VER > 11114// default searcher115template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>116class _LIBCUDACXX_TYPE_VIS default_searcher {117public:118 _LIBCUDACXX_INLINE_VISIBILITY119 default_searcher(_ForwardIterator __f, _ForwardIterator __l,120 _BinaryPredicate __p = _BinaryPredicate())121 : __first_(__f), __last_(__l), __pred_(__p) {}122 123 template <typename _ForwardIterator2>124 _LIBCUDACXX_INLINE_VISIBILITY125 pair<_ForwardIterator2, _ForwardIterator2>126 operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const127 {128 return _CUDA_VSTD::__search(__f, __l, __first_, __last_, __pred_,129 typename _CUDA_VSTD::iterator_traits<_ForwardIterator>::iterator_category(),130 typename _CUDA_VSTD::iterator_traits<_ForwardIterator2>::iterator_category());131 }132 133private:134 _ForwardIterator __first_;135 _ForwardIterator __last_;136 _BinaryPredicate __pred_;137 };138 139template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>140_LIBCUDACXX_INLINE_VISIBILITY141default_searcher<_ForwardIterator, _BinaryPredicate>142make_default_searcher( _ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate ())143{144 return default_searcher<_ForwardIterator, _BinaryPredicate>(__f, __l, __p);145}146 147template<class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/> class _BMSkipTable;148 149// General case for BM data searching; use a map150template<class _Key, typename _Value, class _Hash, class _BinaryPredicate>151class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> {152public: // TODO private:153 typedef _Value value_type;154 typedef _Key key_type;155 156 const _Value __default_value_;157 std::unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table;158 159public:160 _LIBCUDACXX_INLINE_VISIBILITY161 _BMSkipTable(std::size_t __sz, _Value __default, _Hash __hf, _BinaryPredicate __pred)162 : __default_value_(__default), __table(__sz, __hf, __pred) {}163 164 _LIBCUDACXX_INLINE_VISIBILITY165 void insert(const key_type &__key, value_type __val)166 {167 __table [__key] = __val; // Would skip_.insert (val) be better here?168 }169 170 _LIBCUDACXX_INLINE_VISIBILITY171 value_type operator [](const key_type & __key) const172 {173 auto __it = __table.find (__key);174 return __it == __table.end() ? __default_value_ : __it->second;175 }176};177 178 179// Special case small numeric values; use an array180template<class _Key, typename _Value, class _Hash, class _BinaryPredicate>181class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> {182private:183 typedef _Value value_type;184 typedef _Key key_type;185 186 typedef typename std::make_unsigned<key_type>::type unsigned_key_type;187 typedef std::array<value_type, _CUDA_VSTD::numeric_limits<unsigned_key_type>::max()> skip_map;188 skip_map __table;189 190public:191 _LIBCUDACXX_INLINE_VISIBILITY192 _BMSkipTable(std::size_t /*__sz*/, _Value __default, _Hash /*__hf*/, _BinaryPredicate /*__pred*/)193 {194 std::fill_n(__table.begin(), __table.size(), __default);195 }196 197 _LIBCUDACXX_INLINE_VISIBILITY198 void insert(key_type __key, value_type __val)199 {200 __table[static_cast<unsigned_key_type>(__key)] = __val;201 }202 203 _LIBCUDACXX_INLINE_VISIBILITY204 value_type operator [](key_type __key) const205 {206 return __table[static_cast<unsigned_key_type>(__key)];207 }208};209 210 211template <class _RandomAccessIterator1,212 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,213 class _BinaryPredicate = equal_to<>>214class _LIBCUDACXX_TYPE_VIS boyer_moore_searcher {215private:216 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type;217 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type;218 typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate,219 _CUDA_VSTD::is_integral<value_type>::value && // what about enums?220 sizeof(value_type) == 1 &&221 is_same<_Hash, hash<value_type>>::value &&222 is_same<_BinaryPredicate, equal_to<>>::value223 > skip_table_type;224 225public:226 boyer_moore_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,227 _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate())228 : __first_(__f), __last_(__l), __pred_(__pred),229 __pattern_length_(_CUDA_VSTD::distance(__first_, __last_)),230 __skip_{make_shared<skip_table_type>(__pattern_length_, -1, __hf, __pred_)},231 __suffix_{make_shared<vector<difference_type>>(__pattern_length_ + 1)}232 {233 // build the skip table234 for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i )235 __skip_->insert(*__f, __i);236 237 this->__build_suffix_table ( __first_, __last_, __pred_ );238 }239 240 template <typename _RandomAccessIterator2>241 pair<_RandomAccessIterator2, _RandomAccessIterator2>242 operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const243 {244 static_assert ( std::is_same<245 std::__remove_cvref_t<typename std::iterator_traits<_RandomAccessIterator1>::value_type>,246 std::__remove_cvref_t<typename std::iterator_traits<_RandomAccessIterator2>::value_type>247 >::value,248 "Corpus and Pattern iterators must point to the same type" );249 250 if (__f == __l ) return make_pair(__l, __l); // empty corpus251 if (__first_ == __last_) return make_pair(__f, __f); // empty pattern252 253 // If the pattern is larger than the corpus, we can't find it!254 if ( __pattern_length_ > _CUDA_VSTD::distance (__f, __l))255 return make_pair(__l, __l);256 257 // Do the search258 return this->__search(__f, __l);259 }260 261public: // TODO private:262 _RandomAccessIterator1 __first_;263 _RandomAccessIterator1 __last_;264 _BinaryPredicate __pred_;265 difference_type __pattern_length_;266 shared_ptr<skip_table_type> __skip_;267 shared_ptr<vector<difference_type>> __suffix_;268 269 template <typename _RandomAccessIterator2>270 pair<_RandomAccessIterator2, _RandomAccessIterator2>271 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const272 {273 _RandomAccessIterator2 __cur = __f;274 const _RandomAccessIterator2 __last = __l - __pattern_length_;275 const skip_table_type & __skip = *__skip_.get();276 const vector<difference_type> & __suffix = *__suffix_.get();277 278 while (__cur <= __last)279 {280 281 // Do we match right where we are?282 difference_type __j = __pattern_length_;283 while (__pred_(__first_ [__j-1], __cur [__j-1])) {284 __j--;285 // We matched - we're done!286 if ( __j == 0 )287 return make_pair(__cur, __cur + __pattern_length_);288 }289 290 // Since we didn't match, figure out how far to skip forward291 difference_type __k = __skip[__cur [ __j - 1 ]];292 difference_type __m = __j - __k - 1;293 if (__k < __j && __m > __suffix[ __j ])294 __cur += __m;295 else296 __cur += __suffix[ __j ];297 }298 299 return make_pair(__l, __l); // We didn't find anything300 }301 302 303 template<typename _Iterator, typename _Container>304 void __compute_bm_prefix ( _Iterator __f, _Iterator __l, _BinaryPredicate __pred, _Container &__prefix )305 {306 const std::size_t __count = _CUDA_VSTD::distance(__f, __l);307 308 __prefix[0] = 0;309 std::size_t __k = 0;310 for ( std::size_t __i = 1; __i < __count; ++__i )311 {312 while ( __k > 0 && !__pred ( __f[__k], __f[__i] ))313 __k = __prefix [ __k - 1 ];314 315 if ( __pred ( __f[__k], __f[__i] ))316 __k++;317 __prefix [ __i ] = __k;318 }319 }320 321 void __build_suffix_table(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,322 _BinaryPredicate __pred)323 {324 const std::size_t __count = _CUDA_VSTD::distance(__f, __l);325 vector<difference_type> & __suffix = *__suffix_.get();326 if (__count > 0)327 {328 _CUDA_VSTD::vector<value_type> __scratch(__count);329 330 __compute_bm_prefix(__f, __l, __pred, __scratch);331 for ( std::size_t __i = 0; __i <= __count; __i++ )332 __suffix[__i] = __count - __scratch[__count-1];333 334 typedef _CUDA_VSTD::reverse_iterator<_RandomAccessIterator1> _RevIter;335 __compute_bm_prefix(_RevIter(__l), _RevIter(__f), __pred, __scratch);336 337 for ( std::size_t __i = 0; __i < __count; __i++ )338 {339 const std::size_t __j = __count - __scratch[__i];340 const difference_type __k = __i - __scratch[__i] + 1;341 342 if (__suffix[__j] > __k)343 __suffix[__j] = __k;344 }345 }346 }347 348};349 350template<class _RandomAccessIterator,351 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,352 class _BinaryPredicate = equal_to<>>353_LIBCUDACXX_INLINE_VISIBILITY354boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>355make_boyer_moore_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,356 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ())357{358 return boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p);359}360 361// boyer-moore-horspool362template <class _RandomAccessIterator1,363 class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,364 class _BinaryPredicate = equal_to<>>365class _LIBCUDACXX_TYPE_VIS boyer_moore_horspool_searcher {366private:367 typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type;368 typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type;369 typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate,370 _CUDA_VSTD::is_integral<value_type>::value && // what about enums?371 sizeof(value_type) == 1 &&372 is_same<_Hash, hash<value_type>>::value &&373 is_same<_BinaryPredicate, equal_to<>>::value374 > skip_table_type;375 376public:377 boyer_moore_horspool_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,378 _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate())379 : __first_(__f), __last_(__l), __pred_(__pred),380 __pattern_length_(_CUDA_VSTD::distance(__first_, __last_)),381 __skip_{_CUDA_VSTD::make_shared<skip_table_type>(__pattern_length_, __pattern_length_, __hf, __pred_)}382 {383 // build the skip table384 if ( __f != __l )385 {386 __l = __l - 1;387 for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i )388 __skip_->insert(*__f, __pattern_length_ - 1 - __i);389 }390 }391 392 template <typename _RandomAccessIterator2>393 pair<_RandomAccessIterator2, _RandomAccessIterator2>394 operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const395 {396 static_assert ( std::is_same<397 std::__remove_cvref_t<typename std::iterator_traits<_RandomAccessIterator1>::value_type>,398 std::__remove_cvref_t<typename std::iterator_traits<_RandomAccessIterator2>::value_type>399 >::value,400 "Corpus and Pattern iterators must point to the same type" );401 402 if (__f == __l ) return make_pair(__l, __l); // empty corpus403 if (__first_ == __last_) return make_pair(__f, __f); // empty pattern404 405 // If the pattern is larger than the corpus, we can't find it!406 if ( __pattern_length_ > _CUDA_VSTD::distance (__f, __l))407 return make_pair(__l, __l);408 409 // Do the search410 return this->__search(__f, __l);411 }412 413private:414 _RandomAccessIterator1 __first_;415 _RandomAccessIterator1 __last_;416 _BinaryPredicate __pred_;417 difference_type __pattern_length_;418 shared_ptr<skip_table_type> __skip_;419 420 template <typename _RandomAccessIterator2>421 pair<_RandomAccessIterator2, _RandomAccessIterator2>422 __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const {423 _RandomAccessIterator2 __cur = __f;424 const _RandomAccessIterator2 __last = __l - __pattern_length_;425 const skip_table_type & __skip = *__skip_.get();426 427 while (__cur <= __last)428 {429 // Do we match right where we are?430 difference_type __j = __pattern_length_;431 while (__pred_(__first_[__j-1], __cur[__j-1]))432 {433 __j--;434 // We matched - we're done!435 if ( __j == 0 )436 return make_pair(__cur, __cur + __pattern_length_);437 }438 __cur += __skip[__cur[__pattern_length_-1]];439 }440 441 return make_pair(__l, __l);442 }443};444 445template<class _RandomAccessIterator,446 class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,447 class _BinaryPredicate = equal_to<>>448_LIBCUDACXX_INLINE_VISIBILITY449boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>450make_boyer_moore_horspool_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,451 _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ())452{453 return boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p);454}455 456#endif // _LIBCUDACXX_STD_VER > 11457 458_LIBCUDACXX_END_NAMESPACE_LFTS459 460_LIBCUDACXX_POP_MACROS461 462#endif /* _LIBCUDACXX_EXPERIMENTAL_FUNCTIONAL */463