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