mirrors/llvm-project
0
0
Fork 0
mirror of https://github.com/llvm/llvm-project.git synced 2025-04-23 21:56:04 +00:00
Code Issues Projects Releases Wiki Activity
llvm-project/libcxx/include/__algorithm/ranges_mismatch.h

Ignoring revisions in .git-blame-ignore-revs. Click here to bypass and see the normal blame view.

99 lines
3.6 KiB
C
Raw Permalink Normal View History

[libc++][ranges] Implement ranges::mismatch Implement `ranges::mismatch` Reviewed By: Quuxplusone, ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D117817
2022-03-08 23:12:35 +01:00
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef _LIBCPP___ALGORITHM_RANGES_MISMATCH_H
#define _LIBCPP___ALGORITHM_RANGES_MISMATCH_H
#include <__algorithm/in_in_result.h>
[libc++] Optimize the two range overload of mismatch (#86853) ``` ----------------------------------------------------------------------------- Benchmark old new ----------------------------------------------------------------------------- bm_mismatch_two_range_overload<char>/1 0.941 ns 1.88 ns bm_mismatch_two_range_overload<char>/2 1.43 ns 2.15 ns bm_mismatch_two_range_overload<char>/3 1.95 ns 2.55 ns bm_mismatch_two_range_overload<char>/4 2.58 ns 2.90 ns bm_mismatch_two_range_overload<char>/5 3.75 ns 3.31 ns bm_mismatch_two_range_overload<char>/6 5.00 ns 3.83 ns bm_mismatch_two_range_overload<char>/7 5.59 ns 4.35 ns bm_mismatch_two_range_overload<char>/8 6.37 ns 4.84 ns bm_mismatch_two_range_overload<char>/16 11.8 ns 6.72 ns bm_mismatch_two_range_overload<char>/64 45.5 ns 2.59 ns bm_mismatch_two_range_overload<char>/512 366 ns 12.6 ns bm_mismatch_two_range_overload<char>/4096 2890 ns 91.6 ns bm_mismatch_two_range_overload<char>/32768 23038 ns 758 ns bm_mismatch_two_range_overload<char>/262144 142813 ns 6573 ns bm_mismatch_two_range_overload<char>/1048576 366679 ns 26710 ns bm_mismatch_two_range_overload<short>/1 0.934 ns 1.88 ns bm_mismatch_two_range_overload<short>/2 1.30 ns 2.58 ns bm_mismatch_two_range_overload<short>/3 1.76 ns 3.28 ns bm_mismatch_two_range_overload<short>/4 2.24 ns 3.98 ns bm_mismatch_two_range_overload<short>/5 2.80 ns 4.92 ns bm_mismatch_two_range_overload<short>/6 3.58 ns 6.01 ns bm_mismatch_two_range_overload<short>/7 4.29 ns 7.03 ns bm_mismatch_two_range_overload<short>/8 4.67 ns 7.39 ns bm_mismatch_two_range_overload<short>/16 9.86 ns 13.1 ns bm_mismatch_two_range_overload<short>/64 38.9 ns 4.55 ns bm_mismatch_two_range_overload<short>/512 348 ns 27.7 ns bm_mismatch_two_range_overload<short>/4096 2881 ns 225 ns bm_mismatch_two_range_overload<short>/32768 23111 ns 1715 ns bm_mismatch_two_range_overload<short>/262144 184846 ns 14416 ns bm_mismatch_two_range_overload<short>/1048576 742885 ns 57264 ns bm_mismatch_two_range_overload<int>/1 0.838 ns 1.19 ns bm_mismatch_two_range_overload<int>/2 1.19 ns 1.65 ns bm_mismatch_two_range_overload<int>/3 1.83 ns 2.06 ns bm_mismatch_two_range_overload<int>/4 2.38 ns 2.42 ns bm_mismatch_two_range_overload<int>/5 3.60 ns 2.47 ns bm_mismatch_two_range_overload<int>/6 3.68 ns 3.05 ns bm_mismatch_two_range_overload<int>/7 4.32 ns 3.36 ns bm_mismatch_two_range_overload<int>/8 5.18 ns 3.58 ns bm_mismatch_two_range_overload<int>/16 10.6 ns 2.84 ns bm_mismatch_two_range_overload<int>/64 39.0 ns 7.78 ns bm_mismatch_two_range_overload<int>/512 247 ns 53.9 ns bm_mismatch_two_range_overload<int>/4096 1927 ns 429 ns bm_mismatch_two_range_overload<int>/32768 15569 ns 3393 ns bm_mismatch_two_range_overload<int>/262144 125413 ns 28504 ns bm_mismatch_two_range_overload<int>/1048576 504549 ns 112729 ns ```
2024-04-01 18:21:51 +02:00
#include <__algorithm/mismatch.h>
#include <__algorithm/unwrap_range.h>
[libc++][ranges] Implement ranges::mismatch Implement `ranges::mismatch` Reviewed By: Quuxplusone, ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D117817
2022-03-08 23:12:35 +01:00
#include <__config>
#include <__functional/identity.h>
#include <__functional/invoke.h>
#include <__functional/ranges_operations.h>
#include <__iterator/concepts.h>
#include <__iterator/indirectly_comparable.h>
#include <__ranges/access.h>
#include <__ranges/concepts.h>
#include <__ranges/dangling.h>
#include <__utility/move.h>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
#endif
[libc++] Fix missing and incorrect push/pop macros (#79204) We recently noticed that the unwrap_iter.h file was pushing macros, but it was pushing them again instead of popping them at the end of the file. This led to libc++ basically swallowing any custom definition of these macros in user code: #define min HELLO #include <algorithm> // min is not HELLO anymore, it's not defined While investigating this issue, I noticed that our push/pop pragmas were actually entirely wrong too. Indeed, instead of pushing macros like `move`, we'd push `move(int, int)` in the pragma, which is not a valid macro name. As a result, we would not actually push macros like `move` -- instead we'd simply undefine them. This led to the following code not working: #define move HELLO #include <algorithm> // move is not HELLO anymore Fixing the pragma push/pop incantations led to a cascade of issues because we use identifiers like `move` in a large number of places, and all of these headers would now need to do the push/pop dance. This patch fixes all these issues. First, it adds a check that we don't swallow important names like min, max, move or refresh as explained above. This is done by augmenting the existing system_reserved_names.gen.py test to also check that the macros are what we expect after including each header. Second, it fixes the push/pop pragmas to work properly and adds missing pragmas to all the files I could detect a failure in via the newly added test. rdar://121365472
2024-01-25 15:48:46 -05:00
_LIBCPP_PUSH_MACROS
#include <__undef_macros>
[libc++][ranges] Implement ranges::mismatch Implement `ranges::mismatch` Reviewed By: Quuxplusone, ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D117817
2022-03-08 23:12:35 +01:00
_LIBCPP_BEGIN_NAMESPACE_STD
[libc++][NFC] Replace _LIBCPP_STD_VER > x with _LIBCPP_STD_VER >= x This change is almost fully mechanical. The only interesting change is in `generate_feature_test_macro_components.py` to generate `_LIBCPP_STD_VER >=` instead. To avoid churn in the git-blame this commit should be added to the `.git-blame-ignore-revs` once committed. Reviewed By: ldionne, var-const, #libc Spies: jloser, libcxx-commits, arichardson, arphaman, wenlei Differential Revision: https://reviews.llvm.org/D143962
2023-02-14 00:56:09 +01:00
#if _LIBCPP_STD_VER >= 20
[libc++][ranges] Implement ranges::mismatch Implement `ranges::mismatch` Reviewed By: Quuxplusone, ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D117817
2022-03-08 23:12:35 +01:00
namespace ranges {
template <class _I1, class _I2>
using mismatch_result = in_in_result<_I1, _I2>;
[libc++] Remove dedicated namespaces for ranges functions (#76543) We originally put implementation-detail function objects into individual namespaces for `std::ranges` without a good reason for doing so. This practice was continued, presumably because there was prior art. Since there's no reason to keep these namespaces, this commit removes them, which will slightly impact binary size. This commit does not apply to CPOs, some of which need additional work.
2024-08-01 05:54:06 -07:00
struct __mismatch {
[libc++][ranges] Implement ranges::mismatch Implement `ranges::mismatch` Reviewed By: Quuxplusone, ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D117817
2022-03-08 23:12:35 +01:00
template <class _I1, class _S1, class _I2, class _S2, class _Pred, class _Proj1, class _Proj2>
static _LIBCPP_HIDE_FROM_ABI constexpr mismatch_result<_I1, _I2>
__go(_I1 __first1, _S1 __last1, _I2 __first2, _S2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
[libc++] Optimize the two range overload of mismatch (#86853) ``` ----------------------------------------------------------------------------- Benchmark old new ----------------------------------------------------------------------------- bm_mismatch_two_range_overload<char>/1 0.941 ns 1.88 ns bm_mismatch_two_range_overload<char>/2 1.43 ns 2.15 ns bm_mismatch_two_range_overload<char>/3 1.95 ns 2.55 ns bm_mismatch_two_range_overload<char>/4 2.58 ns 2.90 ns bm_mismatch_two_range_overload<char>/5 3.75 ns 3.31 ns bm_mismatch_two_range_overload<char>/6 5.00 ns 3.83 ns bm_mismatch_two_range_overload<char>/7 5.59 ns 4.35 ns bm_mismatch_two_range_overload<char>/8 6.37 ns 4.84 ns bm_mismatch_two_range_overload<char>/16 11.8 ns 6.72 ns bm_mismatch_two_range_overload<char>/64 45.5 ns 2.59 ns bm_mismatch_two_range_overload<char>/512 366 ns 12.6 ns bm_mismatch_two_range_overload<char>/4096 2890 ns 91.6 ns bm_mismatch_two_range_overload<char>/32768 23038 ns 758 ns bm_mismatch_two_range_overload<char>/262144 142813 ns 6573 ns bm_mismatch_two_range_overload<char>/1048576 366679 ns 26710 ns bm_mismatch_two_range_overload<short>/1 0.934 ns 1.88 ns bm_mismatch_two_range_overload<short>/2 1.30 ns 2.58 ns bm_mismatch_two_range_overload<short>/3 1.76 ns 3.28 ns bm_mismatch_two_range_overload<short>/4 2.24 ns 3.98 ns bm_mismatch_two_range_overload<short>/5 2.80 ns 4.92 ns bm_mismatch_two_range_overload<short>/6 3.58 ns 6.01 ns bm_mismatch_two_range_overload<short>/7 4.29 ns 7.03 ns bm_mismatch_two_range_overload<short>/8 4.67 ns 7.39 ns bm_mismatch_two_range_overload<short>/16 9.86 ns 13.1 ns bm_mismatch_two_range_overload<short>/64 38.9 ns 4.55 ns bm_mismatch_two_range_overload<short>/512 348 ns 27.7 ns bm_mismatch_two_range_overload<short>/4096 2881 ns 225 ns bm_mismatch_two_range_overload<short>/32768 23111 ns 1715 ns bm_mismatch_two_range_overload<short>/262144 184846 ns 14416 ns bm_mismatch_two_range_overload<short>/1048576 742885 ns 57264 ns bm_mismatch_two_range_overload<int>/1 0.838 ns 1.19 ns bm_mismatch_two_range_overload<int>/2 1.19 ns 1.65 ns bm_mismatch_two_range_overload<int>/3 1.83 ns 2.06 ns bm_mismatch_two_range_overload<int>/4 2.38 ns 2.42 ns bm_mismatch_two_range_overload<int>/5 3.60 ns 2.47 ns bm_mismatch_two_range_overload<int>/6 3.68 ns 3.05 ns bm_mismatch_two_range_overload<int>/7 4.32 ns 3.36 ns bm_mismatch_two_range_overload<int>/8 5.18 ns 3.58 ns bm_mismatch_two_range_overload<int>/16 10.6 ns 2.84 ns bm_mismatch_two_range_overload<int>/64 39.0 ns 7.78 ns bm_mismatch_two_range_overload<int>/512 247 ns 53.9 ns bm_mismatch_two_range_overload<int>/4096 1927 ns 429 ns bm_mismatch_two_range_overload<int>/32768 15569 ns 3393 ns bm_mismatch_two_range_overload<int>/262144 125413 ns 28504 ns bm_mismatch_two_range_overload<int>/1048576 504549 ns 112729 ns ```
2024-04-01 18:21:51 +02:00
if constexpr (forward_iterator<_I1> && forward_iterator<_I2>) {
auto __range1 = std::__unwrap_range(__first1, __last1);
auto __range2 = std::__unwrap_range(__first2, __last2);
auto __res =
std::__mismatch(__range1.first, __range1.second, __range2.first, __range2.second, __pred, __proj1, __proj2);
return {std::__rewrap_range<_S1>(__first1, __res.first), std::__rewrap_range<_S2>(__first2, __res.second)};
} else {
auto __res = std::__mismatch(
std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __pred, __proj1, __proj2);
return {std::move(__res.first), std::move(__res.second)};
[libc++][ranges] Implement ranges::mismatch Implement `ranges::mismatch` Reviewed By: Quuxplusone, ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D117817
2022-03-08 23:12:35 +01:00
}
}
template <input_iterator _I1,
sentinel_for<_I1> _S1,
input_iterator _I2,
sentinel_for<_I2> _S2,
class _Pred = ranges::equal_to,
class _Proj1 = identity,
class _Proj2 = identity>
requires indirectly_comparable<_I1, _I2, _Pred, _Proj1, _Proj2>
[libc++] Remove _LIBCPP_DISABLE_NODISCARD_EXTENSIONS and refactor the tests (#87094) This also adds a few tests that were missing.
2024-04-22 22:13:58 +02:00
[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr mismatch_result<_I1, _I2> operator()(
[libc++][ranges] Implement ranges::mismatch Implement `ranges::mismatch` Reviewed By: Quuxplusone, ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D117817
2022-03-08 23:12:35 +01:00
_I1 __first1, _S1 __last1, _I2 __first2, _S2 __last2, _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const {
return __go(std::move(__first1), __last1, std::move(__first2), __last2, __pred, __proj1, __proj2);
}
template <input_range _R1,
input_range _R2,
class _Pred = ranges::equal_to,
class _Proj1 = identity,
class _Proj2 = identity>
requires indirectly_comparable<iterator_t<_R1>, iterator_t<_R2>, _Pred, _Proj1, _Proj2>
[libc++] Remove _LIBCPP_DISABLE_NODISCARD_EXTENSIONS and refactor the tests (#87094) This also adds a few tests that were missing.
2024-04-22 22:13:58 +02:00
[[nodiscard]]
[libc++] Optimize the two range overload of mismatch (#86853) ``` ----------------------------------------------------------------------------- Benchmark old new ----------------------------------------------------------------------------- bm_mismatch_two_range_overload<char>/1 0.941 ns 1.88 ns bm_mismatch_two_range_overload<char>/2 1.43 ns 2.15 ns bm_mismatch_two_range_overload<char>/3 1.95 ns 2.55 ns bm_mismatch_two_range_overload<char>/4 2.58 ns 2.90 ns bm_mismatch_two_range_overload<char>/5 3.75 ns 3.31 ns bm_mismatch_two_range_overload<char>/6 5.00 ns 3.83 ns bm_mismatch_two_range_overload<char>/7 5.59 ns 4.35 ns bm_mismatch_two_range_overload<char>/8 6.37 ns 4.84 ns bm_mismatch_two_range_overload<char>/16 11.8 ns 6.72 ns bm_mismatch_two_range_overload<char>/64 45.5 ns 2.59 ns bm_mismatch_two_range_overload<char>/512 366 ns 12.6 ns bm_mismatch_two_range_overload<char>/4096 2890 ns 91.6 ns bm_mismatch_two_range_overload<char>/32768 23038 ns 758 ns bm_mismatch_two_range_overload<char>/262144 142813 ns 6573 ns bm_mismatch_two_range_overload<char>/1048576 366679 ns 26710 ns bm_mismatch_two_range_overload<short>/1 0.934 ns 1.88 ns bm_mismatch_two_range_overload<short>/2 1.30 ns 2.58 ns bm_mismatch_two_range_overload<short>/3 1.76 ns 3.28 ns bm_mismatch_two_range_overload<short>/4 2.24 ns 3.98 ns bm_mismatch_two_range_overload<short>/5 2.80 ns 4.92 ns bm_mismatch_two_range_overload<short>/6 3.58 ns 6.01 ns bm_mismatch_two_range_overload<short>/7 4.29 ns 7.03 ns bm_mismatch_two_range_overload<short>/8 4.67 ns 7.39 ns bm_mismatch_two_range_overload<short>/16 9.86 ns 13.1 ns bm_mismatch_two_range_overload<short>/64 38.9 ns 4.55 ns bm_mismatch_two_range_overload<short>/512 348 ns 27.7 ns bm_mismatch_two_range_overload<short>/4096 2881 ns 225 ns bm_mismatch_two_range_overload<short>/32768 23111 ns 1715 ns bm_mismatch_two_range_overload<short>/262144 184846 ns 14416 ns bm_mismatch_two_range_overload<short>/1048576 742885 ns 57264 ns bm_mismatch_two_range_overload<int>/1 0.838 ns 1.19 ns bm_mismatch_two_range_overload<int>/2 1.19 ns 1.65 ns bm_mismatch_two_range_overload<int>/3 1.83 ns 2.06 ns bm_mismatch_two_range_overload<int>/4 2.38 ns 2.42 ns bm_mismatch_two_range_overload<int>/5 3.60 ns 2.47 ns bm_mismatch_two_range_overload<int>/6 3.68 ns 3.05 ns bm_mismatch_two_range_overload<int>/7 4.32 ns 3.36 ns bm_mismatch_two_range_overload<int>/8 5.18 ns 3.58 ns bm_mismatch_two_range_overload<int>/16 10.6 ns 2.84 ns bm_mismatch_two_range_overload<int>/64 39.0 ns 7.78 ns bm_mismatch_two_range_overload<int>/512 247 ns 53.9 ns bm_mismatch_two_range_overload<int>/4096 1927 ns 429 ns bm_mismatch_two_range_overload<int>/32768 15569 ns 3393 ns bm_mismatch_two_range_overload<int>/262144 125413 ns 28504 ns bm_mismatch_two_range_overload<int>/1048576 504549 ns 112729 ns ```
2024-04-01 18:21:51 +02:00
_LIBCPP_HIDE_FROM_ABI constexpr mismatch_result<borrowed_iterator_t<_R1>, borrowed_iterator_t<_R2>>
[libc++][ranges] Implement ranges::mismatch Implement `ranges::mismatch` Reviewed By: Quuxplusone, ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D117817
2022-03-08 23:12:35 +01:00
operator()(_R1&& __r1, _R2&& __r2, _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
return __go(
ranges::begin(__r1), ranges::end(__r1), ranges::begin(__r2), ranges::end(__r2), __pred, __proj1, __proj2);
}
};
inline namespace __cpo {
[libc++] Remove dedicated namespaces for ranges functions (#76543) We originally put implementation-detail function objects into individual namespaces for `std::ranges` without a good reason for doing so. This practice was continued, presumably because there was prior art. Since there's no reason to keep these namespaces, this commit removes them, which will slightly impact binary size. This commit does not apply to CPOs, some of which need additional work.
2024-08-01 05:54:06 -07:00
constexpr inline auto mismatch = __mismatch{};
[libc++][ranges] Implement ranges::mismatch Implement `ranges::mismatch` Reviewed By: Quuxplusone, ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D117817
2022-03-08 23:12:35 +01:00
} // namespace __cpo
} // namespace ranges
[libc++][NFC] Replace _LIBCPP_STD_VER > x with _LIBCPP_STD_VER >= x This change is almost fully mechanical. The only interesting change is in `generate_feature_test_macro_components.py` to generate `_LIBCPP_STD_VER >=` instead. To avoid churn in the git-blame this commit should be added to the `.git-blame-ignore-revs` once committed. Reviewed By: ldionne, var-const, #libc Spies: jloser, libcxx-commits, arichardson, arphaman, wenlei Differential Revision: https://reviews.llvm.org/D143962
2023-02-14 00:56:09 +01:00
#endif // _LIBCPP_STD_VER >= 20
[libc++][ranges] Implement ranges::mismatch Implement `ranges::mismatch` Reviewed By: Quuxplusone, ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D117817
2022-03-08 23:12:35 +01:00
_LIBCPP_END_NAMESPACE_STD
[libc++] Fix missing and incorrect push/pop macros (#79204) We recently noticed that the unwrap_iter.h file was pushing macros, but it was pushing them again instead of popping them at the end of the file. This led to libc++ basically swallowing any custom definition of these macros in user code: #define min HELLO #include <algorithm> // min is not HELLO anymore, it's not defined While investigating this issue, I noticed that our push/pop pragmas were actually entirely wrong too. Indeed, instead of pushing macros like `move`, we'd push `move(int, int)` in the pragma, which is not a valid macro name. As a result, we would not actually push macros like `move` -- instead we'd simply undefine them. This led to the following code not working: #define move HELLO #include <algorithm> // move is not HELLO anymore Fixing the pragma push/pop incantations led to a cascade of issues because we use identifiers like `move` in a large number of places, and all of these headers would now need to do the push/pop dance. This patch fixes all these issues. First, it adds a check that we don't swallow important names like min, max, move or refresh as explained above. This is done by augmenting the existing system_reserved_names.gen.py test to also check that the macros are what we expect after including each header. Second, it fixes the push/pop pragmas to work properly and adds missing pragmas to all the files I could detect a failure in via the newly added test. rdar://121365472
2024-01-25 15:48:46 -05:00
_LIBCPP_POP_MACROS
[libc++][ranges] Implement ranges::mismatch Implement `ranges::mismatch` Reviewed By: Quuxplusone, ldionne, #libc Spies: libcxx-commits, mgorny Differential Revision: https://reviews.llvm.org/D117817
2022-03-08 23:12:35 +01:00
#endif // _LIBCPP___ALGORITHM_RANGES_MISMATCH_H
Reference in New Issue Copy Permalink