utility (48826B)
1 // -*- C++ -*- 2 //===-------------------------- utility -----------------------------------===// 3 // 4 // The LLVM Compiler Infrastructure 5 // 6 // This file is dual licensed under the MIT and the University of Illinois Open 7 // Source Licenses. See LICENSE.TXT for details. 8 // 9 //===----------------------------------------------------------------------===// 10 11 #ifndef _LIBCPP_UTILITY 12 #define _LIBCPP_UTILITY 13 14 /* 15 utility synopsis 16 17 #include <initializer_list> 18 19 namespace std 20 { 21 22 template <class T> 23 void 24 swap(T& a, T& b); 25 26 namespace rel_ops 27 { 28 template<class T> bool operator!=(const T&, const T&); 29 template<class T> bool operator> (const T&, const T&); 30 template<class T> bool operator<=(const T&, const T&); 31 template<class T> bool operator>=(const T&, const T&); 32 } 33 34 template<class T> 35 void 36 swap(T& a, T& b) noexcept(is_nothrow_move_constructible<T>::value && 37 is_nothrow_move_assignable<T>::value); 38 39 template <class T, size_t N> 40 void 41 swap(T (&a)[N], T (&b)[N]) noexcept(noexcept(swap(*a, *b))); 42 43 template <class T> T&& forward(typename remove_reference<T>::type& t) noexcept; // constexpr in C++14 44 template <class T> T&& forward(typename remove_reference<T>::type&& t) noexcept; // constexpr in C++14 45 46 template <class T> typename remove_reference<T>::type&& move(T&&) noexcept; // constexpr in C++14 47 48 template <class T> 49 typename conditional 50 < 51 !is_nothrow_move_constructible<T>::value && is_copy_constructible<T>::value, 52 const T&, 53 T&& 54 >::type 55 move_if_noexcept(T& x) noexcept; // constexpr in C++14 56 57 template <class T> constexpr add_const_t<T>& as_const(T& t) noexcept; // C++17 58 template <class T> void as_const(const T&&) = delete; // C++17 59 60 template <class T> typename add_rvalue_reference<T>::type declval() noexcept; 61 62 template <class T1, class T2> 63 struct pair 64 { 65 typedef T1 first_type; 66 typedef T2 second_type; 67 68 T1 first; 69 T2 second; 70 71 pair(const pair&) = default; 72 pair(pair&&) = default; 73 constexpr pair(); 74 pair(const T1& x, const T2& y); // constexpr in C++14 75 template <class U, class V> pair(U&& x, V&& y); // constexpr in C++14 76 template <class U, class V> pair(const pair<U, V>& p); // constexpr in C++14 77 template <class U, class V> pair(pair<U, V>&& p); // constexpr in C++14 78 template <class... Args1, class... Args2> 79 pair(piecewise_construct_t, tuple<Args1...> first_args, 80 tuple<Args2...> second_args); 81 82 template <class U, class V> pair& operator=(const pair<U, V>& p); 83 pair& operator=(pair&& p) noexcept(is_nothrow_move_assignable<T1>::value && 84 is_nothrow_move_assignable<T2>::value); 85 template <class U, class V> pair& operator=(pair<U, V>&& p); 86 87 void swap(pair& p) noexcept(is_nothrow_swappable_v<T1> && 88 is_nothrow_swappable_v<T2>); 89 }; 90 91 template <class T1, class T2> bool operator==(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 92 template <class T1, class T2> bool operator!=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 93 template <class T1, class T2> bool operator< (const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 94 template <class T1, class T2> bool operator> (const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 95 template <class T1, class T2> bool operator>=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 96 template <class T1, class T2> bool operator<=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 97 98 template <class T1, class T2> pair<V1, V2> make_pair(T1&&, T2&&); // constexpr in C++14 99 template <class T1, class T2> 100 void 101 swap(pair<T1, T2>& x, pair<T1, T2>& y) noexcept(noexcept(x.swap(y))); 102 103 struct piecewise_construct_t { }; 104 inline constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t(); 105 106 template <class T> struct tuple_size; 107 template <size_t I, class T> class tuple_element; 108 109 template <class T1, class T2> struct tuple_size<pair<T1, T2> >; 110 template <class T1, class T2> struct tuple_element<0, pair<T1, T2> >; 111 template <class T1, class T2> struct tuple_element<1, pair<T1, T2> >; 112 113 template<size_t I, class T1, class T2> 114 typename tuple_element<I, pair<T1, T2> >::type& 115 get(pair<T1, T2>&) noexcept; // constexpr in C++14 116 117 template<size_t I, class T1, class T2> 118 const typename tuple_element<I, pair<T1, T2> >::type& 119 get(const pair<T1, T2>&) noexcept; // constexpr in C++14 120 121 template<size_t I, class T1, class T2> 122 typename tuple_element<I, pair<T1, T2> >::type&& 123 get(pair<T1, T2>&&) noexcept; // constexpr in C++14 124 125 template<size_t I, class T1, class T2> 126 const typename tuple_element<I, pair<T1, T2> >::type&& 127 get(const pair<T1, T2>&&) noexcept; // constexpr in C++14 128 129 template<class T1, class T2> 130 constexpr T1& get(pair<T1, T2>&) noexcept; // C++14 131 132 template<class T1, class T2> 133 constexpr const T1& get(const pair<T1, T2>&) noexcept; // C++14 134 135 template<class T1, class T2> 136 constexpr T1&& get(pair<T1, T2>&&) noexcept; // C++14 137 138 template<class T1, class T2> 139 constexpr const T1&& get(const pair<T1, T2>&&) noexcept; // C++14 140 141 template<class T1, class T2> 142 constexpr T1& get(pair<T2, T1>&) noexcept; // C++14 143 144 template<class T1, class T2> 145 constexpr const T1& get(const pair<T2, T1>&) noexcept; // C++14 146 147 template<class T1, class T2> 148 constexpr T1&& get(pair<T2, T1>&&) noexcept; // C++14 149 150 template<class T1, class T2> 151 constexpr const T1&& get(const pair<T2, T1>&&) noexcept; // C++14 152 153 // C++14 154 155 template<class T, T... I> 156 struct integer_sequence 157 { 158 typedef T value_type; 159 160 static constexpr size_t size() noexcept; 161 }; 162 163 template<size_t... I> 164 using index_sequence = integer_sequence<size_t, I...>; 165 166 template<class T, T N> 167 using make_integer_sequence = integer_sequence<T, 0, 1, ..., N-1>; 168 template<size_t N> 169 using make_index_sequence = make_integer_sequence<size_t, N>; 170 171 template<class... T> 172 using index_sequence_for = make_index_sequence<sizeof...(T)>; 173 174 template<class T, class U=T> 175 T exchange(T& obj, U&& new_value); 176 177 // 20.2.7, in-place construction // C++17 178 struct in_place_t { 179 explicit in_place_t() = default; 180 }; 181 inline constexpr in_place_t in_place{}; 182 template <class T> 183 struct in_place_type_t { 184 explicit in_place_type_t() = default; 185 }; 186 template <class T> 187 inline constexpr in_place_type_t<T> in_place_type{}; 188 template <size_t I> 189 struct in_place_index_t { 190 explicit in_place_index_t() = default; 191 }; 192 template <size_t I> 193 inline constexpr in_place_index_t<I> in_place_index{}; 194 195 } // std 196 197 */ 198 199 #include <__config> 200 #include <__tuple> 201 #include <type_traits> 202 #include <initializer_list> 203 #include <cstddef> 204 #include <cstring> 205 #include <cstdint> 206 #include <version> 207 #include <__debug> 208 209 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 210 #pragma GCC system_header 211 #endif 212 213 _LIBCPP_BEGIN_NAMESPACE_STD 214 215 namespace rel_ops 216 { 217 218 template<class _Tp> 219 inline _LIBCPP_INLINE_VISIBILITY 220 bool 221 operator!=(const _Tp& __x, const _Tp& __y) 222 { 223 return !(__x == __y); 224 } 225 226 template<class _Tp> 227 inline _LIBCPP_INLINE_VISIBILITY 228 bool 229 operator> (const _Tp& __x, const _Tp& __y) 230 { 231 return __y < __x; 232 } 233 234 template<class _Tp> 235 inline _LIBCPP_INLINE_VISIBILITY 236 bool 237 operator<=(const _Tp& __x, const _Tp& __y) 238 { 239 return !(__y < __x); 240 } 241 242 template<class _Tp> 243 inline _LIBCPP_INLINE_VISIBILITY 244 bool 245 operator>=(const _Tp& __x, const _Tp& __y) 246 { 247 return !(__x < __y); 248 } 249 250 } // rel_ops 251 252 // swap_ranges 253 254 255 template <class _ForwardIterator1, class _ForwardIterator2> 256 inline _LIBCPP_INLINE_VISIBILITY 257 _ForwardIterator2 258 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) 259 { 260 for(; __first1 != __last1; ++__first1, (void) ++__first2) 261 swap(*__first1, *__first2); 262 return __first2; 263 } 264 265 // forward declared in <type_traits> 266 template<class _Tp, size_t _Np> 267 inline _LIBCPP_INLINE_VISIBILITY 268 typename enable_if< 269 __is_swappable<_Tp>::value 270 >::type 271 swap(_Tp (&__a)[_Np], _Tp (&__b)[_Np]) _NOEXCEPT_(__is_nothrow_swappable<_Tp>::value) 272 { 273 _VSTD::swap_ranges(__a, __a + _Np, __b); 274 } 275 276 template <class _Tp> 277 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 278 #ifndef _LIBCPP_CXX03_LANG 279 typename conditional 280 < 281 !is_nothrow_move_constructible<_Tp>::value && is_copy_constructible<_Tp>::value, 282 const _Tp&, 283 _Tp&& 284 >::type 285 #else // _LIBCPP_CXX03_LANG 286 const _Tp& 287 #endif 288 move_if_noexcept(_Tp& __x) _NOEXCEPT 289 { 290 return _VSTD::move(__x); 291 } 292 293 #if _LIBCPP_STD_VER > 14 294 template <class _Tp> constexpr add_const_t<_Tp>& as_const(_Tp& __t) noexcept { return __t; } 295 template <class _Tp> void as_const(const _Tp&&) = delete; 296 #endif 297 298 struct _LIBCPP_TEMPLATE_VIS piecewise_construct_t { }; 299 #if defined(_LIBCPP_CXX03_LANG) || defined(_LIBCPP_BUILDING_LIBRARY) 300 extern _LIBCPP_EXPORTED_FROM_ABI const piecewise_construct_t piecewise_construct;// = piecewise_construct_t(); 301 #else 302 /* _LIBCPP_INLINE_VAR */ constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t(); 303 #endif 304 305 #if defined(_LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR) 306 template <class, class> 307 struct __non_trivially_copyable_base { 308 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 309 __non_trivially_copyable_base() _NOEXCEPT {} 310 _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 311 __non_trivially_copyable_base(__non_trivially_copyable_base const&) _NOEXCEPT {} 312 }; 313 #endif 314 315 template <class _T1, class _T2> 316 struct _LIBCPP_TEMPLATE_VIS pair 317 #if defined(_LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR) 318 : private __non_trivially_copyable_base<_T1, _T2> 319 #endif 320 { 321 typedef _T1 first_type; 322 typedef _T2 second_type; 323 324 _T1 first; 325 _T2 second; 326 327 #if !defined(_LIBCPP_CXX03_LANG) 328 pair(pair const&) = default; 329 pair(pair&&) = default; 330 #else 331 // Use the implicitly declared copy constructor in C++03 332 #endif 333 334 #ifdef _LIBCPP_CXX03_LANG 335 _LIBCPP_INLINE_VISIBILITY 336 pair() : first(), second() {} 337 338 _LIBCPP_INLINE_VISIBILITY 339 pair(_T1 const& __t1, _T2 const& __t2) : first(__t1), second(__t2) {} 340 341 template <class _U1, class _U2> 342 _LIBCPP_INLINE_VISIBILITY 343 pair(const pair<_U1, _U2>& __p) : first(__p.first), second(__p.second) {} 344 345 _LIBCPP_INLINE_VISIBILITY 346 pair& operator=(pair const& __p) { 347 first = __p.first; 348 second = __p.second; 349 return *this; 350 } 351 #else 352 template <bool _Val> 353 using _EnableB = typename enable_if<_Val, bool>::type; 354 355 struct _CheckArgs { 356 template <class _U1, class _U2> 357 static constexpr bool __enable_default() { 358 return is_default_constructible<_U1>::value 359 && is_default_constructible<_U2>::value; 360 } 361 362 template <class _U1, class _U2> 363 static constexpr bool __enable_explicit() { 364 return is_constructible<first_type, _U1>::value 365 && is_constructible<second_type, _U2>::value 366 && (!is_convertible<_U1, first_type>::value 367 || !is_convertible<_U2, second_type>::value); 368 } 369 370 template <class _U1, class _U2> 371 static constexpr bool __enable_implicit() { 372 return is_constructible<first_type, _U1>::value 373 && is_constructible<second_type, _U2>::value 374 && is_convertible<_U1, first_type>::value 375 && is_convertible<_U2, second_type>::value; 376 } 377 }; 378 379 template <bool _MaybeEnable> 380 using _CheckArgsDep = typename conditional< 381 _MaybeEnable, _CheckArgs, __check_tuple_constructor_fail>::type; 382 383 struct _CheckTupleLikeConstructor { 384 template <class _Tuple> 385 static constexpr bool __enable_implicit() { 386 return __tuple_convertible<_Tuple, pair>::value; 387 } 388 389 template <class _Tuple> 390 static constexpr bool __enable_explicit() { 391 return __tuple_constructible<_Tuple, pair>::value 392 && !__tuple_convertible<_Tuple, pair>::value; 393 } 394 395 template <class _Tuple> 396 static constexpr bool __enable_assign() { 397 return __tuple_assignable<_Tuple, pair>::value; 398 } 399 }; 400 401 template <class _Tuple> 402 using _CheckTLC = typename conditional< 403 __tuple_like_with_size<_Tuple, 2>::value 404 && !is_same<typename decay<_Tuple>::type, pair>::value, 405 _CheckTupleLikeConstructor, 406 __check_tuple_constructor_fail 407 >::type; 408 409 template<bool _Dummy = true, _EnableB< 410 _CheckArgsDep<_Dummy>::template __enable_default<_T1, _T2>() 411 > = false> 412 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 413 pair() _NOEXCEPT_(is_nothrow_default_constructible<first_type>::value && 414 is_nothrow_default_constructible<second_type>::value) 415 : first(), second() {} 416 417 template <bool _Dummy = true, _EnableB< 418 _CheckArgsDep<_Dummy>::template __enable_explicit<_T1 const&, _T2 const&>() 419 > = false> 420 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 421 explicit pair(_T1 const& __t1, _T2 const& __t2) 422 _NOEXCEPT_(is_nothrow_copy_constructible<first_type>::value && 423 is_nothrow_copy_constructible<second_type>::value) 424 : first(__t1), second(__t2) {} 425 426 template<bool _Dummy = true, _EnableB< 427 _CheckArgsDep<_Dummy>::template __enable_implicit<_T1 const&, _T2 const&>() 428 > = false> 429 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 430 pair(_T1 const& __t1, _T2 const& __t2) 431 _NOEXCEPT_(is_nothrow_copy_constructible<first_type>::value && 432 is_nothrow_copy_constructible<second_type>::value) 433 : first(__t1), second(__t2) {} 434 435 template<class _U1, class _U2, _EnableB< 436 _CheckArgs::template __enable_explicit<_U1, _U2>() 437 > = false> 438 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 439 explicit pair(_U1&& __u1, _U2&& __u2) 440 _NOEXCEPT_((is_nothrow_constructible<first_type, _U1>::value && 441 is_nothrow_constructible<second_type, _U2>::value)) 442 : first(_VSTD::forward<_U1>(__u1)), second(_VSTD::forward<_U2>(__u2)) {} 443 444 template<class _U1, class _U2, _EnableB< 445 _CheckArgs::template __enable_implicit<_U1, _U2>() 446 > = false> 447 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 448 pair(_U1&& __u1, _U2&& __u2) 449 _NOEXCEPT_((is_nothrow_constructible<first_type, _U1>::value && 450 is_nothrow_constructible<second_type, _U2>::value)) 451 : first(_VSTD::forward<_U1>(__u1)), second(_VSTD::forward<_U2>(__u2)) {} 452 453 template<class _U1, class _U2, _EnableB< 454 _CheckArgs::template __enable_explicit<_U1 const&, _U2 const&>() 455 > = false> 456 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 457 explicit pair(pair<_U1, _U2> const& __p) 458 _NOEXCEPT_((is_nothrow_constructible<first_type, _U1 const&>::value && 459 is_nothrow_constructible<second_type, _U2 const&>::value)) 460 : first(__p.first), second(__p.second) {} 461 462 template<class _U1, class _U2, _EnableB< 463 _CheckArgs::template __enable_implicit<_U1 const&, _U2 const&>() 464 > = false> 465 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 466 pair(pair<_U1, _U2> const& __p) 467 _NOEXCEPT_((is_nothrow_constructible<first_type, _U1 const&>::value && 468 is_nothrow_constructible<second_type, _U2 const&>::value)) 469 : first(__p.first), second(__p.second) {} 470 471 template<class _U1, class _U2, _EnableB< 472 _CheckArgs::template __enable_explicit<_U1, _U2>() 473 > = false> 474 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 475 explicit pair(pair<_U1, _U2>&&__p) 476 _NOEXCEPT_((is_nothrow_constructible<first_type, _U1&&>::value && 477 is_nothrow_constructible<second_type, _U2&&>::value)) 478 : first(_VSTD::forward<_U1>(__p.first)), second(_VSTD::forward<_U2>(__p.second)) {} 479 480 template<class _U1, class _U2, _EnableB< 481 _CheckArgs::template __enable_implicit<_U1, _U2>() 482 > = false> 483 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 484 pair(pair<_U1, _U2>&& __p) 485 _NOEXCEPT_((is_nothrow_constructible<first_type, _U1&&>::value && 486 is_nothrow_constructible<second_type, _U2&&>::value)) 487 : first(_VSTD::forward<_U1>(__p.first)), second(_VSTD::forward<_U2>(__p.second)) {} 488 489 template<class _Tuple, _EnableB< 490 _CheckTLC<_Tuple>::template __enable_explicit<_Tuple>() 491 > = false> 492 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 493 explicit pair(_Tuple&& __p) 494 : first(_VSTD::get<0>(_VSTD::forward<_Tuple>(__p))), 495 second(_VSTD::get<1>(_VSTD::forward<_Tuple>(__p))) {} 496 497 template<class _Tuple, _EnableB< 498 _CheckTLC<_Tuple>::template __enable_implicit<_Tuple>() 499 > = false> 500 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 501 pair(_Tuple&& __p) 502 : first(_VSTD::get<0>(_VSTD::forward<_Tuple>(__p))), 503 second(_VSTD::get<1>(_VSTD::forward<_Tuple>(__p))) {} 504 505 template <class... _Args1, class... _Args2> 506 _LIBCPP_INLINE_VISIBILITY 507 pair(piecewise_construct_t __pc, 508 tuple<_Args1...> __first_args, tuple<_Args2...> __second_args) 509 _NOEXCEPT_((is_nothrow_constructible<first_type, _Args1...>::value && 510 is_nothrow_constructible<second_type, _Args2...>::value)) 511 : pair(__pc, __first_args, __second_args, 512 typename __make_tuple_indices<sizeof...(_Args1)>::type(), 513 typename __make_tuple_indices<sizeof...(_Args2) >::type()) {} 514 515 _LIBCPP_INLINE_VISIBILITY 516 pair& operator=(typename conditional< 517 is_copy_assignable<first_type>::value && 518 is_copy_assignable<second_type>::value, 519 pair, __nat>::type const& __p) 520 _NOEXCEPT_(is_nothrow_copy_assignable<first_type>::value && 521 is_nothrow_copy_assignable<second_type>::value) 522 { 523 first = __p.first; 524 second = __p.second; 525 return *this; 526 } 527 528 _LIBCPP_INLINE_VISIBILITY 529 pair& operator=(typename conditional< 530 is_move_assignable<first_type>::value && 531 is_move_assignable<second_type>::value, 532 pair, __nat>::type&& __p) 533 _NOEXCEPT_(is_nothrow_move_assignable<first_type>::value && 534 is_nothrow_move_assignable<second_type>::value) 535 { 536 first = _VSTD::forward<first_type>(__p.first); 537 second = _VSTD::forward<second_type>(__p.second); 538 return *this; 539 } 540 541 template <class _Tuple, _EnableB< 542 _CheckTLC<_Tuple>::template __enable_assign<_Tuple>() 543 > = false> 544 _LIBCPP_INLINE_VISIBILITY 545 pair& operator=(_Tuple&& __p) { 546 first = _VSTD::get<0>(_VSTD::forward<_Tuple>(__p)); 547 second = _VSTD::get<1>(_VSTD::forward<_Tuple>(__p)); 548 return *this; 549 } 550 #endif 551 552 _LIBCPP_INLINE_VISIBILITY 553 void 554 swap(pair& __p) _NOEXCEPT_(__is_nothrow_swappable<first_type>::value && 555 __is_nothrow_swappable<second_type>::value) 556 { 557 using _VSTD::swap; 558 swap(first, __p.first); 559 swap(second, __p.second); 560 } 561 private: 562 563 #ifndef _LIBCPP_CXX03_LANG 564 template <class... _Args1, class... _Args2, size_t... _I1, size_t... _I2> 565 _LIBCPP_INLINE_VISIBILITY 566 pair(piecewise_construct_t, 567 tuple<_Args1...>& __first_args, tuple<_Args2...>& __second_args, 568 __tuple_indices<_I1...>, __tuple_indices<_I2...>); 569 #endif 570 }; 571 572 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 573 template<class _T1, class _T2> 574 pair(_T1, _T2) -> pair<_T1, _T2>; 575 #endif // _LIBCPP_HAS_NO_DEDUCTION_GUIDES 576 577 template <class _T1, class _T2> 578 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 579 bool 580 operator==(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 581 { 582 return __x.first == __y.first && __x.second == __y.second; 583 } 584 585 template <class _T1, class _T2> 586 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 587 bool 588 operator!=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 589 { 590 return !(__x == __y); 591 } 592 593 template <class _T1, class _T2> 594 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 595 bool 596 operator< (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 597 { 598 return __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second); 599 } 600 601 template <class _T1, class _T2> 602 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 603 bool 604 operator> (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 605 { 606 return __y < __x; 607 } 608 609 template <class _T1, class _T2> 610 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 611 bool 612 operator>=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 613 { 614 return !(__x < __y); 615 } 616 617 template <class _T1, class _T2> 618 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 619 bool 620 operator<=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 621 { 622 return !(__y < __x); 623 } 624 625 template <class _T1, class _T2> 626 inline _LIBCPP_INLINE_VISIBILITY 627 typename enable_if 628 < 629 __is_swappable<_T1>::value && 630 __is_swappable<_T2>::value, 631 void 632 >::type 633 swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y) 634 _NOEXCEPT_((__is_nothrow_swappable<_T1>::value && 635 __is_nothrow_swappable<_T2>::value)) 636 { 637 __x.swap(__y); 638 } 639 640 template <class _Tp> 641 struct __unwrap_reference { typedef _Tp type; }; 642 643 template <class _Tp> 644 struct __unwrap_reference<reference_wrapper<_Tp> > { typedef _Tp& type; }; 645 646 #if _LIBCPP_STD_VER > 17 647 template <class _Tp> 648 struct unwrap_reference : __unwrap_reference<_Tp> { }; 649 650 template <class _Tp> 651 struct unwrap_ref_decay : unwrap_reference<typename decay<_Tp>::type> { }; 652 #endif // > C++17 653 654 template <class _Tp> 655 struct __unwrap_ref_decay 656 #if _LIBCPP_STD_VER > 17 657 : unwrap_ref_decay<_Tp> 658 #else 659 : __unwrap_reference<typename decay<_Tp>::type> 660 #endif 661 { }; 662 663 #ifndef _LIBCPP_CXX03_LANG 664 665 template <class _T1, class _T2> 666 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 667 pair<typename __unwrap_ref_decay<_T1>::type, typename __unwrap_ref_decay<_T2>::type> 668 make_pair(_T1&& __t1, _T2&& __t2) 669 { 670 return pair<typename __unwrap_ref_decay<_T1>::type, typename __unwrap_ref_decay<_T2>::type> 671 (_VSTD::forward<_T1>(__t1), _VSTD::forward<_T2>(__t2)); 672 } 673 674 #else // _LIBCPP_CXX03_LANG 675 676 template <class _T1, class _T2> 677 inline _LIBCPP_INLINE_VISIBILITY 678 pair<_T1,_T2> 679 make_pair(_T1 __x, _T2 __y) 680 { 681 return pair<_T1, _T2>(__x, __y); 682 } 683 684 #endif // _LIBCPP_CXX03_LANG 685 686 template <class _T1, class _T2> 687 struct _LIBCPP_TEMPLATE_VIS tuple_size<pair<_T1, _T2> > 688 : public integral_constant<size_t, 2> {}; 689 690 template <size_t _Ip, class _T1, class _T2> 691 class _LIBCPP_TEMPLATE_VIS tuple_element<_Ip, pair<_T1, _T2> > 692 { 693 static_assert(_Ip < 2, "Index out of bounds in std::tuple_element<std::pair<T1, T2>>"); 694 }; 695 696 template <class _T1, class _T2> 697 class _LIBCPP_TEMPLATE_VIS tuple_element<0, pair<_T1, _T2> > 698 { 699 public: 700 typedef _T1 type; 701 }; 702 703 template <class _T1, class _T2> 704 class _LIBCPP_TEMPLATE_VIS tuple_element<1, pair<_T1, _T2> > 705 { 706 public: 707 typedef _T2 type; 708 }; 709 710 template <size_t _Ip> struct __get_pair; 711 712 template <> 713 struct __get_pair<0> 714 { 715 template <class _T1, class _T2> 716 static 717 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 718 _T1& 719 get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;} 720 721 template <class _T1, class _T2> 722 static 723 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 724 const _T1& 725 get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;} 726 727 #ifndef _LIBCPP_CXX03_LANG 728 template <class _T1, class _T2> 729 static 730 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 731 _T1&& 732 get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T1>(__p.first);} 733 734 template <class _T1, class _T2> 735 static 736 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 737 const _T1&& 738 get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<const _T1>(__p.first);} 739 #endif // _LIBCPP_CXX03_LANG 740 }; 741 742 template <> 743 struct __get_pair<1> 744 { 745 template <class _T1, class _T2> 746 static 747 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 748 _T2& 749 get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;} 750 751 template <class _T1, class _T2> 752 static 753 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 754 const _T2& 755 get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;} 756 757 #ifndef _LIBCPP_CXX03_LANG 758 template <class _T1, class _T2> 759 static 760 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 761 _T2&& 762 get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T2>(__p.second);} 763 764 template <class _T1, class _T2> 765 static 766 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 767 const _T2&& 768 get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<const _T2>(__p.second);} 769 #endif // _LIBCPP_CXX03_LANG 770 }; 771 772 template <size_t _Ip, class _T1, class _T2> 773 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 774 typename tuple_element<_Ip, pair<_T1, _T2> >::type& 775 get(pair<_T1, _T2>& __p) _NOEXCEPT 776 { 777 return __get_pair<_Ip>::get(__p); 778 } 779 780 template <size_t _Ip, class _T1, class _T2> 781 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 782 const typename tuple_element<_Ip, pair<_T1, _T2> >::type& 783 get(const pair<_T1, _T2>& __p) _NOEXCEPT 784 { 785 return __get_pair<_Ip>::get(__p); 786 } 787 788 #ifndef _LIBCPP_CXX03_LANG 789 template <size_t _Ip, class _T1, class _T2> 790 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 791 typename tuple_element<_Ip, pair<_T1, _T2> >::type&& 792 get(pair<_T1, _T2>&& __p) _NOEXCEPT 793 { 794 return __get_pair<_Ip>::get(_VSTD::move(__p)); 795 } 796 797 template <size_t _Ip, class _T1, class _T2> 798 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 799 const typename tuple_element<_Ip, pair<_T1, _T2> >::type&& 800 get(const pair<_T1, _T2>&& __p) _NOEXCEPT 801 { 802 return __get_pair<_Ip>::get(_VSTD::move(__p)); 803 } 804 #endif // _LIBCPP_CXX03_LANG 805 806 #if _LIBCPP_STD_VER > 11 807 template <class _T1, class _T2> 808 inline _LIBCPP_INLINE_VISIBILITY 809 constexpr _T1 & get(pair<_T1, _T2>& __p) _NOEXCEPT 810 { 811 return __get_pair<0>::get(__p); 812 } 813 814 template <class _T1, class _T2> 815 inline _LIBCPP_INLINE_VISIBILITY 816 constexpr _T1 const & get(pair<_T1, _T2> const& __p) _NOEXCEPT 817 { 818 return __get_pair<0>::get(__p); 819 } 820 821 template <class _T1, class _T2> 822 inline _LIBCPP_INLINE_VISIBILITY 823 constexpr _T1 && get(pair<_T1, _T2>&& __p) _NOEXCEPT 824 { 825 return __get_pair<0>::get(_VSTD::move(__p)); 826 } 827 828 template <class _T1, class _T2> 829 inline _LIBCPP_INLINE_VISIBILITY 830 constexpr _T1 const && get(pair<_T1, _T2> const&& __p) _NOEXCEPT 831 { 832 return __get_pair<0>::get(_VSTD::move(__p)); 833 } 834 835 template <class _T1, class _T2> 836 inline _LIBCPP_INLINE_VISIBILITY 837 constexpr _T1 & get(pair<_T2, _T1>& __p) _NOEXCEPT 838 { 839 return __get_pair<1>::get(__p); 840 } 841 842 template <class _T1, class _T2> 843 inline _LIBCPP_INLINE_VISIBILITY 844 constexpr _T1 const & get(pair<_T2, _T1> const& __p) _NOEXCEPT 845 { 846 return __get_pair<1>::get(__p); 847 } 848 849 template <class _T1, class _T2> 850 inline _LIBCPP_INLINE_VISIBILITY 851 constexpr _T1 && get(pair<_T2, _T1>&& __p) _NOEXCEPT 852 { 853 return __get_pair<1>::get(_VSTD::move(__p)); 854 } 855 856 template <class _T1, class _T2> 857 inline _LIBCPP_INLINE_VISIBILITY 858 constexpr _T1 const && get(pair<_T2, _T1> const&& __p) _NOEXCEPT 859 { 860 return __get_pair<1>::get(_VSTD::move(__p)); 861 } 862 863 #endif 864 865 #if _LIBCPP_STD_VER > 11 866 867 template<class _Tp, _Tp... _Ip> 868 struct _LIBCPP_TEMPLATE_VIS integer_sequence 869 { 870 typedef _Tp value_type; 871 static_assert( is_integral<_Tp>::value, 872 "std::integer_sequence can only be instantiated with an integral type" ); 873 static 874 _LIBCPP_INLINE_VISIBILITY 875 constexpr 876 size_t 877 size() noexcept { return sizeof...(_Ip); } 878 }; 879 880 template<size_t... _Ip> 881 using index_sequence = integer_sequence<size_t, _Ip...>; 882 883 #if __has_builtin(__make_integer_seq) && !defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE) 884 885 template <class _Tp, _Tp _Ep> 886 using __make_integer_sequence = __make_integer_seq<integer_sequence, _Tp, _Ep>; 887 888 #else 889 890 template<typename _Tp, _Tp _Np> using __make_integer_sequence_unchecked = 891 typename __detail::__make<_Np>::type::template __convert<integer_sequence, _Tp>; 892 893 template <class _Tp, _Tp _Ep> 894 struct __make_integer_sequence_checked 895 { 896 static_assert(is_integral<_Tp>::value, 897 "std::make_integer_sequence can only be instantiated with an integral type" ); 898 static_assert(0 <= _Ep, "std::make_integer_sequence must have a non-negative sequence length"); 899 // Workaround GCC bug by preventing bad installations when 0 <= _Ep 900 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68929 901 typedef __make_integer_sequence_unchecked<_Tp, 0 <= _Ep ? _Ep : 0> type; 902 }; 903 904 template <class _Tp, _Tp _Ep> 905 using __make_integer_sequence = typename __make_integer_sequence_checked<_Tp, _Ep>::type; 906 907 #endif 908 909 template<class _Tp, _Tp _Np> 910 using make_integer_sequence = __make_integer_sequence<_Tp, _Np>; 911 912 template<size_t _Np> 913 using make_index_sequence = make_integer_sequence<size_t, _Np>; 914 915 template<class... _Tp> 916 using index_sequence_for = make_index_sequence<sizeof...(_Tp)>; 917 918 #endif // _LIBCPP_STD_VER > 11 919 920 #if _LIBCPP_STD_VER > 11 921 template<class _T1, class _T2 = _T1> 922 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 923 _T1 exchange(_T1& __obj, _T2 && __new_value) 924 { 925 _T1 __old_value = _VSTD::move(__obj); 926 __obj = _VSTD::forward<_T2>(__new_value); 927 return __old_value; 928 } 929 #endif // _LIBCPP_STD_VER > 11 930 931 #if _LIBCPP_STD_VER > 14 932 933 struct _LIBCPP_TYPE_VIS in_place_t { 934 explicit in_place_t() = default; 935 }; 936 _LIBCPP_INLINE_VAR constexpr in_place_t in_place{}; 937 938 template <class _Tp> 939 struct _LIBCPP_TEMPLATE_VIS in_place_type_t { 940 explicit in_place_type_t() = default; 941 }; 942 template <class _Tp> 943 _LIBCPP_INLINE_VAR constexpr in_place_type_t<_Tp> in_place_type{}; 944 945 template <size_t _Idx> 946 struct _LIBCPP_TYPE_VIS in_place_index_t { 947 explicit in_place_index_t() = default; 948 }; 949 template <size_t _Idx> 950 _LIBCPP_INLINE_VAR constexpr in_place_index_t<_Idx> in_place_index{}; 951 952 template <class _Tp> struct __is_inplace_type_imp : false_type {}; 953 template <class _Tp> struct __is_inplace_type_imp<in_place_type_t<_Tp>> : true_type {}; 954 955 template <class _Tp> 956 using __is_inplace_type = __is_inplace_type_imp<__uncvref_t<_Tp>>; 957 958 template <class _Tp> struct __is_inplace_index_imp : false_type {}; 959 template <size_t _Idx> struct __is_inplace_index_imp<in_place_index_t<_Idx>> : true_type {}; 960 961 template <class _Tp> 962 using __is_inplace_index = __is_inplace_index_imp<__uncvref_t<_Tp>>; 963 964 #endif // _LIBCPP_STD_VER > 14 965 966 template <class _Arg, class _Result> 967 struct _LIBCPP_TEMPLATE_VIS unary_function 968 { 969 typedef _Arg argument_type; 970 typedef _Result result_type; 971 }; 972 973 template <class _Size> 974 inline _LIBCPP_INLINE_VISIBILITY 975 _Size 976 __loadword(const void* __p) 977 { 978 _Size __r; 979 std::memcpy(&__r, __p, sizeof(__r)); 980 return __r; 981 } 982 983 // We use murmur2 when size_t is 32 bits, and cityhash64 when size_t 984 // is 64 bits. This is because cityhash64 uses 64bit x 64bit 985 // multiplication, which can be very slow on 32-bit systems. 986 template <class _Size, size_t = sizeof(_Size)*__CHAR_BIT__> 987 struct __murmur2_or_cityhash; 988 989 template <class _Size> 990 struct __murmur2_or_cityhash<_Size, 32> 991 { 992 inline _Size operator()(const void* __key, _Size __len) 993 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK; 994 }; 995 996 // murmur2 997 template <class _Size> 998 _Size 999 __murmur2_or_cityhash<_Size, 32>::operator()(const void* __key, _Size __len) 1000 { 1001 const _Size __m = 0x5bd1e995; 1002 const _Size __r = 24; 1003 _Size __h = __len; 1004 const unsigned char* __data = static_cast<const unsigned char*>(__key); 1005 for (; __len >= 4; __data += 4, __len -= 4) 1006 { 1007 _Size __k = __loadword<_Size>(__data); 1008 __k *= __m; 1009 __k ^= __k >> __r; 1010 __k *= __m; 1011 __h *= __m; 1012 __h ^= __k; 1013 } 1014 switch (__len) 1015 { 1016 case 3: 1017 __h ^= __data[2] << 16; 1018 _LIBCPP_FALLTHROUGH(); 1019 case 2: 1020 __h ^= __data[1] << 8; 1021 _LIBCPP_FALLTHROUGH(); 1022 case 1: 1023 __h ^= __data[0]; 1024 __h *= __m; 1025 } 1026 __h ^= __h >> 13; 1027 __h *= __m; 1028 __h ^= __h >> 15; 1029 return __h; 1030 } 1031 1032 template <class _Size> 1033 struct __murmur2_or_cityhash<_Size, 64> 1034 { 1035 inline _Size operator()(const void* __key, _Size __len) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK; 1036 1037 private: 1038 // Some primes between 2^63 and 2^64. 1039 static const _Size __k0 = 0xc3a5c85c97cb3127ULL; 1040 static const _Size __k1 = 0xb492b66fbe98f273ULL; 1041 static const _Size __k2 = 0x9ae16a3b2f90404fULL; 1042 static const _Size __k3 = 0xc949d7c7509e6557ULL; 1043 1044 static _Size __rotate(_Size __val, int __shift) { 1045 return __shift == 0 ? __val : ((__val >> __shift) | (__val << (64 - __shift))); 1046 } 1047 1048 static _Size __rotate_by_at_least_1(_Size __val, int __shift) { 1049 return (__val >> __shift) | (__val << (64 - __shift)); 1050 } 1051 1052 static _Size __shift_mix(_Size __val) { 1053 return __val ^ (__val >> 47); 1054 } 1055 1056 static _Size __hash_len_16(_Size __u, _Size __v) 1057 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1058 { 1059 const _Size __mul = 0x9ddfea08eb382d69ULL; 1060 _Size __a = (__u ^ __v) * __mul; 1061 __a ^= (__a >> 47); 1062 _Size __b = (__v ^ __a) * __mul; 1063 __b ^= (__b >> 47); 1064 __b *= __mul; 1065 return __b; 1066 } 1067 1068 static _Size __hash_len_0_to_16(const char* __s, _Size __len) 1069 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1070 { 1071 if (__len > 8) { 1072 const _Size __a = __loadword<_Size>(__s); 1073 const _Size __b = __loadword<_Size>(__s + __len - 8); 1074 return __hash_len_16(__a, __rotate_by_at_least_1(__b + __len, __len)) ^ __b; 1075 } 1076 if (__len >= 4) { 1077 const uint32_t __a = __loadword<uint32_t>(__s); 1078 const uint32_t __b = __loadword<uint32_t>(__s + __len - 4); 1079 return __hash_len_16(__len + (__a << 3), __b); 1080 } 1081 if (__len > 0) { 1082 const unsigned char __a = __s[0]; 1083 const unsigned char __b = __s[__len >> 1]; 1084 const unsigned char __c = __s[__len - 1]; 1085 const uint32_t __y = static_cast<uint32_t>(__a) + 1086 (static_cast<uint32_t>(__b) << 8); 1087 const uint32_t __z = __len + (static_cast<uint32_t>(__c) << 2); 1088 return __shift_mix(__y * __k2 ^ __z * __k3) * __k2; 1089 } 1090 return __k2; 1091 } 1092 1093 static _Size __hash_len_17_to_32(const char *__s, _Size __len) 1094 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1095 { 1096 const _Size __a = __loadword<_Size>(__s) * __k1; 1097 const _Size __b = __loadword<_Size>(__s + 8); 1098 const _Size __c = __loadword<_Size>(__s + __len - 8) * __k2; 1099 const _Size __d = __loadword<_Size>(__s + __len - 16) * __k0; 1100 return __hash_len_16(__rotate(__a - __b, 43) + __rotate(__c, 30) + __d, 1101 __a + __rotate(__b ^ __k3, 20) - __c + __len); 1102 } 1103 1104 // Return a 16-byte hash for 48 bytes. Quick and dirty. 1105 // Callers do best to use "random-looking" values for a and b. 1106 static pair<_Size, _Size> __weak_hash_len_32_with_seeds( 1107 _Size __w, _Size __x, _Size __y, _Size __z, _Size __a, _Size __b) 1108 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1109 { 1110 __a += __w; 1111 __b = __rotate(__b + __a + __z, 21); 1112 const _Size __c = __a; 1113 __a += __x; 1114 __a += __y; 1115 __b += __rotate(__a, 44); 1116 return pair<_Size, _Size>(__a + __z, __b + __c); 1117 } 1118 1119 // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. 1120 static pair<_Size, _Size> __weak_hash_len_32_with_seeds( 1121 const char* __s, _Size __a, _Size __b) 1122 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1123 { 1124 return __weak_hash_len_32_with_seeds(__loadword<_Size>(__s), 1125 __loadword<_Size>(__s + 8), 1126 __loadword<_Size>(__s + 16), 1127 __loadword<_Size>(__s + 24), 1128 __a, 1129 __b); 1130 } 1131 1132 // Return an 8-byte hash for 33 to 64 bytes. 1133 static _Size __hash_len_33_to_64(const char *__s, size_t __len) 1134 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1135 { 1136 _Size __z = __loadword<_Size>(__s + 24); 1137 _Size __a = __loadword<_Size>(__s) + 1138 (__len + __loadword<_Size>(__s + __len - 16)) * __k0; 1139 _Size __b = __rotate(__a + __z, 52); 1140 _Size __c = __rotate(__a, 37); 1141 __a += __loadword<_Size>(__s + 8); 1142 __c += __rotate(__a, 7); 1143 __a += __loadword<_Size>(__s + 16); 1144 _Size __vf = __a + __z; 1145 _Size __vs = __b + __rotate(__a, 31) + __c; 1146 __a = __loadword<_Size>(__s + 16) + __loadword<_Size>(__s + __len - 32); 1147 __z += __loadword<_Size>(__s + __len - 8); 1148 __b = __rotate(__a + __z, 52); 1149 __c = __rotate(__a, 37); 1150 __a += __loadword<_Size>(__s + __len - 24); 1151 __c += __rotate(__a, 7); 1152 __a += __loadword<_Size>(__s + __len - 16); 1153 _Size __wf = __a + __z; 1154 _Size __ws = __b + __rotate(__a, 31) + __c; 1155 _Size __r = __shift_mix((__vf + __ws) * __k2 + (__wf + __vs) * __k0); 1156 return __shift_mix(__r * __k0 + __vs) * __k2; 1157 } 1158 }; 1159 1160 // cityhash64 1161 template <class _Size> 1162 _Size 1163 __murmur2_or_cityhash<_Size, 64>::operator()(const void* __key, _Size __len) 1164 { 1165 const char* __s = static_cast<const char*>(__key); 1166 if (__len <= 32) { 1167 if (__len <= 16) { 1168 return __hash_len_0_to_16(__s, __len); 1169 } else { 1170 return __hash_len_17_to_32(__s, __len); 1171 } 1172 } else if (__len <= 64) { 1173 return __hash_len_33_to_64(__s, __len); 1174 } 1175 1176 // For strings over 64 bytes we hash the end first, and then as we 1177 // loop we keep 56 bytes of state: v, w, x, y, and z. 1178 _Size __x = __loadword<_Size>(__s + __len - 40); 1179 _Size __y = __loadword<_Size>(__s + __len - 16) + 1180 __loadword<_Size>(__s + __len - 56); 1181 _Size __z = __hash_len_16(__loadword<_Size>(__s + __len - 48) + __len, 1182 __loadword<_Size>(__s + __len - 24)); 1183 pair<_Size, _Size> __v = __weak_hash_len_32_with_seeds(__s + __len - 64, __len, __z); 1184 pair<_Size, _Size> __w = __weak_hash_len_32_with_seeds(__s + __len - 32, __y + __k1, __x); 1185 __x = __x * __k1 + __loadword<_Size>(__s); 1186 1187 // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks. 1188 __len = (__len - 1) & ~static_cast<_Size>(63); 1189 do { 1190 __x = __rotate(__x + __y + __v.first + __loadword<_Size>(__s + 8), 37) * __k1; 1191 __y = __rotate(__y + __v.second + __loadword<_Size>(__s + 48), 42) * __k1; 1192 __x ^= __w.second; 1193 __y += __v.first + __loadword<_Size>(__s + 40); 1194 __z = __rotate(__z + __w.first, 33) * __k1; 1195 __v = __weak_hash_len_32_with_seeds(__s, __v.second * __k1, __x + __w.first); 1196 __w = __weak_hash_len_32_with_seeds(__s + 32, __z + __w.second, 1197 __y + __loadword<_Size>(__s + 16)); 1198 std::swap(__z, __x); 1199 __s += 64; 1200 __len -= 64; 1201 } while (__len != 0); 1202 return __hash_len_16( 1203 __hash_len_16(__v.first, __w.first) + __shift_mix(__y) * __k1 + __z, 1204 __hash_len_16(__v.second, __w.second) + __x); 1205 } 1206 1207 template <class _Tp, size_t = sizeof(_Tp) / sizeof(size_t)> 1208 struct __scalar_hash; 1209 1210 template <class _Tp> 1211 struct __scalar_hash<_Tp, 0> 1212 : public unary_function<_Tp, size_t> 1213 { 1214 _LIBCPP_INLINE_VISIBILITY 1215 size_t operator()(_Tp __v) const _NOEXCEPT 1216 { 1217 union 1218 { 1219 _Tp __t; 1220 size_t __a; 1221 } __u; 1222 __u.__a = 0; 1223 __u.__t = __v; 1224 return __u.__a; 1225 } 1226 }; 1227 1228 template <class _Tp> 1229 struct __scalar_hash<_Tp, 1> 1230 : public unary_function<_Tp, size_t> 1231 { 1232 _LIBCPP_INLINE_VISIBILITY 1233 size_t operator()(_Tp __v) const _NOEXCEPT 1234 { 1235 union 1236 { 1237 _Tp __t; 1238 size_t __a; 1239 } __u; 1240 __u.__t = __v; 1241 return __u.__a; 1242 } 1243 }; 1244 1245 template <class _Tp> 1246 struct __scalar_hash<_Tp, 2> 1247 : public unary_function<_Tp, size_t> 1248 { 1249 _LIBCPP_INLINE_VISIBILITY 1250 size_t operator()(_Tp __v) const _NOEXCEPT 1251 { 1252 union 1253 { 1254 _Tp __t; 1255 struct 1256 { 1257 size_t __a; 1258 size_t __b; 1259 } __s; 1260 } __u; 1261 __u.__t = __v; 1262 return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u)); 1263 } 1264 }; 1265 1266 template <class _Tp> 1267 struct __scalar_hash<_Tp, 3> 1268 : public unary_function<_Tp, size_t> 1269 { 1270 _LIBCPP_INLINE_VISIBILITY 1271 size_t operator()(_Tp __v) const _NOEXCEPT 1272 { 1273 union 1274 { 1275 _Tp __t; 1276 struct 1277 { 1278 size_t __a; 1279 size_t __b; 1280 size_t __c; 1281 } __s; 1282 } __u; 1283 __u.__t = __v; 1284 return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u)); 1285 } 1286 }; 1287 1288 template <class _Tp> 1289 struct __scalar_hash<_Tp, 4> 1290 : public unary_function<_Tp, size_t> 1291 { 1292 _LIBCPP_INLINE_VISIBILITY 1293 size_t operator()(_Tp __v) const _NOEXCEPT 1294 { 1295 union 1296 { 1297 _Tp __t; 1298 struct 1299 { 1300 size_t __a; 1301 size_t __b; 1302 size_t __c; 1303 size_t __d; 1304 } __s; 1305 } __u; 1306 __u.__t = __v; 1307 return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u)); 1308 } 1309 }; 1310 1311 struct _PairT { 1312 size_t first; 1313 size_t second; 1314 }; 1315 1316 _LIBCPP_INLINE_VISIBILITY 1317 inline size_t __hash_combine(size_t __lhs, size_t __rhs) _NOEXCEPT { 1318 typedef __scalar_hash<_PairT> _HashT; 1319 const _PairT __p = {__lhs, __rhs}; 1320 return _HashT()(__p); 1321 } 1322 1323 template<class _Tp> 1324 struct _LIBCPP_TEMPLATE_VIS hash<_Tp*> 1325 : public unary_function<_Tp*, size_t> 1326 { 1327 _LIBCPP_INLINE_VISIBILITY 1328 size_t operator()(_Tp* __v) const _NOEXCEPT 1329 { 1330 union 1331 { 1332 _Tp* __t; 1333 size_t __a; 1334 } __u; 1335 __u.__t = __v; 1336 return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u)); 1337 } 1338 }; 1339 1340 1341 template <> 1342 struct _LIBCPP_TEMPLATE_VIS hash<bool> 1343 : public unary_function<bool, size_t> 1344 { 1345 _LIBCPP_INLINE_VISIBILITY 1346 size_t operator()(bool __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1347 }; 1348 1349 template <> 1350 struct _LIBCPP_TEMPLATE_VIS hash<char> 1351 : public unary_function<char, size_t> 1352 { 1353 _LIBCPP_INLINE_VISIBILITY 1354 size_t operator()(char __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1355 }; 1356 1357 template <> 1358 struct _LIBCPP_TEMPLATE_VIS hash<signed char> 1359 : public unary_function<signed char, size_t> 1360 { 1361 _LIBCPP_INLINE_VISIBILITY 1362 size_t operator()(signed char __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1363 }; 1364 1365 template <> 1366 struct _LIBCPP_TEMPLATE_VIS hash<unsigned char> 1367 : public unary_function<unsigned char, size_t> 1368 { 1369 _LIBCPP_INLINE_VISIBILITY 1370 size_t operator()(unsigned char __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1371 }; 1372 1373 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS 1374 1375 template <> 1376 struct _LIBCPP_TEMPLATE_VIS hash<char16_t> 1377 : public unary_function<char16_t, size_t> 1378 { 1379 _LIBCPP_INLINE_VISIBILITY 1380 size_t operator()(char16_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1381 }; 1382 1383 template <> 1384 struct _LIBCPP_TEMPLATE_VIS hash<char32_t> 1385 : public unary_function<char32_t, size_t> 1386 { 1387 _LIBCPP_INLINE_VISIBILITY 1388 size_t operator()(char32_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1389 }; 1390 1391 #endif // _LIBCPP_HAS_NO_UNICODE_CHARS 1392 1393 template <> 1394 struct _LIBCPP_TEMPLATE_VIS hash<wchar_t> 1395 : public unary_function<wchar_t, size_t> 1396 { 1397 _LIBCPP_INLINE_VISIBILITY 1398 size_t operator()(wchar_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1399 }; 1400 1401 template <> 1402 struct _LIBCPP_TEMPLATE_VIS hash<short> 1403 : public unary_function<short, size_t> 1404 { 1405 _LIBCPP_INLINE_VISIBILITY 1406 size_t operator()(short __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1407 }; 1408 1409 template <> 1410 struct _LIBCPP_TEMPLATE_VIS hash<unsigned short> 1411 : public unary_function<unsigned short, size_t> 1412 { 1413 _LIBCPP_INLINE_VISIBILITY 1414 size_t operator()(unsigned short __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1415 }; 1416 1417 template <> 1418 struct _LIBCPP_TEMPLATE_VIS hash<int> 1419 : public unary_function<int, size_t> 1420 { 1421 _LIBCPP_INLINE_VISIBILITY 1422 size_t operator()(int __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1423 }; 1424 1425 template <> 1426 struct _LIBCPP_TEMPLATE_VIS hash<unsigned int> 1427 : public unary_function<unsigned int, size_t> 1428 { 1429 _LIBCPP_INLINE_VISIBILITY 1430 size_t operator()(unsigned int __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1431 }; 1432 1433 template <> 1434 struct _LIBCPP_TEMPLATE_VIS hash<long> 1435 : public unary_function<long, size_t> 1436 { 1437 _LIBCPP_INLINE_VISIBILITY 1438 size_t operator()(long __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1439 }; 1440 1441 template <> 1442 struct _LIBCPP_TEMPLATE_VIS hash<unsigned long> 1443 : public unary_function<unsigned long, size_t> 1444 { 1445 _LIBCPP_INLINE_VISIBILITY 1446 size_t operator()(unsigned long __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1447 }; 1448 1449 template <> 1450 struct _LIBCPP_TEMPLATE_VIS hash<long long> 1451 : public __scalar_hash<long long> 1452 { 1453 }; 1454 1455 template <> 1456 struct _LIBCPP_TEMPLATE_VIS hash<unsigned long long> 1457 : public __scalar_hash<unsigned long long> 1458 { 1459 }; 1460 1461 #ifndef _LIBCPP_HAS_NO_INT128 1462 1463 template <> 1464 struct _LIBCPP_TEMPLATE_VIS hash<__int128_t> 1465 : public __scalar_hash<__int128_t> 1466 { 1467 }; 1468 1469 template <> 1470 struct _LIBCPP_TEMPLATE_VIS hash<__uint128_t> 1471 : public __scalar_hash<__uint128_t> 1472 { 1473 }; 1474 1475 #endif 1476 1477 template <> 1478 struct _LIBCPP_TEMPLATE_VIS hash<float> 1479 : public __scalar_hash<float> 1480 { 1481 _LIBCPP_INLINE_VISIBILITY 1482 size_t operator()(float __v) const _NOEXCEPT 1483 { 1484 // -0.0 and 0.0 should return same hash 1485 if (__v == 0.0) 1486 return 0; 1487 return __scalar_hash<float>::operator()(__v); 1488 } 1489 }; 1490 1491 template <> 1492 struct _LIBCPP_TEMPLATE_VIS hash<double> 1493 : public __scalar_hash<double> 1494 { 1495 _LIBCPP_INLINE_VISIBILITY 1496 size_t operator()(double __v) const _NOEXCEPT 1497 { 1498 // -0.0 and 0.0 should return same hash 1499 if (__v == 0.0) 1500 return 0; 1501 return __scalar_hash<double>::operator()(__v); 1502 } 1503 }; 1504 1505 template <> 1506 struct _LIBCPP_TEMPLATE_VIS hash<long double> 1507 : public __scalar_hash<long double> 1508 { 1509 _LIBCPP_INLINE_VISIBILITY 1510 size_t operator()(long double __v) const _NOEXCEPT 1511 { 1512 // -0.0 and 0.0 should return same hash 1513 if (__v == 0.0) 1514 return 0; 1515 #if defined(__i386__) 1516 // Zero out padding bits 1517 union 1518 { 1519 long double __t; 1520 struct 1521 { 1522 size_t __a; 1523 size_t __b; 1524 size_t __c; 1525 size_t __d; 1526 } __s; 1527 } __u; 1528 __u.__s.__a = 0; 1529 __u.__s.__b = 0; 1530 __u.__s.__c = 0; 1531 __u.__s.__d = 0; 1532 __u.__t = __v; 1533 return __u.__s.__a ^ __u.__s.__b ^ __u.__s.__c ^ __u.__s.__d; 1534 #elif defined(__x86_64__) 1535 // Zero out padding bits 1536 union 1537 { 1538 long double __t; 1539 struct 1540 { 1541 size_t __a; 1542 size_t __b; 1543 } __s; 1544 } __u; 1545 __u.__s.__a = 0; 1546 __u.__s.__b = 0; 1547 __u.__t = __v; 1548 return __u.__s.__a ^ __u.__s.__b; 1549 #else 1550 return __scalar_hash<long double>::operator()(__v); 1551 #endif 1552 } 1553 }; 1554 1555 #if _LIBCPP_STD_VER > 11 1556 1557 template <class _Tp, bool = is_enum<_Tp>::value> 1558 struct _LIBCPP_TEMPLATE_VIS __enum_hash 1559 : public unary_function<_Tp, size_t> 1560 { 1561 _LIBCPP_INLINE_VISIBILITY 1562 size_t operator()(_Tp __v) const _NOEXCEPT 1563 { 1564 typedef typename underlying_type<_Tp>::type type; 1565 return hash<type>{}(static_cast<type>(__v)); 1566 } 1567 }; 1568 template <class _Tp> 1569 struct _LIBCPP_TEMPLATE_VIS __enum_hash<_Tp, false> { 1570 __enum_hash() = delete; 1571 __enum_hash(__enum_hash const&) = delete; 1572 __enum_hash& operator=(__enum_hash const&) = delete; 1573 }; 1574 1575 template <class _Tp> 1576 struct _LIBCPP_TEMPLATE_VIS hash : public __enum_hash<_Tp> 1577 { 1578 }; 1579 #endif 1580 1581 #if _LIBCPP_STD_VER > 14 1582 1583 template <> 1584 struct _LIBCPP_TEMPLATE_VIS hash<nullptr_t> 1585 : public unary_function<nullptr_t, size_t> 1586 { 1587 _LIBCPP_INLINE_VISIBILITY 1588 size_t operator()(nullptr_t) const _NOEXCEPT { 1589 return 662607004ull; 1590 } 1591 }; 1592 #endif 1593 1594 #ifndef _LIBCPP_CXX03_LANG 1595 template <class _Key, class _Hash> 1596 using __check_hash_requirements = integral_constant<bool, 1597 is_copy_constructible<_Hash>::value && 1598 is_move_constructible<_Hash>::value && 1599 __invokable_r<size_t, _Hash, _Key const&>::value 1600 >; 1601 1602 template <class _Key, class _Hash = std::hash<_Key> > 1603 using __has_enabled_hash = integral_constant<bool, 1604 __check_hash_requirements<_Key, _Hash>::value && 1605 is_default_constructible<_Hash>::value 1606 >; 1607 1608 #if _LIBCPP_STD_VER > 14 1609 template <class _Type, class> 1610 using __enable_hash_helper_imp = _Type; 1611 1612 template <class _Type, class ..._Keys> 1613 using __enable_hash_helper = __enable_hash_helper_imp<_Type, 1614 typename enable_if<__all<__has_enabled_hash<_Keys>::value...>::value>::type 1615 >; 1616 #else 1617 template <class _Type, class ...> 1618 using __enable_hash_helper = _Type; 1619 #endif 1620 1621 #endif // !_LIBCPP_CXX03_LANG 1622 1623 _LIBCPP_END_NAMESPACE_STD 1624 1625 #endif // _LIBCPP_UTILITY