diff options
Diffstat (limited to 'libcxx/include/__utility')
| -rw-r--r-- | libcxx/include/__utility/default_three_way_comparator.h | 50 | ||||
| -rw-r--r-- | libcxx/include/__utility/in_place.h | 2 | ||||
| -rw-r--r-- | libcxx/include/__utility/lazy_synth_three_way_comparator.h | 90 | ||||
| -rw-r--r-- | libcxx/include/__utility/try_key_extraction.h | 114 |
4 files changed, 255 insertions, 1 deletions
diff --git a/libcxx/include/__utility/default_three_way_comparator.h b/libcxx/include/__utility/default_three_way_comparator.h new file mode 100644 index 000000000000..ce423c6ce98e --- /dev/null +++ b/libcxx/include/__utility/default_three_way_comparator.h @@ -0,0 +1,50 @@ +//===----------------------------------------------------------------------===// +// +// 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___UTILITY_DEFAULT_THREE_WAY_COMPARATOR_H +#define _LIBCPP___UTILITY_DEFAULT_THREE_WAY_COMPARATOR_H + +#include <__config> +#include <__type_traits/enable_if.h> +#include <__type_traits/is_arithmetic.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +// This struct can be specialized to provide a three way comparator between _LHS and _RHS. +// The return value should be +// - less than zero if (lhs_val < rhs_val) +// - greater than zero if (rhs_val < lhs_val) +// - zero otherwise +template <class _LHS, class _RHS, class = void> +struct __default_three_way_comparator; + +template <class _Tp> +struct __default_three_way_comparator<_Tp, _Tp, __enable_if_t<is_arithmetic<_Tp>::value> > { + _LIBCPP_HIDE_FROM_ABI static int operator()(_Tp __lhs, _Tp __rhs) { + if (__lhs < __rhs) + return -1; + if (__lhs > __rhs) + return 1; + return 0; + } +}; + +template <class _LHS, class _RHS, bool = true> +inline const bool __has_default_three_way_comparator_v = false; + +template <class _LHS, class _RHS> +inline const bool + __has_default_three_way_comparator_v< _LHS, _RHS, sizeof(__default_three_way_comparator<_LHS, _RHS>) >= 0> = true; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___UTILITY_DEFAULT_THREE_WAY_COMPARATOR_H diff --git a/libcxx/include/__utility/in_place.h b/libcxx/include/__utility/in_place.h index ade4b6685a11..c5bfa947058f 100644 --- a/libcxx/include/__utility/in_place.h +++ b/libcxx/include/__utility/in_place.h @@ -22,7 +22,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER >= 17 -struct _LIBCPP_EXPORTED_FROM_ABI in_place_t { +struct in_place_t { explicit in_place_t() = default; }; inline constexpr in_place_t in_place{}; diff --git a/libcxx/include/__utility/lazy_synth_three_way_comparator.h b/libcxx/include/__utility/lazy_synth_three_way_comparator.h new file mode 100644 index 000000000000..ca98845f0419 --- /dev/null +++ b/libcxx/include/__utility/lazy_synth_three_way_comparator.h @@ -0,0 +1,90 @@ +//===----------------------------------------------------------------------===// +// +// 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___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H +#define _LIBCPP___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H + +#include <__config> +#include <__type_traits/desugars_to.h> +#include <__type_traits/enable_if.h> +#include <__utility/default_three_way_comparator.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +// This file implements a __lazy_synth_three_way_comparator, which tries to build an efficient three way comparison from +// a binary comparator. That is done in multiple steps: +// 1) Check whether the comparator desugars to a less-than operator +// If that is the case, check whether there exists a specialization of `__default_three_way_comparator`, which +// can be specialized to implement a three way comparator for the specific types. +// 2) Fall back to doing a lazy less than/greater than comparison + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <class _Comparator, class _LHS, class _RHS> +struct __lazy_compare_result { + const _Comparator& __comp_; + const _LHS& __lhs_; + const _RHS& __rhs_; + + _LIBCPP_HIDE_FROM_ABI + __lazy_compare_result(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator& __comp, + _LIBCPP_CTOR_LIFETIMEBOUND const _LHS& __lhs, + _LIBCPP_CTOR_LIFETIMEBOUND const _RHS& __rhs) + : __comp_(__comp), __lhs_(__lhs), __rhs_(__rhs) {} + + _LIBCPP_HIDE_FROM_ABI bool __less() const { return __comp_(__lhs_, __rhs_); } + _LIBCPP_HIDE_FROM_ABI bool __greater() const { return __comp_(__rhs_, __lhs_); } +}; + +// This class provides three way comparison between _LHS and _RHS as efficiently as possible. This can be specialized if +// a comparator only compares part of the object, potentially allowing an efficient three way comparison between the +// subobjects. The specialization should use the __lazy_synth_three_way_comparator for the subobjects to achieve this. +template <class _Comparator, class _LHS, class _RHS, class = void> +struct __lazy_synth_three_way_comparator { + const _Comparator& __comp_; + + _LIBCPP_HIDE_FROM_ABI __lazy_synth_three_way_comparator(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator& __comp) + : __comp_(__comp) {} + + _LIBCPP_HIDE_FROM_ABI __lazy_compare_result<_Comparator, _LHS, _RHS> + operator()(_LIBCPP_LIFETIMEBOUND const _LHS& __lhs, _LIBCPP_LIFETIMEBOUND const _RHS& __rhs) const { + return __lazy_compare_result<_Comparator, _LHS, _RHS>(__comp_, __lhs, __rhs); + } +}; + +struct __eager_compare_result { + int __res_; + + _LIBCPP_HIDE_FROM_ABI explicit __eager_compare_result(int __res) : __res_(__res) {} + + _LIBCPP_HIDE_FROM_ABI bool __less() const { return __res_ < 0; } + _LIBCPP_HIDE_FROM_ABI bool __greater() const { return __res_ > 0; } +}; + +template <class _Comparator, class _LHS, class _RHS> +struct __lazy_synth_three_way_comparator<_Comparator, + _LHS, + _RHS, + __enable_if_t<__desugars_to_v<__less_tag, _Comparator, _LHS, _RHS> && + __has_default_three_way_comparator_v<_LHS, _RHS> > > { + // This lifetimebound annotation is technically incorrect, but other specializations actually capture the lifetime of + // the comparator. + _LIBCPP_HIDE_FROM_ABI __lazy_synth_three_way_comparator(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator&) {} + + // Same comment as above. + _LIBCPP_HIDE_FROM_ABI static __eager_compare_result + operator()(_LIBCPP_LIFETIMEBOUND const _LHS& __lhs, _LIBCPP_LIFETIMEBOUND const _RHS& __rhs) { + return __eager_compare_result(__default_three_way_comparator<_LHS, _RHS>()(__lhs, __rhs)); + } +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H diff --git a/libcxx/include/__utility/try_key_extraction.h b/libcxx/include/__utility/try_key_extraction.h new file mode 100644 index 000000000000..755c08214019 --- /dev/null +++ b/libcxx/include/__utility/try_key_extraction.h @@ -0,0 +1,114 @@ +//===----------------------------------------------------------------------===// +// +// 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___UTILITY_TRY_EXTRACT_KEY_H +#define _LIBCPP___UTILITY_TRY_EXTRACT_KEY_H + +#include <__config> +#include <__fwd/pair.h> +#include <__fwd/tuple.h> +#include <__type_traits/enable_if.h> +#include <__type_traits/is_same.h> +#include <__type_traits/remove_const.h> +#include <__type_traits/remove_const_ref.h> +#include <__utility/declval.h> +#include <__utility/forward.h> +#include <__utility/piecewise_construct.h> +#include <__utility/priority_tag.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <class _KeyT, class _Ret, class _WithKey, class _WithoutKey, class... _Args> +_LIBCPP_HIDE_FROM_ABI _Ret +__try_key_extraction_impl(__priority_tag<0>, _WithKey, _WithoutKey __without_key, _Args&&... __args) { + return __without_key(std::forward<_Args>(__args)...); +} + +template <class _KeyT, + class _Ret, + class _WithKey, + class _WithoutKey, + class _Arg, + __enable_if_t<is_same<_KeyT, __remove_const_ref_t<_Arg> >::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI _Ret +__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg&& __arg) { + return __with_key(__arg, std::forward<_Arg>(__arg)); +} + +template <class _KeyT, + class _Ret, + class _WithKey, + class _WithoutKey, + class _Arg, + __enable_if_t<__is_pair_v<__remove_const_ref_t<_Arg> > && + is_same<__remove_const_t<typename __remove_const_ref_t<_Arg>::first_type>, _KeyT>::value, + int> = 0> +_LIBCPP_HIDE_FROM_ABI _Ret +__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg&& __arg) { + return __with_key(__arg.first, std::forward<_Arg>(__arg)); +} + +template <class _KeyT, + class _Ret, + class _WithKey, + class _WithoutKey, + class _Arg1, + class _Arg2, + __enable_if_t<is_same<_KeyT, __remove_const_ref_t<_Arg1> >::value, int> = 0> +_LIBCPP_HIDE_FROM_ABI _Ret +__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg1&& __arg1, _Arg2&& __arg2) { + return __with_key(__arg1, std::forward<_Arg1>(__arg1), std::forward<_Arg2>(__arg2)); +} + +#ifndef _LIBCPP_CXX03_LANG +template <class _KeyT, + class _Ret, + class _WithKey, + class _WithoutKey, + class _PiecewiseConstruct, + class _Tuple1, + class _Tuple2, + __enable_if_t<is_same<__remove_const_ref_t<_PiecewiseConstruct>, piecewise_construct_t>::value && + __is_tuple_v<_Tuple1> && tuple_size<_Tuple1>::value == 1 && + is_same<__remove_const_ref_t<typename tuple_element<0, _Tuple1>::type>, _KeyT>::value, + int> = 0> +_LIBCPP_HIDE_FROM_ABI _Ret __try_key_extraction_impl( + __priority_tag<1>, + _WithKey __with_key, + _WithoutKey, + _PiecewiseConstruct&& __pc, + _Tuple1&& __tuple1, + _Tuple2&& __tuple2) { + return __with_key( + std::get<0>(__tuple1), + std::forward<_PiecewiseConstruct>(__pc), + std::forward<_Tuple1>(__tuple1), + std::forward<_Tuple2>(__tuple2)); +} +#endif // _LIBCPP_CXX03_LANG + +// This function tries extracting the given _KeyT from _Args... +// If it succeeds to extract the key, it calls the `__with_key` function with the extracted key and all of the +// arguments. Otherwise it calls the `__without_key` function with all of the arguments. +// +// Both `__with_key` and `__without_key` must take all arguments by reference. +template <class _KeyT, class _WithKey, class _WithoutKey, class... _Args> +_LIBCPP_HIDE_FROM_ABI decltype(std::declval<_WithoutKey>()(std::declval<_Args>()...)) +__try_key_extraction(_WithKey __with_key, _WithoutKey __without_key, _Args&&... __args) { + using _Ret = decltype(__without_key(std::forward<_Args>(__args)...)); + return std::__try_key_extraction_impl<_KeyT, _Ret>( + __priority_tag<1>(), __with_key, __without_key, std::forward<_Args>(__args)...); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___UTILITY_TRY_EXTRACT_KEY_H |