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