summaryrefslogtreecommitdiffstats
path: root/libcxx/include/algorithm
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Last commit included some extra constexpr; remove themMarshall Clow2017-05-251-3/+3
| | | | llvm-svn: 303862
* Make for_each_n only avaliable on C++17Marshall Clow2017-05-251-3/+5
| | | | llvm-svn: 303856
* Add non-parallel version of for_each_n (+tests) from the Parallelism TSMarshall Clow2017-05-251-0/+21
| | | | llvm-svn: 303833
* Don't interfere with the __builtin_foo namespace under MSVCEric Fiselier2017-05-101-22/+103
| | | | | | | | | This patch follows up on feedback received in the review for D32988. Specifically that libc++ should not mess with the __builtin namespace, and that libc++ should use __popcnt to implement __pop_count under MSVC. llvm-svn: 302731
* [libc++] Refactor Windows support headers.Eric Fiselier2017-05-101-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This patch refactors and tries to remove as much of the Windows support headers as possible. This is needed because they currently introduce super weird include cycles and dependencies between STL and libc headers. The changes in this patch are: * remove `support/win32/support.h` completely. The required parts have either been moved into `support/win32/msvc_support.h` (for `MSVC` only helpers not needed by Clang), or directly into their respective `foo.h` headers. * Combine `locale_win32.h` and `locale_mgmt_win32.h` into a single headers, this header should only be included within `__locale` or `locale` to avoid include cycles. * Remove the unneeded parts of `limits_win32.h` and re-name it to `limits_msvc_win32.h` since it's only needed by Clang. I've tested this patch using Clang on Windows, but I suspect it might technically regress our non-existent support for MSVC. Is somebody able to double check? This refactor is needed to support upcoming fixes to `<locale>` on Windows. Reviewers: bcraig, rmaprath, compnerd, EricWF Reviewed By: EricWF Subscribers: majnemer, cfe-commits Differential Revision: https://reviews.llvm.org/D32988 llvm-svn: 302727
* Cleanup _LIBCPP_HAS_NO_<c++11-feature> in algorithmEric Fiselier2017-04-181-9/+9
| | | | llvm-svn: 300625
* Fix C++17 dylib buildEric Fiselier2017-04-031-1/+2
| | | | llvm-svn: 299401
* Remove random_shuffle in C++17. Please use shuffle instead. If you have to, ↵Marshall Clow2017-03-231-2/+4
| | | | | | you cant get it back by defining _LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE before including any libc++ headers. llvm-svn: 298597
* Replace identifiers called `__out` because Windows.h #defines it.Eric Fiselier2017-01-071-11/+11
| | | | | | | | Windows is greedy and it defines the identifier `__out` as a macro. This patch renames all conflicting libc++ identifiers in order to correctly work on Windows. llvm-svn: 291345
* Fix __wrap_iter in debug mode and apply _NOEXCEPT_DEBUG to itEric Fiselier2016-12-281-0/+14
| | | | llvm-svn: 290654
* Fix unused parameters and variablesEric Fiselier2016-12-231-2/+5
| | | | llvm-svn: 290459
* [libcxx] remove unused codeAditya Kumar2016-11-291-70/+2
| | | | | | | | | The macro _LIBCPP_UNROLL_LOOPS isn't used anywhere so the code was dead. Differential Revision: https://reviews.llvm.org/D26991 llvm-svn: 288143
* Fixes for LWG 2598, 2686, 2739, 2742, 2747, and 2759, which were adopted ↵Marshall Clow2016-11-141-1/+1
| | | | | | last week in Issaquah llvm-svn: 286858
* Implement C++17 std::sample.Eric Fiselier2016-08-281-0/+78
| | | | | | | | This patch implements the std::sample function added to C++17 from LFTS. It also removes the std::experimental::sample implementation which now forwards to std::sample. llvm-svn: 279948
* Remove trailing WS [NFC]Aditya Kumar2016-08-251-15/+15
| | | | llvm-svn: 279731
* Implement LCM and GCD for C++17. Same code as for Library Fundamentals TS.Marshall Clow2016-07-261-2/+2
| | | | llvm-svn: 276751
* Add heterogeneous comparator support for __debug_less. Fixes PR17147.Eric Fiselier2016-07-191-1/+15
| | | | llvm-svn: 276059
* Add is_swappable/is_nothrow_swappable traitsEric Fiselier2016-04-211-1/+1
| | | | llvm-svn: 267079
* Remove unused internal routines. No functional changeMarshall Clow2016-04-041-28/+0
| | | | llvm-svn: 265363
* Implement P0253R1: Fixing a design mistake in the searchers interface.Marshall Clow2016-03-081-21/+23
| | | | llvm-svn: 262928
* Implement P0025R0: 'An algorithm to clamp a value between a pair of boundary ↵Marshall Clow2016-03-071-0/+27
| | | | | | values' for C++17 llvm-svn: 262871
* Fix PR#25973 : 'basic_string::assign(InputIt, InputIt) doesn't provide the ↵Marshall Clow2016-01-131-19/+0
| | | | | | strong exception safety guarantee'. This turned out to be a pervasive problem in <string>, which required a fair amount of rework. Add in an optimization for when iterators provide noexcept increment/comparison/assignment/dereference (which covers many of the iterators in libc++). Reviewed as http://reviews.llvm.org/D15862 llvm-svn: 257682
* Make reverse() call iter_swap like the standard says, instead of calling ↵Marshall Clow2015-11-021-2/+2
| | | | | | swap directly. No real change. llvm-svn: 251836
* Fix warnings about pessimizing return moves for C++11 and higherDimitry Andric2015-08-191-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Throughout the libc++ headers, there are a few instances where _VSTD::move() is used to return a local variable. Howard commented in r189039 that these were there "for non-obvious reasons such as to help things limp along in C++03 language mode". However, when compiling these headers with warnings on, and in C++11 or higher mode (like we do in FreeBSD), they cause the following complaints about pessimizing moves: In file included from tests.cpp:26: In file included from tests.hpp:29: /usr/include/c++/v1/map:1368:12: error: moving a local object in a return statement prevents copy elision [-Werror,-Wpessimizing-move] return _VSTD::move(__h); // explicitly moved for C++03 ^ /usr/include/c++/v1/__config:368:15: note: expanded from macro '_VSTD' #define _VSTD std::_LIBCPP_NAMESPACE ^ Attempt to fix this by adding a _LIBCPP_EXPLICIT_MOVE() macro to __config, which gets defined to _VSTD::move for pre-C++11, and to nothing for C++11 and later. I am not completely satisfied with the macro name (I also considered _LIBCPP_COMPAT_MOVE and some other variants), so suggestions are welcome. :) Reviewers: mclow.lists, howard.hinnant, EricWF Subscribers: arthur.j.odwyer, cfe-commits Differential Revision: http://reviews.llvm.org/D11394 llvm-svn: 245421
* Fix PR#24267. use numeric_limits::max instead of ~0 for 'all ones', since ↵Marshall Clow2015-07-301-1/+1
| | | | | | that might give wrong answers on a 1's complement machine. llvm-svn: 243674
* Fix a self-move bug in inplace_merge. Thanks to Ted and Dexon for the report ↵Marshall Clow2015-07-291-8/+32
| | | | | | and the suggested fix. llvm-svn: 243530
* Fix some places where we could call memmove(null,xxx,0) - which is UBMarshall Clow2015-06-021-6/+14
| | | | llvm-svn: 238831
* Fix for LWG Issue 2369: constexpr max(initializer_list) vs max_elementMarshall Clow2015-05-101-33/+18
| | | | llvm-svn: 236952
* Fix PR 22541: When values are equal, minmax should return the rightmost one ↵Marshall Clow2015-02-111-6/+6
| | | | | | in the initializer_list llvm-svn: 228839
* [libcxx] Properly convert the count arguments to the *_n algorithms before use.Eric Fiselier2015-02-101-6/+14
| | | | | | | | | | | | | | | | | Summary: The requirement on the `Size` type passed to *_n algorithms is that it is convertible to an integral type. This means we can't use a variable of type `Size` directly. Instead we need to convert it to an integral type first. The problem is finding out what integral type to convert it to. `__convert_to_integral` figures out what integral type to convert it to and performs the conversion, It also promotes the resulting integral type so that it is at least as big as an integer. `__convert_to_integral` also has a special case for converting enums. This should only work on non-scoped enumerations because it does not apply an explicit conversion from the enum to its underlying type. Reviewers: chandlerc, mclow.lists Reviewed By: mclow.lists Subscribers: cfe-commits Differential Revision: http://reviews.llvm.org/D7449 llvm-svn: 228704
* Get tests running with warnings. Fix warnings in headers and testsEric Fiselier2015-02-051-4/+0
| | | | llvm-svn: 228344
* Fix PR#22433. The algorithm is_partitioned was testing an item in the middle ↵Marshall Clow2015-02-021-0/+3
| | | | | | of the sequence twice. llvm-svn: 227824
* Fix PR#22427. The implementation of inplace_merge had a \'small data set\' ↵Marshall Clow2015-02-021-13/+3
| | | | | | optimization; if either half of the merge was small (i.e, less than 9 items), it did an inplace merge rather than allocating a buffer and doing a faster/smarter merge. However, this failed to satisfy the complexity requirements in the standard. Remove that code. Add tests to check the complexity, and add the same tests for std::merge, since we are in that section of the test suite anyway. llvm-svn: 227811
* Reorder a couple of operations in inplace_merge so that we can meet the ↵Marshall Clow2015-02-021-5/+3
| | | | | | complexity guidelines mandated by the standard. References PR22427 llvm-svn: 227808
* Fix use of operator comma in is_permutation and delete comma operator for ↵Eric Fiselier2014-10-271-1/+1
| | | | | | | | | test iterators. The comma operators in the test iterators give better error messages when they are deleted as opposed to not defined. Delete these functions when possible. llvm-svn: 220715
* [libcxx] Fix use of operator comma where the types can be user definedEric Fiselier2014-10-271-16/+16
| | | | | | | | | | | | | | | | Summary: An evil user might overload operator comma. Use a void cast to make sure any user overload is not selected. Modify all the test iterators to define operator comma. Reviewers: danalbert, mclow.lists Reviewed By: mclow.lists Subscribers: cfe-commits Differential Revision: http://reviews.llvm.org/D5929 llvm-svn: 220706
* Fix for mismatch to handle evil iterators which overload operator commaMarshall Clow2014-09-161-2/+2
| | | | llvm-svn: 217903
* NFC. Move definition of _LIBCPP_ASSERT into __debug header and remove ↵Eric Fiselier2014-08-101-0/+2
| | | | | | | | | | | | | | | | | | external include guards. Things done in this patch: 1. Make __debug include __config since it uses macros from it. 2. The current method of defining _LIBCPP_ASSERT is prone to redefinitions. Move the null _LIBCPP_ASSERT definition into the __debug header to prevent this. 3. Remove external <__debug> include gaurds. <__debug> guards almost all of its contents internally. There is no reason to be doing it externally. This patch should not change any functionality. llvm-svn: 215332
* Fix std::make_heap's worst case time complexityDavid Majnemer2014-07-221-54/+68
| | | | | | | | | | | | | | | | | std::make_heap is currently implemented by iteratively applying a siftup-type algorithm. Since sift-up is O(ln n), this gives std::make_heap a worst case time complexity of O(n ln n). The C++ standard mandates that std::make_heap make no more than O(3n) comparisons, this makes our std::make_heap out of spec. Fix this by introducing an implementation of __sift_down and switch std::make_heap to create the heap using it. This gives std::make_heap linear time complexity in the worst case. This fixes PR20161. llvm-svn: 213615
OpenPOWER on IntegriCloud