aboutsummaryrefslogtreecommitdiff
path: root/libcxx/include/algorithm
AgeCommit message (Collapse)AuthorFilesLines
2023-02-27[libc++] Improves clang-format settings.Mark de Wever1-111/+111
Add a new test based .clang-format file which inherits from the generic one. This moves some test specific formatting rules to the test directory. The main benefit is that headers are sorted, which makes it more likely to catch these errors before creating a review instead of spotting the error in the CI clang-tidy step. Reviewed By: ldionne, philnik, #libc Differential Revision: https://reviews.llvm.org/D144755
2023-02-17[libc++] Granularize <bit> includesNikolas Klauser1-0/+1
Reviewed By: ldionne, #libc Spies: libcxx-commits Differential Revision: https://reviews.llvm.org/D141228
2023-02-13[libc++] Granularize <type_traits> includes in <algorithm>Nikolas Klauser1-1/+1
Reviewed By: Mordante, #libc Spies: libcxx-commits, wenlei Differential Revision: https://reviews.llvm.org/D140673
2023-02-12[libc++][spaceship] Implement `lexicographical_compare_three_way`Adrian Vogelsgesang1-0/+13
The implementation makes use of the freedom added by LWG 3410. We have two variants of this algorithm: * a fast path for random access iterators: This fast path computes the maximum number of loop iterations up-front and does not compare the iterators against their limits on every loop iteration. * A basic implementation for all other iterators: This implementation compares the iterators against their limits in every loop iteration. However, it still takes advantage of the freedom added by LWG 3410 to avoid unnecessary additional iterator comparisons, as originally specified by P1614R2. https://godbolt.org/z/7xbMEen5e shows the benefit of the fast path: The hot loop generated of `lexicographical_compare_three_way3` is more tight than for `lexicographical_compare_three_way1`. The added benchmark illustrates how this leads to a 30% - 50% performance improvement on integer vectors. Implements part of P1614R2 "The Mothership has Landed" Fixes LWG 3410 and LWG 3350 Differential Revision: https://reviews.llvm.org/D131395
2023-01-13Reapply "[libc++][ranges]Refactor `copy{,_backward}` and `move{,_backward}`"varconst1-1/+1
This reverts commit a6e1080b87db8fbe0e1afadd96af5a3c0bd5e279. Fix the conditions when the `memmove` optimization can be applied and refactor them out into a reusable type trait, fix and significantly expand the tests. Differential Revision: https://reviews.llvm.org/D139235
2023-01-08[libc++] Granularize <bit> and remove <__bits>Nikolas Klauser1-1/+0
Reviewed By: Mordante, #libc Spies: libcxx-commits Differential Revision: https://reviews.llvm.org/D141225
2022-11-05[libc++] Granularize <concept> includesNikolas Klauser1-0/+1
Reviewed By: ldionne, #libc Spies: libcxx-commits Differential Revision: https://reviews.llvm.org/D137283
2022-10-02Revert "[libc++][ranges]Refactor `copy{,_backward}` and `move{,_backward}`"Vitaly Buka1-1/+1
Breaks msan, asan https://lab.llvm.org/buildbot/#/builders/5/builds/27904 This reverts commit 005916de58f73aa5c4264c084ba7b0e21040d88f.
2022-10-01[libc++][ranges]Refactor `copy{,_backward}` and `move{,_backward}`Konstantin Varlamov1-1/+1
Instead of using `reverse_iterator`, share the optimization between the 4 algorithms. The key observation here that `memmove` applies to both `copy` and `move` identically, and to their `_backward` versions very similarly. All algorithms now follow the same pattern along the lines of: ``` if constexpr (can_memmove<InIter, OutIter>) { memmove(first, last, out); } else { naive_implementation(first, last, out); } ``` A follow-up will delete `unconstrained_reverse_iterator`. This patch removes duplication and divergence between `std::copy`, `std::move` and `std::move_backward`. It also improves testing: - the test for whether the optimization is used only applied to `std::copy` and, more importantly, was essentially a no-op because it would still pass if the optimization was not used; - there were no tests to make sure the optimization is not used when the effect would be visible. Differential Revision: https://reviews.llvm.org/D130695
2022-09-27[libc++][NFC] Fix some standard-mandated includes commentsNikolas Klauser1-0/+2
Reviewed By: ldionne, #libc Spies: libcxx-commits Differential Revision: https://reviews.llvm.org/D134447
2022-09-25[libc++] Rewrites graph_header_deps.py.Mark de Wever1-1/+1
The new version is a lot simpler and has less option which were not used. This uses the CSV files as generated by D133127 as input data. The current Python script has more features but uses a simple "grep" making the output less accurate: - Conditionally included header are always included. This is an issue since part of our includes are unneeded transitive includes. Based on the language version they may be omitted. The script however always includes them. - Includes in comments are processed as-if they are includes. This is an issue when comments explain how certain data is generated; of course there are digraphs which the script omits. This implementation uses Clang's --trace-includes to generate the includes per header. This means the input of the generation script always has the real list of includes. Libc++ is moving from large monolithic Standard headers to more fine grained headers. For example, algorithm includes every header in `__algorithm`. Adding all these detail headers in the graph makes the output unusable. Instead it only shows the Standard headers. The transitive includes of the detail headers are parsed and "attributed" to the Standard header including them. This gives an accurate include graph without the unneeded clutter. Note that this graph is still big. This changes fixes the cyclic dependency issue with the previous version of the tool so the markers and its documentation is removed. Since the input has no cycles the CI test is removed. Reviewed By: #libc, ldionne Differential Revision: https://reviews.llvm.org/D134188
2022-09-05[libc++] Granularize the rest of memoryNikolas Klauser1-2/+4
Reviewed By: ldionne, #libc Spies: vitalybuka, paulkirth, libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D132790
2022-09-03[NFC][libc++] Moves transitive includes location.Mark de Wever1-9/+9
As discussed in D132284 they will be moved to the end. Reviewed By: #libc, Mordante Differential Revision: https://reviews.llvm.org/D133212
2022-09-02Revert "[libc++] Granularize the rest of memory"Vitaly Buka1-5/+2
Breaks buildbots. This reverts commit 30adaa730c4768b5eb06719c808b2884fcf53cf3.
2022-09-02[libc++] Granularize the rest of memoryNikolas Klauser1-2/+5
Reviewed By: ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D132790
2022-08-31[libc++] Reduces the number of transitive includes.Mark de Wever1-2/+5
This defines a new policy for removal of transitive includes. The goal of the policy it to make it relatively easy to remove headers when needed, but avoid breaking developers using and vendors shipping libc++. The method used is to guard transitive includes based on the C++ language version. For the upcoming C++23 we can remove headers when we want, but for other language versions we try to keep it to a minimum. In this code the transitive include of `<chrono>` is removed since D128577 introduces a header cycle between `<format>` and `<chrono>`. This cycle is indirectly required by the Standard. Our cycle dependency tool basically is a grep based tool, so it needs some hints to ignore cycles. With the input of our transitive include tests we can create a better tool. However that's out of the scope of this patch. Note the flag `_LIBCPP_REMOVE_TRANSITIVE_INCLUDES` remains unchanged. So users can still opt-out of transitives includes entirely. Reviewed By: #libc, ldionne, philnik Differential Revision: https://reviews.llvm.org/D132284
2022-08-04[libc++][ranges] Implement `ranges::is_permutation`Nikolas Klauser1-0/+16
Co-authored-by: Konstantin Varlamov <varconst@apple.com> Differential Revision: https://reviews.llvm.org/D127194
2022-08-04[libc++][NFC] Remove rebase artifactIgor Zhukov1-1/+0
I found it in this commit: https://github.com/llvm/llvm-project/commit/a203acb9dd7227323d6161431225189d49917744 Reviewed By: Mordante Differential Revision: https://reviews.llvm.org/D131163
2022-08-04[libc++][ranges] Implement `ranges::clamp`Nikolas Klauser1-0/+7
Differential Revision: https://reviews.llvm.org/D126193
2022-08-03[libc++][ranges] Implement `ranges::rotate`.Konstantin Varlamov1-0/+8
Also fix `ranges::stable_sort` and `ranges::inplace_merge` to support proxy iterators now that their internal implementations can correctly dispatch `rotate`. Differential Revision: https://reviews.llvm.org/D130758
2022-08-02[libc++][ranges] Implement `ranges::{prev, next}_permutation`.Nikolas Klauser1-0/+33
Co-authored-by: Konstantin Varlamov <varconst@apple.com> Differential Revision: https://reviews.llvm.org/D129859
2022-08-02[libc++][ranges] Implement `ranges::sample`.Konstantin Varlamov1-0/+13
Differential Revision: https://reviews.llvm.org/D130865
2022-08-02[libc++][ranges] Implement `ranges::replace_copy{,_if}`.Nikolas Klauser1-0/+39
Co-authored-by: Konstantin Varlamov <varconst@apple.com> Differential Revision: https://reviews.llvm.org/D129806
2022-08-02[libc++][ranges] Implement `ranges::remove_copy{, _if}`.Nikolas Klauser1-0/+34
Co-authored-by: Hui Xie <hui.xie1990@gmail.com> Differential Revision: https://reviews.llvm.org/D130599
2022-07-30[libc++][ranges] Implement `std::ranges::partial_sort_copy`.Konstantin Varlamov1-0/+20
Differential Revision: https://reviews.llvm.org/D130532
2022-07-29[libc++][ranges] implement `std::ranges::unique{_copy}`Hui Xie1-0/+30
implement `std::ranges::unique` and `std::ranges::unique_copy` Differential Revision: https://reviews.llvm.org/D130404
2022-07-28[libc++][ranges] implement `std::ranges::inplace_merge`Hui Xie1-4/+16
Differential Revision: https://reviews.llvm.org/D130627
2022-07-26[libc++][ranges] Implement `ranges::is_heap{,_until}`.Konstantin Varlamov1-0/+19
Differential Revision: https://reviews.llvm.org/D130547
2022-07-26[libc++][ranges] Implement `ranges::generate{,_n}`.Konstantin Varlamov1-0/+14
Differential Revision: https://reviews.llvm.org/D130552
2022-07-22[libc++][ranges] Implement `ranges::shuffle`.Konstantin Varlamov1-0/+11
Differential Revision: https://reviews.llvm.org/D130321
2022-07-22[libc++][ranges] implement `std::ranges::includes`Hui Xie1-0/+15
implement `std::ranges::includes` and delegate to `std::includes` Differential Revision: https://reviews.llvm.org/D130116
2022-07-22[libc++][ranges] implement `std::ranges::equal_range`Hui Xie1-0/+12
implement `std::ranges::equal_range` which delegates to `std::equal_range` Differential Revision: https://reviews.llvm.org/D129796
2022-07-20[libc++][ranges] Implement `std::ranges::partition_{point,copy}`.Konstantin Varlamov1-0/+30
Reviewed By: #libc, huixie90, ldionne Differential Revision: https://reviews.llvm.org/D130070
2022-07-19[libc++][ranges] Implement `ranges::partial_sort`.varconst1-0/+12
Differential Revision: https://reviews.llvm.org/D128744
2022-07-18[libc++][ranges] Implement `ranges::{,stable_}partition`.Konstantin Varlamov1-0/+24
Differential Revision: https://reviews.llvm.org/D129624
2022-07-14[libc++][ranges] implement `std::ranges::set_union`Hui Xie1-0/+18
[libc++][ranges] implement `std::ranges::set_union` Differential Revision: https://reviews.llvm.org/D129657
2022-07-13[libc++][ranges] implement `std::ranges::set_symmetric_difference`Hui Xie1-0/+21
[libc++][ranges] implement `std::ranges::set_symmetric_difference` Differential Revision: https://reviews.llvm.org/D129520
2022-07-13[libc++] Implement ranges::find_end, ranges::search{, _n}Nikolas Klauser1-0/+46
Reviewed By: var-const, #libc, huixie90 Spies: thakis, h-vetinari, huixie90, libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D124079
2022-07-13Revert "[libc++] Implement ranges::find_end, ranges::search{, _n}"Nikolas Klauser1-46/+0
This reverts commit 76a76518507ccc59ccdad5b83f44dc8c3d9593c7.
2022-07-13[libc++] Implement ranges::find_end, ranges::search{, _n}Nikolas Klauser1-0/+46
Reviewed By: var-const, #libc, huixie90 Spies: h-vetinari, huixie90, libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D124079
2022-07-11[libc++] Implement ranges::{reverse, rotate}_copyNikolas Klauser1-2/+30
Reviewed By: var-const, #libc Spies: huixie90, libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D127211
2022-07-11[libc++][ranges] implement `std::ranges::set_intersection`Hui Xie1-0/+20
implement `std::ranges::set_intersection` by reusing the classic `std::set_intersenction` added unit tests Differential Revision: https://reviews.llvm.org/D129233
2022-07-08[libc++][ranges] Implement modifying heap algorithms:Konstantin Varlamov1-0/+48
- `ranges::make_heap`; - `ranges::push_heap`; - `ranges::pop_heap`; - `ranges::sort_heap`. Differential Revision: https://reviews.llvm.org/D128115
2022-07-08[libc++][ranges] Implement `ranges::nth_element`.Konstantin Varlamov1-0/+12
Differential Revision: https://reviews.llvm.org/D128149
2022-07-08[libcxx][ranges] implement `std::ranges::set_difference`Hui Xie1-0/+19
implement `std::ranges::set_difference` reused classic std::set_difference added unit tests Differential Revision: https://reviews.llvm.org/D128983
2022-07-06[libc++] Implement ranges::remove{, _if}Nikolas Klauser1-0/+22
Reviewed By: var-const, #libc Spies: huixie90, sstefan1, libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D128618
2022-07-04[libc++] Implement `std::ranges::merge`Hui Xie1-0/+18
Implement `std::ranges::merge`. added unit tests Differential Revision: https://reviews.llvm.org/D128611
2022-07-01[libc++][ranges] Implement `ranges::stable_sort`.Konstantin Varlamov1-3/+13
Differential Revision: https://reviews.llvm.org/D127834
2022-06-28[libc++][ranges] Finish LWG issues directly related to the One Ranges Proposal.Konstantin Varlamov1-5/+34
- P1252 ("Ranges Design Cleanup") -- deprecate `move_iterator::operator->` starting from C++20; add range comparisons to the `<functional>` synopsis. This restores `move_iterator::operator->` that was incorrectly deleted in D117656; it's still defined in the latest draft, see http://eel.is/c++draft/depr.move.iter.elem. Note that changes to `*_result` types from 6.1 in the paper are no longer relevant now that these types are aliases; - P2106 ("Alternative wording for GB315 and GB316") -- add a few `*_result` types to the synopsis in `<algorithm>` (some algorithms are not implemented yet and thus some of the proposal still cannot be marked as done); Also mark already done issues as done (or as nothing to do): - P2091 ("Fixing Issues With Range Access CPOs") was already implemented (this patch adds tests for some ill-formed cases); - LWG 3247 ("`ranges::iter_move` should perform ADL-only lookup of `iter_move`") was already implemented; - LWG 3300 ("Non-array ssize overload is underconstrained") doesn't affect the implementation; - LWG 3335 ("Resolve C++20 NB comments US 273 and GB 274") was already implemented; - LWG 3355 ("The memory algorithms should support move-only input iterators introduced by P1207") was already implemented (except for testing). Differential Revision: https://reviews.llvm.org/D126053
2022-06-27[libc++] Re-add transitive includes that had been removed since LLVM 14Louis Dionne1-0/+6
This commit re-adds transitive includes that had been removed by 4cd04d1687f1, c36870c8e79c, a83f4b9cda57, 1458458b558d, 2e2f3158c604, and 489637e66dd3. This should cover almost all the includes that had been removed since LLVM 14 and that would contribute to breaking user code when releasing LLVM 15. It is possible to disable the inclusion of these headers by defining _LIBCPP_REMOVE_TRANSITIVE_INCLUDES. The intent is that vendors will enable that macro and start fixing downstream issues immediately. We can then remove the macro (and the transitive includes) by default in a future release. That way, we will break users only once by removing transitive includes in bulk instead of doing it bit by bit a every release, which is more disruptive for users. Note 1: The set of headers to re-add was found by re-generating the transitive include test on a checkout of release/14.x, which provided the list of all transitive includes we used to provide. Note 2: Several includes of <vector>, <optional>, <array> and <unordered_map> have been added in this commit. These transitive inclusions were added when we implemented boyer_moore_searcher in <functional>. Note 3: This is a best effort patch to try and resolve downstream breakage caused since branching LLVM 14. I wasn't able to perfectly mirror transitive includes in LLVM 14 for a few headers, so I added a release note explaining it. To summarize, adding boyer_moore_searcher created a bunch of circular dependencies, so we have to break backwards compatibility in a few cases. Differential Revision: https://reviews.llvm.org/D128661
generated by cgit v1.1 at 2025-09-29 20:23:00 +0000