diff options
Diffstat (limited to 'third_party/libcxx/include/c++/v1/__pstl')
17 files changed, 0 insertions, 2736 deletions
diff --git a/third_party/libcxx/include/c++/v1/__pstl/backend.h b/third_party/libcxx/include/c++/v1/__pstl/backend.h deleted file mode 100644 index 5980b07..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/backend.h +++ /dev/null @@ -1,39 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_BACKEND_H -#define _LIBCPP___PSTL_BACKEND_H - -#include <__config> -#include <__pstl/backend_fwd.h> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -# if defined(_LIBCPP_PSTL_BACKEND_SERIAL) -# include <__pstl/backends/default.h> -# include <__pstl/backends/serial.h> -# elif defined(_LIBCPP_PSTL_BACKEND_STD_THREAD) -# include <__pstl/backends/default.h> -# include <__pstl/backends/std_thread.h> -# elif defined(_LIBCPP_PSTL_BACKEND_LIBDISPATCH) -# include <__pstl/backends/default.h> -# include <__pstl/backends/libdispatch.h> -# endif - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_BACKEND_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/backend_fwd.h b/third_party/libcxx/include/c++/v1/__pstl/backend_fwd.h deleted file mode 100644 index a52e6db..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/backend_fwd.h +++ /dev/null @@ -1,313 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_BACKEND_FWD_H -#define _LIBCPP___PSTL_BACKEND_FWD_H - -#include <__config> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -// -// This header declares available PSTL backends and the functions that must be implemented in order for the -// PSTL algorithms to be provided. -// -// Backends often do not implement the full set of functions themselves -- a configuration of the PSTL is -// usually a set of backends "stacked" together which each implement some algorithms under some execution -// policies. It is only necessary for the "stack" of backends to implement all algorithms under all execution -// policies, but a single backend is not required to implement everything on its own. -// -// The signatures used by each backend function are documented below. -// -// Exception handling -// ================== -// -// PSTL backends are expected to report errors (i.e. failure to allocate) by returning a disengaged `optional` from -// their implementation. Exceptions shouldn't be used to report an internal failure-to-allocate, since all exceptions -// are turned into a program termination at the front-end level. When a backend returns a disengaged `optional` to the -// frontend, the frontend will turn that into a call to `std::__throw_bad_alloc();` to report the internal failure to -// the user. -// - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -template <class... _Backends> -struct __backend_configuration; - -struct __default_backend_tag; -struct __libdispatch_backend_tag; -struct __serial_backend_tag; -struct __std_thread_backend_tag; - -# if defined(_LIBCPP_PSTL_BACKEND_SERIAL) -using __current_configuration _LIBCPP_NODEBUG = __backend_configuration<__serial_backend_tag, __default_backend_tag>; -# elif defined(_LIBCPP_PSTL_BACKEND_STD_THREAD) -using __current_configuration _LIBCPP_NODEBUG = - __backend_configuration<__std_thread_backend_tag, __default_backend_tag>; -# elif defined(_LIBCPP_PSTL_BACKEND_LIBDISPATCH) -using __current_configuration _LIBCPP_NODEBUG = - __backend_configuration<__libdispatch_backend_tag, __default_backend_tag>; -# else - -// ...New vendors can add parallel backends here... - -# error "Invalid PSTL backend configuration" -# endif - -template <class _Backend, class _ExecutionPolicy> -struct __find_if; -// template <class _Policy, class _ForwardIterator, class _Predicate> -// optional<_ForwardIterator> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __find_if_not; -// template <class _Policy, class _ForwardIterator, class _Predicate> -// optional<_ForwardIterator> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __find; -// template <class _Policy, class _ForwardIterator, class _Tp> -// optional<_ForwardIterator> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __any_of; -// template <class _Policy, class _ForwardIterator, class _Predicate> -// optional<bool> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __all_of; -// template <class _Policy, class _ForwardIterator, class _Predicate> -// optional<bool> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __none_of; -// template <class _Policy, class _ForwardIterator, class _Predicate> -// optional<bool> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __is_partitioned; -// template <class _Policy, class _ForwardIterator, class _Predicate> -// optional<bool> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __for_each; -// template <class _Policy, class _ForwardIterator, class _Function> -// optional<__empty> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Function __func) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __for_each_n; -// template <class _Policy, class _ForwardIterator, class _Size, class _Function> -// optional<__empty> -// operator()(_Policy&&, _ForwardIterator __first, _Size __size, _Function __func) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __fill; -// template <class _Policy, class _ForwardIterator, class _Tp> -// optional<__empty> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __fill_n; -// template <class _Policy, class _ForwardIterator, class _Size, class _Tp> -// optional<__empty> -// operator()(_Policy&&, _ForwardIterator __first, _Size __n, _Tp const& __value) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __replace; -// template <class _Policy, class _ForwardIterator, class _Tp> -// optional<__empty> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, -// _Tp const& __old, _Tp const& __new) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __replace_if; -// template <class _Policy, class _ForwardIterator, class _Predicate, class _Tp> -// optional<__empty> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, -// _Predicate __pred, _Tp const& __new_value) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __generate; -// template <class _Policy, class _ForwardIterator, class _Generator> -// optional<__empty> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Generator __gen) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __generate_n; -// template <class _Policy, class _ForwardIterator, class _Size, class _Generator> -// optional<__empty> -// operator()(_Policy&&, _ForwardIterator __first, _Size __n, _Generator __gen) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __merge; -// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Comp> -// optional<_ForwardOutIterator> -// operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1, -// _ForwardIterator2 __first2, _ForwardIterator2 __last2, -// _ForwardOutIterator __result, _Comp __comp) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __stable_sort; -// template <class _Policy, class _RandomAccessIterator, class _Comp> -// optional<__empty> -// operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __sort; -// template <class _Policy, class _RandomAccessIterator, class _Comp> -// optional<__empty> -// operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __transform; -// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _UnaryOperation> -// optional<_ForwardOutIterator> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, -// _ForwardOutIterator __result, -// _UnaryOperation __op) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __transform_binary; -// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, -// class _ForwardOutIterator, -// class _BinaryOperation> -// optional<_ForwardOutIterator> -// operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1, -// _ForwardIterator2 __first2, -// _ForwardOutIterator __result, -// _BinaryOperation __op) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __replace_copy_if; -// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Predicate, class _Tp> -// optional<__empty> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, -// _ForwardOutIterator __out_it, -// _Predicate __pred, -// _Tp const& __new_value) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __replace_copy; -// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Tp> -// optional<__empty> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, -// _ForwardOutIterator __out_it, -// _Tp const& __old_value, -// _Tp const& __new_value) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __move; -// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator> -// optional<_ForwardOutIterator> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, -// _ForwardOutIterator __out_it) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __copy; -// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator> -// optional<_ForwardOutIterator> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, -// _ForwardOutIterator __out_it) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __copy_n; -// template <class _Policy, class _ForwardIterator, class _Size, class _ForwardOutIterator> -// optional<_ForwardOutIterator> -// operator()(_Policy&&, _ForwardIterator __first, _Size __n, _ForwardOutIterator __out_it) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __rotate_copy; -// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator> -// optional<_ForwardOutIterator> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, -// _ForwardOutIterator __out_it) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __transform_reduce; -// template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation> -// optional<_Tp> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, -// _Tp __init, -// _BinaryOperation __reduce, -// _UnaryOperation __transform) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __transform_reduce_binary; -// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, -// class _Tp, class _BinaryOperation1, class _BinaryOperation2> -// optional<_Tp> operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1, -// _ForwardIterator2 __first2, -// _Tp __init, -// _BinaryOperation1 __reduce, -// _BinaryOperation2 __transform) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __count_if; -// template <class _Policy, class _ForwardIterator, class _Predicate> -// optional<__iter_diff_t<_ForwardIterator>> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __count; -// template <class _Policy, class _ForwardIterator, class _Tp> -// optional<__iter_diff_t<_ForwardIterator>> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __equal_3leg; -// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate> -// optional<bool> -// operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1, -// _ForwardIterator2 __first2, -// _Predicate __pred) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __equal; -// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate> -// optional<bool> -// operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1, -// _ForwardIterator2 __first2, _ForwardIterator2 __last2, -// _Predicate __pred) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __reduce; -// template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation> -// optional<_Tp> -// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, -// _Tp __init, _BinaryOperation __op) const noexcept; - -template <class _Backend, class _ExecutionPolicy> -struct __is_sorted; -// template <class _Policy, class _ForwardIterator, class _Comp> -// optional<bool> -// operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Comp&& __comp) const noexcept; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_BACKEND_FWD_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/backends/default.h b/third_party/libcxx/include/c++/v1/__pstl/backends/default.h deleted file mode 100644 index be90715..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/backends/default.h +++ /dev/null @@ -1,539 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_BACKENDS_DEFAULT_H -#define _LIBCPP___PSTL_BACKENDS_DEFAULT_H - -#include <__algorithm/copy_n.h> -#include <__algorithm/equal.h> -#include <__algorithm/fill_n.h> -#include <__algorithm/for_each_n.h> -#include <__algorithm/is_sorted.h> -#include <__config> -#include <__functional/identity.h> -#include <__functional/not_fn.h> -#include <__functional/operations.h> -#include <__iterator/concepts.h> -#include <__iterator/iterator_traits.h> -#include <__iterator/next.h> -#include <__pstl/backend_fwd.h> -#include <__pstl/dispatch.h> -#include <__utility/empty.h> -#include <__utility/forward.h> -#include <__utility/move.h> -#include <optional> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -// -// This file provides an incomplete PSTL backend that implements all of the PSTL algorithms -// based on a smaller set of basis operations. -// -// It is intended as a building block for other PSTL backends that implement some operations more -// efficiently but may not want to define the full set of PSTL algorithms. -// -// This backend implements all the PSTL algorithms based on the following basis operations: -// -// find_if family -// -------------- -// - find -// - find_if_not -// - any_of -// - all_of -// - none_of -// - is_partitioned -// -// for_each family -// --------------- -// - for_each_n -// - fill -// - fill_n -// - replace -// - replace_if -// - generate -// - generate_n -// -// merge family -// ------------ -// No other algorithms based on merge -// -// stable_sort family -// ------------------ -// - sort -// -// transform_reduce and transform_reduce_binary family -// --------------------------------------------------- -// - count_if -// - count -// - equal(3 legs) -// - equal -// - is_sorted -// - reduce -// -// transform and transform_binary family -// ------------------------------------- -// - replace_copy_if -// - replace_copy -// - move -// - copy -// - copy_n -// - rotate_copy -// - -////////////////////////////////////////////////////////////// -// find_if family -////////////////////////////////////////////////////////////// -template <class _ExecutionPolicy> -struct __find<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Tp> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept { - using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>; - return _FindIf()( - __policy, std::move(__first), std::move(__last), [&](__iterator_reference<_ForwardIterator> __element) { - return __element == __value; - }); - } -}; - -template <class _ExecutionPolicy> -struct __find_if_not<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Pred> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { - using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>; - return _FindIf()(__policy, __first, __last, std::not_fn(std::forward<_Pred>(__pred))); - } -}; - -template <class _ExecutionPolicy> -struct __any_of<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Pred> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { - using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>; - auto __res = _FindIf()(__policy, __first, __last, std::forward<_Pred>(__pred)); - if (!__res) - return nullopt; - return *__res != __last; - } -}; - -template <class _ExecutionPolicy> -struct __all_of<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Pred> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { - using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>; - auto __res = _AnyOf()(__policy, __first, __last, [&](__iterator_reference<_ForwardIterator> __value) { - return !__pred(__value); - }); - if (!__res) - return nullopt; - return !*__res; - } -}; - -template <class _ExecutionPolicy> -struct __none_of<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Pred> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { - using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>; - auto __res = _AnyOf()(__policy, __first, __last, std::forward<_Pred>(__pred)); - if (!__res) - return nullopt; - return !*__res; - } -}; - -template <class _ExecutionPolicy> -struct __is_partitioned<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Pred> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { - using _FindIfNot = __dispatch<__find_if_not, __current_configuration, _ExecutionPolicy>; - auto __maybe_first = _FindIfNot()(__policy, std::move(__first), __last, __pred); - if (__maybe_first == nullopt) - return nullopt; - - __first = *__maybe_first; - if (__first == __last) - return true; - ++__first; - using _NoneOf = __dispatch<__none_of, __current_configuration, _ExecutionPolicy>; - return _NoneOf()(__policy, std::move(__first), std::move(__last), __pred); - } -}; - -////////////////////////////////////////////////////////////// -// for_each family -////////////////////////////////////////////////////////////// -template <class _ExecutionPolicy> -struct __for_each_n<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Size, class _Function> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) const noexcept { - if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>; - _ForwardIterator __last = __first + __size; - return _ForEach()(__policy, std::move(__first), std::move(__last), std::move(__func)); - } else { - // Otherwise, use the serial algorithm to avoid doing two passes over the input - std::for_each_n(std::move(__first), __size, std::move(__func)); - return __empty{}; - } - } -}; - -template <class _ExecutionPolicy> -struct __fill<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Tp> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept { - using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>; - using _Ref = __iterator_reference<_ForwardIterator>; - return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __value; }); - } -}; - -template <class _ExecutionPolicy> -struct __fill_n<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Size, class _Tp> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Tp const& __value) const noexcept { - if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - using _Fill = __dispatch<__fill, __current_configuration, _ExecutionPolicy>; - _ForwardIterator __last = __first + __n; - return _Fill()(__policy, std::move(__first), std::move(__last), __value); - } else { - // Otherwise, use the serial algorithm to avoid doing two passes over the input - std::fill_n(std::move(__first), __n, __value); - return optional<__empty>{__empty{}}; - } - } -}; - -template <class _ExecutionPolicy> -struct __replace<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Tp> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __old, _Tp const& __new) - const noexcept { - using _ReplaceIf = __dispatch<__replace_if, __current_configuration, _ExecutionPolicy>; - using _Ref = __iterator_reference<_ForwardIterator>; - return _ReplaceIf()( - __policy, std::move(__first), std::move(__last), [&](_Ref __element) { return __element == __old; }, __new); - } -}; - -template <class _ExecutionPolicy> -struct __replace_if<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Pred, class _Tp> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()( - _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred, _Tp const& __new_value) - const noexcept { - using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>; - using _Ref = __iterator_reference<_ForwardIterator>; - return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { - if (__pred(__element)) - __element = __new_value; - }); - } -}; - -template <class _ExecutionPolicy> -struct __generate<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Generator> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator&& __gen) const noexcept { - using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>; - using _Ref = __iterator_reference<_ForwardIterator>; - return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __gen(); }); - } -}; - -template <class _ExecutionPolicy> -struct __generate_n<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Size, class _Generator> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Generator&& __gen) const noexcept { - using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>; - using _Ref = __iterator_reference<_ForwardIterator>; - return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __gen(); }); - } -}; - -////////////////////////////////////////////////////////////// -// stable_sort family -////////////////////////////////////////////////////////////// -template <class _ExecutionPolicy> -struct __sort<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _RandomAccessIterator, class _Comp> - _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()( - _Policy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept { - using _StableSort = __dispatch<__stable_sort, __current_configuration, _ExecutionPolicy>; - return _StableSort()(__policy, std::move(__first), std::move(__last), std::forward<_Comp>(__comp)); - } -}; - -////////////////////////////////////////////////////////////// -// transform_reduce family -////////////////////////////////////////////////////////////// -template <class _ExecutionPolicy> -struct __count_if<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Predicate> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>> operator()( - _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred) const noexcept { - using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>; - using _DiffT = __iterator_difference_type<_ForwardIterator>; - using _Ref = __iterator_reference<_ForwardIterator>; - return _TransformReduce()( - __policy, std::move(__first), std::move(__last), _DiffT{}, std::plus{}, [&](_Ref __element) -> _DiffT { - return __pred(__element) ? _DiffT(1) : _DiffT(0); - }); - } -}; - -template <class _ExecutionPolicy> -struct __count<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Tp> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept { - using _CountIf = __dispatch<__count_if, __current_configuration, _ExecutionPolicy>; - using _Ref = __iterator_reference<_ForwardIterator>; - return _CountIf()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) -> bool { - return __element == __value; - }); - } -}; - -template <class _ExecutionPolicy> -struct __equal_3leg<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> - operator()(_Policy&& __policy, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _Predicate&& __pred) const noexcept { - using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>; - return _TransformReduce()( - __policy, - std::move(__first1), - std::move(__last1), - std::move(__first2), - true, - std::logical_and{}, - std::forward<_Predicate>(__pred)); - } -}; - -template <class _ExecutionPolicy> -struct __equal<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> - operator()(_Policy&& __policy, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _ForwardIterator2 __last2, - _Predicate&& __pred) const noexcept { - if constexpr (__has_random_access_iterator_category<_ForwardIterator1>::value && - __has_random_access_iterator_category<_ForwardIterator2>::value) { - if (__last1 - __first1 != __last2 - __first2) - return false; - // Fall back to the 3 legged algorithm - using _Equal3Leg = __dispatch<__equal_3leg, __current_configuration, _ExecutionPolicy>; - return _Equal3Leg()( - __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::forward<_Predicate>(__pred)); - } else { - // If we don't have random access, fall back to the serial algorithm cause we can't do much - return std::equal( - std::move(__first1), - std::move(__last1), - std::move(__first2), - std::move(__last2), - std::forward<_Predicate>(__pred)); - } - } -}; - -template <class _ExecutionPolicy> -struct __reduce<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_Tp> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation&& __op) - const noexcept { - using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>; - return _TransformReduce()( - __policy, - std::move(__first), - std::move(__last), - std::move(__init), - std::forward<_BinaryOperation>(__op), - __identity{}); - } -}; - -template <class _ExecutionPolicy> -struct __is_sorted<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Comp> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Comp&& __comp) const noexcept { - if constexpr (__has_bidirectional_iterator_category<_ForwardIterator>::value) { - if (__first == __last) - return true; // Empty, sorted by definition - _ForwardIterator __first2 = std::next(__first); - if (__first2 == __last) - return true; // Only one element, sorted by definition - --__last; // Make two iterator ranges: [__first, __first + n - 1) and [__first + 1, __first + n) - using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>; - using _Ref = __iterator_reference<_ForwardIterator>; - return _TransformReduce()( - __policy, - std::move(__first), - std::move(__last), - std::move(__first2), - true, - std::logical_and{}, - [&](_Ref __left, _Ref __right) -> bool { return !__comp(__right, __left); }); - } else { - // Currently anything outside bidirectional iterators has to be processed serially - return std::is_sorted(std::move(__first), std::move(__last), std::forward<_Comp>(__comp)); - } - } -}; - -////////////////////////////////////////////////////////////// -// transform family -////////////////////////////////////////////////////////////// -template <class _ExecutionPolicy> -struct __replace_copy_if<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Pred, class _Tp> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&& __policy, - _ForwardIterator __first, - _ForwardIterator __last, - _ForwardOutIterator __out_it, - _Pred&& __pred, - _Tp const& __new_value) const noexcept { - using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>; - using _Ref = __iterator_reference<_ForwardIterator>; - auto __res = - _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](_Ref __element) { - return __pred(__element) ? __new_value : __element; - }); - if (__res == nullopt) - return nullopt; - return __empty{}; - } -}; - -template <class _ExecutionPolicy> -struct __replace_copy<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Tp> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&& __policy, - _ForwardIterator __first, - _ForwardIterator __last, - _ForwardOutIterator __out_it, - _Tp const& __old_value, - _Tp const& __new_value) const noexcept { - using _ReplaceCopyIf = __dispatch<__replace_copy_if, __current_configuration, _ExecutionPolicy>; - using _Ref = __iterator_reference<_ForwardIterator>; - return _ReplaceCopyIf()( - __policy, - std::move(__first), - std::move(__last), - std::move(__out_it), - [&](_Ref __element) { return __element == __old_value; }, - __new_value); - } -}; - -// TODO: Use the std::copy/move shenanigans to forward to std::memmove -// Investigate whether we want to still forward to std::transform(policy) -// in that case for the execution::par part, or whether we actually want -// to run everything serially in that case. -template <class _ExecutionPolicy> -struct __move<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _ForwardOutIterator> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it) - const noexcept { - using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>; - return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](auto&& __element) { - return std::move(__element); - }); - } -}; - -// TODO: Use the std::copy/move shenanigans to forward to std::memmove -template <class _ExecutionPolicy> -struct __copy<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _ForwardOutIterator> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it) - const noexcept { - using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>; - return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), __identity()); - } -}; - -template <class _ExecutionPolicy> -struct __copy_n<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Size, class _ForwardOutIterator> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> - operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __out_it) const noexcept { - if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>; - _ForwardIterator __last = __first + __n; - return _Copy()(__policy, std::move(__first), std::move(__last), std::move(__out_it)); - } else { - // Otherwise, use the serial algorithm to avoid doing two passes over the input - return std::copy_n(std::move(__first), __n, std::move(__out_it)); - } - } -}; - -template <class _ExecutionPolicy> -struct __rotate_copy<__default_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _ForwardOutIterator> - [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> - operator()(_Policy&& __policy, - _ForwardIterator __first, - _ForwardIterator __middle, - _ForwardIterator __last, - _ForwardOutIterator __out_it) const noexcept { - using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>; - auto __result_mid = _Copy()(__policy, __middle, std::move(__last), std::move(__out_it)); - if (__result_mid == nullopt) - return nullopt; - return _Copy()(__policy, std::move(__first), std::move(__middle), *std::move(__result_mid)); - } -}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_BACKENDS_DEFAULT_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/backends/libdispatch.h b/third_party/libcxx/include/c++/v1/__pstl/backends/libdispatch.h deleted file mode 100644 index 88d4231..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/backends/libdispatch.h +++ /dev/null @@ -1,402 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_BACKENDS_LIBDISPATCH_H -#define _LIBCPP___PSTL_BACKENDS_LIBDISPATCH_H - -#include <__algorithm/inplace_merge.h> -#include <__algorithm/lower_bound.h> -#include <__algorithm/max.h> -#include <__algorithm/merge.h> -#include <__algorithm/upper_bound.h> -#include <__atomic/atomic.h> -#include <__config> -#include <__cstddef/ptrdiff_t.h> -#include <__exception/terminate.h> -#include <__iterator/iterator_traits.h> -#include <__iterator/move_iterator.h> -#include <__memory/allocator.h> -#include <__memory/construct_at.h> -#include <__memory/destroy.h> -#include <__memory/unique_ptr.h> -#include <__new/exceptions.h> -#include <__numeric/reduce.h> -#include <__pstl/backend_fwd.h> -#include <__pstl/cpu_algos/any_of.h> -#include <__pstl/cpu_algos/cpu_traits.h> -#include <__pstl/cpu_algos/fill.h> -#include <__pstl/cpu_algos/find_if.h> -#include <__pstl/cpu_algos/for_each.h> -#include <__pstl/cpu_algos/merge.h> -#include <__pstl/cpu_algos/stable_sort.h> -#include <__pstl/cpu_algos/transform.h> -#include <__pstl/cpu_algos/transform_reduce.h> -#include <__utility/empty.h> -#include <__utility/exception_guard.h> -#include <__utility/move.h> -#include <__utility/pair.h> -#include <optional> - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -namespace __libdispatch { -// ::dispatch_apply is marked as __attribute__((nothrow)) because it doesn't let exceptions propagate, and neither do -// we. -// TODO: Do we want to add [[_Clang::__callback__(__func, __context, __)]]? -_LIBCPP_EXPORTED_FROM_ABI void -__dispatch_apply(size_t __chunk_count, void* __context, void (*__func)(void* __context, size_t __chunk)) noexcept; - -template <class _Func> -_LIBCPP_HIDE_FROM_ABI void __dispatch_apply(size_t __chunk_count, _Func __func) noexcept { - __libdispatch::__dispatch_apply(__chunk_count, &__func, [](void* __context, size_t __chunk) { - (*static_cast<_Func*>(__context))(__chunk); - }); -} - -struct __chunk_partitions { - ptrdiff_t __chunk_count_; // includes the first chunk - ptrdiff_t __chunk_size_; - ptrdiff_t __first_chunk_size_; -}; - -[[__gnu__::__const__]] _LIBCPP_EXPORTED_FROM_ABI __chunk_partitions __partition_chunks(ptrdiff_t __size) noexcept; - -template <class _RandomAccessIterator, class _Functor> -_LIBCPP_HIDE_FROM_ABI optional<__empty> -__dispatch_parallel_for(__chunk_partitions __partitions, _RandomAccessIterator __first, _Functor __func) { - // Perform the chunked execution. - __libdispatch::__dispatch_apply(__partitions.__chunk_count_, [&](size_t __chunk) { - auto __this_chunk_size = __chunk == 0 ? __partitions.__first_chunk_size_ : __partitions.__chunk_size_; - auto __index = - __chunk == 0 - ? 0 - : (__chunk * __partitions.__chunk_size_) + (__partitions.__first_chunk_size_ - __partitions.__chunk_size_); - __func(__first + __index, __first + __index + __this_chunk_size); - }); - - return __empty{}; -} -} // namespace __libdispatch - -template <> -struct __cpu_traits<__libdispatch_backend_tag> { - template <class _RandomAccessIterator, class _Functor> - _LIBCPP_HIDE_FROM_ABI static optional<__empty> - __for_each(_RandomAccessIterator __first, _RandomAccessIterator __last, _Functor __func) { - return __libdispatch::__dispatch_parallel_for( - __libdispatch::__partition_chunks(__last - __first), std::move(__first), std::move(__func)); - } - - template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIteratorOut> - struct __merge_range { - __merge_range(_RandomAccessIterator1 __mid1, _RandomAccessIterator2 __mid2, _RandomAccessIteratorOut __result) - : __mid1_(__mid1), __mid2_(__mid2), __result_(__result) {} - - _RandomAccessIterator1 __mid1_; - _RandomAccessIterator2 __mid2_; - _RandomAccessIteratorOut __result_; - }; - - template <typename _RandomAccessIterator1, - typename _RandomAccessIterator2, - typename _RandomAccessIterator3, - typename _Compare, - typename _LeafMerge> - _LIBCPP_HIDE_FROM_ABI static optional<__empty> - __merge(_RandomAccessIterator1 __first1, - _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, - _RandomAccessIterator2 __last2, - _RandomAccessIterator3 __result, - _Compare __comp, - _LeafMerge __leaf_merge) noexcept { - __libdispatch::__chunk_partitions __partitions = - __libdispatch::__partition_chunks(std::max<ptrdiff_t>(__last1 - __first1, __last2 - __first2)); - - if (__partitions.__chunk_count_ == 0) - return __empty{}; - - if (__partitions.__chunk_count_ == 1) { - __leaf_merge(__first1, __last1, __first2, __last2, __result, __comp); - return __empty{}; - } - - using __merge_range_t = __merge_range<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3>; - auto const __n_ranges = __partitions.__chunk_count_ + 1; - - // TODO: use __uninitialized_buffer - auto __destroy = [=](__merge_range_t* __ptr) { - std::destroy_n(__ptr, __n_ranges); - std::allocator<__merge_range_t>().deallocate(__ptr, __n_ranges); - }; - - unique_ptr<__merge_range_t[], decltype(__destroy)> __ranges( - [&]() -> __merge_range_t* { -# if _LIBCPP_HAS_EXCEPTIONS - try { -# endif - return std::allocator<__merge_range_t>().allocate(__n_ranges); -# if _LIBCPP_HAS_EXCEPTIONS - } catch (const std::bad_alloc&) { - return nullptr; - } -# endif - }(), - __destroy); - - if (!__ranges) - return nullopt; - - // TODO: Improve the case where the smaller range is merged into just a few (or even one) chunks of the larger case - __merge_range_t* __r = __ranges.get(); - std::__construct_at(__r++, __first1, __first2, __result); - - bool __iterate_first_range = __last1 - __first1 > __last2 - __first2; - - auto __compute_chunk = [&](size_t __chunk_size) -> __merge_range_t { - auto [__mid1, __mid2] = [&] { - if (__iterate_first_range) { - auto __m1 = __first1 + __chunk_size; - auto __m2 = std::lower_bound(__first2, __last2, __m1[-1], __comp); - return std::make_pair(__m1, __m2); - } else { - auto __m2 = __first2 + __chunk_size; - auto __m1 = std::lower_bound(__first1, __last1, __m2[-1], __comp); - return std::make_pair(__m1, __m2); - } - }(); - - __result += (__mid1 - __first1) + (__mid2 - __first2); - __first1 = __mid1; - __first2 = __mid2; - return {std::move(__mid1), std::move(__mid2), __result}; - }; - - // handle first chunk - std::__construct_at(__r++, __compute_chunk(__partitions.__first_chunk_size_)); - - // handle 2 -> N - 1 chunks - for (ptrdiff_t __i = 0; __i != __partitions.__chunk_count_ - 2; ++__i) - std::__construct_at(__r++, __compute_chunk(__partitions.__chunk_size_)); - - // handle last chunk - std::__construct_at(__r, __last1, __last2, __result); - - __libdispatch::__dispatch_apply(__partitions.__chunk_count_, [&](size_t __index) { - auto __first_iters = __ranges[__index]; - auto __last_iters = __ranges[__index + 1]; - __leaf_merge( - __first_iters.__mid1_, - __last_iters.__mid1_, - __first_iters.__mid2_, - __last_iters.__mid2_, - __first_iters.__result_, - __comp); - }); - - return __empty{}; - } - - template <class _RandomAccessIterator, class _Transform, class _Value, class _Combiner, class _Reduction> - _LIBCPP_HIDE_FROM_ABI static optional<_Value> __transform_reduce( - _RandomAccessIterator __first, - _RandomAccessIterator __last, - _Transform __transform, - _Value __init, - _Combiner __combiner, - _Reduction __reduction) { - if (__first == __last) - return __init; - - auto __partitions = __libdispatch::__partition_chunks(__last - __first); - - auto __destroy = [__count = __partitions.__chunk_count_](_Value* __ptr) { - std::destroy_n(__ptr, __count); - std::allocator<_Value>().deallocate(__ptr, __count); - }; - - // TODO: use __uninitialized_buffer - // TODO: allocate one element per worker instead of one element per chunk - unique_ptr<_Value[], decltype(__destroy)> __values( - std::allocator<_Value>().allocate(__partitions.__chunk_count_), __destroy); - - // __dispatch_apply is noexcept - __libdispatch::__dispatch_apply(__partitions.__chunk_count_, [&](size_t __chunk) { - auto __this_chunk_size = __chunk == 0 ? __partitions.__first_chunk_size_ : __partitions.__chunk_size_; - auto __index = __chunk == 0 ? 0 - : (__chunk * __partitions.__chunk_size_) + - (__partitions.__first_chunk_size_ - __partitions.__chunk_size_); - if (__this_chunk_size != 1) { - std::__construct_at( - __values.get() + __chunk, - __reduction(__first + __index + 2, - __first + __index + __this_chunk_size, - __combiner(__transform(__first + __index), __transform(__first + __index + 1)))); - } else { - std::__construct_at(__values.get() + __chunk, __transform(__first + __index)); - } - }); - - return std::reduce( - std::make_move_iterator(__values.get()), - std::make_move_iterator(__values.get() + __partitions.__chunk_count_), - std::move(__init), - __combiner); - } - - template <class _RandomAccessIterator, class _Comp, class _LeafSort> - _LIBCPP_HIDE_FROM_ABI static optional<__empty> - __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp, _LeafSort __leaf_sort) { - const auto __size = __last - __first; - auto __partitions = __libdispatch::__partition_chunks(__size); - - if (__partitions.__chunk_count_ == 0) - return __empty{}; - - if (__partitions.__chunk_count_ == 1) { - __leaf_sort(__first, __last, __comp); - return __empty{}; - } - - using _Value = __iterator_value_type<_RandomAccessIterator>; - - auto __destroy = [__size](_Value* __ptr) { - std::destroy_n(__ptr, __size); - std::allocator<_Value>().deallocate(__ptr, __size); - }; - - // TODO: use __uninitialized_buffer - unique_ptr<_Value[], decltype(__destroy)> __values(std::allocator<_Value>().allocate(__size), __destroy); - - // Initialize all elements to a moved-from state - // TODO: Don't do this - this can be done in the first merge - see https://llvm.org/PR63928 - std::__construct_at(__values.get(), std::move(*__first)); - for (__iterator_difference_type<_RandomAccessIterator> __i = 1; __i != __size; ++__i) { - std::__construct_at(__values.get() + __i, std::move(__values.get()[__i - 1])); - } - *__first = std::move(__values.get()[__size - 1]); - - __libdispatch::__dispatch_parallel_for( - __partitions, - __first, - [&__leaf_sort, &__comp](_RandomAccessIterator __chunk_first, _RandomAccessIterator __chunk_last) { - __leaf_sort(std::move(__chunk_first), std::move(__chunk_last), __comp); - }); - - bool __objects_are_in_buffer = false; - do { - const auto __old_chunk_size = __partitions.__chunk_size_; - if (__partitions.__chunk_count_ % 2 == 1) { - auto __inplace_merge_chunks = [&__comp, &__partitions](auto __first_chunk_begin) { - std::inplace_merge( - __first_chunk_begin, - __first_chunk_begin + __partitions.__first_chunk_size_, - __first_chunk_begin + __partitions.__first_chunk_size_ + __partitions.__chunk_size_, - __comp); - }; - if (__objects_are_in_buffer) - __inplace_merge_chunks(__values.get()); - else - __inplace_merge_chunks(__first); - __partitions.__first_chunk_size_ += 2 * __partitions.__chunk_size_; - } else { - __partitions.__first_chunk_size_ += __partitions.__chunk_size_; - } - - __partitions.__chunk_size_ *= 2; - __partitions.__chunk_count_ /= 2; - - auto __merge_chunks = [__partitions, __old_chunk_size, &__comp](auto __from_first, auto __to_first) { - __libdispatch::__dispatch_parallel_for( - __partitions, - __from_first, - [__old_chunk_size, &__from_first, &__to_first, &__comp](auto __chunk_first, auto __chunk_last) { - std::merge(std::make_move_iterator(__chunk_first), - std::make_move_iterator(__chunk_last - __old_chunk_size), - std::make_move_iterator(__chunk_last - __old_chunk_size), - std::make_move_iterator(__chunk_last), - __to_first + (__chunk_first - __from_first), - __comp); - }); - }; - - if (__objects_are_in_buffer) - __merge_chunks(__values.get(), __first); - else - __merge_chunks(__first, __values.get()); - __objects_are_in_buffer = !__objects_are_in_buffer; - } while (__partitions.__chunk_count_ > 1); - - if (__objects_are_in_buffer) { - std::move(__values.get(), __values.get() + __size, __first); - } - - return __empty{}; - } - - _LIBCPP_HIDE_FROM_ABI static void __cancel_execution() {} - - static constexpr size_t __lane_size = 64; -}; - -// Mandatory implementations of the computational basis -template <class _ExecutionPolicy> -struct __find_if<__libdispatch_backend_tag, _ExecutionPolicy> - : __cpu_parallel_find_if<__libdispatch_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __for_each<__libdispatch_backend_tag, _ExecutionPolicy> - : __cpu_parallel_for_each<__libdispatch_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __merge<__libdispatch_backend_tag, _ExecutionPolicy> - : __cpu_parallel_merge<__libdispatch_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __stable_sort<__libdispatch_backend_tag, _ExecutionPolicy> - : __cpu_parallel_stable_sort<__libdispatch_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __transform<__libdispatch_backend_tag, _ExecutionPolicy> - : __cpu_parallel_transform<__libdispatch_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __transform_binary<__libdispatch_backend_tag, _ExecutionPolicy> - : __cpu_parallel_transform_binary<__libdispatch_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __transform_reduce<__libdispatch_backend_tag, _ExecutionPolicy> - : __cpu_parallel_transform_reduce<__libdispatch_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __transform_reduce_binary<__libdispatch_backend_tag, _ExecutionPolicy> - : __cpu_parallel_transform_reduce_binary<__libdispatch_backend_tag, _ExecutionPolicy> {}; - -// Not mandatory, but better optimized -template <class _ExecutionPolicy> -struct __any_of<__libdispatch_backend_tag, _ExecutionPolicy> - : __cpu_parallel_any_of<__libdispatch_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __fill<__libdispatch_backend_tag, _ExecutionPolicy> - : __cpu_parallel_fill<__libdispatch_backend_tag, _ExecutionPolicy> {}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_BACKENDS_LIBDISPATCH_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/backends/serial.h b/third_party/libcxx/include/c++/v1/__pstl/backends/serial.h deleted file mode 100644 index f414201..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/backends/serial.h +++ /dev/null @@ -1,185 +0,0 @@ -// -*- C++ -*- -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_BACKENDS_SERIAL_H -#define _LIBCPP___PSTL_BACKENDS_SERIAL_H - -#include <__algorithm/find_if.h> -#include <__algorithm/for_each.h> -#include <__algorithm/merge.h> -#include <__algorithm/stable_sort.h> -#include <__algorithm/transform.h> -#include <__config> -#include <__numeric/transform_reduce.h> -#include <__pstl/backend_fwd.h> -#include <__utility/empty.h> -#include <__utility/forward.h> -#include <__utility/move.h> -#include <optional> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -// -// This partial PSTL backend runs everything serially. -// -// TODO: Right now, the serial backend must be used with another backend -// like the "default backend" because it doesn't implement all the -// necessary PSTL operations. It would be better to dispatch all -// algorithms to their serial counterpart directly, since this can -// often be more efficient than the "default backend"'s implementation -// if we end up running serially anyways. -// - -template <class _ExecutionPolicy> -struct __find_if<__serial_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Pred> - _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator> - operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { - return std::find_if(std::move(__first), std::move(__last), std::forward<_Pred>(__pred)); - } -}; - -template <class _ExecutionPolicy> -struct __for_each<__serial_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Function> - _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Function&& __func) const noexcept { - std::for_each(std::move(__first), std::move(__last), std::forward<_Function>(__func)); - return __empty{}; - } -}; - -template <class _ExecutionPolicy> -struct __merge<__serial_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Comp> - _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()( - _Policy&&, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _ForwardIterator2 __last2, - _ForwardOutIterator __outit, - _Comp&& __comp) const noexcept { - return std::merge( - std::move(__first1), - std::move(__last1), - std::move(__first2), - std::move(__last2), - std::move(__outit), - std::forward<_Comp>(__comp)); - } -}; - -template <class _ExecutionPolicy> -struct __stable_sort<__serial_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _RandomAccessIterator, class _Comp> - _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept { - std::stable_sort(std::move(__first), std::move(__last), std::forward<_Comp>(__comp)); - return __empty{}; - } -}; - -template <class _ExecutionPolicy> -struct __transform<__serial_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _UnaryOperation> - _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()( - _Policy&&, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __outit, _UnaryOperation&& __op) - const noexcept { - return std::transform( - std::move(__first), std::move(__last), std::move(__outit), std::forward<_UnaryOperation>(__op)); - } -}; - -template <class _ExecutionPolicy> -struct __transform_binary<__serial_backend_tag, _ExecutionPolicy> { - template <class _Policy, - class _ForwardIterator1, - class _ForwardIterator2, - class _ForwardOutIterator, - class _BinaryOperation> - _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> - operator()(_Policy&&, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _ForwardOutIterator __outit, - _BinaryOperation&& __op) const noexcept { - return std::transform( - std::move(__first1), - std::move(__last1), - std::move(__first2), - std::move(__outit), - std::forward<_BinaryOperation>(__op)); - } -}; - -template <class _ExecutionPolicy> -struct __transform_reduce<__serial_backend_tag, _ExecutionPolicy> { - template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation> - _LIBCPP_HIDE_FROM_ABI optional<_Tp> - operator()(_Policy&&, - _ForwardIterator __first, - _ForwardIterator __last, - _Tp __init, - _BinaryOperation&& __reduce, - _UnaryOperation&& __transform) const noexcept { - return std::transform_reduce( - std::move(__first), - std::move(__last), - std::move(__init), - std::forward<_BinaryOperation>(__reduce), - std::forward<_UnaryOperation>(__transform)); - } -}; - -template <class _ExecutionPolicy> -struct __transform_reduce_binary<__serial_backend_tag, _ExecutionPolicy> { - template <class _Policy, - class _ForwardIterator1, - class _ForwardIterator2, - class _Tp, - class _BinaryOperation1, - class _BinaryOperation2> - _LIBCPP_HIDE_FROM_ABI optional<_Tp> operator()( - _Policy&&, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _Tp __init, - _BinaryOperation1&& __reduce, - _BinaryOperation2&& __transform) const noexcept { - return std::transform_reduce( - std::move(__first1), - std::move(__last1), - std::move(__first2), - std::move(__init), - std::forward<_BinaryOperation1>(__reduce), - std::forward<_BinaryOperation2>(__transform)); - } -}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_BACKENDS_SERIAL_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/backends/std_thread.h b/third_party/libcxx/include/c++/v1/__pstl/backends/std_thread.h deleted file mode 100644 index dd2c3f1..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/backends/std_thread.h +++ /dev/null @@ -1,139 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_BACKENDS_STD_THREAD_H -#define _LIBCPP___PSTL_BACKENDS_STD_THREAD_H - -#include <__config> -#include <__pstl/backend_fwd.h> -#include <__pstl/cpu_algos/any_of.h> -#include <__pstl/cpu_algos/cpu_traits.h> -#include <__pstl/cpu_algos/fill.h> -#include <__pstl/cpu_algos/find_if.h> -#include <__pstl/cpu_algos/for_each.h> -#include <__pstl/cpu_algos/merge.h> -#include <__pstl/cpu_algos/stable_sort.h> -#include <__pstl/cpu_algos/transform.h> -#include <__pstl/cpu_algos/transform_reduce.h> -#include <__utility/empty.h> -#include <__utility/move.h> -#include <optional> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -// -// This partial backend implementation is for testing purposes only and not meant for production use. This will be -// replaced by a proper implementation once the PSTL implementation is somewhat stable. -// -// This is intended to be used on top of the "default backend". -// - -template <> -struct __cpu_traits<__std_thread_backend_tag> { - template <class _RandomAccessIterator, class _Fp> - _LIBCPP_HIDE_FROM_ABI static optional<__empty> - __for_each(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) { - __f(__first, __last); - return __empty{}; - } - - template <class _Index, class _UnaryOp, class _Tp, class _BinaryOp, class _Reduce> - _LIBCPP_HIDE_FROM_ABI static optional<_Tp> - __transform_reduce(_Index __first, _Index __last, _UnaryOp, _Tp __init, _BinaryOp, _Reduce __reduce) { - return __reduce(std::move(__first), std::move(__last), std::move(__init)); - } - - template <class _RandomAccessIterator, class _Compare, class _LeafSort> - _LIBCPP_HIDE_FROM_ABI static optional<__empty> - __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _LeafSort __leaf_sort) { - __leaf_sort(__first, __last, __comp); - return __empty{}; - } - - _LIBCPP_HIDE_FROM_ABI static void __cancel_execution() {} - - template <class _RandomAccessIterator1, - class _RandomAccessIterator2, - class _RandomAccessIterator3, - class _Compare, - class _LeafMerge> - _LIBCPP_HIDE_FROM_ABI static optional<__empty> - __merge(_RandomAccessIterator1 __first1, - _RandomAccessIterator1 __last1, - _RandomAccessIterator2 __first2, - _RandomAccessIterator2 __last2, - _RandomAccessIterator3 __outit, - _Compare __comp, - _LeafMerge __leaf_merge) { - __leaf_merge(__first1, __last1, __first2, __last2, __outit, __comp); - return __empty{}; - } - - static constexpr size_t __lane_size = 64; -}; - -// Mandatory implementations of the computational basis -template <class _ExecutionPolicy> -struct __find_if<__std_thread_backend_tag, _ExecutionPolicy> - : __cpu_parallel_find_if<__std_thread_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __for_each<__std_thread_backend_tag, _ExecutionPolicy> - : __cpu_parallel_for_each<__std_thread_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __merge<__std_thread_backend_tag, _ExecutionPolicy> - : __cpu_parallel_merge<__std_thread_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __stable_sort<__std_thread_backend_tag, _ExecutionPolicy> - : __cpu_parallel_stable_sort<__std_thread_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __transform<__std_thread_backend_tag, _ExecutionPolicy> - : __cpu_parallel_transform<__std_thread_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __transform_binary<__std_thread_backend_tag, _ExecutionPolicy> - : __cpu_parallel_transform_binary<__std_thread_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __transform_reduce<__std_thread_backend_tag, _ExecutionPolicy> - : __cpu_parallel_transform_reduce<__std_thread_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __transform_reduce_binary<__std_thread_backend_tag, _ExecutionPolicy> - : __cpu_parallel_transform_reduce_binary<__std_thread_backend_tag, _ExecutionPolicy> {}; - -// Not mandatory, but better optimized -template <class _ExecutionPolicy> -struct __any_of<__std_thread_backend_tag, _ExecutionPolicy> - : __cpu_parallel_any_of<__std_thread_backend_tag, _ExecutionPolicy> {}; - -template <class _ExecutionPolicy> -struct __fill<__std_thread_backend_tag, _ExecutionPolicy> - : __cpu_parallel_fill<__std_thread_backend_tag, _ExecutionPolicy> {}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_BACKENDS_STD_THREAD_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/any_of.h b/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/any_of.h deleted file mode 100644 index 803db79..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/any_of.h +++ /dev/null @@ -1,103 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_CPU_ALGOS_ANY_OF_H -#define _LIBCPP___PSTL_CPU_ALGOS_ANY_OF_H - -#include <__algorithm/any_of.h> -#include <__assert> -#include <__atomic/atomic.h> -#include <__atomic/memory_order.h> -#include <__config> -#include <__iterator/concepts.h> -#include <__pstl/backend_fwd.h> -#include <__pstl/cpu_algos/cpu_traits.h> -#include <__type_traits/is_execution_policy.h> -#include <__utility/move.h> -#include <__utility/pair.h> -#include <cstdint> -#include <optional> - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -template <class _Backend, class _Index, class _Brick> -_LIBCPP_HIDE_FROM_ABI optional<bool> __parallel_or(_Index __first, _Index __last, _Brick __f) { - std::atomic<bool> __found(false); - auto __ret = __cpu_traits<_Backend>::__for_each(__first, __last, [__f, &__found](_Index __i, _Index __j) { - if (!__found.load(std::memory_order_relaxed) && __f(__i, __j)) { - __found.store(true, std::memory_order_relaxed); - __cpu_traits<_Backend>::__cancel_execution(); - } - }); - if (!__ret) - return nullopt; - return static_cast<bool>(__found); -} - -// TODO: check whether __simd_first() can be used here -template <class _Index, class _DifferenceType, class _Pred> -_LIBCPP_HIDE_FROM_ABI bool __simd_or(_Index __first, _DifferenceType __n, _Pred __pred) noexcept { - _DifferenceType __block_size = 4 < __n ? 4 : __n; - const _Index __last = __first + __n; - while (__last != __first) { - int32_t __flag = 1; - _PSTL_PRAGMA_SIMD_REDUCTION(& : __flag) - for (_DifferenceType __i = 0; __i < __block_size; ++__i) - if (__pred(*(__first + __i))) - __flag = 0; - if (!__flag) - return true; - - __first += __block_size; - if (__last - __first >= __block_size << 1) { - // Double the block _Size. Any unnecessary iterations can be amortized against work done so far. - __block_size <<= 1; - } else { - __block_size = __last - __first; - } - } - return false; -} - -template <class _Backend, class _RawExecutionPolicy> -struct __cpu_parallel_any_of { - template <class _Policy, class _ForwardIterator, class _Predicate> - _LIBCPP_HIDE_FROM_ABI optional<bool> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept { - if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - return __pstl::__parallel_or<_Backend>( - __first, __last, [&__policy, &__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) { - using _AnyOfUnseq = __pstl::__any_of<_Backend, __remove_parallel_policy_t<_RawExecutionPolicy>>; - auto __res = _AnyOfUnseq()(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __pred); - _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!"); - return *std::move(__res); - }); - } else if constexpr (__is_unsequenced_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - return __pstl::__simd_or(__first, __last - __first, __pred); - } else { - return std::any_of(__first, __last, __pred); - } - } -}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_CPU_ALGOS_ANY_OF_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/cpu_traits.h b/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/cpu_traits.h deleted file mode 100644 index ec16224..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/cpu_traits.h +++ /dev/null @@ -1,89 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_CPU_ALGOS_CPU_TRAITS_H -#define _LIBCPP___PSTL_CPU_ALGOS_CPU_TRAITS_H - -#include <__config> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -// __cpu_traits -// -// This traits class encapsulates the basis operations for a CPU-based implementation of the PSTL. -// All the operations in the PSTL can be implemented from these basis operations, so a pure CPU backend -// only needs to customize these traits in order to get an implementation of the whole PSTL. -// -// Basis operations -// ================ -// -// template <class _RandomAccessIterator, class _Functor> -// optional<__empty> __for_each(_RandomAccessIterator __first, _RandomAccessIterator __last, _Functor __func); -// - __func must take a subrange of [__first, __last) that should be executed in serial -// -// template <class _Iterator, class _UnaryOp, class _Tp, class _BinaryOp, class _Reduction> -// optional<_Tp> __transform_reduce(_Iterator __first, _Iterator __last, _UnaryOp, _Tp __init, _BinaryOp, _Reduction); -// -// template <class _RandomAccessIterator1, -// class _RandomAccessIterator2, -// class _RandomAccessIterator3, -// class _Compare, -// class _LeafMerge> -// optional<_RandomAccessIterator3> __merge(_RandomAccessIterator1 __first1, -// _RandomAccessIterator1 __last1, -// _RandomAccessIterator2 __first2, -// _RandomAccessIterator2 __last2, -// _RandomAccessIterator3 __outit, -// _Compare __comp, -// _LeafMerge __leaf_merge); -// -// template <class _RandomAccessIterator, class _Comp, class _LeafSort> -// optional<__empty> __stable_sort(_RandomAccessIterator __first, -// _RandomAccessIterator __last, -// _Comp __comp, -// _LeafSort __leaf_sort); -// -// void __cancel_execution(); -// Cancel the execution of other jobs - they aren't needed anymore. This is not a binding request, -// some backends may not actually be able to cancel jobs. -// -// constexpr size_t __lane_size; -// Size of SIMD lanes. -// TODO: Merge this with __native_vector_size from __algorithm/simd_utils.h -// -// -// Exception handling -// ================== -// -// CPU backends are expected to report errors (i.e. failure to allocate) by returning a disengaged `optional` from their -// implementation. Exceptions shouldn't be used to report an internal failure-to-allocate, since all exceptions are -// turned into a program termination at the front-end level. When a backend returns a disengaged `optional` to the -// frontend, the frontend will turn that into a call to `std::__throw_bad_alloc();` to report the internal failure to -// the user. - -template <class _Backend> -struct __cpu_traits; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_CPU_ALGOS_CPU_TRAITS_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/fill.h b/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/fill.h deleted file mode 100644 index 3e59365..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/fill.h +++ /dev/null @@ -1,70 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_CPU_ALGOS_FILL_H -#define _LIBCPP___PSTL_CPU_ALGOS_FILL_H - -#include <__algorithm/fill.h> -#include <__assert> -#include <__config> -#include <__iterator/concepts.h> -#include <__pstl/backend_fwd.h> -#include <__pstl/cpu_algos/cpu_traits.h> -#include <__type_traits/is_execution_policy.h> -#include <__utility/empty.h> -#include <optional> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -template <class _Index, class _DifferenceType, class _Tp> -_LIBCPP_HIDE_FROM_ABI _Index __simd_fill_n(_Index __first, _DifferenceType __n, const _Tp& __value) noexcept { - _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED - _PSTL_PRAGMA_SIMD - for (_DifferenceType __i = 0; __i < __n; ++__i) - __first[__i] = __value; - return __first + __n; -} - -template <class _Backend, class _RawExecutionPolicy> -struct __cpu_parallel_fill { - template <class _Policy, class _ForwardIterator, class _Tp> - _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept { - if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - return __cpu_traits<_Backend>::__for_each( - __first, __last, [&__policy, &__value](_ForwardIterator __brick_first, _ForwardIterator __brick_last) { - using _FillUnseq = __pstl::__fill<_Backend, __remove_parallel_policy_t<_RawExecutionPolicy>>; - [[maybe_unused]] auto __res = - _FillUnseq()(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __value); - _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!"); - }); - } else if constexpr (__is_unsequenced_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - __pstl::__simd_fill_n(__first, __last - __first, __value); - return __empty{}; - } else { - std::fill(__first, __last, __value); - return __empty{}; - } - } -}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -#endif // _LIBCPP___PSTL_CPU_ALGOS_FILL_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/find_if.h b/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/find_if.h deleted file mode 100644 index aae64b6..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/find_if.h +++ /dev/null @@ -1,140 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_CPU_ALGOS_FIND_IF_H -#define _LIBCPP___PSTL_CPU_ALGOS_FIND_IF_H - -#include <__algorithm/find_if.h> -#include <__assert> -#include <__atomic/atomic.h> -#include <__config> -#include <__functional/operations.h> -#include <__iterator/concepts.h> -#include <__iterator/iterator_traits.h> -#include <__pstl/backend_fwd.h> -#include <__pstl/cpu_algos/cpu_traits.h> -#include <__type_traits/is_execution_policy.h> -#include <__utility/move.h> -#include <__utility/pair.h> -#include <optional> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -template <class _Backend, class _Index, class _Brick, class _Compare> -_LIBCPP_HIDE_FROM_ABI optional<_Index> -__parallel_find(_Index __first, _Index __last, _Brick __f, _Compare __comp, bool __b_first) { - typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType; - const _DifferenceType __n = __last - __first; - _DifferenceType __initial_dist = __b_first ? __n : -1; - std::atomic<_DifferenceType> __extremum(__initial_dist); - // TODO: find out what is better here: parallel_for or parallel_reduce - auto __res = - __cpu_traits<_Backend>::__for_each(__first, __last, [__comp, __f, __first, &__extremum](_Index __i, _Index __j) { - // See "Reducing Contention Through Priority Updates", PPoPP '13, for discussion of - // why using a shared variable scales fairly well in this situation. - if (__comp(__i - __first, __extremum)) { - _Index __result = __f(__i, __j); - // If not '__last' returned then we found what we want so put this to extremum - if (__result != __j) { - const _DifferenceType __k = __result - __first; - for (_DifferenceType __old = __extremum; __comp(__k, __old); __old = __extremum) { - __extremum.compare_exchange_weak(__old, __k); - } - } - } - }); - if (!__res) - return nullopt; - return __extremum.load() != __initial_dist ? __first + __extremum.load() : __last; -} - -template <class _Backend, class _Index, class _DifferenceType, class _Compare> -_LIBCPP_HIDE_FROM_ABI _Index -__simd_first(_Index __first, _DifferenceType __begin, _DifferenceType __end, _Compare __comp) noexcept { - // Experiments show good block sizes like this - const _DifferenceType __block_size = 8; - alignas(__cpu_traits<_Backend>::__lane_size) _DifferenceType __lane[__block_size] = {0}; - while (__end - __begin >= __block_size) { - _DifferenceType __found = 0; - _PSTL_PRAGMA_SIMD_REDUCTION(| : __found) for (_DifferenceType __i = __begin; __i < __begin + __block_size; ++__i) { - const _DifferenceType __t = __comp(__first, __i); - __lane[__i - __begin] = __t; - __found |= __t; - } - if (__found) { - _DifferenceType __i; - // This will vectorize - for (__i = 0; __i < __block_size; ++__i) { - if (__lane[__i]) { - break; - } - } - return __first + __begin + __i; - } - __begin += __block_size; - } - - // Keep remainder scalar - while (__begin != __end) { - if (__comp(__first, __begin)) { - return __first + __begin; - } - ++__begin; - } - return __first + __end; -} - -template <class _Backend, class _RawExecutionPolicy> -struct __cpu_parallel_find_if { - template <class _Policy, class _ForwardIterator, class _Predicate> - _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept { - if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - return __pstl::__parallel_find<_Backend>( - __first, - __last, - [&__policy, &__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) { - using _FindIfUnseq = __pstl::__find_if<_Backend, __remove_parallel_policy_t<_RawExecutionPolicy>>; - auto __res = _FindIfUnseq()(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __pred); - _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!"); - return *std::move(__res); - }, - less<>{}, - true); - } else if constexpr (__is_unsequenced_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - using __diff_t = __iterator_difference_type<_ForwardIterator>; - return __pstl::__simd_first<_Backend>( - __first, __diff_t(0), __last - __first, [&__pred](_ForwardIterator __iter, __diff_t __i) { - return __pred(__iter[__i]); - }); - } else { - return std::find_if(__first, __last, __pred); - } - } -}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_CPU_ALGOS_FIND_IF_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/for_each.h b/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/for_each.h deleted file mode 100644 index cec719b..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/for_each.h +++ /dev/null @@ -1,70 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_CPU_ALGOS_FOR_EACH_H -#define _LIBCPP___PSTL_CPU_ALGOS_FOR_EACH_H - -#include <__algorithm/for_each.h> -#include <__assert> -#include <__config> -#include <__iterator/concepts.h> -#include <__pstl/backend_fwd.h> -#include <__pstl/cpu_algos/cpu_traits.h> -#include <__type_traits/is_execution_policy.h> -#include <__utility/empty.h> -#include <optional> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -template <class _Iterator, class _DifferenceType, class _Function> -_LIBCPP_HIDE_FROM_ABI _Iterator __simd_for_each(_Iterator __first, _DifferenceType __n, _Function __f) noexcept { - _PSTL_PRAGMA_SIMD - for (_DifferenceType __i = 0; __i < __n; ++__i) - __f(__first[__i]); - - return __first + __n; -} - -template <class _Backend, class _RawExecutionPolicy> -struct __cpu_parallel_for_each { - template <class _Policy, class _ForwardIterator, class _Function> - _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Function __func) const noexcept { - if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - return __cpu_traits<_Backend>::__for_each( - __first, __last, [&__policy, __func](_ForwardIterator __brick_first, _ForwardIterator __brick_last) { - using _ForEachUnseq = __pstl::__for_each<_Backend, __remove_parallel_policy_t<_RawExecutionPolicy>>; - [[maybe_unused]] auto __res = - _ForEachUnseq()(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __func); - _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!"); - }); - } else if constexpr (__is_unsequenced_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - __pstl::__simd_for_each(__first, __last - __first, __func); - return __empty{}; - } else { - std::for_each(__first, __last, __func); - return __empty{}; - } - } -}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -#endif // _LIBCPP___PSTL_CPU_ALGOS_FOR_EACH_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/merge.h b/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/merge.h deleted file mode 100644 index a9069ca..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/merge.h +++ /dev/null @@ -1,89 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_CPU_ALGOS_MERGE_H -#define _LIBCPP___PSTL_CPU_ALGOS_MERGE_H - -#include <__algorithm/merge.h> -#include <__assert> -#include <__config> -#include <__iterator/concepts.h> -#include <__pstl/backend_fwd.h> -#include <__pstl/cpu_algos/cpu_traits.h> -#include <__type_traits/is_execution_policy.h> -#include <__utility/move.h> -#include <optional> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -template <class _Backend, class _RawExecutionPolicy> -struct __cpu_parallel_merge { - template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Comp> - _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()( - _Policy&& __policy, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _ForwardIterator2 __last2, - _ForwardOutIterator __result, - _Comp __comp) const noexcept { - if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value && - __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value && - __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) { - auto __res = __cpu_traits<_Backend>::__merge( - __first1, - __last1, - __first2, - __last2, - __result, - __comp, - [&__policy](_ForwardIterator1 __g_first1, - _ForwardIterator1 __g_last1, - _ForwardIterator2 __g_first2, - _ForwardIterator2 __g_last2, - _ForwardOutIterator __g_result, - _Comp __g_comp) { - using _MergeUnseq = __pstl::__merge<_Backend, __remove_parallel_policy_t<_RawExecutionPolicy>>; - [[maybe_unused]] auto __g_res = _MergeUnseq()( - std::__remove_parallel_policy(__policy), - std::move(__g_first1), - std::move(__g_last1), - std::move(__g_first2), - std::move(__g_last2), - std::move(__g_result), - std::move(__g_comp)); - _LIBCPP_ASSERT_INTERNAL(__g_res, "unsed/sed should never try to allocate!"); - }); - if (!__res) - return nullopt; - return __result + (__last1 - __first1) + (__last2 - __first2); - } else { - return std::merge(__first1, __last1, __first2, __last2, __result, __comp); - } - } -}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_CPU_ALGOS_MERGE_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/stable_sort.h b/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/stable_sort.h deleted file mode 100644 index 5afdd3f..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/stable_sort.h +++ /dev/null @@ -1,51 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_CPU_ALGOS_STABLE_SORT_H -#define _LIBCPP___PSTL_CPU_ALGOS_STABLE_SORT_H - -#include <__algorithm/stable_sort.h> -#include <__config> -#include <__pstl/backend_fwd.h> -#include <__pstl/cpu_algos/cpu_traits.h> -#include <__type_traits/is_execution_policy.h> -#include <__utility/empty.h> -#include <optional> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -template <class _Backend, class _RawExecutionPolicy> -struct __cpu_parallel_stable_sort { - template <class _Policy, class _RandomAccessIterator, class _Comp> - _LIBCPP_HIDE_FROM_ABI optional<__empty> - operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) const noexcept { - if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy>) { - return __cpu_traits<_Backend>::__stable_sort( - __first, __last, __comp, [](_RandomAccessIterator __g_first, _RandomAccessIterator __g_last, _Comp __g_comp) { - std::stable_sort(__g_first, __g_last, __g_comp); - }); - } else { - std::stable_sort(__first, __last, __comp); - return __empty{}; - } - } -}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -#endif // _LIBCPP___PSTL_CPU_ALGOS_STABLE_SORT_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/transform.h b/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/transform.h deleted file mode 100644 index 30d117d..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/transform.h +++ /dev/null @@ -1,156 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_CPU_ALGOS_TRANSFORM_H -#define _LIBCPP___PSTL_CPU_ALGOS_TRANSFORM_H - -#include <__algorithm/transform.h> -#include <__assert> -#include <__config> -#include <__iterator/concepts.h> -#include <__iterator/iterator_traits.h> -#include <__pstl/backend_fwd.h> -#include <__pstl/cpu_algos/cpu_traits.h> -#include <__type_traits/is_execution_policy.h> -#include <__utility/move.h> -#include <optional> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -template <class _Iterator1, class _DifferenceType, class _Iterator2, class _Function> -_LIBCPP_HIDE_FROM_ABI _Iterator2 -__simd_transform(_Iterator1 __first1, _DifferenceType __n, _Iterator2 __first2, _Function __f) noexcept { - _PSTL_PRAGMA_SIMD - for (_DifferenceType __i = 0; __i < __n; ++__i) - __f(__first1[__i], __first2[__i]); - return __first2 + __n; -} - -template <class _Iterator1, class _DifferenceType, class _Iterator2, class _Iterator3, class _Function> -_LIBCPP_HIDE_FROM_ABI _Iterator3 __simd_transform( - _Iterator1 __first1, _DifferenceType __n, _Iterator2 __first2, _Iterator3 __first3, _Function __f) noexcept { - _PSTL_PRAGMA_SIMD - for (_DifferenceType __i = 0; __i < __n; ++__i) - __f(__first1[__i], __first2[__i], __first3[__i]); - return __first3 + __n; -} - -template <class _Backend, class _RawExecutionPolicy> -struct __cpu_parallel_transform { - template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _UnaryOperation> - _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> - operator()(_Policy&& __policy, - _ForwardIterator __first, - _ForwardIterator __last, - _ForwardOutIterator __result, - _UnaryOperation __op) const noexcept { - if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value && - __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) { - __cpu_traits<_Backend>::__for_each( - __first, - __last, - [&__policy, __op, __first, __result](_ForwardIterator __brick_first, _ForwardIterator __brick_last) { - using _TransformUnseq = __pstl::__transform<_Backend, __remove_parallel_policy_t<_RawExecutionPolicy>>; - auto __res = _TransformUnseq()( - std::__remove_parallel_policy(__policy), - __brick_first, - __brick_last, - __result + (__brick_first - __first), - __op); - _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!"); - return *std::move(__res); - }); - return __result + (__last - __first); - } else if constexpr (__is_unsequenced_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value && - __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) { - return __pstl::__simd_transform( - __first, - __last - __first, - __result, - [&](__iterator_reference<_ForwardIterator> __in_value, - __iterator_reference<_ForwardOutIterator> __out_value) { __out_value = __op(__in_value); }); - } else { - return std::transform(__first, __last, __result, __op); - } - } -}; - -template <class _Backend, class _RawExecutionPolicy> -struct __cpu_parallel_transform_binary { - template <class _Policy, - class _ForwardIterator1, - class _ForwardIterator2, - class _ForwardOutIterator, - class _BinaryOperation> - _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> - operator()(_Policy&& __policy, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _ForwardOutIterator __result, - _BinaryOperation __op) const noexcept { - if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value && - __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value && - __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) { - auto __res = __cpu_traits<_Backend>::__for_each( - __first1, - __last1, - [&__policy, __op, __first1, __first2, __result]( - _ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last) { - using _TransformBinaryUnseq = - __pstl::__transform_binary<_Backend, __remove_parallel_policy_t<_RawExecutionPolicy>>; - return _TransformBinaryUnseq()( - std::__remove_parallel_policy(__policy), - __brick_first, - __brick_last, - __first2 + (__brick_first - __first1), - __result + (__brick_first - __first1), - __op); - }); - if (!__res) - return nullopt; - return __result + (__last1 - __first1); - } else if constexpr (__is_unsequenced_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value && - __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value && - __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) { - return __pstl::__simd_transform( - __first1, - __last1 - __first1, - __first2, - __result, - [&](__iterator_reference<_ForwardIterator1> __in1, - __iterator_reference<_ForwardIterator2> __in2, - __iterator_reference<_ForwardOutIterator> __out_value) { __out_value = __op(__in1, __in2); }); - } else { - return std::transform(__first1, __last1, __first2, __result, __op); - } - } -}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_CPU_ALGOS_TRANSFORM_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/transform_reduce.h b/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/transform_reduce.h deleted file mode 100644 index edfb28b..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/cpu_algos/transform_reduce.h +++ /dev/null @@ -1,219 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_CPU_ALGOS_TRANSFORM_REDUCE_H -#define _LIBCPP___PSTL_CPU_ALGOS_TRANSFORM_REDUCE_H - -#include <__assert> -#include <__config> -#include <__iterator/concepts.h> -#include <__iterator/iterator_traits.h> -#include <__numeric/transform_reduce.h> -#include <__pstl/backend_fwd.h> -#include <__pstl/cpu_algos/cpu_traits.h> -#include <__type_traits/desugars_to.h> -#include <__type_traits/is_arithmetic.h> -#include <__type_traits/is_execution_policy.h> -#include <__utility/move.h> -#include <optional> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -template <typename _Backend, - typename _DifferenceType, - typename _Tp, - typename _BinaryOperation, - typename _UnaryOperation, - typename _UnaryResult = invoke_result_t<_UnaryOperation, _DifferenceType>, - __enable_if_t<__desugars_to_v<__plus_tag, _BinaryOperation, _Tp, _UnaryResult> && is_arithmetic_v<_Tp> && - is_arithmetic_v<_UnaryResult>, - int> = 0> -_LIBCPP_HIDE_FROM_ABI _Tp -__simd_transform_reduce(_DifferenceType __n, _Tp __init, _BinaryOperation, _UnaryOperation __f) noexcept { - _PSTL_PRAGMA_SIMD_REDUCTION(+ : __init) - for (_DifferenceType __i = 0; __i < __n; ++__i) - __init += __f(__i); - return __init; -} - -template <typename _Backend, - typename _Size, - typename _Tp, - typename _BinaryOperation, - typename _UnaryOperation, - typename _UnaryResult = invoke_result_t<_UnaryOperation, _Size>, - __enable_if_t<!(__desugars_to_v<__plus_tag, _BinaryOperation, _Tp, _UnaryResult> && is_arithmetic_v<_Tp> && - is_arithmetic_v<_UnaryResult>), - int> = 0> -_LIBCPP_HIDE_FROM_ABI _Tp -__simd_transform_reduce(_Size __n, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __f) noexcept { - constexpr size_t __lane_size = __cpu_traits<_Backend>::__lane_size; - const _Size __block_size = __lane_size / sizeof(_Tp); - if (__n > 2 * __block_size && __block_size > 1) { - alignas(__lane_size) char __lane_buffer[__lane_size]; - _Tp* __lane = reinterpret_cast<_Tp*>(__lane_buffer); - - // initializer - _PSTL_PRAGMA_SIMD - for (_Size __i = 0; __i < __block_size; ++__i) { - ::new (__lane + __i) _Tp(__binary_op(__f(__i), __f(__block_size + __i))); - } - // main loop - _Size __i = 2 * __block_size; - const _Size __last_iteration = __block_size * (__n / __block_size); - for (; __i < __last_iteration; __i += __block_size) { - _PSTL_PRAGMA_SIMD - for (_Size __j = 0; __j < __block_size; ++__j) { - __lane[__j] = __binary_op(std::move(__lane[__j]), __f(__i + __j)); - } - } - // remainder - _PSTL_PRAGMA_SIMD - for (_Size __j = 0; __j < __n - __last_iteration; ++__j) { - __lane[__j] = __binary_op(std::move(__lane[__j]), __f(__last_iteration + __j)); - } - // combiner - for (_Size __j = 0; __j < __block_size; ++__j) { - __init = __binary_op(std::move(__init), std::move(__lane[__j])); - } - // destroyer - _PSTL_PRAGMA_SIMD - for (_Size __j = 0; __j < __block_size; ++__j) { - __lane[__j].~_Tp(); - } - } else { - for (_Size __i = 0; __i < __n; ++__i) { - __init = __binary_op(std::move(__init), __f(__i)); - } - } - return __init; -} - -template <class _Backend, class _RawExecutionPolicy> -struct __cpu_parallel_transform_reduce_binary { - template <class _Policy, - class _ForwardIterator1, - class _ForwardIterator2, - class _Tp, - class _BinaryOperation1, - class _BinaryOperation2> - _LIBCPP_HIDE_FROM_ABI optional<_Tp> operator()( - _Policy&& __policy, - _ForwardIterator1 __first1, - _ForwardIterator1 __last1, - _ForwardIterator2 __first2, - _Tp __init, - _BinaryOperation1 __reduce, - _BinaryOperation2 __transform) const noexcept { - if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value && - __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) { - return __cpu_traits<_Backend>::__transform_reduce( - __first1, - std::move(__last1), - [__first1, __first2, __transform](_ForwardIterator1 __iter) { - return __transform(*__iter, *(__first2 + (__iter - __first1))); - }, - std::move(__init), - std::move(__reduce), - [&__policy, __first1, __first2, __reduce, __transform]( - _ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last, _Tp __brick_init) { - using _TransformReduceBinaryUnseq = - __pstl::__transform_reduce_binary<_Backend, __remove_parallel_policy_t<_RawExecutionPolicy>>; - return *_TransformReduceBinaryUnseq()( - std::__remove_parallel_policy(__policy), - __brick_first, - std::move(__brick_last), - __first2 + (__brick_first - __first1), - std::move(__brick_init), - std::move(__reduce), - std::move(__transform)); - }); - } else if constexpr (__is_unsequenced_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value && - __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) { - return __pstl::__simd_transform_reduce<_Backend>( - __last1 - __first1, - std::move(__init), - std::move(__reduce), - [&](__iterator_difference_type<_ForwardIterator1> __i) { return __transform(__first1[__i], __first2[__i]); }); - } else { - return std::transform_reduce( - std::move(__first1), - std::move(__last1), - std::move(__first2), - std::move(__init), - std::move(__reduce), - std::move(__transform)); - } - } -}; - -template <class _Backend, class _RawExecutionPolicy> -struct __cpu_parallel_transform_reduce { - template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation> - _LIBCPP_HIDE_FROM_ABI optional<_Tp> - operator()(_Policy&& __policy, - _ForwardIterator __first, - _ForwardIterator __last, - _Tp __init, - _BinaryOperation __reduce, - _UnaryOperation __transform) const noexcept { - if constexpr (__is_parallel_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - return __cpu_traits<_Backend>::__transform_reduce( - std::move(__first), - std::move(__last), - [__transform](_ForwardIterator __iter) { return __transform(*__iter); }, - std::move(__init), - __reduce, - [&__policy, __transform, __reduce](auto __brick_first, auto __brick_last, _Tp __brick_init) { - using _TransformReduceUnseq = - __pstl::__transform_reduce<_Backend, __remove_parallel_policy_t<_RawExecutionPolicy>>; - auto __res = _TransformReduceUnseq()( - std::__remove_parallel_policy(__policy), - std::move(__brick_first), - std::move(__brick_last), - std::move(__brick_init), - std::move(__reduce), - std::move(__transform)); - _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!"); - return *std::move(__res); - }); - } else if constexpr (__is_unsequenced_execution_policy_v<_RawExecutionPolicy> && - __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { - return __pstl::__simd_transform_reduce<_Backend>( - __last - __first, - std::move(__init), - std::move(__reduce), - [=, &__transform](__iterator_difference_type<_ForwardIterator> __i) { return __transform(__first[__i]); }); - } else { - return std::transform_reduce( - std::move(__first), std::move(__last), std::move(__init), std::move(__reduce), std::move(__transform)); - } - } -}; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_CPU_ALGOS_TRANSFORM_REDUCE_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/dispatch.h b/third_party/libcxx/include/c++/v1/__pstl/dispatch.h deleted file mode 100644 index 8288423..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/dispatch.h +++ /dev/null @@ -1,71 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_DISPATCH_H -#define _LIBCPP___PSTL_DISPATCH_H - -#include <__config> -#include <__pstl/backend_fwd.h> -#include <__type_traits/conditional.h> -#include <__type_traits/enable_if.h> -#include <__type_traits/integral_constant.h> -#include <__type_traits/type_identity.h> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -template <template <class, class> class _Algorithm, class _Backend, class _ExecutionPolicy, class = void> -constexpr bool __is_implemented_v = false; - -template <template <class, class> class _Algorithm, class _Backend, class _ExecutionPolicy> -constexpr bool __is_implemented_v<_Algorithm, - _Backend, - _ExecutionPolicy, - __enable_if_t<sizeof(_Algorithm<_Backend, _ExecutionPolicy>)>> = true; - -// Helpful to provide better error messages. This will show the algorithm and the execution policy -// in the compiler diagnostic. -template <template <class, class> class _Algorithm, class _ExecutionPolicy> -constexpr bool __cant_find_backend_for = false; - -template <template <class, class> class _Algorithm, class _BackendConfiguration, class _ExecutionPolicy> -struct __find_first_implemented; - -template <template <class, class> class _Algorithm, class _ExecutionPolicy> -struct __find_first_implemented<_Algorithm, __backend_configuration<>, _ExecutionPolicy> { - static_assert(__cant_find_backend_for<_Algorithm, _ExecutionPolicy>, - "Could not find a PSTL backend for the given algorithm and execution policy"); -}; - -template <template <class, class> class _Algorithm, class _B1, class... _Bn, class _ExecutionPolicy> -struct __find_first_implemented<_Algorithm, __backend_configuration<_B1, _Bn...>, _ExecutionPolicy> - : _If<__is_implemented_v<_Algorithm, _B1, _ExecutionPolicy>, - __type_identity<_Algorithm<_B1, _ExecutionPolicy>>, - __find_first_implemented<_Algorithm, __backend_configuration<_Bn...>, _ExecutionPolicy> > {}; - -template <template <class, class> class _Algorithm, class _BackendConfiguration, class _ExecutionPolicy> -using __dispatch _LIBCPP_NODEBUG = - typename __find_first_implemented<_Algorithm, _BackendConfiguration, _ExecutionPolicy>::type; - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_DISPATCH_H diff --git a/third_party/libcxx/include/c++/v1/__pstl/handle_exception.h b/third_party/libcxx/include/c++/v1/__pstl/handle_exception.h deleted file mode 100644 index 3b5fca8..0000000 --- a/third_party/libcxx/include/c++/v1/__pstl/handle_exception.h +++ /dev/null @@ -1,61 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___PSTL_HANDLE_EXCEPTION_H -#define _LIBCPP___PSTL_HANDLE_EXCEPTION_H - -#include <__config> -#include <__new/exceptions.h> -#include <__utility/forward.h> -#include <__utility/move.h> -#include <optional> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -#if _LIBCPP_STD_VER >= 17 - -_LIBCPP_BEGIN_NAMESPACE_STD -namespace __pstl { - -template <class _BackendFunction, class... _Args> -_LIBCPP_HIDE_FROM_ABI auto __handle_exception_impl(_Args&&... __args) noexcept { - return _BackendFunction{}(std::forward<_Args>(__args)...); -} - -// This function is used to call a backend PSTL algorithm from a frontend algorithm. -// -// All PSTL backend algorithms return an optional denoting whether there was an -// "infrastructure"-level failure (aka failure to allocate). This function takes -// care of unwrapping that and throwing `bad_alloc()` in case there was a problem -// in the underlying implementation. -// -// We must also be careful not to call any user code that could throw an exception -// (such as moving or copying iterators) in here since that should terminate the -// program, which is why we delegate to a noexcept helper below. -template <class _BackendFunction, class... _Args> -_LIBCPP_HIDE_FROM_ABI auto __handle_exception(_Args&&... __args) { - auto __result = __pstl::__handle_exception_impl<_BackendFunction>(std::forward<_Args>(__args)...); - if (__result == nullopt) - std::__throw_bad_alloc(); - else - return std::move(*__result); -} - -} // namespace __pstl -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER >= 17 - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___PSTL_HANDLE_EXCEPTION_H |