1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___ALGORITHM_EQUAL_H 11 #define _LIBCPP___ALGORITHM_EQUAL_H 12 13 #include <__algorithm/comp.h> 14 #include <__algorithm/min.h> 15 #include <__algorithm/unwrap_iter.h> 16 #include <__config> 17 #include <__functional/identity.h> 18 #include <__fwd/bit_reference.h> 19 #include <__iterator/distance.h> 20 #include <__iterator/iterator_traits.h> 21 #include <__memory/pointer_traits.h> 22 #include <__string/constexpr_c_functions.h> 23 #include <__type_traits/desugars_to.h> 24 #include <__type_traits/enable_if.h> 25 #include <__type_traits/invoke.h> 26 #include <__type_traits/is_equality_comparable.h> 27 #include <__type_traits/is_same.h> 28 #include <__type_traits/is_volatile.h> 29 #include <__utility/move.h> 30 31 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 32 # pragma GCC system_header 33 #endif 34 35 _LIBCPP_PUSH_MACROS 36 #include <__undef_macros> 37 38 _LIBCPP_BEGIN_NAMESPACE_STD 39 40 template <class _Cp, bool _IsConst1, bool _IsConst2> 41 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool 42 __equal_unaligned(__bit_iterator<_Cp, _IsConst1> __first1, 43 __bit_iterator<_Cp, _IsConst1> __last1, 44 __bit_iterator<_Cp, _IsConst2> __first2) { 45 using _It = __bit_iterator<_Cp, _IsConst1>; 46 using difference_type = typename _It::difference_type; 47 using __storage_type = typename _It::__storage_type; 48 49 const int __bits_per_word = _It::__bits_per_word; 50 difference_type __n = __last1 - __first1; 51 if (__n > 0) { 52 // do first word 53 if (__first1.__ctz_ != 0) { 54 unsigned __clz_f = __bits_per_word - __first1.__ctz_; 55 difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n); 56 __n -= __dn; 57 __storage_type __m = std::__middle_mask<__storage_type>(__clz_f - __dn, __first1.__ctz_); 58 __storage_type __b = *__first1.__seg_ & __m; 59 unsigned __clz_r = __bits_per_word - __first2.__ctz_; 60 __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r); 61 __m = std::__middle_mask<__storage_type>(__clz_r - __ddn, __first2.__ctz_); 62 if (__first2.__ctz_ > __first1.__ctz_) { 63 if (static_cast<__storage_type>(*__first2.__seg_ & __m) != 64 static_cast<__storage_type>(__b << (__first2.__ctz_ - __first1.__ctz_))) 65 return false; 66 } else { 67 if (static_cast<__storage_type>(*__first2.__seg_ & __m) != 68 static_cast<__storage_type>(__b >> (__first1.__ctz_ - __first2.__ctz_))) 69 return false; 70 } 71 __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; 72 __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); 73 __dn -= __ddn; 74 if (__dn > 0) { 75 __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n); 76 if (static_cast<__storage_type>(*__first2.__seg_ & __m) != 77 static_cast<__storage_type>(__b >> (__first1.__ctz_ + __ddn))) 78 return false; 79 __first2.__ctz_ = static_cast<unsigned>(__dn); 80 } 81 ++__first1.__seg_; 82 // __first1.__ctz_ = 0; 83 } 84 // __first1.__ctz_ == 0; 85 // do middle words 86 unsigned __clz_r = __bits_per_word - __first2.__ctz_; 87 __storage_type __m = std::__leading_mask<__storage_type>(__first2.__ctz_); 88 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) { 89 __storage_type __b = *__first1.__seg_; 90 if (static_cast<__storage_type>(*__first2.__seg_ & __m) != static_cast<__storage_type>(__b << __first2.__ctz_)) 91 return false; 92 ++__first2.__seg_; 93 if (static_cast<__storage_type>(*__first2.__seg_ & static_cast<__storage_type>(~__m)) != 94 static_cast<__storage_type>(__b >> __clz_r)) 95 return false; 96 } 97 // do last word 98 if (__n > 0) { 99 __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n); 100 __storage_type __b = *__first1.__seg_ & __m; 101 __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r)); 102 __m = std::__middle_mask<__storage_type>(__clz_r - __dn, __first2.__ctz_); 103 if (static_cast<__storage_type>(*__first2.__seg_ & __m) != static_cast<__storage_type>(__b << __first2.__ctz_)) 104 return false; 105 __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; 106 __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); 107 __n -= __dn; 108 if (__n > 0) { 109 __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n); 110 if (static_cast<__storage_type>(*__first2.__seg_ & __m) != static_cast<__storage_type>(__b >> __dn)) 111 return false; 112 } 113 } 114 } 115 return true; 116 } 117 118 template <class _Cp, bool _IsConst1, bool _IsConst2> 119 [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool 120 __equal_aligned(__bit_iterator<_Cp, _IsConst1> __first1, 121 __bit_iterator<_Cp, _IsConst1> __last1, 122 __bit_iterator<_Cp, _IsConst2> __first2) { 123 using _It = __bit_iterator<_Cp, _IsConst1>; 124 using difference_type = typename _It::difference_type; 125 using __storage_type = typename _It::__storage_type; 126 127 const int __bits_per_word = _It::__bits_per_word; 128 difference_type __n = __last1 - __first1; 129 if (__n > 0) { 130 // do first word 131 if (__first1.__ctz_ != 0) { 132 unsigned __clz = __bits_per_word - __first1.__ctz_; 133 difference_type __dn = std::min(static_cast<difference_type>(__clz), __n); 134 __n -= __dn; 135 __storage_type __m = std::__middle_mask<__storage_type>(__clz - __dn, __first1.__ctz_); 136 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 137 return false; 138 ++__first2.__seg_; 139 ++__first1.__seg_; 140 // __first1.__ctz_ = 0; 141 // __first2.__ctz_ = 0; 142 } 143 // __first1.__ctz_ == 0; 144 // __first2.__ctz_ == 0; 145 // do middle words 146 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) 147 if (*__first2.__seg_ != *__first1.__seg_) 148 return false; 149 // do last word 150 if (__n > 0) { 151 __storage_type __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n); 152 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) 153 return false; 154 } 155 } 156 return true; 157 } 158 159 template <class _Cp, 160 bool _IsConst1, 161 bool _IsConst2, 162 class _BinaryPredicate, 163 __enable_if_t<__desugars_to_v<__equal_tag, _BinaryPredicate, bool, bool>, int> = 0> 164 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_iter_impl( 165 __bit_iterator<_Cp, _IsConst1> __first1, 166 __bit_iterator<_Cp, _IsConst1> __last1, 167 __bit_iterator<_Cp, _IsConst2> __first2, 168 _BinaryPredicate) { 169 if (__first1.__ctz_ == __first2.__ctz_) 170 return std::__equal_aligned(__first1, __last1, __first2); 171 return std::__equal_unaligned(__first1, __last1, __first2); 172 } 173 174 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 175 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_iter_impl( 176 _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate& __pred) { 177 for (; __first1 != __last1; ++__first1, (void)++__first2) 178 if (!__pred(*__first1, *__first2)) 179 return false; 180 return true; 181 } 182 183 template <class _Tp, 184 class _Up, 185 class _BinaryPredicate, 186 __enable_if_t<__desugars_to_v<__equal_tag, _BinaryPredicate, _Tp, _Up> && !is_volatile<_Tp>::value && 187 !is_volatile<_Up>::value && __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value, 188 int> = 0> 189 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 190 __equal_iter_impl(_Tp* __first1, _Tp* __last1, _Up* __first2, _BinaryPredicate&) { 191 return std::__constexpr_memcmp_equal(__first1, __first2, __element_count(__last1 - __first1)); 192 } 193 194 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 195 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 196 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred) { 197 return std::__equal_iter_impl( 198 std::__unwrap_iter(__first1), std::__unwrap_iter(__last1), std::__unwrap_iter(__first2), __pred); 199 } 200 201 template <class _InputIterator1, class _InputIterator2> 202 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 203 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2) { 204 return std::equal(__first1, __last1, __first2, __equal_to()); 205 } 206 207 #if _LIBCPP_STD_VER >= 14 208 209 template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2> 210 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_impl( 211 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __comp, _Proj1& __proj1, _Proj2& __proj2) { 212 while (__first1 != __last1 && __first2 != __last2) { 213 if (!std::__invoke(__comp, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) 214 return false; 215 ++__first1; 216 ++__first2; 217 } 218 return __first1 == __last1 && __first2 == __last2; 219 } 220 221 template <class _Tp, 222 class _Up, 223 class _Pred, 224 class _Proj1, 225 class _Proj2, 226 __enable_if_t<__desugars_to_v<__equal_tag, _Pred, _Tp, _Up> && __is_identity<_Proj1>::value && 227 __is_identity<_Proj2>::value && !is_volatile<_Tp>::value && !is_volatile<_Up>::value && 228 __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value, 229 int> = 0> 230 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 231 __equal_impl(_Tp* __first1, _Tp* __last1, _Up* __first2, _Up*, _Pred&, _Proj1&, _Proj2&) { 232 return std::__constexpr_memcmp_equal(__first1, __first2, __element_count(__last1 - __first1)); 233 } 234 235 template <class _Cp, 236 bool _IsConst1, 237 bool _IsConst2, 238 class _Pred, 239 class _Proj1, 240 class _Proj2, 241 __enable_if_t<__desugars_to_v<__equal_tag, _Pred, bool, bool> && __is_identity<_Proj1>::value && 242 __is_identity<_Proj2>::value, 243 int> = 0> 244 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_impl( 245 __bit_iterator<_Cp, _IsConst1> __first1, 246 __bit_iterator<_Cp, _IsConst1> __last1, 247 __bit_iterator<_Cp, _IsConst2> __first2, 248 __bit_iterator<_Cp, _IsConst2>, 249 _Pred&, 250 _Proj1&, 251 _Proj2&) { 252 if (__first1.__ctz_ == __first2.__ctz_) 253 return std::__equal_aligned(__first1, __last1, __first2); 254 return std::__equal_unaligned(__first1, __last1, __first2); 255 } 256 257 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate> 258 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 259 equal(_InputIterator1 __first1, 260 _InputIterator1 __last1, 261 _InputIterator2 __first2, 262 _InputIterator2 __last2, 263 _BinaryPredicate __pred) { 264 if constexpr (__has_random_access_iterator_category<_InputIterator1>::value && 265 __has_random_access_iterator_category<_InputIterator2>::value) { 266 if (std::distance(__first1, __last1) != std::distance(__first2, __last2)) 267 return false; 268 } 269 __identity __proj; 270 return std::__equal_impl( 271 std::__unwrap_iter(__first1), 272 std::__unwrap_iter(__last1), 273 std::__unwrap_iter(__first2), 274 std::__unwrap_iter(__last2), 275 __pred, 276 __proj, 277 __proj); 278 } 279 280 template <class _InputIterator1, class _InputIterator2> 281 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool 282 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { 283 return std::equal(__first1, __last1, __first2, __last2, __equal_to()); 284 } 285 286 #endif // _LIBCPP_STD_VER >= 14 287 288 _LIBCPP_END_NAMESPACE_STD 289 290 _LIBCPP_POP_MACROS 291 292 #endif // _LIBCPP___ALGORITHM_EQUAL_H 293