diff --git a/libcxx/docs/Status/PSTLPaper.csv b/libcxx/docs/Status/PSTLPaper.csv --- a/libcxx/docs/Status/PSTLPaper.csv +++ b/libcxx/docs/Status/PSTLPaper.csv @@ -27,7 +27,7 @@ | `[alg.merge] `_,std::inplace_merge,Nikolas Klauser,|Not Started| | `[alg.heap.operations] `_,std::is_heap,Nikolas Klauser,|Not Started| | `[alg.heap.operations] `_,std::is_heap_until,Nikolas Klauser,|Not Started| -| `[alg.partitions] `_,std::is_partitioned,Nikolas Klauser,|Not Started| +| `[alg.partitions] `_,std::is_partitioned,Nikolas Klauser,|Complete| | `[alg.sort] `_,std::is_sorted,Nikolas Klauser,|Not Started| | `[alg.sort] `_,std::is_sorted_until,Nikolas Klauser,|Not Started| | `[alg.lex.comparison] `_,std::lexicographical_compare,Nikolas Klauser,|Not Started| diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -90,6 +90,7 @@ __algorithm/pstl_find.h __algorithm/pstl_for_each.h __algorithm/pstl_frontend_dispatch.h + __algorithm/pstl_is_partitioned.h __algorithm/pstl_generate.h __algorithm/pstl_merge.h __algorithm/pstl_replace.h diff --git a/libcxx/include/__algorithm/pstl_backend.h b/libcxx/include/__algorithm/pstl_backend.h --- a/libcxx/include/__algorithm/pstl_backend.h +++ b/libcxx/include/__algorithm/pstl_backend.h @@ -101,6 +101,9 @@ template void __pstl_generate(_Backend, _Iterator __first, _Iterator __last, _Generator __gen); + template + void __pstl_is_partitioned(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred); + template void __pstl_generator_n(_Backend, _Iterator __first, _Size __n, _Generator __gen); diff --git a/libcxx/include/__algorithm/pstl_is_partitioned.h b/libcxx/include/__algorithm/pstl_is_partitioned.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_is_partitioned.h @@ -0,0 +1,52 @@ +//===----------------------------------------------------------------------===// +// +// 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_IS_PARITTIONED +#define _LIBCPP___ALGORITHM_PSTL_IS_PARITTIONED + +#include <__algorithm/pstl_backend.h> +#include <__algorithm/pstl_find.h> +#include <__algorithm/pstl_frontend_dispatch.h> +#include <__config> +#include <__type_traits/is_execution_policy.h> +#include <__type_traits/remove_cvref.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_is_partitioned(); + +template , + enable_if_t, int> = 0> +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool +is_partitioned(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { + return std::__pstl_frontend_dispatch( + _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_is_partitioned), + [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last, _Predicate __g_pred) { + __g_first = std::find_if_not(__policy, __g_first, __g_last, __g_pred); + return std::find_if(__g_first, __g_last, __g_pred) == __g_last; + }, + std::move(__first), + std::move(__last), + std::move(__pred)); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___ALGORITHM_PSTL_IS_PARITTIONED diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1816,6 +1816,7 @@ #include <__algorithm/pstl_find.h> #include <__algorithm/pstl_for_each.h> #include <__algorithm/pstl_generate.h> +#include <__algorithm/pstl_is_partitioned.h> #include <__algorithm/pstl_merge.h> #include <__algorithm/pstl_replace.h> #include <__algorithm/pstl_stable_sort.h> diff --git a/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp b/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp --- a/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp +++ b/libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp @@ -146,6 +146,15 @@ pstl_fill_n_called = true; } +bool pstl_is_partitioned_called = false; + +template +bool __pstl_is_partitioned(TestBackend, ForwardIterator, ForwardIterator, Func) { + assert(!pstl_is_partitioned_called); + pstl_is_partitioned_called = true; + return {}; +} + bool pstl_replace_called = false; template @@ -287,6 +296,8 @@ assert(std::pstl_generate_called); (void)std::generate_n(TestPolicy{}, std::begin(a), std::size(a), pred); assert(std::pstl_generate_n_called); + (void)std::is_partitioned(TestPolicy{}, std::begin(a), std::end(a), pred); + assert(std::pstl_generate_n_called); (void)std::replace(TestPolicy{}, std::begin(a), std::end(a), 0, 0); assert(std::pstl_replace_called); (void)std::replace_if(TestPolicy{}, std::begin(a), std::end(a), pred, 0); diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.partitions/pstl.is_partitioned.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.partitions/pstl.is_partitioned.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.partitions/pstl.is_partitioned.pass.cpp @@ -0,0 +1,75 @@ +//===----------------------------------------------------------------------===// +// +// 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: libcpp-has-no-incomplete-pstl + +// template +// bool is_partitioned(ExecutionPolicy&& exec, +// ForwardIterator first, ForwardIterator last, Predicate pred); + +#include +#include +#include + +#include "test_iterators.h" +#include "test_execution_policies.h" + +template +struct Test { + template + void operator()(Policy&& policy) { + { // simple test + int a[] = {1, 2, 3, 4, 5}; + assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 3; })); + } + { // check that the range is paritioned if the predicate returns true for all elements + int a[] = {1, 2, 3, 4, 5}; + assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int) { return true; })); + } + { // check that the range is paritioned if the predicate returns false for all elements + int a[] = {1, 2, 3, 4, 5}; + assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int) { return false; })); + } + { // check that false is returned if the range is not partitioned + int a[] = {1, 2, 3, 2, 5}; + assert(!std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 3; })); + } + { // check that an range is partitioned + int a[] = {1, 2, 3, 2, 5}; + assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::begin(a)), [](int i) { return i < 3; })); + } + { // check that a single element is partitioned + int a[] = {1}; + assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 3; })); + } + { // check that a range is parititoned when the partition point is the first element + int a[] = {1, 2, 2, 4, 5}; + assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 2; })); + } + { // check that a range is parititoned when the partition point is the last element + int a[] = {1, 2, 2, 4, 5}; + assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 2; })); + } + { // check that a large range works + std::vector vec(150, 4); + vec[0] = 2; + vec[1] = 1; + assert(std::is_partitioned(policy, Iter(std::data(vec)), Iter(std::data(vec) + std::size(vec)), [](int i) { + return i < 3; + })); + } + } +}; + +int main(int, char**) { + types::for_each(types::forward_iterator_list{}, TestIteratorWithPolicies{}); + + return 0; +}