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