summaryrefslogtreecommitdiff
path: root/libcxx/src/algorithm.cpp
AgeCommit message (Collapse)Author
2025-08-28[libc++] Fix broken precondition of __bit_log2 (#155476)Louis Dionne
In #135303, we started using `__bit_log2` instead of `__log2i` inside `std::sort`. However, `__bit_log2` has a precondition that `__log2i` didn't have, which is that the input is non-zero. While it technically makes no sense to request the logarithm of 0, `__log2i` handled that case and returned 0 without issues. After switching to `__bit_log2`, passing 0 as an input results in an unsigned integer overflow which can trigger `-fsanitize=unsigned-integer-overflow`. While not technically UB in itself, it's clearly not intended either. To fix this, we add an internal assertion to `__bit_log2` which catches the issue in our test suite, and we make sure not to violate `__bit_log2`'s preconditions before we call it from `std::sort`.
2025-05-28Revert "[libc++] Introduce ABI sensitive areas to avoid requiring ↵James Y Knight
_LIBCPP_HIDE_FROM_ABI everywhere (#131156)" (#141756) This reverts commit c861fe8a71e64f3d2108c58147e7375cd9314521. Unfortunately, this use of hidden visibility attributes causes user-defined specializations of standard-library types to also be marked hidden by default, which is incorrect. See discussion thread on #131156. ...and also reverts the follow-up commits: Revert "[libc++] Add explicit ABI annotations to functions from the block runtime declared in <__functional/function.h> (#140592)" This reverts commit 3e4c9dc299c35155934688184319d391b298fff7. Revert "[libc++] Make ABI annotations explicit for windows-specific code (#140507)" This reverts commit f73287e623a6c2e4a3485832bc3e10860cd26eb5. Revert "[libc++][NFC] Replace a few "namespace std" with the correct macro (#140510)" This reverts commit 1d411f27c769a32cb22ce50b9dc4421e34fd40dd.
2025-05-18[libc++] Introduce ABI sensitive areas to avoid requiring ↵Nikolas Klauser
_LIBCPP_HIDE_FROM_ABI everywhere (#131156) This patch introduces `_LIBCPP_{BEGIN,END}_EXPLICIT_ABI_ANNOTATIONS`, which allow us to have implicit annotations for most functions, and just where it's not "hide_from_abi everything" we add explicit annotations. This allows us to drop the `_LIBCPP_HIDE_FROM_ABI` macro from most functions in libc++.
2024-11-06[libc++] Refactor the configuration macros to being always defined (#112094)Nikolas Klauser
This is a follow-up to #89178. This updates the `<__config_site>` macros.
2024-10-30Reapply "[libc++] Simplify the implementation of std::sort a bit (#104902)" ↵Nikolas Klauser
(#114023) This reverts commit ef44e4659878f2. The patch was originally reverted because it was deemed to introduce a performance regression for small inputs, however it also fixed a previous performance regression for larger inputs. So overall, this patch is desirable.
2024-09-20Revert "[libc++] Simplify the implementation of std::sort a bit (#104902)"Louis Dionne
This reverts commit d4ffccfce103b01401b8a9222e373f2d404f8439, which caused a performance regression that needs to be investigated further.
2024-08-27[libc++] Simplify the implementation of std::sort a bit (#104902)Nikolas Klauser
This does a few things to canonicalize the library a bit. Specifically - use `__desugars_to_v` instead of the custom `__is_simple_comparator` - make `__use_branchless_sort` an inline variable - remove the `_maybe_branchless` versions of the `__sortN` functions and overload based on whether we can do branchless sorting instead.
2023-06-06[libc++] Refactor __lessNikolas Klauser
This simplifies the usage of `__less` by making the class not depend on the types compared, but instead the `operator()`. We can't remove the template completely because we explicitly instantiate `std::__sort` with `__less<T>`. Reviewed By: ldionne, #libc Spies: arichardson, EricWF, libcxx-commits, mgrang Differential Revision: https://reviews.llvm.org/D145285
2023-02-01[libc++] Forward ranges::sort to instantiations in the dylibNikolas Klauser
This patch removes `_WrapAlgPolicy` and related functionality. Instead, we explicitly forward to `__sort` now if we have an instantiation inside the dylib. If we don't we just call `__introsort`. Reviewed By: ldionne, #libc Spies: sstefan1, libcxx-commits Differential Revision: https://reviews.llvm.org/D140824
2023-02-01[libc++] Remove explicit instantiations of __insertion_sort_incomplete and ↵Nikolas Klauser
__sort5 from the dylib These instantiations were never visible, because they are only used in `__sort`, which is also explicitly instantiated in the dylib. Reviewed By: ldionne, #libc Spies: #libc_vendors, emaste, nemanjai, libcxx-commits Differential Revision: https://reviews.llvm.org/D142185
2022-06-16[libc++][ranges] Implement `ranges::sort`.Konstantin Varlamov
Differential Revision: https://reviews.llvm.org/D127557
2022-02-15[libc++] Replace `#include ""` with `<>` in libcxx/src/. NFCI.Arthur O'Dwyer
Our best guess is that the two syntaxes should have exactly equivalent effects, so, let's be consistent with what we do in libcxx/include/. I've left `#include "include/x.h"` and `#include "../y.h"` alone because I'm less sure that they're interchangeable, and they aren't inconsistent with libcxx/include/ because libcxx/include/ never does that kind of thing. Also, use the `_LIBCPP_PUSH_MACROS/POP_MACROS` dance for `<__undef_macros>`, even though it's technically unnecessary in a standalone .cpp file, just so we have consistently one way to do it. Differential Revision: https://reviews.llvm.org/D119561
2021-11-17[runtimes][NFC] Remove filenames at the top of the license noticeLouis Dionne
We've stopped doing it in libc++ for a while now because these names would end up rotting as we move things around and copy/paste stuff. This cleans up all the existing files so as to stop the spreading as people copy-paste headers around.
2021-10-12[libc++] Add an option to disable wide character support in libc++Louis Dionne
Some embedded platforms do not wish to support the C library functionality for handling wchar_t because they have no use for it. It makes sense for libc++ to work properly on those platforms, so this commit adds a carve-out of functionality for wchar_t. Unfortunately, unlike some other carve-outs (e.g. random device), this patch touches several parts of the library. However, despite the wide impact of this patch, I still think it is important to support this configuration since it makes it much simpler to port libc++ to some embedded platforms. Differential Revision: https://reviews.llvm.org/D111265
2020-06-30[libc++] Split dylib instantiations for deprecated std::random_shuffle into ↵Louis Dionne
a separate source file That makes it easier to exclude from the build if one wants to build libc++ without support for the deprecated std::random_shuffle.
2019-12-02[libcxx{,abi}] Emit deplibs only when detected by CMakeMichał Górny
This is a followup to 35bc5276ca3. It fixes the dependent libs usage in libcxx and libcxxabi to link pthread and rt libraries only if CMake detects them, rather than based on explicit platform blacklist. Differential Revision: https://reviews.llvm.org/D70888
2019-07-22[runtimes] Don't depend on libpthread on AndroidYi Kong
r362048 added support for ELF dependent libraries, but broke Android build since Android does not have libpthread. Remove the dependency on the Android build. Differential Revision: https://reviews.llvm.org/D65098 llvm-svn: 366734
2019-05-30[runtimes] Check if pragma comment(lib, ...) is supported firstPetr Hosek
This fixes the issue introduced by r362048 where we always use pragma comment(lib, ...) for dependent libraries when the compiler is Clang, but older Clang versions don't support this pragma so we need to check first if it's supported before using it. llvm-svn: 362055
2019-05-30[runtimes] Support ELF dependent libraries featurePetr Hosek
As of r360984, LLD supports dependent libraries feature for ELF. libunwind, libc++abi and libc++ have library dependencies: libdl librt and libpthread, which means that when libunwind and libc++ are being statically linked (using -static-libstdc++ flag), user has to manually specify -ldl -lpthread which is onerous. This change includes the lib pragma to specify the library dependencies directly in the source that uses those libraries. This doesn't make any difference when using linkers that don't support dependent libraries. However, when using LLD that has dependent libraries feature, users no longer have to manually specifying library dependencies when using static linking, linker will pick the library automatically. Differential Revision: https://reviews.llvm.org/D62090 llvm-svn: 362048
2019-01-19Update more file headers across all of the LLVM projects in the monorepoChandler Carruth
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
2016-09-28Mark libc++ internal globals with _LIBCPP_SAFE_STATIC.Eric Fiselier
This patch applies the _LIBCPP_SAFE_STATIC attribute to internal globals, most of which are locking primitives, in order to ensure that they can safely be used during program startup. This patch also fixes an unsafe static init issue with the global locks used to implement atomic operations on shared pointers. Previously the locks were initialized using a dynamically initialized pointer, so it was possible that the pointer was uninitialized. llvm-svn: 282640
2016-05-06Refactor pthread usage of libcxx.Asiri Rathnayake
This patch extracts out all the pthread dependencies of libcxx into the new header __threading_support. The motivation is to make it easy to re-target libcxx into platforms that do not support pthread. Original patch from Fulvio Esposito (fulvio.esposito@outlook.com) - D11781 Applied with tweaks - D19412 Change-Id: I301111f0075de93dd8129416e06babc195aa936b llvm-svn: 268734
2014-09-05Allow libc++ to be built on systems without POSIX threadsJonathan Roelofs
If you're crazy enough to want this sort of thing, then add -D_LIBCPP_HAS_NO_THREADS to your CXXFLAGS and --param=additiona_features=libcpp-has-no-threads to your lit commnad line. http://reviews.llvm.org/D3969 llvm-svn: 217271
2014-08-15Revert "Turn off extern templates for most uses."Justin Bogner
Turning off explicit template instantiation leads to a pretty significant build time and code size cost. We're better off dealing with ABI incompatibility issues that come up in a less heavy handed way. This reverts commit r189610. llvm-svn: 215740
2013-08-29Turn off extern templates for most uses. It is causing more problems than ↵Howard Hinnant
it is worth. The extern templates will still be built into the dylib, mainly for ABI stability purposes. And the client can still turn these back on with a #define if desire. This fixes http://llvm.org/bugs/show_bug.cgi?id=17027. However there's no associated test for the test suite because http://llvm.org/bugs/show_bug.cgi?id=17027 needs mismatched dylib and headers to fire. llvm-svn: 189610
2010-11-16license changeHoward Hinnant
llvm-svn: 119395
2010-05-26Completed [alg.random.shuffle].Howard Hinnant
llvm-svn: 104708
2010-05-11Wiped out some non-ascii characters that snuck into the copyright.Howard Hinnant
llvm-svn: 103516
2010-05-11libcxx initial importHoward Hinnant
llvm-svn: 103490