summaryrefslogtreecommitdiffstats
path: root/libcxx/include/algorithm
Commit message (Collapse)AuthorAgeFilesLines
* Rename __is_foo_iterator traits to reflect their Cpp17 nature.Eric Fiselier2019-11-181-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.
* [libc++] Fixed copy/copy_n/copy_backward for compilers that do not support ↵Louis Dionne2019-11-071-4/+4
| | | | | | is_constant_evaluated. Differential Revision: https://reviews.llvm.org/D69940
* [libc++][P0202] Marked algorithms copy/copy_n/copy_if/copy_backward constexprLouis Dionne2019-11-061-19/+47
| | | | | | Thanks to Michael Park for the patch. Differential Revision: https://reviews.llvm.org/D68837
* Add a missing _VSTD:: before a call to merge. Fixes PR43034. Checked the ↵Marshall Clow2019-08-201-1/+1
| | | | | | rest of 'algorithm' looking for unqualified calls. Didn't find any. llvm-svn: 369463
* Fix a couple of unguarded operator, calls in algorithm. Fixes PR#43063. ↵Marshall Clow2019-08-201-13/+13
| | | | | | Updated all the heap tests to check this. llvm-svn: 369448
* [pstl][libc++] Provide uglified header names for interface headersLouis Dionne2019-08-061-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
* [libc++] Take 2: Integrate the PSTL into libc++Louis Dionne2019-08-051-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
* Revert "[libc++] Integrate the PSTL into libc++"Louis Dionne2019-07-191-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
* [libc++] Integrate the PSTL into libc++Louis Dionne2019-07-191-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
* Reorganize the 'bit' header to make most of the facilities available for ↵Marshall Clow2019-07-121-1/+1
| | | | | | internal use pre-C++20. NFC for external users llvm-svn: 365854
* Make move and forward work in C++03.Eric Fiselier2019-06-211-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
* [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
OpenPOWER on IntegriCloud