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_HAS_NO_RVALUE_REFERENCES 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_HAS_NO_RVALUE_REFERENCES 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_HAS_NO_CONSTEXPR) || 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_HAS_NO_RVALUE_REFERENCES 612 613 614template <class _Tp> 615struct __make_pair_return_impl 616{ 617 typedef _Tp type; 618}; 619 620template <class _Tp> 621struct __make_pair_return_impl<reference_wrapper<_Tp>> 622{ 623 typedef _Tp& type; 624}; 625 626template <class _Tp> 627struct __make_pair_return 628{ 629 typedef typename __make_pair_return_impl<typename decay<_Tp>::type>::type type; 630}; 631 632template <class _T1, class _T2> 633inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 634pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type> 635make_pair(_T1&& __t1, _T2&& __t2) 636{ 637 return pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type> 638 (_VSTD::forward<_T1>(__t1), _VSTD::forward<_T2>(__t2)); 639} 640 641#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 642 643template <class _T1, class _T2> 644inline _LIBCPP_INLINE_VISIBILITY 645pair<_T1,_T2> 646make_pair(_T1 __x, _T2 __y) 647{ 648 return pair<_T1, _T2>(__x, __y); 649} 650 651#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 652 653template <class _T1, class _T2> 654 class _LIBCPP_TEMPLATE_VIS tuple_size<pair<_T1, _T2> > 655 : public integral_constant<size_t, 2> {}; 656 657template <class _T1, class _T2> 658class _LIBCPP_TEMPLATE_VIS tuple_element<0, pair<_T1, _T2> > 659{ 660public: 661 typedef _T1 type; 662}; 663 664template <class _T1, class _T2> 665class _LIBCPP_TEMPLATE_VIS tuple_element<1, pair<_T1, _T2> > 666{ 667public: 668 typedef _T2 type; 669}; 670 671template <size_t _Ip> struct __get_pair; 672 673template <> 674struct __get_pair<0> 675{ 676 template <class _T1, class _T2> 677 static 678 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 679 _T1& 680 get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;} 681 682 template <class _T1, class _T2> 683 static 684 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 685 const _T1& 686 get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;} 687 688#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 689 690 template <class _T1, class _T2> 691 static 692 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 693 _T1&& 694 get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T1>(__p.first);} 695 696 template <class _T1, class _T2> 697 static 698 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 699 const _T1&& 700 get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<const _T1>(__p.first);} 701 702#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 703}; 704 705template <> 706struct __get_pair<1> 707{ 708 template <class _T1, class _T2> 709 static 710 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 711 _T2& 712 get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;} 713 714 template <class _T1, class _T2> 715 static 716 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 717 const _T2& 718 get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;} 719 720#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 721 722 template <class _T1, class _T2> 723 static 724 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 725 _T2&& 726 get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T2>(__p.second);} 727 728 template <class _T1, class _T2> 729 static 730 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 731 const _T2&& 732 get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<const _T2>(__p.second);} 733 734#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 735}; 736 737template <size_t _Ip, class _T1, class _T2> 738inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 739typename tuple_element<_Ip, pair<_T1, _T2> >::type& 740get(pair<_T1, _T2>& __p) _NOEXCEPT 741{ 742 return __get_pair<_Ip>::get(__p); 743} 744 745template <size_t _Ip, class _T1, class _T2> 746inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 747const typename tuple_element<_Ip, pair<_T1, _T2> >::type& 748get(const pair<_T1, _T2>& __p) _NOEXCEPT 749{ 750 return __get_pair<_Ip>::get(__p); 751} 752 753#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 754 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 771#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 772 773#if _LIBCPP_STD_VER > 11 774template <class _T1, class _T2> 775inline _LIBCPP_INLINE_VISIBILITY 776constexpr _T1 & get(pair<_T1, _T2>& __p) _NOEXCEPT 777{ 778 return __get_pair<0>::get(__p); 779} 780 781template <class _T1, class _T2> 782inline _LIBCPP_INLINE_VISIBILITY 783constexpr _T1 const & get(pair<_T1, _T2> const& __p) _NOEXCEPT 784{ 785 return __get_pair<0>::get(__p); 786} 787 788template <class _T1, class _T2> 789inline _LIBCPP_INLINE_VISIBILITY 790constexpr _T1 && get(pair<_T1, _T2>&& __p) _NOEXCEPT 791{ 792 return __get_pair<0>::get(_VSTD::move(__p)); 793} 794 795template <class _T1, class _T2> 796inline _LIBCPP_INLINE_VISIBILITY 797constexpr _T1 const && get(pair<_T1, _T2> const&& __p) _NOEXCEPT 798{ 799 return __get_pair<0>::get(_VSTD::move(__p)); 800} 801 802template <class _T1, class _T2> 803inline _LIBCPP_INLINE_VISIBILITY 804constexpr _T1 & get(pair<_T2, _T1>& __p) _NOEXCEPT 805{ 806 return __get_pair<1>::get(__p); 807} 808 809template <class _T1, class _T2> 810inline _LIBCPP_INLINE_VISIBILITY 811constexpr _T1 const & get(pair<_T2, _T1> const& __p) _NOEXCEPT 812{ 813 return __get_pair<1>::get(__p); 814} 815 816template <class _T1, class _T2> 817inline _LIBCPP_INLINE_VISIBILITY 818constexpr _T1 && get(pair<_T2, _T1>&& __p) _NOEXCEPT 819{ 820 return __get_pair<1>::get(_VSTD::move(__p)); 821} 822 823template <class _T1, class _T2> 824inline _LIBCPP_INLINE_VISIBILITY 825constexpr _T1 const && get(pair<_T2, _T1> const&& __p) _NOEXCEPT 826{ 827 return __get_pair<1>::get(_VSTD::move(__p)); 828} 829 830#endif 831 832#if _LIBCPP_STD_VER > 11 833 834template<class _Tp, _Tp... _Ip> 835struct _LIBCPP_TEMPLATE_VIS integer_sequence 836{ 837 typedef _Tp value_type; 838 static_assert( is_integral<_Tp>::value, 839 "std::integer_sequence can only be instantiated with an integral type" ); 840 static 841 _LIBCPP_INLINE_VISIBILITY 842 constexpr 843 size_t 844 size() noexcept { return sizeof...(_Ip); } 845}; 846 847template<size_t... _Ip> 848 using index_sequence = integer_sequence<size_t, _Ip...>; 849 850#if __has_builtin(__make_integer_seq) && !defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE) 851 852template <class _Tp, _Tp _Ep> 853using __make_integer_sequence = __make_integer_seq<integer_sequence, _Tp, _Ep>; 854 855#else 856 857template<typename _Tp, _Tp _Np> using __make_integer_sequence_unchecked = 858 typename __detail::__make<_Np>::type::template __convert<integer_sequence, _Tp>; 859 860template <class _Tp, _Tp _Ep> 861struct __make_integer_sequence_checked 862{ 863 static_assert(is_integral<_Tp>::value, 864 "std::make_integer_sequence can only be instantiated with an integral type" ); 865 static_assert(0 <= _Ep, "std::make_integer_sequence must have a non-negative sequence length"); 866 // Workaround GCC bug by preventing bad installations when 0 <= _Ep 867 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68929 868 typedef __make_integer_sequence_unchecked<_Tp, 0 <= _Ep ? _Ep : 0> type; 869}; 870 871template <class _Tp, _Tp _Ep> 872using __make_integer_sequence = typename __make_integer_sequence_checked<_Tp, _Ep>::type; 873 874#endif 875 876template<class _Tp, _Tp _Np> 877 using make_integer_sequence = __make_integer_sequence<_Tp, _Np>; 878 879template<size_t _Np> 880 using make_index_sequence = make_integer_sequence<size_t, _Np>; 881 882template<class... _Tp> 883 using index_sequence_for = make_index_sequence<sizeof...(_Tp)>; 884 885#endif // _LIBCPP_STD_VER > 11 886 887#if _LIBCPP_STD_VER > 11 888template<class _T1, class _T2 = _T1> 889inline _LIBCPP_INLINE_VISIBILITY 890_T1 exchange(_T1& __obj, _T2 && __new_value) 891{ 892 _T1 __old_value = _VSTD::move(__obj); 893 __obj = _VSTD::forward<_T2>(__new_value); 894 return __old_value; 895} 896#endif // _LIBCPP_STD_VER > 11 897 898#if _LIBCPP_STD_VER > 14 899 900struct _LIBCPP_TYPE_VIS in_place_t { 901 explicit in_place_t() = default; 902}; 903#ifndef _LIBCPP_HAS_NO_INLINE_VARIABLES 904inline 905#endif 906constexpr in_place_t in_place{}; 907 908template <class _Tp> 909struct _LIBCPP_TYPE_VIS in_place_type_t { 910 explicit in_place_type_t() = default; 911}; 912template <class _Tp> 913#ifndef _LIBCPP_HAS_NO_INLINE_VARIABLES 914inline 915#endif 916constexpr 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#ifndef _LIBCPP_HAS_NO_INLINE_VARIABLES 924inline 925#endif 926constexpr in_place_index_t<_Idx> in_place_index{}; 927 928template <class _Tp> struct __is_inplace_type_imp : false_type {}; 929template <class _Tp> struct __is_inplace_type_imp<in_place_type_t<_Tp>> : true_type {}; 930 931template <class _Tp> 932using __is_inplace_type = __is_inplace_type_imp<__uncvref_t<_Tp>>; 933 934#endif // _LIBCPP_STD_VER > 14 935 936template <class _Arg, class _Result> 937struct _LIBCPP_TEMPLATE_VIS unary_function 938{ 939 typedef _Arg argument_type; 940 typedef _Result result_type; 941}; 942 943template <class _Size> 944inline _LIBCPP_INLINE_VISIBILITY 945_Size 946__loadword(const void* __p) 947{ 948 _Size __r; 949 std::memcpy(&__r, __p, sizeof(__r)); 950 return __r; 951} 952 953// We use murmur2 when size_t is 32 bits, and cityhash64 when size_t 954// is 64 bits. This is because cityhash64 uses 64bit x 64bit 955// multiplication, which can be very slow on 32-bit systems. 956template <class _Size, size_t = sizeof(_Size)*__CHAR_BIT__> 957struct __murmur2_or_cityhash; 958 959template <class _Size> 960struct __murmur2_or_cityhash<_Size, 32> 961{ 962 inline _Size operator()(const void* __key, _Size __len) 963 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK; 964}; 965 966// murmur2 967template <class _Size> 968_Size 969__murmur2_or_cityhash<_Size, 32>::operator()(const void* __key, _Size __len) 970{ 971 const _Size __m = 0x5bd1e995; 972 const _Size __r = 24; 973 _Size __h = __len; 974 const unsigned char* __data = static_cast<const unsigned char*>(__key); 975 for (; __len >= 4; __data += 4, __len -= 4) 976 { 977 _Size __k = __loadword<_Size>(__data); 978 __k *= __m; 979 __k ^= __k >> __r; 980 __k *= __m; 981 __h *= __m; 982 __h ^= __k; 983 } 984 switch (__len) 985 { 986 case 3: 987 __h ^= __data[2] << 16; 988 case 2: 989 __h ^= __data[1] << 8; 990 case 1: 991 __h ^= __data[0]; 992 __h *= __m; 993 } 994 __h ^= __h >> 13; 995 __h *= __m; 996 __h ^= __h >> 15; 997 return __h; 998} 999 1000template <class _Size> 1001struct __murmur2_or_cityhash<_Size, 64> 1002{ 1003 inline _Size operator()(const void* __key, _Size __len) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK; 1004 1005 private: 1006 // Some primes between 2^63 and 2^64. 1007 static const _Size __k0 = 0xc3a5c85c97cb3127ULL; 1008 static const _Size __k1 = 0xb492b66fbe98f273ULL; 1009 static const _Size __k2 = 0x9ae16a3b2f90404fULL; 1010 static const _Size __k3 = 0xc949d7c7509e6557ULL; 1011 1012 static _Size __rotate(_Size __val, int __shift) { 1013 return __shift == 0 ? __val : ((__val >> __shift) | (__val << (64 - __shift))); 1014 } 1015 1016 static _Size __rotate_by_at_least_1(_Size __val, int __shift) { 1017 return (__val >> __shift) | (__val << (64 - __shift)); 1018 } 1019 1020 static _Size __shift_mix(_Size __val) { 1021 return __val ^ (__val >> 47); 1022 } 1023 1024 static _Size __hash_len_16(_Size __u, _Size __v) 1025 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1026 { 1027 const _Size __mul = 0x9ddfea08eb382d69ULL; 1028 _Size __a = (__u ^ __v) * __mul; 1029 __a ^= (__a >> 47); 1030 _Size __b = (__v ^ __a) * __mul; 1031 __b ^= (__b >> 47); 1032 __b *= __mul; 1033 return __b; 1034 } 1035 1036 static _Size __hash_len_0_to_16(const char* __s, _Size __len) 1037 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1038 { 1039 if (__len > 8) { 1040 const _Size __a = __loadword<_Size>(__s); 1041 const _Size __b = __loadword<_Size>(__s + __len - 8); 1042 return __hash_len_16(__a, __rotate_by_at_least_1(__b + __len, __len)) ^ __b; 1043 } 1044 if (__len >= 4) { 1045 const uint32_t __a = __loadword<uint32_t>(__s); 1046 const uint32_t __b = __loadword<uint32_t>(__s + __len - 4); 1047 return __hash_len_16(__len + (__a << 3), __b); 1048 } 1049 if (__len > 0) { 1050 const unsigned char __a = __s[0]; 1051 const unsigned char __b = __s[__len >> 1]; 1052 const unsigned char __c = __s[__len - 1]; 1053 const uint32_t __y = static_cast<uint32_t>(__a) + 1054 (static_cast<uint32_t>(__b) << 8); 1055 const uint32_t __z = __len + (static_cast<uint32_t>(__c) << 2); 1056 return __shift_mix(__y * __k2 ^ __z * __k3) * __k2; 1057 } 1058 return __k2; 1059 } 1060 1061 static _Size __hash_len_17_to_32(const char *__s, _Size __len) 1062 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1063 { 1064 const _Size __a = __loadword<_Size>(__s) * __k1; 1065 const _Size __b = __loadword<_Size>(__s + 8); 1066 const _Size __c = __loadword<_Size>(__s + __len - 8) * __k2; 1067 const _Size __d = __loadword<_Size>(__s + __len - 16) * __k0; 1068 return __hash_len_16(__rotate(__a - __b, 43) + __rotate(__c, 30) + __d, 1069 __a + __rotate(__b ^ __k3, 20) - __c + __len); 1070 } 1071 1072 // Return a 16-byte hash for 48 bytes. Quick and dirty. 1073 // Callers do best to use "random-looking" values for a and b. 1074 static pair<_Size, _Size> __weak_hash_len_32_with_seeds( 1075 _Size __w, _Size __x, _Size __y, _Size __z, _Size __a, _Size __b) 1076 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1077 { 1078 __a += __w; 1079 __b = __rotate(__b + __a + __z, 21); 1080 const _Size __c = __a; 1081 __a += __x; 1082 __a += __y; 1083 __b += __rotate(__a, 44); 1084 return pair<_Size, _Size>(__a + __z, __b + __c); 1085 } 1086 1087 // Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty. 1088 static pair<_Size, _Size> __weak_hash_len_32_with_seeds( 1089 const char* __s, _Size __a, _Size __b) 1090 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1091 { 1092 return __weak_hash_len_32_with_seeds(__loadword<_Size>(__s), 1093 __loadword<_Size>(__s + 8), 1094 __loadword<_Size>(__s + 16), 1095 __loadword<_Size>(__s + 24), 1096 __a, 1097 __b); 1098 } 1099 1100 // Return an 8-byte hash for 33 to 64 bytes. 1101 static _Size __hash_len_33_to_64(const char *__s, size_t __len) 1102 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 1103 { 1104 _Size __z = __loadword<_Size>(__s + 24); 1105 _Size __a = __loadword<_Size>(__s) + 1106 (__len + __loadword<_Size>(__s + __len - 16)) * __k0; 1107 _Size __b = __rotate(__a + __z, 52); 1108 _Size __c = __rotate(__a, 37); 1109 __a += __loadword<_Size>(__s + 8); 1110 __c += __rotate(__a, 7); 1111 __a += __loadword<_Size>(__s + 16); 1112 _Size __vf = __a + __z; 1113 _Size __vs = __b + __rotate(__a, 31) + __c; 1114 __a = __loadword<_Size>(__s + 16) + __loadword<_Size>(__s + __len - 32); 1115 __z += __loadword<_Size>(__s + __len - 8); 1116 __b = __rotate(__a + __z, 52); 1117 __c = __rotate(__a, 37); 1118 __a += __loadword<_Size>(__s + __len - 24); 1119 __c += __rotate(__a, 7); 1120 __a += __loadword<_Size>(__s + __len - 16); 1121 _Size __wf = __a + __z; 1122 _Size __ws = __b + __rotate(__a, 31) + __c; 1123 _Size __r = __shift_mix((__vf + __ws) * __k2 + (__wf + __vs) * __k0); 1124 return __shift_mix(__r * __k0 + __vs) * __k2; 1125 } 1126}; 1127 1128// cityhash64 1129template <class _Size> 1130_Size 1131__murmur2_or_cityhash<_Size, 64>::operator()(const void* __key, _Size __len) 1132{ 1133 const char* __s = static_cast<const char*>(__key); 1134 if (__len <= 32) { 1135 if (__len <= 16) { 1136 return __hash_len_0_to_16(__s, __len); 1137 } else { 1138 return __hash_len_17_to_32(__s, __len); 1139 } 1140 } else if (__len <= 64) { 1141 return __hash_len_33_to_64(__s, __len); 1142 } 1143 1144 // For strings over 64 bytes we hash the end first, and then as we 1145 // loop we keep 56 bytes of state: v, w, x, y, and z. 1146 _Size __x = __loadword<_Size>(__s + __len - 40); 1147 _Size __y = __loadword<_Size>(__s + __len - 16) + 1148 __loadword<_Size>(__s + __len - 56); 1149 _Size __z = __hash_len_16(__loadword<_Size>(__s + __len - 48) + __len, 1150 __loadword<_Size>(__s + __len - 24)); 1151 pair<_Size, _Size> __v = __weak_hash_len_32_with_seeds(__s + __len - 64, __len, __z); 1152 pair<_Size, _Size> __w = __weak_hash_len_32_with_seeds(__s + __len - 32, __y + __k1, __x); 1153 __x = __x * __k1 + __loadword<_Size>(__s); 1154 1155 // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks. 1156 __len = (__len - 1) & ~static_cast<_Size>(63); 1157 do { 1158 __x = __rotate(__x + __y + __v.first + __loadword<_Size>(__s + 8), 37) * __k1; 1159 __y = __rotate(__y + __v.second + __loadword<_Size>(__s + 48), 42) * __k1; 1160 __x ^= __w.second; 1161 __y += __v.first + __loadword<_Size>(__s + 40); 1162 __z = __rotate(__z + __w.first, 33) * __k1; 1163 __v = __weak_hash_len_32_with_seeds(__s, __v.second * __k1, __x + __w.first); 1164 __w = __weak_hash_len_32_with_seeds(__s + 32, __z + __w.second, 1165 __y + __loadword<_Size>(__s + 16)); 1166 std::swap(__z, __x); 1167 __s += 64; 1168 __len -= 64; 1169 } while (__len != 0); 1170 return __hash_len_16( 1171 __hash_len_16(__v.first, __w.first) + __shift_mix(__y) * __k1 + __z, 1172 __hash_len_16(__v.second, __w.second) + __x); 1173} 1174 1175template <class _Tp, size_t = sizeof(_Tp) / sizeof(size_t)> 1176struct __scalar_hash; 1177 1178template <class _Tp> 1179struct __scalar_hash<_Tp, 0> 1180 : public unary_function<_Tp, size_t> 1181{ 1182 _LIBCPP_INLINE_VISIBILITY 1183 size_t operator()(_Tp __v) const _NOEXCEPT 1184 { 1185 union 1186 { 1187 _Tp __t; 1188 size_t __a; 1189 } __u; 1190 __u.__a = 0; 1191 __u.__t = __v; 1192 return __u.__a; 1193 } 1194}; 1195 1196template <class _Tp> 1197struct __scalar_hash<_Tp, 1> 1198 : public unary_function<_Tp, size_t> 1199{ 1200 _LIBCPP_INLINE_VISIBILITY 1201 size_t operator()(_Tp __v) const _NOEXCEPT 1202 { 1203 union 1204 { 1205 _Tp __t; 1206 size_t __a; 1207 } __u; 1208 __u.__t = __v; 1209 return __u.__a; 1210 } 1211}; 1212 1213template <class _Tp> 1214struct __scalar_hash<_Tp, 2> 1215 : public unary_function<_Tp, size_t> 1216{ 1217 _LIBCPP_INLINE_VISIBILITY 1218 size_t operator()(_Tp __v) const _NOEXCEPT 1219 { 1220 union 1221 { 1222 _Tp __t; 1223 struct 1224 { 1225 size_t __a; 1226 size_t __b; 1227 } __s; 1228 } __u; 1229 __u.__t = __v; 1230 return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u)); 1231 } 1232}; 1233 1234template <class _Tp> 1235struct __scalar_hash<_Tp, 3> 1236 : public unary_function<_Tp, size_t> 1237{ 1238 _LIBCPP_INLINE_VISIBILITY 1239 size_t operator()(_Tp __v) const _NOEXCEPT 1240 { 1241 union 1242 { 1243 _Tp __t; 1244 struct 1245 { 1246 size_t __a; 1247 size_t __b; 1248 size_t __c; 1249 } __s; 1250 } __u; 1251 __u.__t = __v; 1252 return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u)); 1253 } 1254}; 1255 1256template <class _Tp> 1257struct __scalar_hash<_Tp, 4> 1258 : public unary_function<_Tp, size_t> 1259{ 1260 _LIBCPP_INLINE_VISIBILITY 1261 size_t operator()(_Tp __v) const _NOEXCEPT 1262 { 1263 union 1264 { 1265 _Tp __t; 1266 struct 1267 { 1268 size_t __a; 1269 size_t __b; 1270 size_t __c; 1271 size_t __d; 1272 } __s; 1273 } __u; 1274 __u.__t = __v; 1275 return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u)); 1276 } 1277}; 1278 1279struct _PairT { 1280 size_t first; 1281 size_t second; 1282}; 1283 1284_LIBCPP_INLINE_VISIBILITY 1285inline size_t __hash_combine(size_t __lhs, size_t __rhs) _NOEXCEPT { 1286 typedef __scalar_hash<_PairT> _HashT; 1287 const _PairT __p = {__lhs, __rhs}; 1288 return _HashT()(__p); 1289} 1290 1291template<class _Tp> 1292struct _LIBCPP_TEMPLATE_VIS hash<_Tp*> 1293 : public unary_function<_Tp*, size_t> 1294{ 1295 _LIBCPP_INLINE_VISIBILITY 1296 size_t operator()(_Tp* __v) const _NOEXCEPT 1297 { 1298 union 1299 { 1300 _Tp* __t; 1301 size_t __a; 1302 } __u; 1303 __u.__t = __v; 1304 return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u)); 1305 } 1306}; 1307 1308 1309template <> 1310struct _LIBCPP_TEMPLATE_VIS hash<bool> 1311 : public unary_function<bool, size_t> 1312{ 1313 _LIBCPP_INLINE_VISIBILITY 1314 size_t operator()(bool __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1315}; 1316 1317template <> 1318struct _LIBCPP_TEMPLATE_VIS hash<char> 1319 : public unary_function<char, size_t> 1320{ 1321 _LIBCPP_INLINE_VISIBILITY 1322 size_t operator()(char __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1323}; 1324 1325template <> 1326struct _LIBCPP_TEMPLATE_VIS hash<signed char> 1327 : public unary_function<signed char, size_t> 1328{ 1329 _LIBCPP_INLINE_VISIBILITY 1330 size_t operator()(signed char __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1331}; 1332 1333template <> 1334struct _LIBCPP_TEMPLATE_VIS hash<unsigned char> 1335 : public unary_function<unsigned char, size_t> 1336{ 1337 _LIBCPP_INLINE_VISIBILITY 1338 size_t operator()(unsigned char __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1339}; 1340 1341#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS 1342 1343template <> 1344struct _LIBCPP_TEMPLATE_VIS hash<char16_t> 1345 : public unary_function<char16_t, size_t> 1346{ 1347 _LIBCPP_INLINE_VISIBILITY 1348 size_t operator()(char16_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1349}; 1350 1351template <> 1352struct _LIBCPP_TEMPLATE_VIS hash<char32_t> 1353 : public unary_function<char32_t, size_t> 1354{ 1355 _LIBCPP_INLINE_VISIBILITY 1356 size_t operator()(char32_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1357}; 1358 1359#endif // _LIBCPP_HAS_NO_UNICODE_CHARS 1360 1361template <> 1362struct _LIBCPP_TEMPLATE_VIS hash<wchar_t> 1363 : public unary_function<wchar_t, size_t> 1364{ 1365 _LIBCPP_INLINE_VISIBILITY 1366 size_t operator()(wchar_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1367}; 1368 1369template <> 1370struct _LIBCPP_TEMPLATE_VIS hash<short> 1371 : public unary_function<short, size_t> 1372{ 1373 _LIBCPP_INLINE_VISIBILITY 1374 size_t operator()(short __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1375}; 1376 1377template <> 1378struct _LIBCPP_TEMPLATE_VIS hash<unsigned short> 1379 : public unary_function<unsigned short, size_t> 1380{ 1381 _LIBCPP_INLINE_VISIBILITY 1382 size_t operator()(unsigned short __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1383}; 1384 1385template <> 1386struct _LIBCPP_TEMPLATE_VIS hash<int> 1387 : public unary_function<int, size_t> 1388{ 1389 _LIBCPP_INLINE_VISIBILITY 1390 size_t operator()(int __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1391}; 1392 1393template <> 1394struct _LIBCPP_TEMPLATE_VIS hash<unsigned int> 1395 : public unary_function<unsigned int, size_t> 1396{ 1397 _LIBCPP_INLINE_VISIBILITY 1398 size_t operator()(unsigned int __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1399}; 1400 1401template <> 1402struct _LIBCPP_TEMPLATE_VIS hash<long> 1403 : public unary_function<long, size_t> 1404{ 1405 _LIBCPP_INLINE_VISIBILITY 1406 size_t operator()(long __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1407}; 1408 1409template <> 1410struct _LIBCPP_TEMPLATE_VIS hash<unsigned long> 1411 : public unary_function<unsigned long, size_t> 1412{ 1413 _LIBCPP_INLINE_VISIBILITY 1414 size_t operator()(unsigned long __v) const _NOEXCEPT {return static_cast<size_t>(__v);} 1415}; 1416 1417template <> 1418struct _LIBCPP_TEMPLATE_VIS hash<long long> 1419 : public __scalar_hash<long long> 1420{ 1421}; 1422 1423template <> 1424struct _LIBCPP_TEMPLATE_VIS hash<unsigned long long> 1425 : public __scalar_hash<unsigned long long> 1426{ 1427}; 1428 1429#ifndef _LIBCPP_HAS_NO_INT128 1430 1431template <> 1432struct _LIBCPP_TEMPLATE_VIS hash<__int128_t> 1433 : public __scalar_hash<__int128_t> 1434{ 1435}; 1436 1437template <> 1438struct _LIBCPP_TEMPLATE_VIS hash<__uint128_t> 1439 : public __scalar_hash<__uint128_t> 1440{ 1441}; 1442 1443#endif 1444 1445template <> 1446struct _LIBCPP_TEMPLATE_VIS hash<float> 1447 : public __scalar_hash<float> 1448{ 1449 _LIBCPP_INLINE_VISIBILITY 1450 size_t operator()(float __v) const _NOEXCEPT 1451 { 1452 // -0.0 and 0.0 should return same hash 1453 if (__v == 0) 1454 return 0; 1455 return __scalar_hash<float>::operator()(__v); 1456 } 1457}; 1458 1459template <> 1460struct _LIBCPP_TEMPLATE_VIS hash<double> 1461 : public __scalar_hash<double> 1462{ 1463 _LIBCPP_INLINE_VISIBILITY 1464 size_t operator()(double __v) const _NOEXCEPT 1465 { 1466 // -0.0 and 0.0 should return same hash 1467 if (__v == 0) 1468 return 0; 1469 return __scalar_hash<double>::operator()(__v); 1470 } 1471}; 1472 1473template <> 1474struct _LIBCPP_TEMPLATE_VIS hash<long double> 1475 : public __scalar_hash<long double> 1476{ 1477 _LIBCPP_INLINE_VISIBILITY 1478 size_t operator()(long double __v) const _NOEXCEPT 1479 { 1480 // -0.0 and 0.0 should return same hash 1481 if (__v == 0) 1482 return 0; 1483#if defined(__i386__) 1484 // Zero out padding bits 1485 union 1486 { 1487 long double __t; 1488 struct 1489 { 1490 size_t __a; 1491 size_t __b; 1492 size_t __c; 1493 size_t __d; 1494 } __s; 1495 } __u; 1496 __u.__s.__a = 0; 1497 __u.__s.__b = 0; 1498 __u.__s.__c = 0; 1499 __u.__s.__d = 0; 1500 __u.__t = __v; 1501 return __u.__s.__a ^ __u.__s.__b ^ __u.__s.__c ^ __u.__s.__d; 1502#elif defined(__x86_64__) 1503 // Zero out padding bits 1504 union 1505 { 1506 long double __t; 1507 struct 1508 { 1509 size_t __a; 1510 size_t __b; 1511 } __s; 1512 } __u; 1513 __u.__s.__a = 0; 1514 __u.__s.__b = 0; 1515 __u.__t = __v; 1516 return __u.__s.__a ^ __u.__s.__b; 1517#else 1518 return __scalar_hash<long double>::operator()(__v); 1519#endif 1520 } 1521}; 1522 1523#if _LIBCPP_STD_VER > 11 1524 1525template <class _Tp, bool = is_enum<_Tp>::value> 1526struct _LIBCPP_TEMPLATE_VIS __enum_hash 1527 : public unary_function<_Tp, size_t> 1528{ 1529 _LIBCPP_INLINE_VISIBILITY 1530 size_t operator()(_Tp __v) const _NOEXCEPT 1531 { 1532 typedef typename underlying_type<_Tp>::type type; 1533 return hash<type>{}(static_cast<type>(__v)); 1534 } 1535}; 1536template <class _Tp> 1537struct _LIBCPP_TEMPLATE_VIS __enum_hash<_Tp, false> { 1538 __enum_hash() = delete; 1539 __enum_hash(__enum_hash const&) = delete; 1540 __enum_hash& operator=(__enum_hash const&) = delete; 1541}; 1542 1543template <class _Tp> 1544struct _LIBCPP_TEMPLATE_VIS hash : public __enum_hash<_Tp> 1545{ 1546}; 1547#endif 1548 1549#if _LIBCPP_STD_VER > 14 1550 1551template <> 1552struct _LIBCPP_TEMPLATE_VIS hash<nullptr_t> 1553 : public unary_function<nullptr_t, size_t> 1554{ 1555 _LIBCPP_INLINE_VISIBILITY 1556 size_t operator()(nullptr_t) const _NOEXCEPT { 1557 return 662607004ull; 1558 } 1559}; 1560#endif 1561 1562#ifndef _LIBCPP_CXX03_LANG 1563template <class _Key, class _Hash> 1564using __check_hash_requirements = integral_constant<bool, 1565 is_copy_constructible<_Hash>::value && 1566 is_move_constructible<_Hash>::value && 1567 __invokable_r<size_t, _Hash, _Key const&>::value 1568>; 1569 1570template <class _Key, class _Hash = std::hash<_Key> > 1571using __has_enabled_hash = integral_constant<bool, 1572 __check_hash_requirements<_Key, _Hash>::value && 1573 is_default_constructible<_Hash>::value 1574>; 1575 1576#if _LIBCPP_STD_VER > 14 1577template <class _Type, class> 1578using __enable_hash_helper_imp = _Type; 1579 1580template <class _Type, class ..._Keys> 1581using __enable_hash_helper = __enable_hash_helper_imp<_Type, 1582 typename enable_if<__all<__has_enabled_hash<_Keys>::value...>::value>::type 1583>; 1584#else 1585template <class _Type, class ...> 1586using __enable_hash_helper = _Type; 1587#endif 1588 1589#endif // !_LIBCPP_CXX03_LANG 1590 1591_LIBCPP_END_NAMESPACE_STD 1592 1593#endif // _LIBCPP_UTILITY 1594