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_THREE_WAY_H 10 #define _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H 11 12 #include <__algorithm/min.h> 13 #include <__algorithm/three_way_comp_ref_type.h> 14 #include <__compare/compare_three_way.h> 15 #include <__compare/ordering.h> 16 #include <__concepts/arithmetic.h> 17 #include <__config> 18 #include <__iterator/iterator_traits.h> 19 #include <__type_traits/common_type.h> 20 #include <__type_traits/is_copy_constructible.h> 21 #include <__utility/move.h> 22 23 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 24 # pragma GCC system_header 25 #endif 26 27 _LIBCPP_PUSH_MACROS 28 #include <__undef_macros> 29 30 _LIBCPP_BEGIN_NAMESPACE_STD 31 32 #if _LIBCPP_STD_VER >= 20 33 34 // Fast path for random access iterators which computes the number of loop iterations up-front and 35 // then skips the iterator comparisons inside the loop. 36 template <class _InputIterator1, class _InputIterator2, class _Cmp> 37 _LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path( 38 _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp) 39 -> decltype(__comp(*__first1, *__first2)) { 40 static_assert( 41 signed_integral<__iter_diff_t<_InputIterator1>>, "Using a non-integral difference_type is undefined behavior."); 42 static_assert( 43 signed_integral<__iter_diff_t<_InputIterator2>>, "Using a non-integral difference_type is undefined behavior."); 44 45 using _Len1 = __iter_diff_t<_InputIterator1>; 46 using _Len2 = __iter_diff_t<_InputIterator2>; 47 using _Common = common_type_t<_Len1, _Len2>; 48 49 _Len1 __len1 = __last1 - __first1; 50 _Len2 __len2 = __last2 - __first2; 51 _Common __min_len = std::min<_Common>(__len1, __len2); 52 53 for (_Common __i = 0; __i < __min_len; ++__i) { 54 auto __c = __comp(*__first1, *__first2); 55 if (__c != 0) { 56 return __c; 57 } 58 ++__first1; 59 ++__first2; 60 } 61 62 return __len1 <=> __len2; 63 } 64 65 // Unoptimized implementation which compares the iterators against the end in every loop iteration 66 template <class _InputIterator1, class _InputIterator2, class _Cmp> 67 _LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_slow_path( 68 _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp) 69 -> decltype(__comp(*__first1, *__first2)) { 70 while (true) { 71 bool __exhausted1 = __first1 == __last1; 72 bool __exhausted2 = __first2 == __last2; 73 74 if (__exhausted1 || __exhausted2) { 75 if (!__exhausted1) 76 return strong_ordering::greater; 77 if (!__exhausted2) 78 return strong_ordering::less; 79 return strong_ordering::equal; 80 } 81 82 auto __c = __comp(*__first1, *__first2); 83 if (__c != 0) { 84 return __c; 85 } 86 87 ++__first1; 88 ++__first2; 89 } 90 } 91 92 template <class _InputIterator1, class _InputIterator2, class _Cmp> 93 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way( 94 _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp __comp) 95 -> decltype(__comp(*__first1, *__first2)) { 96 static_assert(__comparison_category<decltype(__comp(*__first1, *__first2))>, 97 "The comparator passed to lexicographical_compare_three_way must return a comparison category type."); 98 static_assert(std::is_copy_constructible_v<_InputIterator1>, "Iterators must be copy constructible."); 99 static_assert(std::is_copy_constructible_v<_InputIterator2>, "Iterators must be copy constructible."); 100 __three_way_comp_ref_type<_Cmp> __wrapped_comp_ref(__comp); 101 if constexpr (__has_random_access_iterator_category<_InputIterator1>::value && 102 __has_random_access_iterator_category<_InputIterator2>::value) { 103 return std::__lexicographical_compare_three_way_fast_path( 104 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref); 105 } else { 106 // Unoptimized implementation which compares the iterators against the end in every loop iteration 107 return std::__lexicographical_compare_three_way_slow_path( 108 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref); 109 } 110 } 111 112 template <class _InputIterator1, class _InputIterator2> 113 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way( 114 _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { 115 return std::lexicographical_compare_three_way( 116 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::compare_three_way()); 117 } 118 119 #endif // _LIBCPP_STD_VER >= 20 120 121 _LIBCPP_END_NAMESPACE_STD 122 123 _LIBCPP_POP_MACROS 124 125 #endif // _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H 126