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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_H 10 #define _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_H 11 12 #include <__algorithm/comp.h> 13 #include <__algorithm/min.h> 14 #include <__algorithm/mismatch.h> 15 #include <__algorithm/simd_utils.h> 16 #include <__algorithm/unwrap_iter.h> 17 #include <__config> 18 #include <__functional/identity.h> 19 #include <__iterator/iterator_traits.h> 20 #include <__string/constexpr_c_functions.h> 21 #include <__type_traits/desugars_to.h> 22 #include <__type_traits/enable_if.h> 23 #include <__type_traits/invoke.h> 24 #include <__type_traits/is_equality_comparable.h> 25 #include <__type_traits/is_integral.h> 26 #include <__type_traits/is_trivially_lexicographically_comparable.h> 27 #include <__type_traits/is_volatile.h> 28 29 #if _LIBCPP_HAS_WIDE_CHARACTERS 30 # include <cwchar> 31 #endif 32 33 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 34 # pragma GCC system_header 35 #endif 36 37 _LIBCPP_PUSH_MACROS 38 #include <__undef_macros> 39 40 _LIBCPP_BEGIN_NAMESPACE_STD 41 42 template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Proj1, class _Proj2, class _Comp> 43 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __lexicographical_compare( 44 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Comp& __comp, _Proj1& __proj1, _Proj2& __proj2) { 45 while (__first2 != __last2) { 46 if (__first1 == __last1 || 47 std::__invoke(__comp, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) 48 return true; 49 if (std::__invoke(__comp, std::__invoke(__proj2, *__first2), std::__invoke(__proj1, *__first1))) 50 return false; 51 ++__first1; 52 ++__first2; 53 } 54 return false; 55 } 56 57 #if _LIBCPP_STD_VER >= 14 58 59 // If the comparison operation is equivalent to < and that is a total order, we know that we can use equality comparison 60 // on that type instead to extract some information. Furthermore, if equality comparison on that type is trivial, the 61 // user can't observe that we're calling it. So instead of using the user-provided total order, we use std::mismatch, 62 // which uses equality comparison (and is vertorized). Additionally, if the type is trivially lexicographically 63 // comparable, we can go one step further and use std::memcmp directly instead of calling std::mismatch. 64 template <class _Tp, 65 class _Proj1, 66 class _Proj2, 67 class _Comp, 68 __enable_if_t<__desugars_to_v<__totally_ordered_less_tag, _Comp, _Tp, _Tp> && !is_volatile<_Tp>::value && 69 __libcpp_is_trivially_equality_comparable<_Tp, _Tp>::value && 70 __is_identity<_Proj1>::value && __is_identity<_Proj2>::value, 71 int> = 0> 72 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 73 __lexicographical_compare(_Tp* __first1, _Tp* __last1, _Tp* __first2, _Tp* __last2, _Comp&, _Proj1&, _Proj2&) { 74 if constexpr (__is_trivially_lexicographically_comparable_v<_Tp, _Tp>) { 75 auto __res = 76 std::__constexpr_memcmp(__first1, __first2, __element_count(std::min(__last1 - __first1, __last2 - __first2))); 77 if (__res == 0) 78 return __last1 - __first1 < __last2 - __first2; 79 return __res < 0; 80 } 81 # if _LIBCPP_HAS_WIDE_CHARACTERS 82 else if constexpr (is_same<__remove_cv_t<_Tp>, wchar_t>::value) { 83 auto __res = std::__constexpr_wmemcmp(__first1, __first2, std::min(__last1 - __first1, __last2 - __first2)); 84 if (__res == 0) 85 return __last1 - __first1 < __last2 - __first2; 86 return __res < 0; 87 } 88 # endif // _LIBCPP_HAS_WIDE_CHARACTERS 89 else { 90 auto __res = std::mismatch(__first1, __last1, __first2, __last2); 91 if (__res.second == __last2) 92 return false; 93 if (__res.first == __last1) 94 return true; 95 return *__res.first < *__res.second; 96 } 97 } 98 99 #endif // _LIBCPP_STD_VER >= 14 100 101 template <class _InputIterator1, class _InputIterator2, class _Compare> 102 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool lexicographical_compare( 103 _InputIterator1 __first1, 104 _InputIterator1 __last1, 105 _InputIterator2 __first2, 106 _InputIterator2 __last2, 107 _Compare __comp) { 108 __identity __proj; 109 return std::__lexicographical_compare( 110 std::__unwrap_iter(__first1), 111 std::__unwrap_iter(__last1), 112 std::__unwrap_iter(__first2), 113 std::__unwrap_iter(__last2), 114 __comp, 115 __proj, 116 __proj); 117 } 118 119 template <class _InputIterator1, class _InputIterator2> 120 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool lexicographical_compare( 121 _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { 122 return std::lexicographical_compare(__first1, __last1, __first2, __last2, __less<>()); 123 } 124 125 _LIBCPP_END_NAMESPACE_STD 126 127 _LIBCPP_POP_MACROS 128 129 #endif // _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_H 130