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 19namespace std 20{ 21 22template <class T> 23 void 24 swap(T& a, T& b); 25 26namespace 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 34template<class T> 35void 36swap(T& a, T& b) noexcept(is_nothrow_move_constructible<T>::value && 37 is_nothrow_move_assignable<T>::value); 38 39template <class T, size_t N> 40void 41swap(T (&a)[N], T (&b)[N]) noexcept(noexcept(swap(*a, *b))); 42 43template <class T> T&& forward(typename remove_reference<T>::type& t) noexcept; // constexpr in C++14 44template <class T> T&& forward(typename remove_reference<T>::type&& t) noexcept; // constexpr in C++14 45 46template <class T> typename remove_reference<T>::type&& move(T&&) noexcept; // constexpr in C++14 47 48template <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 57template <class T> constexpr add_const_t<T>& as_const(T& t) noexcept; // C++17 58template <class T> void as_const(const T&&) = delete; // C++17 59 60template <class T> typename add_rvalue_reference<T>::type declval() noexcept; 61 62template <class T1, class T2> 63struct 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 91template <class T1, class T2> bool operator==(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 92template <class T1, class T2> bool operator!=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 93template <class T1, class T2> bool operator< (const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 94template <class T1, class T2> bool operator> (const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 95template <class T1, class T2> bool operator>=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 96template <class T1, class T2> bool operator<=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14 97 98template <class T1, class T2> pair<V1, V2> make_pair(T1&&, T2&&); // constexpr in C++14 99template <class T1, class T2> 100void 101swap(pair<T1, T2>& x, pair<T1, T2>& y) noexcept(noexcept(x.swap(y))); 102 103struct piecewise_construct_t { }; 104inline constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t(); 105 106template <class T> struct tuple_size; 107template <size_t I, class T> class tuple_element; 108 109template <class T1, class T2> struct tuple_size<pair<T1, T2> >; 110template <class T1, class T2> struct tuple_element<0, pair<T1, T2> >; 111template <class T1, class T2> struct tuple_element<1, pair<T1, T2> >; 112 113template<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 117template<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 121template<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 125template<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 129template<class T1, class T2> 130 constexpr T1& get(pair<T1, T2>&) noexcept; // C++14 131 132template<class T1, class T2> 133 constexpr const T1& get(const pair<T1, T2>&) noexcept; // C++14 134 135template<class T1, class T2> 136 constexpr T1&& get(pair<T1, T2>&&) noexcept; // C++14 137 138template<class T1, class T2> 139 constexpr const T1&& get(const pair<T1, T2>&&) noexcept; // C++14 140 141template<class T1, class T2> 142 constexpr T1& get(pair<T2, T1>&) noexcept; // C++14 143 144template<class T1, class T2> 145 constexpr const T1& get(const pair<T2, T1>&) noexcept; // C++14 146 147template<class T1, class T2> 148 constexpr T1&& get(pair<T2, T1>&&) noexcept; // C++14 149 150template<class T1, class T2> 151 constexpr const T1&& get(const pair<T2, T1>&&) noexcept; // C++14 152 153// C++14 154 155template<class T, T... I> 156struct integer_sequence 157{ 158 typedef T value_type; 159 160 static constexpr size_t size() noexcept; 161}; 162 163template<size_t... I> 164 using index_sequence = integer_sequence<size_t, I...>; 165 166template<class T, T N> 167 using make_integer_sequence = integer_sequence<T, 0, 1, ..., N-1>; 168template<size_t N> 169 using make_index_sequence = make_integer_sequence<size_t, N>; 170 171template<class... T> 172 using index_sequence_for = make_index_sequence<sizeof...(T)>; 173 174template<class T, class U=T> 175 T exchange(T& obj, U&& new_value); 176 177// 20.2.7, in-place construction // C++17 178struct in_place_t { 179 explicit in_place_t() = default; 180}; 181inline constexpr in_place_t in_place{}; 182template <class T> 183 struct in_place_type_t { 184 explicit in_place_type_t() = default; 185 }; 186template <class T> 187 inline constexpr in_place_type_t<T> in_place_type{}; 188template <size_t I> 189 struct in_place_index_t { 190 explicit in_place_index_t() = default; 191 }; 192template <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 215namespace rel_ops 216{ 217 218template<class _Tp> 219inline _LIBCPP_INLINE_VISIBILITY 220bool 221operator!=(const _Tp& __x, const _Tp& __y) 222{ 223 return !(__x == __y); 224} 225 226template<class _Tp> 227inline _LIBCPP_INLINE_VISIBILITY 228bool 229operator> (const _Tp& __x, const _Tp& __y) 230{ 231 return __y < __x; 232} 233 234template<class _Tp> 235inline _LIBCPP_INLINE_VISIBILITY 236bool 237operator<=(const _Tp& __x, const _Tp& __y) 238{ 239 return !(__y < __x); 240} 241 242template<class _Tp> 243inline _LIBCPP_INLINE_VISIBILITY 244bool 245operator>=(const _Tp& __x, const _Tp& __y) 246{ 247 return !(__x < __y); 248} 249 250} // rel_ops 251 252// swap_ranges 253 254 255template <class _ForwardIterator1, class _ForwardIterator2> 256inline _LIBCPP_INLINE_VISIBILITY 257_ForwardIterator2 258swap_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> 266template<class _Tp, size_t _Np> 267inline _LIBCPP_INLINE_VISIBILITY 268typename enable_if< 269 __is_swappable<_Tp>::value 270>::type 271swap(_Tp (&__a)[_Np], _Tp (&__b)[_Np]) _NOEXCEPT_(__is_nothrow_swappable<_Tp>::value) 272{ 273 _VSTD::swap_ranges(__a, __a + _Np, __b); 274} 275 276template <class _Tp> 277inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 278#ifndef _LIBCPP_CXX03_LANG 279typename 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 286const _Tp& 287#endif 288move_if_noexcept(_Tp& __x) _NOEXCEPT 289{ 290 return _VSTD::move(__x); 291} 292 293#if _LIBCPP_STD_VER > 14 294template <class _Tp> constexpr add_const_t<_Tp>& as_const(_Tp& __t) noexcept { return __t; } 295template <class _Tp> void as_const(const _Tp&&) = delete; 296#endif 297 298struct _LIBCPP_TEMPLATE_VIS piecewise_construct_t { }; 299#if defined(_LIBCPP_CXX03_LANG) || defined(_LIBCPP_BUILDING_LIBRARY) 300extern _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) 306template <class, class> 307struct __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 315template <class _T1, class _T2> 316struct _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 } 561private: 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 573template<class _T1, class _T2> 574pair(_T1, _T2) -> pair<_T1, _T2>; 575#endif // _LIBCPP_HAS_NO_DEDUCTION_GUIDES 576 577template <class _T1, class _T2> 578inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 579bool 580operator==(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 581{ 582 return __x.first == __y.first && __x.second == __y.second; 583} 584 585template <class _T1, class _T2> 586inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 587bool 588operator!=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 589{ 590 return !(__x == __y); 591} 592 593template <class _T1, class _T2> 594inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 595bool 596operator< (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 601template <class _T1, class _T2> 602inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 603bool 604operator> (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 605{ 606 return __y < __x; 607} 608 609template <class _T1, class _T2> 610inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 611bool 612operator>=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 613{ 614 return !(__x < __y); 615} 616 617template <class _T1, class _T2> 618inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 619bool 620operator<=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 621{ 622 return !(__y < __x); 623} 624 625template <class _T1, class _T2> 626inline _LIBCPP_INLINE_VISIBILITY 627typename enable_if 628< 629 __is_swappable<_T1>::value && 630 __is_swappable<_T2>::value, 631 void 632>::type 633swap(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 640template <class _Tp> 641struct __unwrap_reference { typedef _Tp type; }; 642 643template <class _Tp> 644struct __unwrap_reference<reference_wrapper<_Tp> > { typedef _Tp& type; }; 645 646#if _LIBCPP_STD_VER > 17 647template <class _Tp> 648struct unwrap_reference : __unwrap_reference<_Tp> { }; 649 650template <class _Tp> 651struct unwrap_ref_decay : unwrap_reference<typename decay<_Tp>::type> { }; 652#endif // > C++17 653 654template <class _Tp> 655struct __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 665template <class _T1, class _T2> 666inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 667pair<typename __unwrap_ref_decay<_T1>::type, typename __unwrap_ref_decay<_T2>::type> 668make_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 676template <class _T1, class _T2> 677inline _LIBCPP_INLINE_VISIBILITY 678pair<_T1,_T2> 679make_pair(_T1 __x, _T2 __y) 680{ 681 return pair<_T1, _T2>(__x, __y); 682} 683 684#endif // _LIBCPP_CXX03_LANG 685 686template <class _T1, class _T2> 687 struct _LIBCPP_TEMPLATE_VIS tuple_size<pair<_T1, _T2> > 688 : public integral_constant<size_t, 2> {}; 689 690template <size_t _Ip, class _T1, class _T2> 691class _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 696template <class _T1, class _T2> 697class _LIBCPP_TEMPLATE_VIS tuple_element<0, pair<_T1, _T2> > 698{ 699public: 700 typedef _T1 type; 701}; 702 703template <class _T1, class _T2> 704class _LIBCPP_TEMPLATE_VIS tuple_element<1, pair<_T1, _T2> > 705{ 706public: 707 typedef _T2 type; 708}; 709 710template <size_t _Ip> struct __get_pair; 711 712template <> 713struct __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 742template <> 743struct __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 772template <size_t _Ip, class _T1, class _T2> 773inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 774typename tuple_element<_Ip, pair<_T1, _T2> >::type& 775get(pair<_T1, _T2>& __p) _NOEXCEPT 776{ 777 return __get_pair<_Ip>::get(__p); 778} 779 780template <size_t _Ip, class _T1, class _T2> 781inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 782const typename tuple_element<_Ip, pair<_T1, _T2> >::type& 783get(const pair<_T1, _T2>& __p) _NOEXCEPT 784{ 785 return __get_pair<_Ip>::get(__p); 786} 787 788#ifndef _LIBCPP_CXX03_LANG 789template <size_t _Ip, class _T1, class _T2> 790inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 791typename tuple_element<_Ip, pair<_T1, _T2> >::type&& 792get(pair<_T1, _T2>&& __p) _NOEXCEPT 793{ 794 return __get_pair<_Ip>::get(_VSTD::move(__p)); 795} 796 797template <size_t _Ip, class _T1, class _T2> 798inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 799const typename tuple_element<_Ip, pair<_T1, _T2> >::type&& 800get(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 807template <class _T1, class _T2> 808inline _LIBCPP_INLINE_VISIBILITY 809constexpr _T1 & get(pair<_T1, _T2>& __p) _NOEXCEPT 810{ 811 return __get_pair<0>::get(__p); 812} 813 814template <class _T1, class _T2> 815inline _LIBCPP_INLINE_VISIBILITY 816constexpr _T1 const & get(pair<_T1, _T2> const& __p) _NOEXCEPT 817{ 818 return __get_pair<0>::get(__p); 819} 820 821template <class _T1, class _T2> 822inline _LIBCPP_INLINE_VISIBILITY 823constexpr _T1 && get(pair<_T1, _T2>&& __p) _NOEXCEPT 824{ 825 return __get_pair<0>::get(_VSTD::move(__p)); 826} 827 828template <class _T1, class _T2> 829inline _LIBCPP_INLINE_VISIBILITY 830constexpr _T1 const && get(pair<_T1, _T2> const&& __p) _NOEXCEPT 831{ 832 return __get_pair<0>::get(_VSTD::move(__p)); 833} 834 835template <class _T1, class _T2> 836inline _LIBCPP_INLINE_VISIBILITY 837constexpr _T1 & get(pair<_T2, _T1>& __p) _NOEXCEPT 838{ 839 return __get_pair<1>::get(__p); 840} 841 842template <class _T1, class _T2> 843inline _LIBCPP_INLINE_VISIBILITY 844constexpr _T1 const & get(pair<_T2, _T1> const& __p) _NOEXCEPT 845{ 846 return __get_pair<1>::get(__p); 847} 848 849template <class _T1, class _T2> 850inline _LIBCPP_INLINE_VISIBILITY 851constexpr _T1 && get(pair<_T2, _T1>&& __p) _NOEXCEPT 852{ 853 return __get_pair<1>::get(_VSTD::move(__p)); 854} 855 856template <class _T1, class _T2> 857inline _LIBCPP_INLINE_VISIBILITY 858constexpr _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 867template<class _Tp, _Tp... _Ip> 868struct _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 880template<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 885template <class _Tp, _Tp _Ep> 886using __make_integer_sequence = __make_integer_seq<integer_sequence, _Tp, _Ep>; 887 888#else 889 890template<typename _Tp, _Tp _Np> using __make_integer_sequence_unchecked = 891 typename __detail::__make<_Np>::type::template __convert<integer_sequence, _Tp>; 892 893template <class _Tp, _Tp _Ep> 894struct __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 904template <class _Tp, _Tp _Ep> 905using __make_integer_sequence = typename __make_integer_sequence_checked<_Tp, _Ep>::type; 906 907#endif 908 909template<class _Tp, _Tp _Np> 910 using make_integer_sequence = __make_integer_sequence<_Tp, _Np>; 911 912template<size_t _Np> 913 using make_index_sequence = make_integer_sequence<size_t, _Np>; 914 915template<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 921template<class _T1, class _T2 = _T1> 922inline _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 933struct _LIBCPP_TYPE_VIS in_place_t { 934 explicit in_place_t() = default; 935}; 936_LIBCPP_INLINE_VAR constexpr in_place_t in_place{}; 937 938template <class _Tp> 939struct _LIBCPP_TEMPLATE_VIS in_place_type_t { 940 explicit in_place_type_t() = default; 941}; 942template <class _Tp> 943_LIBCPP_INLINE_VAR constexpr in_place_type_t<_Tp> in_place_type{}; 944 945template <size_t _Idx> 946struct _LIBCPP_TYPE_VIS in_place_index_t { 947 explicit in_place_index_t() = default; 948}; 949template <size_t _Idx> 950_LIBCPP_INLINE_VAR constexpr in_place_index_t<_Idx> in_place_index{}; 951 952template <class _Tp> struct __is_inplace_type_imp : false_type {}; 953template <class _Tp> struct __is_inplace_type_imp<in_place_type_t<_Tp>> : true_type {}; 954 955template <class _Tp> 956using __is_inplace_type = __is_inplace_type_imp<__uncvref_t<_Tp>>; 957 958template <class _Tp> struct __is_inplace_index_imp : false_type {}; 959template <size_t _Idx> struct __is_inplace_index_imp<in_place_index_t<_Idx>> : true_type {}; 960 961template <class _Tp> 962using __is_inplace_index = __is_inplace_index_imp<__uncvref_t<_Tp>>; 963 964#endif // _LIBCPP_STD_VER > 14 965 966template <class _Arg, class _Result> 967struct _LIBCPP_TEMPLATE_VIS unary_function 968{ 969 typedef _Arg argument_type; 970 typedef _Result result_type; 971}; 972 973template <class _Size> 974inline _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. 986template <class _Size, size_t = sizeof(_Size)*__CHAR_BIT__> 987struct __murmur2_or_cityhash; 988 989template <class _Size> 990struct __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 997template <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 1032template <class _Size> 1033struct __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 1161template <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 1207template <class _Tp, size_t = sizeof(_Tp) / sizeof(size_t)> 1208struct __scalar_hash; 1209 1210template <class _Tp> 1211struct __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 1228template <class _Tp> 1229struct __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 1245template <class _Tp> 1246struct __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 1266template <class _Tp> 1267struct __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 1288template <class _Tp> 1289struct __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 1311struct _PairT { 1312 size_t first; 1313 size_t second; 1314}; 1315 1316_LIBCPP_INLINE_VISIBILITY 1317inline 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 1323template<class _Tp> 1324struct _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 1341template <> 1342struct _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 1349template <> 1350struct _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 1357template <> 1358struct _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 1365template <> 1366struct _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 1375template <> 1376struct _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 1383template <> 1384struct _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 1393template <> 1394struct _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 1401template <> 1402struct _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 1409template <> 1410struct _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 1417template <> 1418struct _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 1425template <> 1426struct _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 1433template <> 1434struct _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 1441template <> 1442struct _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 1449template <> 1450struct _LIBCPP_TEMPLATE_VIS hash<long long> 1451 : public __scalar_hash<long long> 1452{ 1453}; 1454 1455template <> 1456struct _LIBCPP_TEMPLATE_VIS hash<unsigned long long> 1457 : public __scalar_hash<unsigned long long> 1458{ 1459}; 1460 1461#ifndef _LIBCPP_HAS_NO_INT128 1462 1463template <> 1464struct _LIBCPP_TEMPLATE_VIS hash<__int128_t> 1465 : public __scalar_hash<__int128_t> 1466{ 1467}; 1468 1469template <> 1470struct _LIBCPP_TEMPLATE_VIS hash<__uint128_t> 1471 : public __scalar_hash<__uint128_t> 1472{ 1473}; 1474 1475#endif 1476 1477template <> 1478struct _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 1491template <> 1492struct _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 1505template <> 1506struct _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 1557template <class _Tp, bool = is_enum<_Tp>::value> 1558struct _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}; 1568template <class _Tp> 1569struct _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 1575template <class _Tp> 1576struct _LIBCPP_TEMPLATE_VIS hash : public __enum_hash<_Tp> 1577{ 1578}; 1579#endif 1580 1581#if _LIBCPP_STD_VER > 14 1582 1583template <> 1584struct _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 1595template <class _Key, class _Hash> 1596using __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 1602template <class _Key, class _Hash = std::hash<_Key> > 1603using __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 1609template <class _Type, class> 1610using __enable_hash_helper_imp = _Type; 1611 1612template <class _Type, class ..._Keys> 1613using __enable_hash_helper = __enable_hash_helper_imp<_Type, 1614 typename enable_if<__all<__has_enabled_hash<_Keys>::value...>::value>::type 1615>; 1616#else 1617template <class _Type, class ...> 1618using __enable_hash_helper = _Type; 1619#endif 1620 1621#endif // !_LIBCPP_CXX03_LANG 1622 1623_LIBCPP_END_NAMESPACE_STD 1624 1625#endif // _LIBCPP_UTILITY 1626