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