summaryrefslogtreecommitdiffstats
path: root/libcxx/include/algorithm
Commit message (Collapse)AuthorAgeFilesLines
* [libc++] Make __debug_less::operator() constexprThomas Anderson2019-04-191-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
* [libc++] Fix build failure with _LIBCPP_DEBUG=0 when iterators return values ↵Thomas Anderson2019-04-151-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
* Cleanup how debug comparators are created in <algorithm>Eric Fiselier2019-04-121-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
* libcxx: Add _LIBCPP_NODISCARD_EXT to 38 more functionsNico Weber2019-04-031-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
* Fix PR41017 - Build failure with _LIBCPP_DEBUG=0 and non-const-refEric Fiselier2019-03-081-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
* Add a specialization for '__unwrap_iter' to handle const interators. This ↵Marshall Clow2019-02-061-0/+12
| | | | | | enables the 'memmove' optimization for std::copy, etc. llvm-svn: 353311
* D14686: 'Protect against overloaded comma in random_shuffle and improve ↵Marshall Clow2019-01-241-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
* Update more file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-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
* [libcxx] Speeding up partition_point/lower_bound/upper_boundLouis Dionne2018-12-171-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
* [libcxx] Make sure we can build with -fvisibility=hidden on LinuxLouis Dionne2018-11-211-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
* Revert "Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by ↵Louis Dionne2018-11-011-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
* Bug 39129: Speeding up partition_point/lower_bound/upper_bound/ by using ↵Eric Fiselier2018-10-291-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
* Fix PR39458 _LIBCPP_DEBUG breaks heterogeneous compare.Eric Fiselier2018-10-261-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
* Do the math in uniform_int_distribution::operator() as unsigned to prevent ↵Marshall Clow2018-10-081-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
* [libc++] Add deprecated attributes to many deprecated componentsLouis Dionne2018-09-231-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
* Implement the infrastructure for feature-test macros. Very few actual ↵Marshall Clow2018-09-121-0/+1
| | | | | | feature test macros, though. Reviewed as: https://reviews.llvm.org/D51955 llvm-svn: 342073
* Fix PR# 38900 - don't call swap inside of random_shuffle when we'd be ↵Marshall Clow2018-09-111-1/+2
| | | | | | swapping an element with itself llvm-svn: 341975
* Add diagnostics for min/max algorithms when a InputIterator is used.Eric Fiselier2018-08-221-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
* Recommit r339943 - Establish the <bit> header. NFC yet. Reviewed as ↵Marshall Clow2018-08-171-136/+1
| | | | | | https://reviews.llvm.org/D50815 - with a fix for the sanitizer bots llvm-svn: 340045
* Revert "Establish the <bit> header. NFC yet. Reviewed as ↵Vitaly Buka2018-08-161-1/+136
| | | | | | | | | | https://reviews.llvm.org/D50815" Breaks build on sanitizer bots. This reverts commit r339943. llvm-svn: 339971
* Establish the <bit> header. NFC yet. Reviewed as https://reviews.llvm.org/D50815Marshall Clow2018-08-161-136/+1
| | | | llvm-svn: 339943
* Mark __equal_to 's operations as constexpr.Marshall Clow2018-07-141-4/+4
| | | | llvm-svn: 337087
* Make internal class __wrap_iter constexpr when not using libc++'s debugging ↵Marshall Clow2018-07-131-2/+2
| | | | | | mode. Introduce a new macro _LIBCPP_CONSTEXPR_IF_NODEBUG to mark this. llvm-svn: 337019
* Fix misleading indentation; replace a couple of NULLs with nullptr. Resolves ↵Marshall Clow2018-02-061-2/+2
| | | | | | https://reviews.llvm.org/D42945 ; thanks to Bruce Mitchener for the patch. llvm-svn: 324378
* Fix the BinaryPredicate form of std::is_permutation to not rely on operator==Peter Collingbourne2018-01-261-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
* Last batch of P0202 constexpr additions: includes/set_intersection/exchangeMarshall Clow2018-01-221-11/+11
| | | | llvm-svn: 323159
* Another batch of P0202 constepr algirithms. ↵Marshall Clow2018-01-221-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
* Still more P0202 constexpr-ifying. This batch is: ↵Marshall Clow2018-01-221-11/+12
| | | | | | for_each/for_each_n/lexicographical_compare llvm-svn: 323147
* More P0202 constexpr work. This commit adds ↵Marshall Clow2018-01-201-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
* More P0202 constexpr-ifying in <algorithm>. This commit handles ↵Marshall Clow2018-01-191-10/+10
| | | | | | replace/replace_if/replace_copy/replace_copy_if. llvm-svn: 322975
* More P0202 constexpr-ifying in <algorithm>. This commit handles 'transform'.Marshall Clow2018-01-191-4/+4
| | | | llvm-svn: 322970
* More constexpr algorithms from P0202. search/search_nMarshall Clow2018-01-161-11/+11
| | | | llvm-svn: 322566
* More constexpr algorithms from P0202: lower_bound, upper_bound, equal_range, ↵Marshall Clow2018-01-161-21/+21
| | | | | | binary_search llvm-svn: 322529
* More constexpr (re P0202) - equal and mismatchMarshall Clow2018-01-161-18/+18
| | | | llvm-svn: 322527
* More constexpr from P0202. count and count_if. Also fix a comment that ↵Marshall Clow2018-01-151-6/+6
| | | | | | Morwenn noted. llvm-svn: 322506
* More P0202 constexpr-ifying. All the find_XXX algorithms in this commit.Marshall Clow2018-01-151-18/+18
| | | | llvm-svn: 322504
* partition_point gets the P0202 treatmentMarshall Clow2018-01-151-2/+2
| | | | llvm-svn: 322493
* More constexpr algorithms from P0202. any_of/all_of/none_of.Marshall Clow2018-01-151-6/+6
| | | | llvm-svn: 322492
* First part of P0202: Adding constexpr modifiers to functions in <algorithm> ↵Marshall Clow2018-01-151-51/+46
| | | | | | and <utility>. This commit is all the is_XXX algorithms. llvm-svn: 322489
* Add the C++17 extensions to std::search. Include the default searcher, but ↵Marshall Clow2018-01-081-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
* [libcxx] Fix intrinsics for MSVCShoaib Meenai2017-12-051-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
* Rename identifiers named `__output`Alexander Richardson2017-11-141-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
* Fix PR#35119 : set_union misbehaves with move_iterators. Thanks to Denis ↵Marshall Clow2017-10-301-1/+1
| | | | | | Yaroshevskiy for both the bug report and the fix. llvm-svn: 316914
* Revert 313789 because gcc doesn't like itMarshall Clow2017-09-201-4/+4
| | | | llvm-svn: 313803
* Mark the __eval methods on independent_bits_engine (and ↵Marshall Clow2017-09-201-4/+4
| | | | | | __independent_bits_engine) as const, since they make no changes to the object. NFC. llvm-svn: 313789
* Fix a bit of UB in __independent_bits_engine. Fixes PR#34663Marshall Clow2017-09-201-2/+3
| | | | llvm-svn: 313776
* Fix PR31166: std::inplace_merge seems to be unstable. Thanks to Jan Wilken ↵Marshall Clow2017-08-281-5/+5
| | | | | | Dörrie for the suggested fix. llvm-svn: 311952
* [libc++] Clean up cl warning 4231 disablingShoaib Meenai2017-07-141-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
* [Libc++] Use #pragma push_macro/pop_macro to better handle min/max on WindowsEric Fiselier2017-05-311-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
* Remove uses of _UI because Windows is evil and tchar.h #define's itEric Fiselier2017-05-311-2/+2
| | | | llvm-svn: 304348
OpenPOWER on IntegriCloud