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