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