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