aboutsummaryrefslogtreecommitdiff
path: root/libcxx/include/algorithm
AgeCommit message (Collapse)AuthorFilesLines
2019-04-03libcxx: Add _LIBCPP_NODISCARD_EXT to 38 more functionsNico Weber1-77/+144
This builds on the work done in r342808 and adds _LIBCPP_NODISCARD_EXT to 37 more functions, namely: adjacent_find, all_of, any_of, binary_search, clamp, count_if, count, equal_range, equal, find_end, find_first_not_of, find_first_of, find_if, find, includes, is_heap_until, is_heap, is_partitioned, is_permutation, is_sorted_until, is_sorted, lexicographical_compare, lower_bound, max_element, max, min_element, min, minmax_element, minmax, mismatch, none_of, remove_if, remove, search_n, search, unique, upper_bound The motivation here is that we noticed that find_if is nodiscard with Visual Studio's standard library, and we deemed that useful (https://crbug.com/948122). https://devblogs.microsoft.com/cppblog/c17-progress-in-vs-2017-15-5-and-15-6/ says "Our criteria for emitting the warning are: discarding the return value is a guaranteed leak [...], discarding the return value is near-guaranteed to be incorrect (e.g. remove()/remove_if()/unique()), or the function is essentially a pure observer (e.g. vector::empty() and std::is_sorted())." so I went through algorithm and tried to apply these criteria. Some of these, like vector::empty() are already nodiscard per C++ standard and didn't need changing. I didn't (yet?) go over std::string::find* methods which should probably have _LIBCPP_NODISCARD_EXT too (but not as part of this change). Differential Revision: https://reviews.llvm.org/D60145 llvm-svn: 357619
2019-03-08Fix PR41017 - Build failure with _LIBCPP_DEBUG=0 and non-const-refEric Fiselier1-5/+5
comparator for std::sort() Our debug comparator assumed that the comparator it wraps would always accepts the values by const ref. This isn't required by the standard. This patch makes our __debug_less comparator forward the constness. llvm-svn: 355752
2019-02-06Add a specialization for '__unwrap_iter' to handle const interators. This ↵Marshall Clow1-0/+12
enables the 'memmove' optimization for std::copy, etc. llvm-svn: 353311
2019-01-24D14686: 'Protect against overloaded comma in random_shuffle and improve ↵Marshall Clow1-2/+2
tests' I had to cut back on the tests with this, because they were not C++03 friendly. Thanks to gribozavr for the patch llvm-svn: 352087
2019-01-19Update more file headers across all of the LLVM projects in the monorepoChandler Carruth1-4/+3
to reflect the new license. These used slightly different spellings that defeated my regular expressions. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351648
2018-12-17[libcxx] Speeding up partition_point/lower_bound/upper_boundLouis Dionne1-4/+30
This is a re-application of r345525, which had been reverted by fear of a regression. Reviewed as https://reviews.llvm.org/D53994. Thanks to Denis Yaroshevskiy for the patch. llvm-svn: 349358
2018-11-21[libcxx] Make sure we can build with -fvisibility=hidden on LinuxLouis Dionne1-0/+1
Summary: This commit marks a few functions as hidden and removes them from the ABI list on Linux such that libc++ can be built with -fvisibility=hidden. The functions marked as hidden by this patch were exported from the shared object only because they were implicitly instantiated function templates. It is safe to stop exporting those symbols from the shared object because nobody could actually depend on them: implicit instantiations are not taken from shared objects. The symbols removed in this commit are basically the same that had been removed in https://reviews.llvm.org/D53868, but that patch had to be reverted because it broke the build (because the functions were not marked as hidden like this patch does). Reviewers: EricWF, mclow.lists Subscribers: christof, jkorous, dexonsmith, libcxx-commits Differential Revision: https://reviews.llvm.org/D54639 llvm-svn: 347395
2018-11-01Revert "Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by ↵Louis Dionne1-30/+4
using unsigned division by 2 when possible." This reverts r345525. I'm reverting because that patch apparently caused a regression on certain platforms (see https://reviews.llvm.org/D53994). Since we don't fully understand the reasons for the regression, I'm reverting until we can provide a fix we understand. llvm-svn: 345893
2018-10-29Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using ↵Eric Fiselier1-4/+30
unsigned division by 2 when possible. Patch by Denis Yaroshevskiy (denis.yaroshevskij@gmail.com) The rational and measurements can be found in the bug description: https://bugs.llvm.org/show_bug.cgi?id=39129 Reviewed as https://reviews.llvm.org/D52697 llvm-svn: 345525
2018-10-26Fix PR39458 _LIBCPP_DEBUG breaks heterogeneous compare.Eric Fiselier1-12/+0
The types/comparators passed to std::upper_bound and std::lower_bound are not required to provided to provide an operator</comp(...) which accepts the arguments in reverse order. Nor are the ranges required to have a strict weak ordering. However, in debug mode we attempted to check the result of a comparison with the arguments reversed, which may not compiler. This patch removes the use of the debug comparator for upper_bound and lower_bound. equal_range et al still use debug comparators when they call __upper_bound and __lower_bound. See llvm.org/PR39458 llvm-svn: 345434
2018-10-08Do the math in uniform_int_distribution::operator() as unsigned to prevent ↵Marshall Clow1-2/+3
UB when overflowing. Also add a UBSAN notification that we're ffine with unsigned overflow. This fixes PR#32617. Thanks to Vincent & Christoph for their help with this issue. llvm-svn: 343996
2018-09-23[libc++] Add deprecated attributes to many deprecated componentsLouis Dionne1-2/+2
Summary: These deprecation warnings are opt-in: they are only enabled when the _LIBCXX_DEPRECATION_WARNINGS macro is defined, which is not the case by default. Note that this is a first step in the right direction, but I wasn't able to get an exhaustive list of all deprecated components per standard, so there's certainly stuff that's missing. The list of components this commit marks as deprecated is: in C++11: - auto_ptr, auto_ptr_ref - binder1st, binder2nd, bind1st(), bind2nd() - pointer_to_unary_function, pointer_to_binary_function, ptr_fun() - mem_fun_t, mem_fun1_t, const_mem_fun_t, const_mem_fun1_t, mem_fun() - mem_fun_ref_t, mem_fun1_ref_t, const_mem_fun_ref_t, const_mem_fun1_ref_t, mem_fun_ref() in C++14: - random_shuffle() in C++17: - unary_negate, binary_negate, not1(), not2() <rdar://problem/18168350> Reviewers: mclow.lists, EricWF Subscribers: christof, dexonsmith, llvm-commits Differential Revision: https://reviews.llvm.org/D48912 llvm-svn: 342843
2018-09-12Implement the infrastructure for feature-test macros. Very few actual ↵Marshall Clow1-0/+1
feature test macros, though. Reviewed as: https://reviews.llvm.org/D51955 llvm-svn: 342073
2018-09-11Fix PR# 38900 - don't call swap inside of random_shuffle when we'd be ↵Marshall Clow1-1/+2
swapping an element with itself llvm-svn: 341975
2018-08-22Add diagnostics for min/max algorithms when a InputIterator is used.Eric Fiselier1-0/+6
These algorithms require a ForwardIterator or better. Ensure we diagnose the contract violation at compile time instead of of silently doing the wrong thing. Further algorithms will be audited in upcoming patches. llvm-svn: 340426
2018-08-17Recommit r339943 - Establish the <bit> header. NFC yet. Reviewed as ↵Marshall Clow1-136/+1
https://reviews.llvm.org/D50815 - with a fix for the sanitizer bots llvm-svn: 340045
2018-08-16Revert "Establish the <bit> header. NFC yet. Reviewed as ↵Vitaly Buka1-1/+136
https://reviews.llvm.org/D50815" Breaks build on sanitizer bots. This reverts commit r339943. llvm-svn: 339971
2018-08-16Establish the <bit> header. NFC yet. Reviewed as https://reviews.llvm.org/D50815Marshall Clow1-136/+1
llvm-svn: 339943
2018-07-14Mark __equal_to 's operations as constexpr.Marshall Clow1-4/+4
llvm-svn: 337087
2018-07-13Make internal class __wrap_iter constexpr when not using libc++'s debugging ↵Marshall Clow1-2/+2
mode. Introduce a new macro _LIBCPP_CONSTEXPR_IF_NODEBUG to mark this. llvm-svn: 337019
2018-02-06Fix misleading indentation; replace a couple of NULLs with nullptr. Resolves ↵Marshall Clow1-2/+2
https://reviews.llvm.org/D42945 ; thanks to Bruce Mitchener for the patch. llvm-svn: 324378
2018-01-26Fix the BinaryPredicate form of std::is_permutation to not rely on operator==Peter Collingbourne1-2/+10
According to [1], forms 2 and 4 of std::is_permutation should use the passed in binary predicate to compare elements. operator== should only be used for forms 1 and 3 which do not take a binary predicate. This CL fixes forms 2 and 4 which relied on operator== for some comparisons. [1] http://en.cppreference.com/w/cpp/algorithm/is_permutation Patch by Thomas Anderson! Differential Revision: https://reviews.llvm.org/D42518 llvm-svn: 323563
2018-01-22Last batch of P0202 constexpr additions: includes/set_intersection/exchangeMarshall Clow1-11/+11
llvm-svn: 323159
2018-01-22Another batch of P0202 constepr algirithms. ↵Marshall Clow1-10/+10
remove/remove_if/remove_copy/remove_copy_if/reverse_copy, and tests (commented out) for rotate_copy, because that depends on std::copy llvm-svn: 323152
2018-01-22Still more P0202 constexpr-ifying. This batch is: ↵Marshall Clow1-11/+12
for_each/for_each_n/lexicographical_compare llvm-svn: 323147
2018-01-20More P0202 constexpr work. This commit adds ↵Marshall Clow1-34/+18
fill/fill_n/generate/generate_n/unique/unique_copy. I removed a specialization of fill_n that recognized when we were dealing with raw pointers and 1 byte trivially-assignable types and did a memset, because the compiler will do that optimization for us. llvm-svn: 323050
2018-01-19More P0202 constexpr-ifying in <algorithm>. This commit handles ↵Marshall Clow1-10/+10
replace/replace_if/replace_copy/replace_copy_if. llvm-svn: 322975
2018-01-19More P0202 constexpr-ifying in <algorithm>. This commit handles 'transform'.Marshall Clow1-4/+4
llvm-svn: 322970
2018-01-16More constexpr algorithms from P0202. search/search_nMarshall Clow1-11/+11
llvm-svn: 322566
2018-01-16More constexpr algorithms from P0202: lower_bound, upper_bound, equal_range, ↵Marshall Clow1-21/+21
binary_search llvm-svn: 322529
2018-01-16More constexpr (re P0202) - equal and mismatchMarshall Clow1-18/+18
llvm-svn: 322527
2018-01-15More constexpr from P0202. count and count_if. Also fix a comment that ↵Marshall Clow1-6/+6
Morwenn noted. llvm-svn: 322506
2018-01-15More P0202 constexpr-ifying. All the find_XXX algorithms in this commit.Marshall Clow1-18/+18
llvm-svn: 322504
2018-01-15partition_point gets the P0202 treatmentMarshall Clow1-2/+2
llvm-svn: 322493
2018-01-15More constexpr algorithms from P0202. any_of/all_of/none_of.Marshall Clow1-6/+6
llvm-svn: 322492
2018-01-15First part of P0202: Adding constexpr modifiers to functions in <algorithm> ↵Marshall Clow1-51/+46
and <utility>. This commit is all the is_XXX algorithms. llvm-svn: 322489
2018-01-08Add the C++17 extensions to std::search. Include the default searcher, but ↵Marshall Clow1-82/+10
not the Boyer-Moore or Boyer-Moore-Horspool searcher (yet). BUT put the BM and BMH tests in place, marked to XFAIL. The other searchers will follow soon llvm-svn: 322019
2017-12-05[libcxx] Fix intrinsics for MSVCShoaib Meenai1-8/+8
The parameter was previously renamed but MSVC path was not updated. Patch by Andrey Khalyavin. Differential Revision: https://reviews.llvm.org/D40774 llvm-svn: 319802
2017-11-14Rename identifiers named `__output`Alexander Richardson1-11/+11
Summary: In the CHERI clang compiler __output and __input are keywords and therefore we can't compile libc++ with our compiler. Reviewers: mclow.lists, EricWF, theraven Reviewed By: EricWF Subscribers: cfe-commits Differential Revision: https://reviews.llvm.org/D39537 llvm-svn: 318144
2017-10-30Fix PR#35119 : set_union misbehaves with move_iterators. Thanks to Denis ↵Marshall Clow1-1/+1
Yaroshevskiy for both the bug report and the fix. llvm-svn: 316914
2017-09-20Revert 313789 because gcc doesn't like itMarshall Clow1-4/+4
llvm-svn: 313803
2017-09-20Mark the __eval methods on independent_bits_engine (and ↵Marshall Clow1-4/+4
__independent_bits_engine) as const, since they make no changes to the object. NFC. llvm-svn: 313789
2017-09-20Fix a bit of UB in __independent_bits_engine. Fixes PR#34663Marshall Clow1-2/+3
llvm-svn: 313776
2017-08-28Fix PR31166: std::inplace_merge seems to be unstable. Thanks to Jan Wilken ↵Marshall Clow1-5/+5
Dörrie for the suggested fix. llvm-svn: 311952
2017-07-14[libc++] Clean up cl warning 4231 disablingShoaib Meenai1-7/+0
Once upon a time, extern templates used to be a Microsoft extension, so cl would warn about their usage, and libc++ suppressed that warning. They've long since been standardized, so the warning is defunct. (libc++ also doesn't currently support building with cl anyway.) llvm-svn: 307997
2017-05-31[Libc++] Use #pragma push_macro/pop_macro to better handle min/max on WindowsEric Fiselier1-2/+6
Summary: This patch improves how libc++ handles min/max macros within the headers. Previously libc++ would undef them and emit a warning. This patch changes libc++ to use `#pragma push_macro` to save the macro before undefining it, and `#pragma pop_macro` to restore the macros and the end of the header. Reviewers: mclow.lists, bcraig, compnerd, EricWF Reviewed By: EricWF Subscribers: cfe-commits, krytarowski Differential Revision: https://reviews.llvm.org/D33080 llvm-svn: 304357
2017-05-31Remove uses of _UI because Windows is evil and tchar.h #define's itEric Fiselier1-2/+2
llvm-svn: 304348
2017-05-25Last commit included some extra constexpr; remove themMarshall Clow1-3/+3
llvm-svn: 303862
2017-05-25Make for_each_n only avaliable on C++17Marshall Clow1-3/+5
llvm-svn: 303856
2017-05-25Add non-parallel version of for_each_n (+tests) from the Parallelism TSMarshall Clow1-0/+21
llvm-svn: 303833
generated by cgit v1.1 at 2025-09-30 17:42:48 +0000