libcxx/include/__cxx03/__pstl/backends/default.h

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef _LIBCPP___PSTL_BACKENDS_DEFAULT_H
  10 #define _LIBCPP___PSTL_BACKENDS_DEFAULT_H
  11
  12 #include <__cxx03/__algorithm/copy_n.h>
  13 #include <__cxx03/__algorithm/equal.h>
  14 #include <__cxx03/__algorithm/fill_n.h>
  15 #include <__cxx03/__algorithm/for_each_n.h>
  16 #include <__cxx03/__config>
  17 #include <__cxx03/__functional/identity.h>
  18 #include <__cxx03/__functional/not_fn.h>
  19 #include <__cxx03/__functional/operations.h>
  20 #include <__cxx03/__iterator/concepts.h>
  21 #include <__cxx03/__iterator/iterator_traits.h>
  22 #include <__cxx03/__pstl/backend_fwd.h>
  23 #include <__cxx03/__pstl/dispatch.h>
  24 #include <__cxx03/__utility/empty.h>
  25 #include <__cxx03/__utility/forward.h>
  26 #include <__cxx03/__utility/move.h>
  27 #include <__cxx03/optional>
  28
  29 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  30 #  pragma GCC system_header
  31 #endif
  32
  33 _LIBCPP_PUSH_MACROS
  34 #include <__cxx03/__undef_macros>
  35
  36 _LIBCPP_BEGIN_NAMESPACE_STD
  37 namespace __pstl {
  38
  39 //
  40 // This file provides an incomplete PSTL backend that implements all of the PSTL algorithms
  41 // based on a smaller set of basis operations.
  42 //
  43 // It is intended as a building block for other PSTL backends that implement some operations more
  44 // efficiently but may not want to define the full set of PSTL algorithms.
  45 //
  46 // This backend implements all the PSTL algorithms based on the following basis operations:
  47 //
  48 // find_if family
  49 // --------------
  50 // - find
  51 // - find_if_not
  52 // - any_of
  53 // - all_of
  54 // - none_of
  55 // - is_partitioned
  56 //
  57 // for_each family
  58 // ---------------
  59 // - for_each_n
  60 // - fill
  61 // - fill_n
  62 // - replace
  63 // - replace_if
  64 // - generate
  65 // - generate_n
  66 //
  67 // merge family
  68 // ------------
  69 // No other algorithms based on merge
  70 //
  71 // stable_sort family
  72 // ------------------
  73 // - sort
  74 //
  75 // transform_reduce and transform_reduce_binary family
  76 // ---------------------------------------------------
  77 // - count_if
  78 // - count
  79 // - equal(3 legs)
  80 // - equal
  81 // - reduce
  82 //
  83 // transform and transform_binary family
  84 // -------------------------------------
  85 // - replace_copy_if
  86 // - replace_copy
  87 // - move
  88 // - copy
  89 // - copy_n
  90 // - rotate_copy
  91 //
  92
  93 //////////////////////////////////////////////////////////////
  94 // find_if family
  95 //////////////////////////////////////////////////////////////
  96 template <class _ExecutionPolicy>
  97 struct __find<__default_backend_tag, _ExecutionPolicy> {
  98   template <class _Policy, class _ForwardIterator, class _Tp>
  99   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
 100   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept {
 101     using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
 102     return _FindIf()(
 103         __policy, std::move(__first), std::move(__last), [&](__iter_reference<_ForwardIterator> __element) {
 104           return __element == __value;
 105         });
 106   }
 107 };
 108
 109 template <class _ExecutionPolicy>
 110 struct __find_if_not<__default_backend_tag, _ExecutionPolicy> {
 111   template <class _Policy, class _ForwardIterator, class _Pred>
 112   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
 113   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
 114     using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
 115     return _FindIf()(__policy, __first, __last, std::not_fn(std::forward<_Pred>(__pred)));
 116   }
 117 };
 118
 119 template <class _ExecutionPolicy>
 120 struct __any_of<__default_backend_tag, _ExecutionPolicy> {
 121   template <class _Policy, class _ForwardIterator, class _Pred>
 122   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
 123   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
 124     using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
 125     auto __res    = _FindIf()(__policy, __first, __last, std::forward<_Pred>(__pred));
 126     if (!__res)
 127       return nullopt;
 128     return *__res != __last;
 129   }
 130 };
 131
 132 template <class _ExecutionPolicy>
 133 struct __all_of<__default_backend_tag, _ExecutionPolicy> {
 134   template <class _Policy, class _ForwardIterator, class _Pred>
 135   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
 136   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
 137     using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;
 138     auto __res   = _AnyOf()(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __value) {
 139       return !__pred(__value);
 140     });
 141     if (!__res)
 142       return nullopt;
 143     return !*__res;
 144   }
 145 };
 146
 147 template <class _ExecutionPolicy>
 148 struct __none_of<__default_backend_tag, _ExecutionPolicy> {
 149   template <class _Policy, class _ForwardIterator, class _Pred>
 150   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
 151   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
 152     using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;
 153     auto __res   = _AnyOf()(__policy, __first, __last, std::forward<_Pred>(__pred));
 154     if (!__res)
 155       return nullopt;
 156     return !*__res;
 157   }
 158 };
 159
 160 template <class _ExecutionPolicy>
 161 struct __is_partitioned<__default_backend_tag, _ExecutionPolicy> {
 162   template <class _Policy, class _ForwardIterator, class _Pred>
 163   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
 164   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
 165     using _FindIfNot   = __dispatch<__find_if_not, __current_configuration, _ExecutionPolicy>;
 166     auto __maybe_first = _FindIfNot()(__policy, std::move(__first), std::move(__last), __pred);
 167     if (__maybe_first == nullopt)
 168       return nullopt;
 169
 170     __first = *__maybe_first;
 171     if (__first == __last)
 172       return true;
 173     ++__first;
 174     using _NoneOf = __dispatch<__none_of, __current_configuration, _ExecutionPolicy>;
 175     return _NoneOf()(__policy, std::move(__first), std::move(__last), __pred);
 176   }
 177 };
 178
 179 //////////////////////////////////////////////////////////////
 180 // for_each family
 181 //////////////////////////////////////////////////////////////
 182 template <class _ExecutionPolicy>
 183 struct __for_each_n<__default_backend_tag, _ExecutionPolicy> {
 184   template <class _Policy, class _ForwardIterator, class _Size, class _Function>
 185   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
 186   operator()(_Policy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) const noexcept {
 187     if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
 188       using _ForEach          = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
 189       _ForwardIterator __last = __first + __size;
 190       return _ForEach()(__policy, std::move(__first), std::move(__last), std::move(__func));
 191     } else {
 192       // Otherwise, use the serial algorithm to avoid doing two passes over the input
 193       std::for_each_n(std::move(__first), __size, std::move(__func));
 194       return __empty{};
 195     }
 196   }
 197 };
 198
 199 template <class _ExecutionPolicy>
 200 struct __fill<__default_backend_tag, _ExecutionPolicy> {
 201   template <class _Policy, class _ForwardIterator, class _Tp>
 202   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
 203   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
 204     using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
 205     using _Ref     = __iter_reference<_ForwardIterator>;
 206     return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __value; });
 207   }
 208 };
 209
 210 template <class _ExecutionPolicy>
 211 struct __fill_n<__default_backend_tag, _ExecutionPolicy> {
 212   template <class _Policy, class _ForwardIterator, class _Size, class _Tp>
 213   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
 214   operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Tp const& __value) const noexcept {
 215     if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
 216       using _Fill             = __dispatch<__fill, __current_configuration, _ExecutionPolicy>;
 217       _ForwardIterator __last = __first + __n;
 218       return _Fill()(__policy, std::move(__first), std::move(__last), __value);
 219     } else {
 220       // Otherwise, use the serial algorithm to avoid doing two passes over the input
 221       std::fill_n(std::move(__first), __n, __value);
 222       return optional<__empty>{__empty{}};
 223     }
 224   }
 225 };
 226
 227 template <class _ExecutionPolicy>
 228 struct __replace<__default_backend_tag, _ExecutionPolicy> {
 229   template <class _Policy, class _ForwardIterator, class _Tp>
 230   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
 231   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __old, _Tp const& __new)
 232       const noexcept {
 233     using _ReplaceIf = __dispatch<__replace_if, __current_configuration, _ExecutionPolicy>;
 234     using _Ref       = __iter_reference<_ForwardIterator>;
 235     return _ReplaceIf()(
 236         __policy, std::move(__first), std::move(__last), [&](_Ref __element) { return __element == __old; }, __new);
 237   }
 238 };
 239
 240 template <class _ExecutionPolicy>
 241 struct __replace_if<__default_backend_tag, _ExecutionPolicy> {
 242   template <class _Policy, class _ForwardIterator, class _Pred, class _Tp>
 243   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
 244       _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred, _Tp const& __new_value)
 245       const noexcept {
 246     using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
 247     using _Ref     = __iter_reference<_ForwardIterator>;
 248     return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) {
 249       if (__pred(__element))
 250         __element = __new_value;
 251     });
 252   }
 253 };
 254
 255 template <class _ExecutionPolicy>
 256 struct __generate<__default_backend_tag, _ExecutionPolicy> {
 257   template <class _Policy, class _ForwardIterator, class _Generator>
 258   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
 259   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator&& __gen) const noexcept {
 260     using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
 261     using _Ref     = __iter_reference<_ForwardIterator>;
 262     return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __gen(); });
 263   }
 264 };
 265
 266 template <class _ExecutionPolicy>
 267 struct __generate_n<__default_backend_tag, _ExecutionPolicy> {
 268   template <class _Policy, class _ForwardIterator, class _Size, class _Generator>
 269   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
 270   operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Generator&& __gen) const noexcept {
 271     using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
 272     using _Ref      = __iter_reference<_ForwardIterator>;
 273     return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __gen(); });
 274   }
 275 };
 276
 277 //////////////////////////////////////////////////////////////
 278 // stable_sort family
 279 //////////////////////////////////////////////////////////////
 280 template <class _ExecutionPolicy>
 281 struct __sort<__default_backend_tag, _ExecutionPolicy> {
 282   template <class _Policy, class _RandomAccessIterator, class _Comp>
 283   _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
 284       _Policy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {
 285     using _StableSort = __dispatch<__stable_sort, __current_configuration, _ExecutionPolicy>;
 286     return _StableSort()(__policy, std::move(__first), std::move(__last), std::forward<_Comp>(__comp));
 287   }
 288 };
 289
 290 //////////////////////////////////////////////////////////////
 291 // transform_reduce family
 292 //////////////////////////////////////////////////////////////
 293 template <class _ExecutionPolicy>
 294 struct __count_if<__default_backend_tag, _ExecutionPolicy> {
 295   template <class _Policy, class _ForwardIterator, class _Predicate>
 296   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iter_diff_t<_ForwardIterator>> operator()(
 297       _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred) const noexcept {
 298     using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
 299     using _DiffT           = __iter_diff_t<_ForwardIterator>;
 300     using _Ref             = __iter_reference<_ForwardIterator>;
 301     return _TransformReduce()(
 302         __policy, std::move(__first), std::move(__last), _DiffT{}, std::plus{}, [&](_Ref __element) -> _DiffT {
 303           return __pred(__element) ? _DiffT(1) : _DiffT(0);
 304         });
 305   }
 306 };
 307
 308 template <class _ExecutionPolicy>
 309 struct __count<__default_backend_tag, _ExecutionPolicy> {
 310   template <class _Policy, class _ForwardIterator, class _Tp>
 311   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iter_diff_t<_ForwardIterator>>
 312   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
 313     using _CountIf = __dispatch<__count_if, __current_configuration, _ExecutionPolicy>;
 314     using _Ref     = __iter_reference<_ForwardIterator>;
 315     return _CountIf()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) -> bool {
 316       return __element == __value;
 317     });
 318   }
 319 };
 320
 321 template <class _ExecutionPolicy>
 322 struct __equal_3leg<__default_backend_tag, _ExecutionPolicy> {
 323   template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
 324   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
 325   operator()(_Policy&& __policy,
 326              _ForwardIterator1 __first1,
 327              _ForwardIterator1 __last1,
 328              _ForwardIterator2 __first2,
 329              _Predicate&& __pred) const noexcept {
 330     using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>;
 331     return _TransformReduce()(
 332         __policy,
 333         std::move(__first1),
 334         std::move(__last1),
 335         std::move(__first2),
 336         true,
 337         std::logical_and{},
 338         std::forward<_Predicate>(__pred));
 339   }
 340 };
 341
 342 template <class _ExecutionPolicy>
 343 struct __equal<__default_backend_tag, _ExecutionPolicy> {
 344   template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
 345   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
 346   operator()(_Policy&& __policy,
 347              _ForwardIterator1 __first1,
 348              _ForwardIterator1 __last1,
 349              _ForwardIterator2 __first2,
 350              _ForwardIterator2 __last2,
 351              _Predicate&& __pred) const noexcept {
 352     if constexpr (__has_random_access_iterator_category<_ForwardIterator1>::value &&
 353                   __has_random_access_iterator_category<_ForwardIterator2>::value) {
 354       if (__last1 - __first1 != __last2 - __first2)
 355         return false;
 356       // Fall back to the 3 legged algorithm
 357       using _Equal3Leg = __dispatch<__equal_3leg, __current_configuration, _ExecutionPolicy>;
 358       return _Equal3Leg()(
 359           __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::forward<_Predicate>(__pred));
 360     } else {
 361       // If we don't have random access, fall back to the serial algorithm cause we can't do much
 362       return std::equal(
 363           std::move(__first1),
 364           std::move(__last1),
 365           std::move(__first2),
 366           std::move(__last2),
 367           std::forward<_Predicate>(__pred));
 368     }
 369   }
 370 };
 371
 372 template <class _ExecutionPolicy>
 373 struct __reduce<__default_backend_tag, _ExecutionPolicy> {
 374   template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation>
 375   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_Tp>
 376   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation&& __op)
 377       const noexcept {
 378     using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
 379     return _TransformReduce()(
 380         __policy,
 381         std::move(__first),
 382         std::move(__last),
 383         std::move(__init),
 384         std::forward<_BinaryOperation>(__op),
 385         __identity{});
 386   }
 387 };
 388
 389 //////////////////////////////////////////////////////////////
 390 // transform family
 391 //////////////////////////////////////////////////////////////
 392 template <class _ExecutionPolicy>
 393 struct __replace_copy_if<__default_backend_tag, _ExecutionPolicy> {
 394   template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Pred, class _Tp>
 395   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
 396   operator()(_Policy&& __policy,
 397              _ForwardIterator __first,
 398              _ForwardIterator __last,
 399              _ForwardOutIterator __out_it,
 400              _Pred&& __pred,
 401              _Tp const& __new_value) const noexcept {
 402     using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
 403     using _Ref       = __iter_reference<_ForwardIterator>;
 404     auto __res =
 405         _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](_Ref __element) {
 406           return __pred(__element) ? __new_value : __element;
 407         });
 408     if (__res == nullopt)
 409       return nullopt;
 410     return __empty{};
 411   }
 412 };
 413
 414 template <class _ExecutionPolicy>
 415 struct __replace_copy<__default_backend_tag, _ExecutionPolicy> {
 416   template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Tp>
 417   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
 418   operator()(_Policy&& __policy,
 419              _ForwardIterator __first,
 420              _ForwardIterator __last,
 421              _ForwardOutIterator __out_it,
 422              _Tp const& __old_value,
 423              _Tp const& __new_value) const noexcept {
 424     using _ReplaceCopyIf = __dispatch<__replace_copy_if, __current_configuration, _ExecutionPolicy>;
 425     using _Ref           = __iter_reference<_ForwardIterator>;
 426     return _ReplaceCopyIf()(
 427         __policy,
 428         std::move(__first),
 429         std::move(__last),
 430         std::move(__out_it),
 431         [&](_Ref __element) { return __element == __old_value; },
 432         __new_value);
 433   }
 434 };
 435
 436 // TODO: Use the std::copy/move shenanigans to forward to std::memmove
 437 //       Investigate whether we want to still forward to std::transform(policy)
 438 //       in that case for the execution::par part, or whether we actually want
 439 //       to run everything serially in that case.
 440 template <class _ExecutionPolicy>
 441 struct __move<__default_backend_tag, _ExecutionPolicy> {
 442   template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
 443   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
 444   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
 445       const noexcept {
 446     using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
 447     return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](auto&& __element) {
 448       return std::move(__element);
 449     });
 450   }
 451 };
 452
 453 // TODO: Use the std::copy/move shenanigans to forward to std::memmove
 454 template <class _ExecutionPolicy>
 455 struct __copy<__default_backend_tag, _ExecutionPolicy> {
 456   template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
 457   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
 458   operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
 459       const noexcept {
 460     using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
 461     return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), __identity());
 462   }
 463 };
 464
 465 template <class _ExecutionPolicy>
 466 struct __copy_n<__default_backend_tag, _ExecutionPolicy> {
 467   template <class _Policy, class _ForwardIterator, class _Size, class _ForwardOutIterator>
 468   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
 469   operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __out_it) const noexcept {
 470     if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
 471       using _Copy             = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
 472       _ForwardIterator __last = __first + __n;
 473       return _Copy()(__policy, std::move(__first), std::move(__last), std::move(__out_it));
 474     } else {
 475       // Otherwise, use the serial algorithm to avoid doing two passes over the input
 476       return std::copy_n(std::move(__first), __n, std::move(__out_it));
 477     }
 478   }
 479 };
 480
 481 template <class _ExecutionPolicy>
 482 struct __rotate_copy<__default_backend_tag, _ExecutionPolicy> {
 483   template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
 484   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
 485   operator()(_Policy&& __policy,
 486              _ForwardIterator __first,
 487              _ForwardIterator __middle,
 488              _ForwardIterator __last,
 489              _ForwardOutIterator __out_it) const noexcept {
 490     using _Copy       = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
 491     auto __result_mid = _Copy()(__policy, __middle, std::move(__last), std::move(__out_it));
 492     if (__result_mid == nullopt)
 493       return nullopt;
 494     return _Copy()(__policy, std::move(__first), std::move(__middle), *std::move(__result_mid));
 495   }
 496 };
 497
 498 } // namespace __pstl
 499 _LIBCPP_END_NAMESPACE_STD
 500
 501 _LIBCPP_POP_MACROS
 502
 503 #endif // _LIBCPP___PSTL_BACKENDS_DEFAULT_H