Author: Arthur O'Dwyer Date: 2021-01-25T12:57:04-05:00 New Revision: 3fbd3eaf28c1e6f2bb9519022611829dfe3b0464
URL: https://github.com/llvm/llvm-project/commit/3fbd3eaf28c1e6f2bb9519022611829dfe3b0464 DIFF: https://github.com/llvm/llvm-project/commit/3fbd3eaf28c1e6f2bb9519022611829dfe3b0464.diff LOG: [libc++] Implement [P0769] "Add shift to algorithm" (shift_left, shift_right) I believe this is a complete implementation of std::shift_left and std::shift_right from http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0769r2.pdf Some test cases copied-with-modification from D60027. Differential Revision: https://reviews.llvm.org/D93819 Added: libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_left.pass.cpp libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp Modified: libcxx/docs/Cxx2aStatusPaperStatus.csv libcxx/docs/FeatureTestMacroTable.rst libcxx/include/algorithm libcxx/include/version libcxx/test/std/language.support/support.limits/support.limits.general/algorithm.version.pass.cpp libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp libcxx/utils/generate_feature_test_macro_components.py Removed: ################################################################################ diff --git a/libcxx/docs/Cxx2aStatusPaperStatus.csv b/libcxx/docs/Cxx2aStatusPaperStatus.csv index 8991a03b2a5c..e30a289470d3 100644 --- a/libcxx/docs/Cxx2aStatusPaperStatus.csv +++ b/libcxx/docs/Cxx2aStatusPaperStatus.csv @@ -38,7 +38,7 @@ "`P0722R3 <https://wg21.link/P0722R3>`__","CWG","Efficient sized delete for variable sized classes","Rapperswil","|Complete|","9.0" "`P0758R1 <https://wg21.link/P0758R1>`__","LWG","Implicit conversion traits and utility functions","Rapperswil","|Complete|","" "`P0759R1 <https://wg21.link/P0759R1>`__","LWG","fpos Requirements","Rapperswil","|Complete|","11.0" -"`P0769R2 <https://wg21.link/P0769R2>`__","LWG","Add shift to <algorithm>","Rapperswil","","" +"`P0769R2 <https://wg21.link/P0769R2>`__","LWG","Add shift to <algorithm>","Rapperswil","|Complete|","12.0" "`P0788R3 <https://wg21.link/P0788R3>`__","LWG","Standard Library Specification in a Concepts and Contracts World","Rapperswil","*Removed in Cologne*","n/a" "`P0879R0 <https://wg21.link/P0879R0>`__","LWG","Constexpr for swap and swap related functions Also resolves LWG issue 2800.","Rapperswil","","" "`P0887R1 <https://wg21.link/P0887R1>`__","LWG","The identity metafunction","Rapperswil","|Complete|","8.0" diff --git a/libcxx/docs/FeatureTestMacroTable.rst b/libcxx/docs/FeatureTestMacroTable.rst index b5db1e08d7bf..ed05488fa711 100644 --- a/libcxx/docs/FeatureTestMacroTable.rst +++ b/libcxx/docs/FeatureTestMacroTable.rst @@ -266,7 +266,7 @@ Status ------------------------------------------------- ----------------- ``__cpp_lib_semaphore`` ``201907L`` ------------------------------------------------- ----------------- - ``__cpp_lib_shift`` *unimplemented* + ``__cpp_lib_shift`` ``201806L`` ------------------------------------------------- ----------------- ``__cpp_lib_smart_ptr_for_overwrite`` *unimplemented* ------------------------------------------------- ----------------- diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index da55e5e9add0..77711d250188 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -301,6 +301,16 @@ template<class RandomAccessIterator, class UniformRandomNumberGenerator> void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g); +template<class ForwardIterator> + constexpr ForwardIterator + shift_left(ForwardIterator first, ForwardIterator last, + typename iterator_traits<ForwardIterator>:: diff erence_type n); // C++20 + +template<class ForwardIterator> + constexpr ForwardIterator + shift_right(ForwardIterator first, ForwardIterator last, + typename iterator_traits<ForwardIterator>:: diff erence_type n); // C++20 + template <class InputIterator, class Predicate> constexpr bool // constexpr in C++20 is_partitioned(InputIterator first, InputIterator last, Predicate pred); @@ -3259,6 +3269,111 @@ template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> } } +#if _LIBCPP_STD_VER > 17 + +// shift_left, shift_right + +template <class _ForwardIterator> +inline _LIBCPP_INLINE_VISIBILITY constexpr +_ForwardIterator +shift_left(_ForwardIterator __first, _ForwardIterator __last, + typename iterator_traits<_ForwardIterator>:: diff erence_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 <class _ForwardIterator> +inline _LIBCPP_INLINE_VISIBILITY constexpr +_ForwardIterator +shift_right(_ForwardIterator __first, _ForwardIterator __last, + typename iterator_traits<_ForwardIterator>:: diff erence_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 <class _InputIterator, class _Predicate> _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 index 5f036a52cacc..813bc1ab9e6a 100644 --- a/libcxx/include/version +++ b/libcxx/include/version @@ -339,7 +339,7 @@ __cpp_lib_void_t 201411L <type_traits> # if !defined(_LIBCPP_HAS_NO_THREADS) # define __cpp_lib_semaphore 201907L # endif -// # define __cpp_lib_shift 201806L +# define __cpp_lib_shift 201806L // # define __cpp_lib_smart_ptr_for_overwrite 202002L // # define __cpp_lib_source_location 201907L # define __cpp_lib_span 202002L 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 index 000000000000..90540f499e15 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_left.pass.cpp @@ -0,0 +1,128 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// <algorithm> + +// template<class ForwardIterator> +// constexpr ForwardIterator +// shift_left(ForwardIterator first, ForwardIterator last, +// typename iterator_traits<ForwardIterator>:: diff erence_type n); + +#include <algorithm> +#include <cassert> + +#include "test_macros.h" +#include "test_iterators.h" +#include "MoveOnly.h" + +template<class T, class Iter> +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 (0 <= k && 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)); + } + } + } + + // n == 0 + { + T input[] = { 0, 1, 2 }; + const T expected[] = { 0, 1, 2 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, 0); + assert(std::equal(std::begin(expected), std::end(expected), b, e)); + assert(it == e); + } + + // n > 0 && n < len + { + T input[] = { 0, 1, 2 }; + const T expected[] = { 1, 2 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, 1); + assert(std::equal(std::begin(expected), std::end(expected), b, it)); + } + { + T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; + const T expected[] = { 3, 4, 5, 6, 7, 8 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, 2); + assert(std::equal(std::begin(expected), std::end(expected), b, it)); + } + { + T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; + const T expected[] = { 7, 8 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, 6); + assert(std::equal(std::begin(expected), std::end(expected), b, it)); + } + + // n == len + { + T input[] = { 0, 1, 2 }; + const T expected[] = { 0, 1, 2 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, std::size(input)); + assert(std::equal(std::begin(expected), std::end(expected), b, e)); + assert(it == b); + } + + // n > len + { + T input[] = { 0, 1, 2 }; + const T expected[] = { 0, 1, 2 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_left(b, e, std::size(input) + 1); + assert(std::equal(std::begin(expected), std::end(expected), b, e)); + assert(it == b); + } + + return true; +} + +int main(int, char**) +{ + test<int, forward_iterator<int*>>(); + test<int, bidirectional_iterator<int*>>(); + test<int, random_access_iterator<int*>>(); + test<int, int*>(); + test<MoveOnly, forward_iterator<MoveOnly*>>(); + test<MoveOnly, bidirectional_iterator<MoveOnly*>>(); + test<MoveOnly, random_access_iterator<MoveOnly*>>(); + test<MoveOnly, MoveOnly*>(); + + static_assert(test<int, forward_iterator<int*>>()); + static_assert(test<int, bidirectional_iterator<int*>>()); + static_assert(test<int, random_access_iterator<int*>>()); + static_assert(test<int, int*>()); + static_assert(test<MoveOnly, forward_iterator<MoveOnly*>>()); + static_assert(test<MoveOnly, bidirectional_iterator<MoveOnly*>>()); + static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>()); + static_assert(test<MoveOnly, MoveOnly*>()); + + 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 index 000000000000..d92387c4c77a --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/shift_right.pass.cpp @@ -0,0 +1,127 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// <algorithm> + +// template<class ForwardIterator> +// constexpr ForwardIterator +// shift_right(ForwardIterator first, ForwardIterator last, +// typename iterator_traits<ForwardIterator>:: diff erence_type n); + +#include <algorithm> +#include <cassert> + +#include "test_macros.h" +#include "test_iterators.h" +#include "MoveOnly.h" + +template<class T, class Iter> +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)); + } + } + } + + // n == 0 + { + T input[] = { 0, 1, 2 }; + const T expected[] = { 0, 1, 2 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, 0); + assert(std::equal(std::begin(expected), std::end(expected), it, e)); + } + + // n > 0 && n < len + { + T input[] = { 0, 1, 2 }; + const T expected[] = { 0, 1 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, 1); + assert(std::equal(std::begin(expected), std::end(expected), it, e)); + } + { + T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; + const T expected[] = { 1, 2, 3, 4, 5, 6 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, 2); + assert(std::equal(std::begin(expected), std::end(expected), it, e)); + } + { + T input[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; + const T expected[] = { 1, 2 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, 6); + assert(std::equal(std::begin(expected), std::end(expected), it, e)); + } + + // n == len + { + T input[] = { 0, 1, 2 }; + const T expected[] = { 0, 1, 2 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, std::size(input)); + assert(std::equal(std::begin(expected), std::end(expected), b, e)); + assert(it == e); + } + + // n > len + { + T input[] = { 0, 1, 2 }; + const T expected[] = { 0, 1, 2 }; + Iter b = Iter(std::begin(input)); + Iter e = Iter(std::end(input)); + Iter it = std::shift_right(b, e, std::size(input) + 1); + assert(std::equal(std::begin(expected), std::end(expected), b, e)); + assert(it == e); + } + + return true; +} + +int main(int, char**) +{ + test<int, forward_iterator<int*>>(); + test<int, bidirectional_iterator<int*>>(); + test<int, random_access_iterator<int*>>(); + test<int, int*>(); + test<MoveOnly, forward_iterator<MoveOnly*>>(); + test<MoveOnly, bidirectional_iterator<MoveOnly*>>(); + test<MoveOnly, random_access_iterator<MoveOnly*>>(); + test<MoveOnly, MoveOnly*>(); + + static_assert(test<int, forward_iterator<int*>>()); + static_assert(test<int, bidirectional_iterator<int*>>()); + static_assert(test<int, random_access_iterator<int*>>()); + static_assert(test<int, int*>()); + static_assert(test<MoveOnly, forward_iterator<MoveOnly*>>()); + static_assert(test<MoveOnly, bidirectional_iterator<MoveOnly*>>()); + static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>()); + static_assert(test<MoveOnly, MoveOnly*>()); + + 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 index 4e570d2d69e0..e081ca79f6f0 100644 --- 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 @@ -201,17 +201,11 @@ # error "__cpp_lib_sample should have the value 201603L in c++20" # endif -# if !defined(_LIBCPP_VERSION) -# ifndef __cpp_lib_shift -# error "__cpp_lib_shift should be defined in c++20" -# endif -# if __cpp_lib_shift != 201806L -# error "__cpp_lib_shift should have the value 201806L in c++20" -# endif -# else // _LIBCPP_VERSION -# ifdef __cpp_lib_shift -# error "__cpp_lib_shift should not be defined because it is unimplemented in libc++!" -# endif +# ifndef __cpp_lib_shift +# error "__cpp_lib_shift should be defined in c++20" +# endif +# if __cpp_lib_shift != 201806L +# error "__cpp_lib_shift should have the value 201806L in c++20" # endif #elif TEST_STD_VER > 20 @@ -276,17 +270,11 @@ # error "__cpp_lib_sample should have the value 201603L in c++2b" # endif -# if !defined(_LIBCPP_VERSION) -# ifndef __cpp_lib_shift -# error "__cpp_lib_shift should be defined in c++2b" -# endif -# if __cpp_lib_shift != 201806L -# error "__cpp_lib_shift should have the value 201806L in c++2b" -# endif -# else // _LIBCPP_VERSION -# ifdef __cpp_lib_shift -# error "__cpp_lib_shift should not be defined because it is unimplemented in libc++!" -# endif +# ifndef __cpp_lib_shift +# error "__cpp_lib_shift should be defined in c++2b" +# endif +# if __cpp_lib_shift != 201806L +# error "__cpp_lib_shift should have the value 201806L in c++2b" # endif #endif // TEST_STD_VER > 20 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 index 289145fdd66d..9e96e2e116e0 100644 --- 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 @@ -3072,17 +3072,11 @@ # endif # endif -# if !defined(_LIBCPP_VERSION) -# ifndef __cpp_lib_shift -# error "__cpp_lib_shift should be defined in c++20" -# endif -# if __cpp_lib_shift != 201806L -# error "__cpp_lib_shift should have the value 201806L in c++20" -# endif -# else // _LIBCPP_VERSION -# ifdef __cpp_lib_shift -# error "__cpp_lib_shift should not be defined because it is unimplemented in libc++!" -# endif +# ifndef __cpp_lib_shift +# error "__cpp_lib_shift should be defined in c++20" +# endif +# if __cpp_lib_shift != 201806L +# error "__cpp_lib_shift should have the value 201806L in c++20" # endif # if !defined(_LIBCPP_VERSION) @@ -4287,17 +4281,11 @@ # endif # endif -# if !defined(_LIBCPP_VERSION) -# ifndef __cpp_lib_shift -# error "__cpp_lib_shift should be defined in c++2b" -# endif -# if __cpp_lib_shift != 201806L -# error "__cpp_lib_shift should have the value 201806L in c++2b" -# endif -# else // _LIBCPP_VERSION -# ifdef __cpp_lib_shift -# error "__cpp_lib_shift should not be defined because it is unimplemented in libc++!" -# endif +# ifndef __cpp_lib_shift +# error "__cpp_lib_shift should be defined in c++2b" +# endif +# if __cpp_lib_shift != 201806L +# error "__cpp_lib_shift should have the value 201806L in c++2b" # endif # if !defined(_LIBCPP_VERSION) diff --git a/libcxx/utils/generate_feature_test_macro_components.py b/libcxx/utils/generate_feature_test_macro_components.py index dc9a5bca0799..00de15dae24a 100755 --- a/libcxx/utils/generate_feature_test_macro_components.py +++ b/libcxx/utils/generate_feature_test_macro_components.py @@ -522,7 +522,6 @@ def add_version_header(tc): "name": "__cpp_lib_shift", "values": { "c++20": 201806 }, "headers": ["algorithm"], - "unimplemented": True, }, { "name": "__cpp_lib_smart_ptr_for_overwrite", "values": { "c++20": 202002 }, _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
