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