diff options
author | Nikolas Klauser <nikolasklauser@berlin.de> | 2023-07-20 14:45:19 -0700 |
---|---|---|
committer | Nikolas Klauser <nikolasklauser@berlin.de> | 2023-07-20 14:45:36 -0700 |
commit | 37e5baf318b1248c189ccc9558f3beb7af736885 (patch) | |
tree | 621efa578cc4cce903fc458fc22111d88116b79d /libcxx | |
parent | 14c55e6e2fa1c342a1ef908445db3d31a3475485 (diff) | |
download | llvm-37e5baf318b1248c189ccc9558f3beb7af736885.zip llvm-37e5baf318b1248c189ccc9558f3beb7af736885.tar.gz llvm-37e5baf318b1248c189ccc9558f3beb7af736885.tar.bz2 |
[libc++][PSTL] Implement std::sort
Reviewed By: #libc, ldionne
Spies: ldionne, libcxx-commits, mgrang
Differential Revision: https://reviews.llvm.org/D152860
Diffstat (limited to 'libcxx')
-rw-r--r-- | libcxx/docs/Status/PSTLPaper.csv | 2 | ||||
-rw-r--r-- | libcxx/include/CMakeLists.txt | 1 | ||||
-rw-r--r-- | libcxx/include/__algorithm/pstl_backend.h | 3 | ||||
-rw-r--r-- | libcxx/include/__algorithm/pstl_sort.h | 62 | ||||
-rw-r--r-- | libcxx/include/algorithm | 1 | ||||
-rw-r--r-- | libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp | 20 | ||||
-rw-r--r-- | libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/pstl.sort.pass.cpp | 113 | ||||
-rw-r--r-- | libcxx/test/support/test_macros.h | 4 |
8 files changed, 205 insertions, 1 deletions
diff --git a/libcxx/docs/Status/PSTLPaper.csv b/libcxx/docs/Status/PSTLPaper.csv index d2a51a3..ad18f80 100644 --- a/libcxx/docs/Status/PSTLPaper.csv +++ b/libcxx/docs/Status/PSTLPaper.csv @@ -62,7 +62,7 @@ Section,Description,Assignee,Complete | `[alg.set.operations] <https://wg21.link/alg.set.operations>`_,std::set_intersection,Nikolas Klauser,|Not Started| | `[alg.set.operations] <https://wg21.link/alg.set.operations>`_,std::set_symmetric_difference,Nikolas Klauser,|Not Started| | `[alg.set.operations] <https://wg21.link/alg.set.operations>`_,std::set_union,Nikolas Klauser,|Not Started| -| `[alg.sort] <https://wg21.link/alg.sort>`_,std::sort,Nikolas Klauser,|Not Started| +| `[alg.sort] <https://wg21.link/alg.sort>`_,std::sort,Nikolas Klauser,|Complete| | `[alg.partitions] <https://wg21.link/alg.partitions>`_,std::stable_partition,Nikolas Klauser,|Not Started| | `[alg.sort] <https://wg21.link/alg.sort>`_,std::stable_sort,Nikolas Klauser,|Complete| | `[alg.swap] <https://wg21.link/alg.swap>`_,std::swap_ranges,Nikolas Klauser,|Not Started| diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index b7c15a2..2bba97f 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -95,6 +95,7 @@ set(files __algorithm/pstl_is_partitioned.h __algorithm/pstl_merge.h __algorithm/pstl_replace.h + __algorithm/pstl_sort.h __algorithm/pstl_stable_sort.h __algorithm/pstl_transform.h __algorithm/push_heap.h diff --git a/libcxx/include/__algorithm/pstl_backend.h b/libcxx/include/__algorithm/pstl_backend.h index 4d02135..93372f0 100644 --- a/libcxx/include/__algorithm/pstl_backend.h +++ b/libcxx/include/__algorithm/pstl_backend.h @@ -150,6 +150,9 @@ implemented, all the algorithms will eventually forward to the basis algorithms _Pred __pred, const _Tp& __new_value); + template <class _ExecutionPolicy, class _Iterator, class _Comp> + void __pstl_sort(_Backend, _Iterator __first, _Iterator __last, _Comp __comp); + // TODO: Complete this list */ diff --git a/libcxx/include/__algorithm/pstl_sort.h b/libcxx/include/__algorithm/pstl_sort.h new file mode 100644 index 0000000..8151495 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_sort.h @@ -0,0 +1,62 @@ +//===----------------------------------------------------------------------===// +// +// 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_SORT_H +#define _LIBCPP___ALGORITHM_PSTL_SORT_H + +#include <__algorithm/pstl_backend.h> +#include <__algorithm/pstl_frontend_dispatch.h> +#include <__algorithm/pstl_stable_sort.h> +#include <__config> +#include <__functional/operations.h> +#include <__type_traits/is_execution_policy.h> +#include <__type_traits/remove_cvref.h> +#include <__utility/forward.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 <class> +void __pstl_sort(); + +template <class _ExecutionPolicy, + class _RandomAccessIterator, + class _Comp, + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0> +_LIBCPP_HIDE_FROM_ABI void +sort(_ExecutionPolicy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { + std::__pstl_frontend_dispatch( + _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_sort), + [&__policy](_RandomAccessIterator __g_first, _RandomAccessIterator __g_last, _Comp __g_comp) { + std::stable_sort(__policy, std::move(__g_first), std::move(__g_last), std::move(__g_comp)); + }, + std::move(__first), + std::move(__last), + std::move(__comp)); +} + +template <class _ExecutionPolicy, + class _RandomAccessIterator, + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0> +_LIBCPP_HIDE_FROM_ABI void +sort(_ExecutionPolicy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last) { + std::sort(std::forward<_ExecutionPolicy>(__policy), std::move(__first), std::move(__last), less{}); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 + +#endif // _LIBCPP___ALGORITHM_PSTL_SORT_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 35cfc1d..76e0d22 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1818,6 +1818,7 @@ template <class BidirectionalIterator, class Compare> #include <__algorithm/pstl_is_partitioned.h> #include <__algorithm/pstl_merge.h> #include <__algorithm/pstl_replace.h> +#include <__algorithm/pstl_sort.h> #include <__algorithm/pstl_stable_sort.h> #include <__algorithm/pstl_transform.h> #include <__algorithm/push_heap.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 index 4abd0ed..919945f 100644 --- 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 @@ -225,6 +225,22 @@ __pstl_reduce(TestBackend, ForwardIterator, ForwardIterator) { return {}; } +bool pstl_sort_called = false; + +template <class, class RandomAccessIterator, class Comp> +void __pstl_sort(TestBackend, RandomAccessIterator, RandomAccessIterator, Comp) { + assert(!pstl_sort_called); + pstl_sort_called = true; +} + +bool pstl_stable_sort_called = false; + +template <class, class RandomAccessIterator, class Comp> +void __pstl_stable_sort(TestBackend, RandomAccessIterator, RandomAccessIterator, Comp) { + assert(!pstl_stable_sort_called); + pstl_stable_sort_called = true; +} + bool pstl_unary_transform_reduce_called = false; template <class, class ForwardIterator, class T, class UnaryOperation, class BinaryOperation> @@ -314,6 +330,10 @@ int main(int, char**) { assert(std::pstl_reduce_with_init_called); (void)std::reduce(TestPolicy{}, std::begin(a), std::end(a)); assert(std::pstl_reduce_without_init_called); + (void)std::sort(TestPolicy{}, std::begin(a), std::end(a)); + assert(std::pstl_sort_called); + (void)std::stable_sort(TestPolicy{}, std::begin(a), std::end(a)); + assert(std::pstl_stable_sort_called); (void)std::transform_reduce(TestPolicy{}, std::begin(a), std::end(a), 0, pred, pred); assert(std::pstl_unary_transform_reduce_called); (void)std::transform_reduce(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), 0, pred, pred); diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/pstl.sort.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/pstl.sort.pass.cpp new file mode 100644 index 0000000..ecde996 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/pstl.sort.pass.cpp @@ -0,0 +1,113 @@ +//===----------------------------------------------------------------------===// +// +// 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<class ExecutionPolicy, class RandomAccessIterator> +// void sort(ExecutionPolicy&& exec, +// RandomAccessIterator first, RandomAccessIterator last); +// +// template<class ExecutionPolicy, class RandomAccessIterator, class Compare> +// void sort(ExecutionPolicy&& exec, +// RandomAccessIterator first, RandomAccessIterator last, +// Compare comp); + +#include <algorithm> +#include <cassert> +#include <numeric> +#include <random> +#include <vector> + +#include "test_execution_policies.h" +#include "test_iterators.h" +#include "test_macros.h" + +template <class Iter> +struct Test { + template <class ExecutionPolicy> + void operator()(ExecutionPolicy&& policy) { + { // simple test + int in[] = {1, 2, 3, 2, 6, 4}; + int expected[] = {1, 2, 2, 3, 4, 6}; + std::sort(policy, Iter(std::begin(in)), Iter(std::end(in))); + assert(std::equal(std::begin(in), std::end(in), std::begin(expected))); + } + { // empty range works + int in[] = {1, 2, 3, 2, 6, 4}; + int expected[] = {1, 2, 3, 2, 6, 4}; + std::sort(policy, Iter(std::begin(in)), Iter(std::begin(in))); + assert(std::equal(std::begin(in), std::end(in), std::begin(expected))); + } + { // single element range works + int in[] = {1}; + int expected[] = {1}; + std::sort(policy, Iter(std::begin(in)), Iter(std::begin(in))); + assert(std::equal(std::begin(in), std::end(in), std::begin(expected))); + } + { // two element range works + int in[] = {2, 1}; + int expected[] = {1, 2}; + std::sort(policy, Iter(std::begin(in)), Iter(std::end(in))); + assert(std::equal(std::begin(in), std::end(in), std::begin(expected))); + } + { // three element range works + int in[] = {2, 1, 4}; + int expected[] = {1, 2, 4}; + std::sort(policy, Iter(std::begin(in)), Iter(std::end(in))); + assert(std::equal(std::begin(in), std::end(in), std::begin(expected))); + } + { // longer range works + int in[] = {2, 1, 4, 4, 7, 2, 4, 1, 6}; + int expected[] = {1, 1, 2, 2, 4, 4, 4, 6, 7}; + std::sort(policy, Iter(std::begin(in)), Iter(std::end(in))); + assert(std::equal(std::begin(in), std::end(in), std::begin(expected))); + } + { // already sorted + int in[] = {1, 1, 2, 2, 4, 4, 4, 6, 7}; + int expected[] = {1, 1, 2, 2, 4, 4, 4, 6, 7}; + std::sort(policy, Iter(std::begin(in)), Iter(std::end(in))); + assert(std::equal(std::begin(in), std::end(in), std::begin(expected))); + } + { // reversed + int in[] = {7, 6, 4, 4, 4, 2, 2, 1, 1}; + int expected[] = {1, 1, 2, 2, 4, 4, 4, 6, 7}; + std::sort(policy, Iter(std::begin(in)), Iter(std::end(in))); + assert(std::equal(std::begin(in), std::end(in), std::begin(expected))); + } + { // repeating pattern + int in[] = {1, 2, 3, 1, 2, 3, 1, 2, 3}; + int expected[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; + std::sort(policy, Iter(std::begin(in)), Iter(std::end(in))); + assert(std::equal(std::begin(in), std::end(in), std::begin(expected))); + } + { // a custom comparator is used + int in[] = {1, 2, 3, 2, 6, 4}; + int expected[] = {6, 4, 3, 2, 2, 1}; + std::sort(policy, Iter(std::begin(in)), Iter(std::end(in)), std::greater{}); + assert(std::equal(std::begin(in), std::end(in), std::begin(expected))); + } +#ifndef TEST_HAS_NO_RANDOM_DEVICE + { // large range + std::vector<int> vec(300); + std::iota(std::begin(vec), std::end(vec), 0); + auto expected = vec; + std::shuffle(std::begin(vec), std::end(vec), std::mt19937_64(std::random_device{}())); + std::sort(Iter(std::data(vec)), Iter(std::data(vec) + std::size(vec))); + assert(vec == expected); + } +#endif + } +}; + +int main(int, char**) { + types::for_each(types::random_access_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{}); + + return 0; +} diff --git a/libcxx/test/support/test_macros.h b/libcxx/test/support/test_macros.h index 62bd85e..80cf600 100644 --- a/libcxx/test/support/test_macros.h +++ b/libcxx/test/support/test_macros.h @@ -398,6 +398,10 @@ inline void DoNotOptimize(Tp const& value) { # define TEST_HAS_NO_C8RTOMB_MBRTOC8 #endif +#if defined(_LIBCPP_HAS_NO_RANDOM_DEVICE) +# define TEST_HAS_NO_RANDOM_DEVICE +#endif + #if defined(TEST_COMPILER_CLANG) # define TEST_DIAGNOSTIC_PUSH _Pragma("clang diagnostic push") # define TEST_DIAGNOSTIC_POP _Pragma("clang diagnostic pop") |