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