__pstl/backends/serial.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___PSTL_BACKENDS_SERIAL_H
0011 #define _LIBCPP___PSTL_BACKENDS_SERIAL_H
0012
0013 #include <__algorithm/find_if.h>
0014 #include <__algorithm/for_each.h>
0015 #include <__algorithm/merge.h>
0016 #include <__algorithm/stable_sort.h>
0017 #include <__algorithm/transform.h>
0018 #include <__config>
0019 #include <__numeric/transform_reduce.h>
0020 #include <__pstl/backend_fwd.h>
0021 #include <__utility/empty.h>
0022 #include <__utility/forward.h>
0023 #include <__utility/move.h>
0024 #include <optional>
0025
0026 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0027 #  pragma GCC system_header
0028 #endif
0029
0030 _LIBCPP_PUSH_MACROS
0031 #include <__undef_macros>
0032
0033 #if _LIBCPP_STD_VER >= 17
0034
0035 _LIBCPP_BEGIN_NAMESPACE_STD
0036 namespace __pstl {
0037
0038 //
0039 // This partial PSTL backend runs everything serially.
0040 //
0041 // TODO: Right now, the serial backend must be used with another backend
0042 //       like the "default backend" because it doesn't implement all the
0043 //       necessary PSTL operations. It would be better to dispatch all
0044 //       algorithms to their serial counterpart directly, since this can
0045 //       often be more efficient than the "default backend"'s implementation
0046 //       if we end up running serially anyways.
0047 //
0048
0049 template <class _ExecutionPolicy>
0050 struct __find_if<__serial_backend_tag, _ExecutionPolicy> {
0051   template <class _Policy, class _ForwardIterator, class _Pred>
0052   _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
0053   operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
0054     return std::find_if(std::move(__first), std::move(__last), std::forward<_Pred>(__pred));
0055   }
0056 };
0057
0058 template <class _ExecutionPolicy>
0059 struct __for_each<__serial_backend_tag, _ExecutionPolicy> {
0060   template <class _Policy, class _ForwardIterator, class _Function>
0061   _LIBCPP_HIDE_FROM_ABI optional<__empty>
0062   operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Function&& __func) const noexcept {
0063     std::for_each(std::move(__first), std::move(__last), std::forward<_Function>(__func));
0064     return __empty{};
0065   }
0066 };
0067
0068 template <class _ExecutionPolicy>
0069 struct __merge<__serial_backend_tag, _ExecutionPolicy> {
0070   template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Comp>
0071   _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()(
0072       _Policy&&,
0073       _ForwardIterator1 __first1,
0074       _ForwardIterator1 __last1,
0075       _ForwardIterator2 __first2,
0076       _ForwardIterator2 __last2,
0077       _ForwardOutIterator __outit,
0078       _Comp&& __comp) const noexcept {
0079     return std::merge(
0080         std::move(__first1),
0081         std::move(__last1),
0082         std::move(__first2),
0083         std::move(__last2),
0084         std::move(__outit),
0085         std::forward<_Comp>(__comp));
0086   }
0087 };
0088
0089 template <class _ExecutionPolicy>
0090 struct __stable_sort<__serial_backend_tag, _ExecutionPolicy> {
0091   template <class _Policy, class _RandomAccessIterator, class _Comp>
0092   _LIBCPP_HIDE_FROM_ABI optional<__empty>
0093   operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {
0094     std::stable_sort(std::move(__first), std::move(__last), std::forward<_Comp>(__comp));
0095     return __empty{};
0096   }
0097 };
0098
0099 template <class _ExecutionPolicy>
0100 struct __transform<__serial_backend_tag, _ExecutionPolicy> {
0101   template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _UnaryOperation>
0102   _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()(
0103       _Policy&&, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __outit, _UnaryOperation&& __op)
0104       const noexcept {
0105     return std::transform(
0106         std::move(__first), std::move(__last), std::move(__outit), std::forward<_UnaryOperation>(__op));
0107   }
0108 };
0109
0110 template <class _ExecutionPolicy>
0111 struct __transform_binary<__serial_backend_tag, _ExecutionPolicy> {
0112   template <class _Policy,
0113             class _ForwardIterator1,
0114             class _ForwardIterator2,
0115             class _ForwardOutIterator,
0116             class _BinaryOperation>
0117   _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
0118   operator()(_Policy&&,
0119              _ForwardIterator1 __first1,
0120              _ForwardIterator1 __last1,
0121              _ForwardIterator2 __first2,
0122              _ForwardOutIterator __outit,
0123              _BinaryOperation&& __op) const noexcept {
0124     return std::transform(
0125         std::move(__first1),
0126         std::move(__last1),
0127         std::move(__first2),
0128         std::move(__outit),
0129         std::forward<_BinaryOperation>(__op));
0130   }
0131 };
0132
0133 template <class _ExecutionPolicy>
0134 struct __transform_reduce<__serial_backend_tag, _ExecutionPolicy> {
0135   template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
0136   _LIBCPP_HIDE_FROM_ABI optional<_Tp>
0137   operator()(_Policy&&,
0138              _ForwardIterator __first,
0139              _ForwardIterator __last,
0140              _Tp __init,
0141              _BinaryOperation&& __reduce,
0142              _UnaryOperation&& __transform) const noexcept {
0143     return std::transform_reduce(
0144         std::move(__first),
0145         std::move(__last),
0146         std::move(__init),
0147         std::forward<_BinaryOperation>(__reduce),
0148         std::forward<_UnaryOperation>(__transform));
0149   }
0150 };
0151
0152 template <class _ExecutionPolicy>
0153 struct __transform_reduce_binary<__serial_backend_tag, _ExecutionPolicy> {
0154   template <class _Policy,
0155             class _ForwardIterator1,
0156             class _ForwardIterator2,
0157             class _Tp,
0158             class _BinaryOperation1,
0159             class _BinaryOperation2>
0160   _LIBCPP_HIDE_FROM_ABI optional<_Tp> operator()(
0161       _Policy&&,
0162       _ForwardIterator1 __first1,
0163       _ForwardIterator1 __last1,
0164       _ForwardIterator2 __first2,
0165       _Tp __init,
0166       _BinaryOperation1&& __reduce,
0167       _BinaryOperation2&& __transform) const noexcept {
0168     return std::transform_reduce(
0169         std::move(__first1),
0170         std::move(__last1),
0171         std::move(__first2),
0172         std::move(__init),
0173         std::forward<_BinaryOperation1>(__reduce),
0174         std::forward<_BinaryOperation2>(__transform));
0175   }
0176 };
0177
0178 } // namespace __pstl
0179 _LIBCPP_END_NAMESPACE_STD
0180
0181 #endif // _LIBCPP_STD_VER >= 17
0182
0183 _LIBCPP_POP_MACROS
0184
0185 #endif // _LIBCPP___PSTL_BACKENDS_SERIAL_H