summaryrefslogtreecommitdiffstats
path: root/libcxx/include/algorithm
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Make the helper routines in string really be constexpr. This required a bit ↵Marshall Clow2014-06-101-5/+15
| | | | | | of refacoring in algorithm as well. Give them better names while we're at it. All of these are internal rotines; no visible functionality change. llvm-svn: 210561
* Per N3924, mark random_shuffle as deprecated in the synopsis for ↵Marshall Clow2014-03-031-2/+3
| | | | | | <algorithm>. Since we don't actually do anything when a call is deprecated, there is no functionality change. Maybe someday, we'll decide to warn when using a deprecated function. llvm-svn: 202672
* Implement LWG2350: min, max, and minmax should be constexpr.Marshall Clow2014-02-191-55/+114
| | | | llvm-svn: 201697
* G M: Restore the ability for libcxx to compile again on mingw 64.Howard Hinnant2013-09-171-0/+3
| | | | llvm-svn: 190837
* Rename _LIBCPP_DEBUG2 to _LIBCPP_DEBUG.Howard Hinnant2013-08-231-71/+71
| | | | llvm-svn: 189140
* Debug mode for string. This commit also marks the first time libc++ ↵Howard Hinnant2013-08-231-0/+4
| | | | | | debug-mode has found a bug (found one in regex). Had to play with extern templates a bit to get this to work since string is heavily used within libc++.dylib. llvm-svn: 189114
* Zhihao Yuan noted that there were a few unneeded statements. Eliminated ↵Howard Hinnant2013-08-221-1/+1
| | | | | | the unnecessary ones, and commented the ones that are there for non-obvious reasons such as to help things limp along in C++03 language mode. llvm-svn: 189039
* Xing Xue: port to IBM XLC++/AIX.Howard Hinnant2013-08-141-0/+4
| | | | llvm-svn: 188396
* Nico Rieck: this patch series fixes visibility issues on Windows as ↵Howard Hinnant2013-08-121-38/+38
| | | | | | explained in <http://lists.cs.uiuc.edu/pipermail/cfe-dev/2013-August/031214.html>. llvm-svn: 188192
* Nico Rieck: Currently _MSC_VER and _WIN32 are used to guard code which isHoward Hinnant2013-08-011-4/+4
| | | | | | | | | | | | | | | | | | | | | | MSVC-specific, MSVCRT-specific, or Windows-specific. Because Clang can also define _MSC_VER, and MSVCRT is not necessarily the only C runtime, these macros should not be used interchangeably. This patch divides all Windows-related bits into the aforementioned categories. Two new macros are introduced: - _LIBCPP_MSVC: Defined when compiling with MSVC. Detected using _MSC_VER, excluding Clang. - _LIBCPP_MSVCRT: Defined when using the Microsoft CRT. This is the default when _WIN32 is defined. This leaves _WIN32 for code using the Windows API. This also corrects the spelling of _LIBCP_HAS_IS_BASE_OF to _LIBCPP_HAS_IS_BASE_OF. Nico, please prepare a patch for CREDITS.TXT, thanks. llvm-svn: 187593
* Taking another swing at correctly optimizing fill_n.Howard Hinnant2013-08-011-9/+11
| | | | llvm-svn: 187587
* Constrain fill_n -> memset operations to include implicit convertibility to ↵Howard Hinnant2013-08-011-0/+1
| | | | | | unsigned char. This fixes http://llvm.org/bugs/show_bug.cgi?id=16764. Also a drive-by fix on a chrono test suite bug. llvm-svn: 187552
* Fix a bug in std::fill_n where memset would end up being called in cases ↵Anders Carlsson2013-07-221-2/+2
| | | | | | | | when it shouldn’t. Reviewed by Howard. llvm-svn: 186875
* Fix incorrect type usage; nice catch by SebastianMarshall Clow2013-05-101-1/+1
| | | | llvm-svn: 181569
* Implement n3607: 'equal', 'mismatch', and 'is_permutation'Marshall Clow2013-05-091-0/+207
| | | | llvm-svn: 181548
* Somehow search_n never got tested, so of course it had a bug in it. This ↵Howard Hinnant2013-04-041-1/+1
| | | | | | fixes http://llvm.org/bugs/show_bug.cgi?id=15667. llvm-svn: 178764
* Change the 'result_type' from unsigned to 'uint_fast32_t'. This eliminates ↵Marshall Clow2013-02-071-1/+1
| | | | | | truncation warnings on Linux llvm-svn: 174669
* Marcin Zalewski: Change the name of a template parameter in __copy_backward ↵Howard Hinnant2013-02-061-2/+2
| | | | | | from _InputIterator to _BidirectionalIterator to better document the intent of the algorithm. llvm-svn: 174544
* Provide a way to disable use of extern templates in libc++. This is ↵Howard Hinnant2012-11-061-33/+33
| | | | | | intended for the clients of libc++, not the libc++ build. The dylib should always contain the extern templates. To disable the client needs to put -D'_LIBCPP_EXTERN_TEMPLATE(...)=' on the command line. llvm-svn: 167486
OpenPOWER on IntegriCloud