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