aboutsummaryrefslogtreecommitdiff
path: root/libcxx/include/algorithm
AgeCommit message (Collapse)AuthorFilesLines
2017-05-10Don't interfere with the __builtin_foo namespace under MSVCEric Fiselier1-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
2017-05-10[libc++] Refactor Windows support headers.Eric Fiselier1-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
2017-04-18Cleanup _LIBCPP_HAS_NO_<c++11-feature> in algorithmEric Fiselier1-9/+9
llvm-svn: 300625
2017-04-03Fix C++17 dylib buildEric Fiselier1-1/+2
llvm-svn: 299401
2017-03-23Remove random_shuffle in C++17. Please use shuffle instead. If you have to, ↵Marshall Clow1-2/+4
you cant get it back by defining _LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE before including any libc++ headers. llvm-svn: 298597
2017-01-07Replace identifiers called `__out` because Windows.h #defines it.Eric Fiselier1-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
2016-12-28Fix __wrap_iter in debug mode and apply _NOEXCEPT_DEBUG to itEric Fiselier1-0/+14
llvm-svn: 290654
2016-12-23Fix unused parameters and variablesEric Fiselier1-2/+5
llvm-svn: 290459
2016-11-29[libcxx] remove unused codeAditya Kumar1-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
2016-11-14Fixes for LWG 2598, 2686, 2739, 2742, 2747, and 2759, which were adopted ↵Marshall Clow1-1/+1
last week in Issaquah llvm-svn: 286858
2016-08-28Implement C++17 std::sample.Eric Fiselier1-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
2016-08-25Remove trailing WS [NFC]Aditya Kumar1-15/+15
llvm-svn: 279731
2016-07-26Implement LCM and GCD for C++17. Same code as for Library Fundamentals TS.Marshall Clow1-2/+2
llvm-svn: 276751
2016-07-19Add heterogeneous comparator support for __debug_less. Fixes PR17147.Eric Fiselier1-1/+15
llvm-svn: 276059
2016-04-21Add is_swappable/is_nothrow_swappable traitsEric Fiselier1-1/+1
llvm-svn: 267079
2016-04-04Remove unused internal routines. No functional changeMarshall Clow1-28/+0
llvm-svn: 265363
2016-03-08Implement P0253R1: Fixing a design mistake in the searchers interface.Marshall Clow1-21/+23
llvm-svn: 262928
2016-03-07Implement P0025R0: 'An algorithm to clamp a value between a pair of boundary ↵Marshall Clow1-0/+27
values' for C++17 llvm-svn: 262871
2016-01-13Fix PR#25973 : 'basic_string::assign(InputIt, InputIt) doesn't provide the ↵Marshall Clow1-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
2015-11-02Make reverse() call iter_swap like the standard says, instead of calling ↵Marshall Clow1-2/+2
swap directly. No real change. llvm-svn: 251836
2015-08-19Fix warnings about pessimizing return moves for C++11 and higherDimitry Andric1-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
2015-07-30Fix PR#24267. use numeric_limits::max instead of ~0 for 'all ones', since ↵Marshall Clow1-1/+1
that might give wrong answers on a 1's complement machine. llvm-svn: 243674
2015-07-29Fix a self-move bug in inplace_merge. Thanks to Ted and Dexon for the report ↵Marshall Clow1-8/+32
and the suggested fix. llvm-svn: 243530
2015-06-02Fix some places where we could call memmove(null,xxx,0) - which is UBMarshall Clow1-6/+14
llvm-svn: 238831
2015-05-10Fix for LWG Issue 2369: constexpr max(initializer_list) vs max_elementMarshall Clow1-33/+18
llvm-svn: 236952
2015-02-11Fix PR 22541: When values are equal, minmax should return the rightmost one ↵Marshall Clow1-6/+6
in the initializer_list llvm-svn: 228839
2015-02-10[libcxx] Properly convert the count arguments to the *_n algorithms before use.Eric Fiselier1-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
2015-02-05Get tests running with warnings. Fix warnings in headers and testsEric Fiselier1-4/+0
llvm-svn: 228344
2015-02-02Fix PR#22433. The algorithm is_partitioned was testing an item in the middle ↵Marshall Clow1-0/+3
of the sequence twice. llvm-svn: 227824
2015-02-02Fix PR#22427. The implementation of inplace_merge had a \'small data set\' ↵Marshall Clow1-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
2015-02-02Reorder a couple of operations in inplace_merge so that we can meet the ↵Marshall Clow1-5/+3
complexity guidelines mandated by the standard. References PR22427 llvm-svn: 227808
2014-10-27Fix use of operator comma in is_permutation and delete comma operator for ↵Eric Fiselier1-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
2014-10-27[libcxx] Fix use of operator comma where the types can be user definedEric Fiselier1-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
2014-09-16Fix for mismatch to handle evil iterators which overload operator commaMarshall Clow1-2/+2
llvm-svn: 217903
2014-08-10NFC. Move definition of _LIBCPP_ASSERT into __debug header and remove ↵Eric Fiselier1-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
2014-07-22Fix std::make_heap's worst case time complexityDavid Majnemer1-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
2014-06-10Make the helper routines in string really be constexpr. This required a bit ↵Marshall Clow1-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
2014-03-03Per N3924, mark random_shuffle as deprecated in the synopsis for ↵Marshall Clow1-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
2014-02-19Implement LWG2350: min, max, and minmax should be constexpr.Marshall Clow1-55/+114
llvm-svn: 201697
2013-09-17G M: Restore the ability for libcxx to compile again on mingw 64.Howard Hinnant1-0/+3
llvm-svn: 190837
2013-08-23Rename _LIBCPP_DEBUG2 to _LIBCPP_DEBUG.Howard Hinnant1-71/+71
llvm-svn: 189140
2013-08-23Debug mode for string. This commit also marks the first time libc++ ↵Howard Hinnant1-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
2013-08-22Zhihao Yuan noted that there were a few unneeded statements. Eliminated ↵Howard Hinnant1-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
2013-08-14Xing Xue: port to IBM XLC++/AIX.Howard Hinnant1-0/+4
llvm-svn: 188396
2013-08-12Nico Rieck: this patch series fixes visibility issues on Windows as ↵Howard Hinnant1-38/+38
explained in <http://lists.cs.uiuc.edu/pipermail/cfe-dev/2013-August/031214.html>. llvm-svn: 188192
2013-08-01Nico Rieck: Currently _MSC_VER and _WIN32 are used to guard code which isHoward Hinnant1-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
2013-08-01Taking another swing at correctly optimizing fill_n.Howard Hinnant1-9/+11
llvm-svn: 187587
2013-08-01Constrain fill_n -> memset operations to include implicit convertibility to ↵Howard Hinnant1-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
2013-07-22Fix a bug in std::fill_n where memset would end up being called in cases ↵Anders Carlsson1-2/+2
when it shouldn’t. Reviewed by Howard. llvm-svn: 186875
2013-05-10Fix incorrect type usage; nice catch by SebastianMarshall Clow1-1/+1
llvm-svn: 181569
generated by cgit v1.1 at 2025-10-01 08:03:38 +0000