diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -44,6 +44,7 @@ -DCMAKE_INSTALL_PREFIX:PATH= -DCMAKE_CXX_FLAGS:STRING=${BENCHMARK_LIBCXX_COMPILE_FLAGS} -DBENCHMARK_USE_LIBCXX:BOOL=ON + -DHAVE_POSIX_REGEX:BOOL=ON -DBENCHMARK_ENABLE_TESTING:BOOL=OFF) #============================================================================== @@ -158,6 +159,7 @@ #============================================================================== set(BENCHMARK_TESTS algorithms.partition_point.bench.cpp + algorithms/equal.bench.cpp algorithms/lower_bound.bench.cpp algorithms/make_heap.bench.cpp algorithms/make_heap_then_sort_heap.bench.cpp diff --git a/libcxx/benchmarks/algorithms/equal.bench.cpp b/libcxx/benchmarks/algorithms/equal.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/equal.bench.cpp @@ -0,0 +1,20 @@ +#include +#include +#include + +constexpr auto max_val = 1 << 16; + +static void bm_equal(benchmark::State& state) +{ + std::vector vec1(state.range(), '1'); + std::vector vec2(state.range(), '1'); + for (auto _ : state) + { + benchmark::DoNotOptimize(vec1); + benchmark::DoNotOptimize(vec2); + benchmark::DoNotOptimize(std::equal(vec1.begin(), vec1.end(), vec2.begin())); + } +} +BENCHMARK(bm_equal)->Range(1, max_val); + +BENCHMARK_MAIN(); diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -579,6 +579,7 @@ __type_traits/is_callable.h __type_traits/is_char_like_type.h __type_traits/is_class.h + __type_traits/is_comparable.h __type_traits/is_compound.h __type_traits/is_const.h __type_traits/is_constant_evaluated.h diff --git a/libcxx/include/__algorithm/equal.h b/libcxx/include/__algorithm/equal.h --- a/libcxx/include/__algorithm/equal.h +++ b/libcxx/include/__algorithm/equal.h @@ -11,9 +11,15 @@ #define _LIBCPP___ALGORITHM_EQUAL_H #include <__algorithm/comp.h> +#include <__algorithm/unwrap_iter.h> #include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/operations.h> +#include <__functional/ranges_operations.h> #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,15 +27,41 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template +struct __is_equal_to : false_type {}; + +template <> +struct __is_equal_to<__equal_to> : true_type {}; + +template +struct __is_equal_to> : true_type {}; + +#if _LIBCPP_STD_VER >= 20 +template <> +struct __is_equal_to : true_type {}; +#endif + template _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool -equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { +__equal_iter_impl(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { for (; __first1 != __last1; ++__first1, (void)++__first2) if (!__pred(*__first1, *__first2)) return false; return true; } +template ::value, int> = 0> +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool +__equal_iter_impl(_Tp* __first1, _Tp* __last1, _Up* __first2, _BinaryPredicate __pred) { + return std::memcmp(__first1, __first2, __last1 - __first1); +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool +equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { + return std::__equal_iter_impl(std::__unwrap_iter(__first1), std::__unwrap_iter(__last1), std::__unwrap_iter(__first2), __pred); +} + template _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) { @@ -47,6 +79,30 @@ return __first1 == __last1 && __first2 == __last2; } +template +_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_impl( + _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __comp, _Proj1& __proj1, _Proj2& __proj2) { + while (__first1 != __last1 && __first2 != __last2) { + if (!std::__invoke(__comp, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) + return false; + ++__first1; + ++__first2; + } + return __first1 == __last1 && __first2 == __last2; +} + +template < + class _Tp, + class _Up, + class _Pred, + class _Proj1, + class _Proj2, + __enable_if_t<__is_equal_to<_Pred>::value && __is_identity<_Proj1>::value && __is_identity<_Proj2>::value, int> = 0> +_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_impl( + _Tp* __first1, _Tp* __last1, _Up* __first2, _Up* __last2, _Pred& __comp, _Proj1& __proj1, _Proj2& __proj2) { + return std::memcmp(__first1, __first2, __last1 - __first1) == 0; +} + template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, @@ -54,8 +110,15 @@ random_access_iterator_tag) { if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) return false; - return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2, - _BinaryPredicate&>(__first1, __last1, __first2, __pred); + __identity __proj; + return std::__equal_impl( + std::__unwrap_iter(__first1), + std::__unwrap_iter(__last1), + std::__unwrap_iter(__first2), + std::__unwrap_iter(__last2), + __pred, + __proj, + __proj); } template diff --git a/libcxx/include/__functional/identity.h b/libcxx/include/__functional/identity.h --- a/libcxx/include/__functional/identity.h +++ b/libcxx/include/__functional/identity.h @@ -19,6 +19,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template +struct __is_identity : false_type {}; + struct __identity { template _LIBCPP_NODISCARD _LIBCPP_CONSTEXPR _Tp&& operator()(_Tp&& __t) const _NOEXCEPT { @@ -28,6 +31,9 @@ using is_transparent = void; }; +template <> +struct __is_identity<__identity> : true_type {}; + #if _LIBCPP_STD_VER > 17 struct identity { @@ -39,6 +45,10 @@ using is_transparent = void; }; + +template <> +struct __is_identity : true_type {}; + #endif // _LIBCPP_STD_VER > 17 _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__memory/unique_ptr.h b/libcxx/include/__memory/unique_ptr.h --- a/libcxx/include/__memory/unique_ptr.h +++ b/libcxx/include/__memory/unique_ptr.h @@ -19,6 +19,7 @@ #include <__memory/allocator_traits.h> // __pointer #include <__memory/auto_ptr.h> #include <__memory/compressed_pair.h> +#include <__type_traits/is_comparable.h> #include <__utility/forward.h> #include <__utility/move.h> #include @@ -493,6 +494,10 @@ } }; +template +struct __is_trivially_comparable, unique_ptr<_Up, _Deleter2>> + : __is_trivially_comparable<_Tp*, _Up*> {}; + template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX23 typename enable_if< __is_swappable<_Dp>::value, void >::type diff --git a/libcxx/include/__type_traits/is_comparable.h b/libcxx/include/__type_traits/is_comparable.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__type_traits/is_comparable.h @@ -0,0 +1,39 @@ +//===----------------------------------------------------------------------===// +// +// 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___TYPE_TRAITS_IS_COMPARABLE_H +#define _LIBCPP___TYPE_TRAITS_IS_COMPARABLE_H + +#include <__config> +#include <__type_traits/integral_constant.h> +#include <__type_traits/is_integral.h> +#include <__type_traits/is_same.h> +#include <__type_traits/remove_cv.h> +#include <__type_traits/void_t.h> +#include <__utility/declval.h> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +struct __is_comparable : false_type {}; + +template +struct __is_comparable<_Tp, _Up, __void_t() == std::declval<_Up>())>> : true_type {}; + +template +struct __is_trivially_comparable + : integral_constant::value && is_integral<_Tp>::value && + is_same<__remove_cv_t<_Tp>, __remove_cv_t<_Up>>::value> {}; + +template +struct __is_trivially_comparable<_Tp*, _Up*> : __is_comparable<_Tp*, _Up*> {}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___TYPE_TRAITS_IS_COMPARABLE_H diff --git a/libcxx/include/__utility/pair.h b/libcxx/include/__utility/pair.h --- a/libcxx/include/__utility/pair.h +++ b/libcxx/include/__utility/pair.h @@ -19,6 +19,8 @@ #include <__tuple/tuple_element.h> #include <__tuple/tuple_indices.h> #include <__tuple/tuple_size.h> +#include <__type_traits/has_unique_object_representation.h> +#include <__type_traits/is_comparable.h> #include <__type_traits/is_implicitly_default_constructible.h> #include <__utility/forward.h> #include <__utility/move.h> @@ -407,6 +409,13 @@ pair(_T1, _T2) -> pair<_T1, _T2>; #endif +template +struct __is_trivially_comparable, pair<_Up1, _Up2>> + : integral_constant< + bool, + sizeof(_Tp1) + sizeof(_Tp2) == sizeof(pair<_Tp1, _Tp2>) && // check that there are not padding bytes + __is_trivially_comparable<_Tp1, _Up1>::value && __is_trivially_comparable<_Tp2, _Up2>::value > {}; + // [pairs.spec], specialized algorithms template diff --git a/libcxx/include/tuple b/libcxx/include/tuple --- a/libcxx/include/tuple +++ b/libcxx/include/tuple @@ -209,6 +209,7 @@ #include <__fwd/array.h> #include <__memory/allocator_arg_t.h> #include <__memory/uses_allocator.h> +#include <__type_traits/is_comparable.h> #include <__type_traits/maybe_const.h> #include <__utility/forward.h> #include <__utility/integer_sequence.h> @@ -1323,6 +1324,12 @@ tuple(allocator_arg_t, _Alloc, tuple<_Tp...>) -> tuple<_Tp...>; #endif +template +struct __is_trivially_comparable, tuple<_Args2...>> + : integral_constant) && // check that we have no padding bytes + __all<__is_trivially_comparable<_Args1, _Args2>::value...>::value> {}; + template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 __enable_if_t<__all<__is_swappable<_Tp>::value...>::value, void>