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