aboutsummaryrefslogtreecommitdiff
path: root/libcxx/include/algorithm
AgeCommit message (Collapse)AuthorFilesLines
2021-06-04[libcxx][gardening] Move all algorithms into their own headers.zoecarver1-5187/+76
This is a fairly mechanical change, it just moves each algorithm into its own header. This is a NFC. Note: during this change, I burned down all the includes, so this follows "include only and exactly what you use." Differential Revision: https://reviews.llvm.org/D103583
2021-06-02Revert "[libc++] NFC: Move unwrap_iter to its own header"Louis Dionne1-1/+59
This reverts commit 924ea3bb53 *again*, this time because it broke the LLDB build with modules. We need to figure out what's up with the libc++ modules build once and for all. Differential Revision: https://reviews.llvm.org/D103369
2021-06-01[libc++] NFC: Move unwrap_iter to its own headerLouis Dionne1-59/+1
This re-applies 9968896cd62a, which was reverted in b13edf6e907b because it broke the build. Differential Revision: https://reviews.llvm.org/D103369
2021-05-29[libc++] Alphabetize and include-what-you-use. NFCI.Arthur O'Dwyer1-6/+6
Differential Revision: https://reviews.llvm.org/D102781
2021-05-29Revert "[libc++] NFC: Move unwrap_iter to its own header"Mark de Wever1-1/+59
This reverts commit 9968896cd62a62b11ac61085534dd598c4bd3c60. This commit seems to cause the build failures of main.
2021-05-28[libc++] NFC: Move unwrap_iter to its own headerLouis Dionne1-59/+1
2021-05-11[libc++] Remove more unnecessary _VSTD:: from type names. NFCI.Arthur O'Dwyer1-4/+3
Differential Revision: https://reviews.llvm.org/D102181
2021-05-11[libc++] s/_VSTD::declval/declval/g. NFCI.Arthur O'Dwyer1-3/+3
2021-05-10[libc++][NFC] Remove _VSTD:: when not needed.Mark de Wever1-9/+9
Reviewed By: #libc, Quuxplusone Differential Revision: https://reviews.llvm.org/D102133
2021-04-20[libc++] NFC: Normalize `#endif //` comment indentationLouis Dionne1-5/+5
2021-02-05[libc++] Further improve the contiguous-iterator story, and fix some bugs.Arthur O'Dwyer1-23/+53
- Quality-of-implementation: Avoid calling __unwrap_iter in constexpr contexts. The user might conceivably write a contiguous iterator where normal iterator arithmetic is constexpr-friendly but `std::to_address(it)` isn't. - Bugfix: When you pass contiguous iterators to `std::copy`, you should get back your contiguous iterator type, not a raw pointer. That means that libc++ can't `__unwrap_iter` unless it also does `__rewrap_iter`. Fortunately, this is implementable. - Improve test coverage of the new `contiguous_iterator` test iterator. This catches the bug described above. - Tests: Stop testing that we can `std::copy` //into// an `input_iterator`. Our test iterators may currently support that, but it seems nonsensical to me. Differential Revision: https://reviews.llvm.org/D95983
2021-02-05Revert "Revert "[libc++] [P0879] constexpr std::nth_element, and rewrite its ↵Arthur O'Dwyer1-68/+76
tests."" This reverts commit b6ffece32035a90d181101f356bd9c04ea1d3122. The bug is now fixed (it was a stupid cut-and-paste kind of error), and the regression test added. The new patch is also simpler than the old one! Differential Revision: https://reviews.llvm.org/D96084
2021-02-04Revert "[libc++] [P0879] constexpr std::nth_element, and rewrite its tests."Jordan Rupprecht1-92/+71
This reverts commit 207d4be4d9d39fbb9aca30e5d5d11245db9bccc1 due to returning incorrect results. Regression test case posted in D96074.
2021-02-03[libc++] [P0879] constexpr std::sortArthur O'Dwyer1-41/+29
This completes libc++'s implementation of P0879 "Constexpr for swap and swap related functions." http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0879r0.html For the feature-macro adjustment, see https://cplusplus.github.io/LWG/issue3256 Differential Revision: https://reviews.llvm.org/D93661
2021-02-03[libc++] Rationalize our treatment of contiguous iterators and __unwrap_iter().Arthur O'Dwyer1-55/+29
- Implement C++20's changes to `reverse_iterator`, so that it won't be accidentally counted as a contiguous iterator in C++20 mode. - Implement C++20's changes to `move_iterator` as well. - `move_iterator` should not be contiguous. This fixes a bug where we optimized `std::copy`-of-move-iterators in an observable way. Add a regression test for that bugfix. - Add libcxx tests for `__is_cpp17_contiguous_iterator` of all relevant standard iterator types. Particularly check that vector::iterator is still considered contiguous in all C++ modes, even C++03. After this patch, there continues to be no supported way to write your own iterator type in C++17-and-earlier such that libc++ will consider it "contiguous"; however, we now fully support the C++20 approach (in C++20 mode only). If you want user-defined contiguous iterators in C++17-and-earlier, libc++'s position is "please upgrade to C++20." Differential Revision: https://reviews.llvm.org/D94807
2021-01-28[libc++] [P0879] constexpr std::nth_element, and rewrite its tests.Arthur O'Dwyer1-71/+92
This patch is more than just adding the `constexpr` keyword, because the old code relied on `goto`, and `goto` is not constexpr-friendly. Refactor to eliminate `goto`, and then mark it as constexpr in C++20. I freely admit that the name `__nth_element_partloop` is bad; I couldn't find any better name because I don't really know what this loop is doing, conceptually. Vice versa, I think `__nth_element_find_guard` has a decent name. Now the only one we're still missing from P0879 is `sort`. Differential Revision: https://reviews.llvm.org/D93557
2021-01-27[libc++] [P0879] constexpr heap and partial_sort algorithmsArthur O'Dwyer1-32/+32
Now the only ones we're still missing from P0879 are `sort` and `nth_element`. Differential Revision: https://reviews.llvm.org/D93512
2021-01-25[libc++] [P0879] constexpr std::reverse, partition, *_permutation.Arthur O'Dwyer1-18/+18
After this patch, the only parts of P0879 that remain missing will be std::nth_element, std::sort, and the heap/partial_sort algorithms. Differential Revision: https://reviews.llvm.org/D93443
2021-01-25[libc++] Implement [P0769] "Add shift to algorithm" (shift_left, shift_right)Arthur O'Dwyer1-0/+115
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
2021-01-19[libc++] [P0935] [C++20] Eradicating unnecessarily explicit default ↵Marek Kurdej1-2/+10
constructors from the standard library. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0935r0.html Reviewed By: ldionne, #libc Differential Revision: https://reviews.llvm.org/D91292
2021-01-12[libc++] Add a missing `<_Compare>` template argument.Arthur O'Dwyer1-3/+4
Sometimes `_Compare` is an lvalue reference type, so letting it be deduced is pretty much always wrong. (Well, less efficient than it could be, anyway.) Differential Revision: https://reviews.llvm.org/D93562
2020-12-14[libc++] Consistently replace `::new(__p) T` with `::new ((void*)__p) T`. NFCI.Arthur O'Dwyer1-18/+18
Everywhere, normalize the whitespace to `::new (EXPR) T`. Everywhere, normalize the spelling of the cast to `(void*)EXPR`. Without the cast to `(void*)`, the expression triggers ADL on GCC. (I think this is a GCC bug: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98249) Even if it doesn't trigger ADL, it still seems incorrect to use any argument that's not exactly `(void*)` because that opens the possibility of overload resolution picking a user-defined overload of `operator new`, which would be wrong. Differential Revision: https://reviews.llvm.org/D93153
2020-12-14[libc++] Fix some one-off typos in comments. NFCI.Arthur O'Dwyer1-2/+2
2020-12-14[libc++] s/Birdirectional/Bidirectional/g. NFCI.Arthur O'Dwyer1-14/+14
2020-12-08[libc++] Add _VSTD:: qualifications to ADL-proof <algorithm>.Arthur O'Dwyer1-92/+92
Relevant blog post: https://quuxplusone.github.io/blog/2019/09/26/uglification-doesnt-stop-adl/ Differential Revision: https://reviews.llvm.org/D92776
2020-12-08[libc++] ADL-proof <iterator>. `__convert_to_integral` is not a ↵Arthur O'Dwyer1-7/+7
customization point. The interesting change here is that we no longer consider `__convert_to_integral` an ADL customization point for the user's types. I think the new behavior is defensible. The old behavior had come from D7449, where Marshall explicitly said "people can't define their own [`__convert_to_integral` overloads]." Differential Revision: https://reviews.llvm.org/D92814
2020-12-04[libc++] Update the commented "synopsis" in <algorithm> to match current ↵Arthur O'Dwyer1-50/+50
reality. The synopsis now reflects what's implemented. It does NOT reflect all of what's specified in C++20. The "constexpr in C++20" markings are still missing from these 12 algorithms, because they are still unimplemented by libc++: reverse partition sort nth_element next_permutation prev_permutation push_heap pop_heap make_heap sort_heap partial_sort partial_sort_copy All of the above algorithms were excluded from [P0202]. All of the above algorithms were made constexpr in [P0879] (along with swap_ranges, iter_swap, and rotate — we've already implemented those three). Differential Revision: https://reviews.llvm.org/D92255
2020-12-04[libc++] [P0202] constexpr set_union, set_difference, ↵Arthur O'Dwyer1-17/+17
set_symmetric_difference, merge These had been waiting on the ability to use `std::copy` from constexpr code (which in turn had been waiting on the ability to use `is_constant_evaluated()` to switch between `memmove` and non-`memmove` implementations of `std::copy`). That work landed a while ago, so these algorithms can all be constexpr in C++20 now. Simultaneously, update the tests for the set algorithms. - Use an element type with "equivalent but not identical" values. - The custom-comparator tests now pass something different from `operator<`. - Make the constexpr coverage match the non-constexpr coverage. Differential Revision: https://reviews.llvm.org/D92255
2020-12-04[libc++] fix std::sort(T**, T**)Brett Gutstein1-1/+1
previously, invocations of std::sort(T**, T**) casted the arguments to (size_t *). this breaks sorting on systems for which pointers don't fit in a size_t. change the cast to (uintptr_t *) and add a test. Differential Revision: https://reviews.llvm.org/D92190
2020-12-01[libc++] Consistently replace `std::` qualification with `_VSTD::` or ↵Arthur O'Dwyer1-5/+5
nothing. NFCI. I used a lot of `git grep` to find places where `std::` was being used outside of comments and assert-messages. There were three outcomes: - Qualified function calls, e.g. `std::move` becomes `_VSTD::move`. This is the most common case. - Typenames that don't need qualification, e.g. `std::allocator` becomes `allocator`. Leaving these as `_VSTD::allocator` would also be fine, but I decided that removing the qualification is more consistent with existing practice. - Names that specifically need un-versioned `std::` qualification, or that I wasn't sure about. For example, I didn't touch any code in <atomic>, <math.h>, <new>, or any ext/ or experimental/ headers; and I didn't touch any instances of `std::type_info`. In some deduction guides, we were accidentally using `class Alloc = typename std::allocator<T>`, despite `std::allocator<T>`'s type-ness not being template-dependent. Because `std::allocator` is a qualified name, this did parse as we intended; but what we meant was simply `class Alloc = allocator<T>`. Differential Revision: https://reviews.llvm.org/D92250
2020-11-27[libc++] Replace several uses of 0 by nullptrBruce Mitchener1-17/+17
Differential Revision: https://reviews.llvm.org/D43159
2020-11-24[libc++] Remove _LIBCPP_CONSTEXPR_AFTER_CXX17_WITH_IS_CONSTANT_EVALUATED.Arthur O'Dwyer1-4/+4
Zoe Carver says: "We decided that libc++ only supports C++20 constexpr algorithms when `is_constant_evaluated` is also supported. Here's a link to the discussion." https://reviews.llvm.org/D65721#inline-735682 Remove _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED from tests, too. See Louis's 5911e6a8857f146fb5a8f23af1d768aba25e7c3e if needed to fix bots. I've applied `UNSUPPORTED: clang-8` preemptively to the altered tests; I don't know for sure that this was needed, because no clang-8 buildbots are triggered on pull requests.
2020-09-14[Take 2] [libc++] Make rotate a constexpr.zoecarver1-22/+46
This patch makes `std::rotate` a constexpr. In doing so, this patch also updates the internal `__move` and `__move_backward` funtions to be constexpr. This patch was previously reverted in ed653184ac63 because it was missing some UNSUPPORTED markup for older compilers. This commit adds it. Differential Revision: https://reviews.llvm.org/D65721
2020-09-14Revert "[libc++] Make rotate a constexpr."zoecarver1-46/+22
This reverts commit 1ec02efee9b1d01cde89f31ca9ba6a46b7662ac5.
2020-09-14[libc++] Finish implementing P0202R3Nicholas-Baron1-3/+4
cppreference lists the support for this paper as partial. I found 4 functions which the paper marks as `constexpr`, but did not use the appropriate macro. Differential Revision: https://reviews.llvm.org/D84275
2020-09-14[libc++] Make rotate a constexpr.zoecarver1-22/+46
This patch makes `std::rotate` a constexpr. In doing so, this patch also updates the internal `__move` and `__move_backward` funtions to be constexpr. Reviewed By: ldionne Differential Revision: https://reviews.llvm.org/D65721
2019-11-18Rename __is_foo_iterator traits to reflect their Cpp17 nature.Eric Fiselier1-8/+8
With the upcoming introduction of iterator concepts in ranges, the meaning of "__is_contiguous_iterator" changes drastically. Currently we intend it to mean "does it have this iterator category", but it could now also mean "does it meet the requirements of this concept", and these can be different.
2019-11-07[libc++] Fixed copy/copy_n/copy_backward for compilers that do not support ↵Louis Dionne1-4/+4
is_constant_evaluated. Differential Revision: https://reviews.llvm.org/D69940
2019-11-06[libc++][P0202] Marked algorithms copy/copy_n/copy_if/copy_backward constexprLouis Dionne1-19/+47
Thanks to Michael Park for the patch. Differential Revision: https://reviews.llvm.org/D68837
2019-08-20Add a missing _VSTD:: before a call to merge. Fixes PR43034. Checked the ↵Marshall Clow1-1/+1
rest of 'algorithm' looking for unqualified calls. Didn't find any. llvm-svn: 369463
2019-08-20Fix a couple of unguarded operator, calls in algorithm. Fixes PR#43063. ↵Marshall Clow1-13/+13
Updated all the heap tests to check this. llvm-svn: 369448
2019-08-06[pstl][libc++] Provide uglified header names for interface headersLouis Dionne1-1/+1
For the few (currently four) headers that make up the PSTL's interface to other Standard Libraries, provide a stable uglified header file that can be included by those Standard Libraries. We can then more easily change the internal organization of the PSTL without having to change the integration with Standard Libraries. llvm-svn: 368088
2019-08-05[libc++] Take 2: Integrate the PSTL into libc++Louis Dionne1-0/+4
Summary: This commit allows specifying LIBCXX_ENABLE_PARALLEL_ALGORITHMS when configuring libc++ in CMake. When that option is enabled, libc++ will assume that the PSTL can be found somewhere on the CMake module path, and it will provide the C++17 parallel algorithms based on the PSTL (that is assumed to be available). The commit also adds support for running the PSTL tests as part of the libc++ test suite. The first attempt to commit this failed because it exposed a bug in the tests for modules. Now that this has been fixed, it should be safe to commit this. Reviewers: EricWF Subscribers: mgorny, christof, jkorous, dexonsmith, libcxx-commits, mclow.lists, EricWF Tags: #libc Differential Revision: https://reviews.llvm.org/D60480 llvm-svn: 367903
2019-07-19Revert "[libc++] Integrate the PSTL into libc++"Louis Dionne1-4/+0
This reverts r366593, which caused unforeseen breakage on the build bots. I'm reverting until the problems have been figured out and fixed. llvm-svn: 366603
2019-07-19[libc++] Integrate the PSTL into libc++Louis Dionne1-0/+4
Summary: This commit allows specifying LIBCXX_ENABLE_PARALLEL_ALGORITHMS when configuring libc++ in CMake. When that option is enabled, libc++ will assume that the PSTL can be found somewhere on the CMake module path, and it will provide the C++17 parallel algorithms based on the PSTL (that is assumed to be available). The commit also adds support for running the PSTL tests as part of the libc++ test suite. Reviewers: rodgert, EricWF Subscribers: mgorny, christof, jkorous, dexonsmith, libcxx-commits, mclow.lists, EricWF Tags: #libc Differential Revision: https://reviews.llvm.org/D60480 llvm-svn: 366593
2019-07-12Reorganize the 'bit' header to make most of the facilities available for ↵Marshall Clow1-1/+1
internal use pre-C++20. NFC for external users llvm-svn: 365854
2019-06-21Make move and forward work in C++03.Eric Fiselier1-4/+0
These functions are key to allowing the use of rvalues and variadics in C++03 mode. Everything works the same as in C++11, except for one tangentially related case: struct T { T(T &&) = default; }; In C++11, T has a deleted copy constructor. But in C++03 Clang gives it both a move and a copy constructor. This seems reasonable enough given the extensions it's using. The other changes in this patch were the minimal set required to keep the tests passing after the move/forward change. Most notably the removal of the `__rv<unique_ptr>` hack that was present in an attempt to make unique_ptr move only without language support. llvm-svn: 364063
2019-04-19[libc++] Make __debug_less::operator() constexprThomas Anderson1-0/+1
This is a followup to [1] which added a new `__debug_less::operator()` overload. [2] added `_LIBCPP_CONSTEXPR_AFTER_CXX17` to the original `__debug_less::operator()` between the time of writing [1] and landing it. This change adds `_LIBCPP_CONSTEXPR_AFTER_CXX17` to the new overload too. [1] https://reviews.llvm.org/rL358423 [2] https://reviews.llvm.org/rL358252 Differential Revision: https://reviews.llvm.org/D60724 llvm-svn: 358725
2019-04-15[libc++] Fix build failure with _LIBCPP_DEBUG=0 when iterators return values ↵Thomas Anderson1-0/+9
instead of references There are many STL algorithms (such as lexicographical_compare) that compare values pointed to by iterators like so: __comp(*it1, *it2); When building with `_LIBCPP_DEBUG=0`, comparators are wrapped in `__debug_less` which does some additional validation. But `__debug_less::operator()` takes non-const references, so if the type of `*it1` is int, not int&, then the build will fail. This change adds a `const&` overload for `operator()` to fix the build. Differential Revision: https://reviews.llvm.org/D60592 llvm-svn: 358423
2019-04-12Cleanup how debug comparators are created in <algorithm>Eric Fiselier1-151/+38
Instead of having an `#if` block in every algorithm using a debug comparator, this patch introduces the __comp_ref_type trait that selects __debug_less in debug mode and _Comp& otherwise. This patch should have no observable functionality change. llvm-svn: 358252
generated by cgit v1.1 at 2025-09-30 13:01:28 +0000