diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -87,6 +87,7 @@ __algorithm/pstl_backends/cpu_backends/transform_reduce.h __algorithm/pstl_copy.h __algorithm/pstl_count.h + __algorithm/pstl_equal.h __algorithm/pstl_fill.h __algorithm/pstl_find.h __algorithm/pstl_for_each.h diff --git a/libcxx/include/__algorithm/pstl_equal.h b/libcxx/include/__algorithm/pstl_equal.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_equal.h @@ -0,0 +1,167 @@ +//===----------------------------------------------------------------------===// +// +// 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___ALGORITHM_PSTL_EQUAL_H +#define _LIBCPP___ALGORITHM_PSTL_EQUAL_H + +#include <__algorithm/pstl_frontend_dispatch.h> +#include <__config> +#include <__functional/operations.h> +#include <__numeric/pstl_transform_reduce.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +void __pstl_equal(); + +template , + enable_if_t, int> = 0> +[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional +__equal(_ExecutionPolicy&& __policy, + _ForwardIterator1&& __first1, + _ForwardIterator1&& __last1, + _ForwardIterator2&& __first2, + _Pred&& __pred) noexcept { + return std::__pstl_frontend_dispatch( + _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_equal), + [&__policy]( + _ForwardIterator1 __g_first1, _ForwardIterator1 __g_last1, _ForwardIterator2 __g_first2, _Pred __g_pred) { + return std::__transform_reduce( + __policy, + std::move(__g_first1), + std::move(__g_last1), + std::move(__g_first2), + true, + std::logical_and{}, + std::move(__g_pred)); + }, + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__pred)); +} + +template , + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI bool +equal(_ExecutionPolicy&& __policy, + _ForwardIterator1 __first1, + _ForwardIterator1 __last1, + _ForwardIterator2 __first2, + _Pred __pred) { + auto __res = std::__equal(__policy, std::move(__first1), std::move(__last1), std::move(__first2), std::move(__pred)); + if (!__res) + std::__throw_bad_alloc(); + return *__res; +} + +template >, int> = 0> +_LIBCPP_HIDE_FROM_ABI bool +equal(_ExecutionPolicy&& __policy, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { + return std::equal(__policy, std::move(__first1), std::move(__last1), std::move(__first2), std::equal_to{}); +} + +template , + enable_if_t, int> = 0> +[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional +__equal(_ExecutionPolicy&& __policy, + _ForwardIterator1&& __first1, + _ForwardIterator1&& __last1, + _ForwardIterator2&& __first2, + _ForwardIterator2&& __last2, + _Pred&& __pred) noexcept { + return std::__pstl_frontend_dispatch( + _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_equal), + [&__policy](_ForwardIterator1 __g_first1, + _ForwardIterator1 __g_last1, + _ForwardIterator2 __g_first2, + _ForwardIterator2 __g_last2, + _Pred __g_pred) -> optional { + if constexpr (__has_random_access_iterator_category<_ForwardIterator1>::value && + __has_random_access_iterator_category<_ForwardIterator2>::value) { + if (__g_last1 - __g_first1 != __g_last2 - __g_first2) + return false; + return std::__equal( + __policy, std::move(__g_first1), std::move(__g_last1), std::move(__g_first2), std::move(__g_pred)); + } else { + (void)__policy; // Avoid unused lambda captue warning + return std::equal( + std::move(__g_first1), + std::move(__g_last1), + std::move(__g_first2), + std::move(__g_last2), + std::move(__g_pred)); + } + }, + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::move(__pred)); +} + +template , + enable_if_t, int> = 0> +_LIBCPP_HIDE_FROM_ABI bool +equal(_ExecutionPolicy&& __policy, + _ForwardIterator1 __first1, + _ForwardIterator1 __last1, + _ForwardIterator2 __first2, + _ForwardIterator2 __last2, + _Pred __pred) { + auto __res = std::__equal( + __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::move(__pred)); + if (!__res) + std::__throw_bad_alloc(); + return *__res; +} + +template >, int> = 0> +_LIBCPP_HIDE_FROM_ABI bool +equal(_ExecutionPolicy&& __policy, + _ForwardIterator1 __first1, + _ForwardIterator1 __last1, + _ForwardIterator2 __first2, + _ForwardIterator2 __last2) { + return std::equal( + __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::equal_to{}); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___ALGORITHM_PSTL_EQUAL_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1811,6 +1811,7 @@ #include <__algorithm/pstl_any_all_none_of.h> #include <__algorithm/pstl_copy.h> #include <__algorithm/pstl_count.h> +#include <__algorithm/pstl_equal.h> #include <__algorithm/pstl_fill.h> #include <__algorithm/pstl_find.h> #include <__algorithm/pstl_for_each.h> diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -809,6 +809,7 @@ module std_private_algorithm_pstl_backends_cpu_backends_transform_reduce [system] { header "__algorithm/pstl_backends/cpu_backends/transform_reduce.h" } module std_private_algorithm_pstl_copy [system] { header "__algorithm/pstl_copy.h" } module std_private_algorithm_pstl_count [system] { header "__algorithm/pstl_count.h" } +module std_private_algorithm_pstl_equal [system] { header "__algorithm/pstl_equal.h" } module std_private_algorithm_pstl_fill [system] { header "__algorithm/pstl_fill.h" } module std_private_algorithm_pstl_find [system] { header "__algorithm/pstl_find.h" diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/pstl.equal.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/pstl.equal.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/pstl.equal.pass.cpp @@ -0,0 +1,98 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14 + +// UNSUPPORETD: libcpp-has-no-incomplete-pstl + +// + +// template +// bool equal(ExecutionPolicy&& exec, +// ForwardIterator1 first1, ForwardIterator1 last1, +// ForwardIterator2 first2); +// +// template +// bool equal(ExecutionPolicy&& exec, +// ForwardIterator1 first1, ForwardIterator1 last1, +// ForwardIterator2 first2, BinaryPredicate pred); +// +// template +// bool equal(ExecutionPolicy&& exec, +// ForwardIterator1 first1, ForwardIterator1 last1, +// ForwardIterator2 first2, ForwardIterator2 last2); +// +// template +// bool equal(ExecutionPolicy&& exec, +// ForwardIterator1 first1, ForwardIterator1 last1, +// ForwardIterator2 first2, ForwardIterator2 last2, +// BinaryPredicate pred); + +#include +#include + +#include "test_execution_policies.h" +#include "test_iterators.h" +#include "test_macros.h" + +template +struct Test { + template + void operator()(Policy&& policy) { + { // 3 iter overloads + int a[] = {1, 2, 3, 4, 5, 6, 7, 8}; + int b[] = {1, 2, 3, 5, 6, 7, 8, 9}; + + // simple test + assert(std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(a)))); + + // check that false is returned on different ranges + assert(!std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)))); + + // check that the predicate is used + assert(std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), [](int lhs, int rhs) { + return lhs == rhs || lhs + 1 == rhs || rhs + 1 == lhs; + })); + } + + { // 4 iter overloads + int a[] = {1, 2, 3, 4, 5, 6, 7, 8}; + int b[] = {1, 2, 3, 5, 6, 7, 8, 9}; + + // simple test + assert(std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(a)), Iter2(std::end(a)))); + + // check that false is returned on different ranges + assert(!std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)))); + + // check that false is returned on different sized ranges + assert( + !std::equal(policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(a)), Iter2(std::end(a) - 1))); + + // check that the predicate is used + assert(std::equal( + policy, + Iter1(std::begin(a)), + Iter1(std::end(a)), + Iter2(std::begin(b)), + Iter2(std::end(b)), + [](int lhs, int rhs) { return lhs == rhs || lhs + 1 == rhs || rhs + 1 == lhs; })); + } + } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, types::apply_type_identity{[](auto v) { + using Iter1 = typename decltype(v)::type; + types::for_each( + types::forward_iterator_list{}, + TestIteratorWithPolicies::template apply>{}); + }}); +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/pstl.exception_handling.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/pstl.exception_handling.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/pstl.exception_handling.pass.cpp @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14 +// UNSUPPORTED: no-exceptions + +// UNSUPPORTED: libcpp-has-no-incomplete-pstl + +// check that std::equal(ExecutionPolicy) terminates on user-thrown exceptions + +#include + +#include "check_assertion.h" +#include "test_execution_policies.h" +#include "test_iterators.h" + +struct ThrowOnCompare {}; + +#ifndef TEST_HAS_NO_EXCEPTIONS +bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; } +#endif + +int main(int, char**) { + test_execution_policies([](auto&& policy) { + EXPECT_STD_TERMINATE([&] { + try { + int a[] = {1, 2}; + int b[] = {1, 2}; + (void)std::equal(policy, + util::throw_on_move_iterator(std::begin(a), 1), + util::throw_on_move_iterator(std::end(a), 1), + util::throw_on_move_iterator(std::begin(b), 1)); + } catch (const util::iterator_error&) { + assert(false); + } + std::terminate(); // make the test pass in case the algorithm didn't move the iterator + }); + EXPECT_STD_TERMINATE([&] { + try { + int a[] = {1, 2}; + int b[] = {1, 2}; + (void)std::equal( + policy, + util::throw_on_move_iterator(std::begin(a), 1), + util::throw_on_move_iterator(std::end(a), 1), + util::throw_on_move_iterator(std::begin(b), 1), + util::throw_on_move_iterator(std::end(b), 1)); + } catch (const util::iterator_error&) { + assert(false); + } + std::terminate(); // make the test pass in case the algorithm didn't move the iterator + }); + }); +}