diff --git a/libcxx/docs/Cxx2aStatusPaperStatus.csv b/libcxx/docs/Cxx2aStatusPaperStatus.csv --- a/libcxx/docs/Cxx2aStatusPaperStatus.csv +++ b/libcxx/docs/Cxx2aStatusPaperStatus.csv @@ -38,7 +38,7 @@ "`P0722R3 `__","CWG","Efficient sized delete for variable sized classes","Rapperswil","|Complete|","9.0" "`P0758R1 `__","LWG","Implicit conversion traits and utility functions","Rapperswil","|Complete|","" "`P0759R1 `__","LWG","fpos Requirements","Rapperswil","|Complete|","11.0" -"`P0769R2 `__","LWG","Add shift to ","Rapperswil","","" +"`P0769R2 `__","LWG","Add shift to ","Rapperswil","|Complete|","12.0" "`P0788R3 `__","LWG","Standard Library Specification in a Concepts and Contracts World","Rapperswil","","" "`P0879R0 `__","LWG","Constexpr for swap and swap related functions Also resolves LWG issue 2800.","Rapperswil","","" "`P0887R1 `__","LWG","The identity metafunction","Rapperswil","|Complete|","8.0" diff --git a/libcxx/docs/FeatureTestMacroTable.rst b/libcxx/docs/FeatureTestMacroTable.rst --- a/libcxx/docs/FeatureTestMacroTable.rst +++ b/libcxx/docs/FeatureTestMacroTable.rst @@ -222,6 +222,8 @@ ------------------------------------------------- ----------------- ``__cpp_lib_ranges`` *unimplemented* ------------------------------------------------- ----------------- + ``__cpp_lib_shift`` ``201806L`` + ------------------------------------------------- ----------------- ``__cpp_lib_span`` ``202002L`` ------------------------------------------------- ----------------- ``__cpp_lib_three_way_comparison`` *unimplemented* diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -301,6 +301,16 @@ void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g); +template + constexpr ForwardIterator + shift_left(ForwardIterator first, ForwardIterator last, + typename iterator_traits::difference_type n); // C++20 + +template + constexpr ForwardIterator + shift_right(ForwardIterator first, ForwardIterator last, + typename iterator_traits::difference_type n); // C++20 + template constexpr bool // constexpr in C++20 is_partitioned(InputIterator first, InputIterator last, Predicate pred); @@ -3251,6 +3261,111 @@ } } +#if _LIBCPP_STD_VER > 17 + +// shift_left, shift_right + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator +shift_left(_ForwardIterator __first, _ForwardIterator __last, + typename iterator_traits<_ForwardIterator>::difference_type __n) +{ + if (__n == 0) { + return __last; + } + + _ForwardIterator __m = __first; + if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) { + if (__n >= __last - __first) { + return __first; + } + __m += __n; + } else { + for (; __n > 0; --__n) { + if (__m == __last) { + return __first; + } + ++__m; + } + } + return _VSTD::move(__m, __last, __first); +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator +shift_right(_ForwardIterator __first, _ForwardIterator __last, + typename iterator_traits<_ForwardIterator>::difference_type __n) +{ + if (__n == 0) { + return __first; + } + + if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) { + decltype(__n) __d = __last - __first; + if (__n >= __d) { + return __last; + } + _ForwardIterator __m = __first + (__d - __n); + return _VSTD::move_backward(__first, __m, __last); + } else if constexpr (__is_cpp17_bidirectional_iterator<_ForwardIterator>::value) { + _ForwardIterator __m = __last; + for (; __n > 0; --__n) { + if (__m == __first) { + return __last; + } + --__m; + } + return _VSTD::move_backward(__first, __m, __last); + } else { + _ForwardIterator __ret = __first; + for (; __n > 0; --__n) { + if (__ret == __last) { + return __last; + } + ++__ret; + } + + // We have an __n-element scratch space from __first to __ret. + // Slide an __n-element window (__trail, __lead) from left to right. + // We're essentially doing swap_ranges(__first, __ret, __trail, __lead) + // over and over; but once __lead reaches __last we needn't bother + // to save the values of elements (__trail, __last). + + auto __trail = __first; + auto __lead = __ret; + while (__trail != __ret) { + if (__lead == __last) { + _VSTD::move(__first, __trail, __ret); + return __ret; + } + ++__trail; + ++__lead; + } + + _ForwardIterator __mid = __first; + while (true) { + if (__lead == __last) { + __trail = _VSTD::move(__mid, __ret, __trail); + _VSTD::move(__first, __mid, __trail); + return __ret; + } + swap(*__mid, *__trail); + ++__mid; + ++__trail; + ++__lead; + if (__mid == __ret) { + __mid = __first; + } + } + } +} + +#endif // _LIBCPP_STD_VER > 17 + +// is_partitioned + template _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 bool is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred) diff --git a/libcxx/include/version b/libcxx/include/version --- a/libcxx/include/version +++ b/libcxx/include/version @@ -110,6 +110,7 @@ __cpp_lib_shared_ptr_arrays 201611L __cpp_lib_shared_ptr_weak_type 201606L __cpp_lib_shared_timed_mutex 201402L +__cpp_lib_shift 201806L __cpp_lib_span 202002L __cpp_lib_string_udls 201304L __cpp_lib_string_view 201606L @@ -274,6 +275,7 @@ # define __cpp_lib_math_constants 201907L # endif // # define __cpp_lib_ranges 201811L +# define __cpp_lib_shift 201806L # define __cpp_lib_span 202002L // # define __cpp_lib_three_way_comparison 201711L # define __cpp_lib_to_array 201907L diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_left.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_left.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_left.pass.cpp @@ -0,0 +1,68 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17 + +// + +// template +// constexpr ForwardIterator +// shift_left(ForwardIterator first, ForwardIterator last, +// typename iterator_traits::difference_type n); + +#include +#include + +#include "test_macros.h" +#include "test_iterators.h" +#include "MoveOnly.h" + +template +constexpr bool test() +{ + int orig[] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9}; + T work[] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9}; + + for (int n = 0; n <= 15; ++n) { + for (int k=0; k <= n+2; ++k) { + std::copy(orig, orig+n, work); + Iter it = std::shift_left(Iter(work), Iter(work+n), k); + if (k < n) { + assert(it == Iter(work+n-k)); + assert(std::equal(orig+k, orig+n, work, work+n-k)); + } else { + assert(it == Iter(work)); + assert(std::equal(orig, orig+n, work, work+n)); + } + } + } + return true; +} + +int main(int, char**) +{ + test>(); + test>(); + test>(); + test(); + test>(); + test>(); + test>(); + test(); + + static_assert(test>()); + static_assert(test>()); + static_assert(test>()); + static_assert(test()); + static_assert(test>()); + static_assert(test>()); + static_assert(test>()); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp @@ -0,0 +1,68 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17 + +// + +// template +// constexpr ForwardIterator +// shift_right(ForwardIterator first, ForwardIterator last, +// typename iterator_traits::difference_type n); + +#include +#include + +#include "test_macros.h" +#include "test_iterators.h" +#include "MoveOnly.h" + +template +constexpr bool test() +{ + int orig[] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9}; + T work[] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9}; + + for (int n = 0; n <= 15; ++n) { + for (int k=0; k <= n+2; ++k) { + std::copy(orig, orig+n, work); + Iter it = std::shift_right(Iter(work), Iter(work+n), k); + if (k < n) { + assert(it == Iter(work+k)); + assert(std::equal(orig, orig+n-k, work+k, work+n)); + } else { + assert(it == Iter(work+n)); + assert(std::equal(orig, orig+n, work, work+n)); + } + } + } + return true; +} + +int main(int, char**) +{ + test>(); + test>(); + test>(); + test(); + test>(); + test>(); + test>(); + test(); + + static_assert(test>()); + static_assert(test>()); + static_assert(test>()); + static_assert(test()); + static_assert(test>()); + static_assert(test>()); + static_assert(test>()); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp b/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp --- a/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp +++ b/libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp @@ -20,6 +20,7 @@ __cpp_lib_ranges 201811L [C++2a] __cpp_lib_robust_nonmodifying_seq_ops 201304L [C++14] __cpp_lib_sample 201603L [C++17] + __cpp_lib_shift 201806L [C++2a] */ #include @@ -51,6 +52,10 @@ # error "__cpp_lib_sample should not be defined before c++17" # endif +# ifdef __cpp_lib_shift +# error "__cpp_lib_shift should not be defined before c++2a" +# endif + #elif TEST_STD_VER == 14 # ifdef __cpp_lib_clamp @@ -80,6 +85,10 @@ # error "__cpp_lib_sample should not be defined before c++17" # endif +# ifdef __cpp_lib_shift +# error "__cpp_lib_shift should not be defined before c++2a" +# endif + #elif TEST_STD_VER == 17 # ifndef __cpp_lib_clamp @@ -124,6 +133,10 @@ # error "__cpp_lib_sample should have the value 201603L in c++17" # endif +# ifdef __cpp_lib_shift +# error "__cpp_lib_shift should not be defined before c++2a" +# endif + #elif TEST_STD_VER > 17 # ifndef __cpp_lib_clamp @@ -186,6 +199,13 @@ # error "__cpp_lib_sample should have the value 201603L in c++2a" # endif +# ifndef __cpp_lib_shift +# error "__cpp_lib_shift should be defined in c++2a" +# endif +# if __cpp_lib_shift != 201806L +# error "__cpp_lib_shift should have the value 201806L in c++2a" +# endif + #endif // TEST_STD_VER > 17 int main(int, char**) { return 0; } diff --git a/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp b/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp --- a/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp +++ b/libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp @@ -97,6 +97,7 @@ __cpp_lib_shared_ptr_arrays 201611L [C++17] __cpp_lib_shared_ptr_weak_type 201606L [C++17] __cpp_lib_shared_timed_mutex 201402L [C++14] + __cpp_lib_shift 201806L [C++2a] __cpp_lib_span 202002L [C++2a] __cpp_lib_string_udls 201304L [C++14] __cpp_lib_string_view 201606L [C++17] @@ -448,6 +449,10 @@ # error "__cpp_lib_shared_timed_mutex should not be defined before c++14" # endif +# ifdef __cpp_lib_shift +# error "__cpp_lib_shift should not be defined before c++2a" +# endif + # ifdef __cpp_lib_span # error "__cpp_lib_span should not be defined before c++2a" # endif @@ -889,6 +894,10 @@ # endif # endif +# ifdef __cpp_lib_shift +# error "__cpp_lib_shift should not be defined before c++2a" +# endif + # ifdef __cpp_lib_span # error "__cpp_lib_span should not be defined before c++2a" # endif @@ -1534,6 +1543,10 @@ # endif # endif +# ifdef __cpp_lib_shift +# error "__cpp_lib_shift should not be defined before c++2a" +# endif + # ifdef __cpp_lib_span # error "__cpp_lib_span should not be defined before c++2a" # endif @@ -2386,6 +2399,13 @@ # endif # endif +# ifndef __cpp_lib_shift +# error "__cpp_lib_shift should be defined in c++2a" +# endif +# if __cpp_lib_shift != 201806L +# error "__cpp_lib_shift should have the value 201806L in c++2a" +# endif + # ifndef __cpp_lib_span # error "__cpp_lib_span should be defined in c++2a" # endif diff --git a/libcxx/utils/generate_feature_test_macro_components.py b/libcxx/utils/generate_feature_test_macro_components.py --- a/libcxx/utils/generate_feature_test_macro_components.py +++ b/libcxx/utils/generate_feature_test_macro_components.py @@ -401,6 +401,10 @@ "values": { "c++2a": int(201811) }, "headers": ["algorithm", "functional", "iterator", "memory", "ranges"], "unimplemented": True, + }, { + "name": "__cpp_lib_shift", + "values": { "c++2a": int(201806) }, + "headers": ["algorithm"], }, { "name": "__cpp_lib_bit_cast", "values": { "c++2a": int(201806) },