109 lines · c
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H10#define _LIBCPP___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H11 12#include <__config>13#include <__type_traits/conjunction.h>14#include <__type_traits/desugars_to.h>15#include <__type_traits/enable_if.h>16#include <__utility/default_three_way_comparator.h>17 18#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)19# pragma GCC system_header20#endif21 22// This file implements a __lazy_synth_three_way_comparator, which tries to build an efficient three way comparison from23// a binary comparator. That is done in multiple steps:24// 1) Check whether the comparator desugars to a less-than operator25// If that is the case, check whether there exists a specialization of `__default_three_way_comparator`, which26// can be specialized to implement a three way comparator for the specific types.27// 2) Fall back to doing a lazy less than/greater than comparison28 29_LIBCPP_BEGIN_NAMESPACE_STD30 31template <class _Comparator, class _LHS, class _RHS>32struct __lazy_compare_result {33 const _Comparator& __comp_;34 const _LHS& __lhs_;35 const _RHS& __rhs_;36 37 _LIBCPP_HIDE_FROM_ABI38 __lazy_compare_result(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator& __comp,39 _LIBCPP_CTOR_LIFETIMEBOUND const _LHS& __lhs,40 _LIBCPP_CTOR_LIFETIMEBOUND const _RHS& __rhs)41 : __comp_(__comp), __lhs_(__lhs), __rhs_(__rhs) {}42 43 _LIBCPP_HIDE_FROM_ABI bool __less() const { return __comp_(__lhs_, __rhs_); }44 _LIBCPP_HIDE_FROM_ABI bool __greater() const { return __comp_(__rhs_, __lhs_); }45};46 47// This class provides three way comparison between _LHS and _RHS as efficiently as possible. This can be specialized if48// a comparator only compares part of the object, potentially allowing an efficient three way comparison between the49// subobjects. The specialization should use the __lazy_synth_three_way_comparator for the subobjects to achieve this.50template <class _Comparator, class _LHS, class _RHS, class = void>51struct __lazy_synth_three_way_comparator {52 const _Comparator& __comp_;53 54 _LIBCPP_HIDE_FROM_ABI __lazy_synth_three_way_comparator(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator& __comp)55 : __comp_(__comp) {}56 57 _LIBCPP_HIDE_FROM_ABI __lazy_compare_result<_Comparator, _LHS, _RHS>58 operator()(_LIBCPP_LIFETIMEBOUND const _LHS& __lhs, _LIBCPP_LIFETIMEBOUND const _RHS& __rhs) const {59 return __lazy_compare_result<_Comparator, _LHS, _RHS>(__comp_, __lhs, __rhs);60 }61};62 63struct __eager_compare_result {64 int __res_;65 66 _LIBCPP_HIDE_FROM_ABI explicit __eager_compare_result(int __res) : __res_(__res) {}67 68 _LIBCPP_HIDE_FROM_ABI bool __less() const { return __res_ < 0; }69 _LIBCPP_HIDE_FROM_ABI bool __greater() const { return __res_ > 0; }70};71 72template <class _Comparator, class _LHS, class _RHS>73struct __lazy_synth_three_way_comparator<_Comparator,74 _LHS,75 _RHS,76 __enable_if_t<_And<__desugars_to<__less_tag, _Comparator, _LHS, _RHS>,77 __has_default_three_way_comparator<_LHS, _RHS> >::value> > {78 // This lifetimebound annotation is technically incorrect, but other specializations actually capture the lifetime of79 // the comparator.80 _LIBCPP_HIDE_FROM_ABI __lazy_synth_three_way_comparator(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator&) {}81 82 // Same comment as above.83 _LIBCPP_HIDE_FROM_ABI static __eager_compare_result84 operator()(_LIBCPP_LIFETIMEBOUND const _LHS& __lhs, _LIBCPP_LIFETIMEBOUND const _RHS& __rhs) {85 return __eager_compare_result(__default_three_way_comparator<_LHS, _RHS>()(__lhs, __rhs));86 }87};88 89template <class _Comparator, class _LHS, class _RHS>90struct __lazy_synth_three_way_comparator<_Comparator,91 _LHS,92 _RHS,93 __enable_if_t<_And<__desugars_to<__greater_tag, _Comparator, _LHS, _RHS>,94 __has_default_three_way_comparator<_LHS, _RHS> >::value> > {95 // This lifetimebound annotation is technically incorrect, but other specializations actually capture the lifetime of96 // the comparator.97 _LIBCPP_HIDE_FROM_ABI __lazy_synth_three_way_comparator(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator&) {}98 99 // Same comment as above.100 _LIBCPP_HIDE_FROM_ABI static __eager_compare_result101 operator()(_LIBCPP_LIFETIMEBOUND const _LHS& __lhs, _LIBCPP_LIFETIMEBOUND const _RHS& __rhs) {102 return __eager_compare_result(-__default_three_way_comparator<_LHS, _RHS>()(__lhs, __rhs));103 }104};105 106_LIBCPP_END_NAMESPACE_STD107 108#endif // _LIBCPP___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H109