LCOV - code coverage report
Current view: top level - usr/include/c++/9 - functional (source / functions) Hit Total Coverage
Test: ROSE Lines: 20 25 80.0 %
Date: 2022-12-08 13:48:47 Functions: 0 2 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // <functional> -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2001-2019 Free Software Foundation, Inc.
       4             : //
       5             : // This file is part of the GNU ISO C++ Library.  This library is free
       6             : // software; you can redistribute it and/or modify it under the
       7             : // terms of the GNU General Public License as published by the
       8             : // Free Software Foundation; either version 3, or (at your option)
       9             : // any later version.
      10             : 
      11             : // This library is distributed in the hope that it will be useful,
      12             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14             : // GNU General Public License for more details.
      15             : 
      16             : // Under Section 7 of GPL version 3, you are granted additional
      17             : // permissions described in the GCC Runtime Library Exception, version
      18             : // 3.1, as published by the Free Software Foundation.
      19             : 
      20             : // You should have received a copy of the GNU General Public License and
      21             : // a copy of the GCC Runtime Library Exception along with this program;
      22             : // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
      23             : // <http://www.gnu.org/licenses/>.
      24             : 
      25             : /*
      26             :  * Copyright (c) 1997
      27             :  * Silicon Graphics Computer Systems, Inc.
      28             :  *
      29             :  * Permission to use, copy, modify, distribute and sell this software
      30             :  * and its documentation for any purpose is hereby granted without fee,
      31             :  * provided that the above copyright notice appear in all copies and
      32             :  * that both that copyright notice and this permission notice appear
      33             :  * in supporting documentation.  Silicon Graphics makes no
      34             :  * representations about the suitability of this software for any
      35             :  * purpose.  It is provided "as is" without express or implied warranty.
      36             :  *
      37             :  */
      38             : 
      39             : /** @file include/functional
      40             :  *  This is a Standard C++ Library header.
      41             :  */
      42             : 
      43             : #ifndef _GLIBCXX_FUNCTIONAL
      44             : #define _GLIBCXX_FUNCTIONAL 1
      45             : 
      46             : #pragma GCC system_header
      47             : 
      48             : #include <bits/c++config.h>
      49             : #include <bits/stl_function.h>
      50             : 
      51             : #if __cplusplus >= 201103L
      52             : 
      53             : #include <new>
      54             : #include <tuple>
      55             : #include <type_traits>
      56             : #include <bits/functional_hash.h>
      57             : #include <bits/invoke.h>
      58             : #include <bits/refwrap.h> // std::reference_wrapper and _Mem_fn_traits
      59             : #include <bits/std_function.h>    // std::function
      60             : #if __cplusplus > 201402L
      61             : # include <unordered_map>
      62             : # include <vector>
      63             : # include <array>
      64             : # include <utility>
      65             : # include <bits/stl_algo.h>
      66             : #endif
      67             : 
      68             : namespace std _GLIBCXX_VISIBILITY(default)
      69             : {
      70             : _GLIBCXX_BEGIN_NAMESPACE_VERSION
      71             : 
      72             : #if __cplusplus > 201402L
      73             : # define __cpp_lib_invoke 201411
      74             : 
      75             :   /// Invoke a callable object.
      76             :   template<typename _Callable, typename... _Args>
      77             :     inline invoke_result_t<_Callable, _Args...>
      78             :     invoke(_Callable&& __fn, _Args&&... __args)
      79             :     noexcept(is_nothrow_invocable_v<_Callable, _Args...>)
      80             :     {
      81             :       return std::__invoke(std::forward<_Callable>(__fn),
      82             :                            std::forward<_Args>(__args)...);
      83             :     }
      84             : #endif
      85             : 
      86             :   template<typename _MemFunPtr,
      87             :            bool __is_mem_fn = is_member_function_pointer<_MemFunPtr>::value>
      88             :     class _Mem_fn_base
      89             :     : public _Mem_fn_traits<_MemFunPtr>::__maybe_type
      90             :     {
      91             :       using _Traits = _Mem_fn_traits<_MemFunPtr>;
      92             : 
      93             :       using _Arity = typename _Traits::__arity;
      94             :       using _Varargs = typename _Traits::__vararg;
      95             : 
      96             :       template<typename _Func, typename... _BoundArgs>
      97             :         friend struct _Bind_check_arity;
      98             : 
      99             :       _MemFunPtr _M_pmf;
     100             : 
     101             :     public:
     102             : 
     103             :       using result_type = typename _Traits::__result_type;
     104             : 
     105             :       explicit constexpr
     106        1479 :       _Mem_fn_base(_MemFunPtr __pmf) noexcept : _M_pmf(__pmf) { }
     107             : 
     108             :       template<typename... _Args>
     109             :         auto
     110        8401 :         operator()(_Args&&... __args) const
     111             :         noexcept(noexcept(
     112             :               std::__invoke(_M_pmf, std::forward<_Args>(__args)...)))
     113             :         -> decltype(std::__invoke(_M_pmf, std::forward<_Args>(__args)...))
     114       18615 :         { return std::__invoke(_M_pmf, std::forward<_Args>(__args)...); }
     115             :     };
     116             : 
     117             :   // Partial specialization for member object pointers.
     118             :   template<typename _MemObjPtr>
     119             :     class _Mem_fn_base<_MemObjPtr, false>
     120             :     {
     121             :       using _Arity = integral_constant<size_t, 0>;
     122             :       using _Varargs = false_type;
     123             : 
     124             :       template<typename _Func, typename... _BoundArgs>
     125             :         friend struct _Bind_check_arity;
     126             : 
     127             :       _MemObjPtr _M_pm;
     128             : 
     129             :     public:
     130             :       explicit constexpr
     131             :       _Mem_fn_base(_MemObjPtr __pm) noexcept : _M_pm(__pm) { }
     132             : 
     133             :       template<typename _Tp>
     134             :         auto
     135             :         operator()(_Tp&& __obj) const
     136             :         noexcept(noexcept(std::__invoke(_M_pm, std::forward<_Tp>(__obj))))
     137             :         -> decltype(std::__invoke(_M_pm, std::forward<_Tp>(__obj)))
     138             :         { return std::__invoke(_M_pm, std::forward<_Tp>(__obj)); }
     139             :     };
     140             : 
     141             :   template<typename _MemberPointer>
     142             :     struct _Mem_fn; // undefined
     143             : 
     144             :   template<typename _Res, typename _Class>
     145             :     struct _Mem_fn<_Res _Class::*>
     146             :     : _Mem_fn_base<_Res _Class::*>
     147             :     {
     148        1479 :       using _Mem_fn_base<_Res _Class::*>::_Mem_fn_base;
     149             :     };
     150             : 
     151             :   // _GLIBCXX_RESOLVE_LIB_DEFECTS
     152             :   // 2048.  Unnecessary mem_fn overloads
     153             :   /**
     154             :    *  @brief Returns a function object that forwards to the member
     155             :    *  pointer @a pm.
     156             :    *  @ingroup functors
     157             :    */
     158             :   template<typename _Tp, typename _Class>
     159             :     inline _Mem_fn<_Tp _Class::*>
     160        1479 :     mem_fn(_Tp _Class::* __pm) noexcept
     161             :     {
     162        1479 :       return _Mem_fn<_Tp _Class::*>(__pm);
     163             :     }
     164             : 
     165             :   /**
     166             :    *  @brief Determines if the given type _Tp is a function object that
     167             :    *  should be treated as a subexpression when evaluating calls to
     168             :    *  function objects returned by bind().
     169             :    *
     170             :    *  C++11 [func.bind.isbind].
     171             :    *  @ingroup binders
     172             :    */
     173             :   template<typename _Tp>
     174             :     struct is_bind_expression
     175             :     : public false_type { };
     176             : 
     177             :   /**
     178             :    *  @brief Determines if the given type _Tp is a placeholder in a
     179             :    *  bind() expression and, if so, which placeholder it is.
     180             :    *
     181             :    *  C++11 [func.bind.isplace].
     182             :    *  @ingroup binders
     183             :    */
     184             :   template<typename _Tp>
     185             :     struct is_placeholder
     186             :     : public integral_constant<int, 0>
     187             :     { };
     188             : 
     189             : #if __cplusplus > 201402L
     190             :   template <typename _Tp> inline constexpr bool is_bind_expression_v
     191             :     = is_bind_expression<_Tp>::value;
     192             :   template <typename _Tp> inline constexpr int is_placeholder_v
     193             :     = is_placeholder<_Tp>::value;
     194             : #endif // C++17
     195             : 
     196             :   /** @brief The type of placeholder objects defined by libstdc++.
     197             :    *  @ingroup binders
     198             :    */
     199             :   template<int _Num> struct _Placeholder { };
     200             : 
     201             :   /** @namespace std::placeholders
     202             :    *  @brief ISO C++11 entities sub-namespace for functional.
     203             :    *  @ingroup binders
     204             :    */
     205             :   namespace placeholders
     206             :   {
     207             :   /* Define a large number of placeholders. There is no way to
     208             :    * simplify this with variadic templates, because we're introducing
     209             :    * unique names for each.
     210             :    */
     211             :     extern const _Placeholder<1> _1;
     212             :     extern const _Placeholder<2> _2;
     213             :     extern const _Placeholder<3> _3;
     214             :     extern const _Placeholder<4> _4;
     215             :     extern const _Placeholder<5> _5;
     216             :     extern const _Placeholder<6> _6;
     217             :     extern const _Placeholder<7> _7;
     218             :     extern const _Placeholder<8> _8;
     219             :     extern const _Placeholder<9> _9;
     220             :     extern const _Placeholder<10> _10;
     221             :     extern const _Placeholder<11> _11;
     222             :     extern const _Placeholder<12> _12;
     223             :     extern const _Placeholder<13> _13;
     224             :     extern const _Placeholder<14> _14;
     225             :     extern const _Placeholder<15> _15;
     226             :     extern const _Placeholder<16> _16;
     227             :     extern const _Placeholder<17> _17;
     228             :     extern const _Placeholder<18> _18;
     229             :     extern const _Placeholder<19> _19;
     230             :     extern const _Placeholder<20> _20;
     231             :     extern const _Placeholder<21> _21;
     232             :     extern const _Placeholder<22> _22;
     233             :     extern const _Placeholder<23> _23;
     234             :     extern const _Placeholder<24> _24;
     235             :     extern const _Placeholder<25> _25;
     236             :     extern const _Placeholder<26> _26;
     237             :     extern const _Placeholder<27> _27;
     238             :     extern const _Placeholder<28> _28;
     239             :     extern const _Placeholder<29> _29;
     240             :   }
     241             : 
     242             :   /**
     243             :    *  Partial specialization of is_placeholder that provides the placeholder
     244             :    *  number for the placeholder objects defined by libstdc++.
     245             :    *  @ingroup binders
     246             :    */
     247             :   template<int _Num>
     248             :     struct is_placeholder<_Placeholder<_Num> >
     249             :     : public integral_constant<int, _Num>
     250             :     { };
     251             : 
     252             :   template<int _Num>
     253             :     struct is_placeholder<const _Placeholder<_Num> >
     254             :     : public integral_constant<int, _Num>
     255             :     { };
     256             : 
     257             : 
     258             :   // Like tuple_element_t but SFINAE-friendly.
     259             :   template<std::size_t __i, typename _Tuple>
     260             :     using _Safe_tuple_element_t
     261             :       = typename enable_if<(__i < tuple_size<_Tuple>::value),
     262             :                            tuple_element<__i, _Tuple>>::type::type;
     263             : 
     264             :   /**
     265             :    *  Maps an argument to bind() into an actual argument to the bound
     266             :    *  function object [func.bind.bind]/10. Only the first parameter should
     267             :    *  be specified: the rest are used to determine among the various
     268             :    *  implementations. Note that, although this class is a function
     269             :    *  object, it isn't entirely normal because it takes only two
     270             :    *  parameters regardless of the number of parameters passed to the
     271             :    *  bind expression. The first parameter is the bound argument and
     272             :    *  the second parameter is a tuple containing references to the
     273             :    *  rest of the arguments.
     274             :    */
     275             :   template<typename _Arg,
     276             :            bool _IsBindExp = is_bind_expression<_Arg>::value,
     277             :            bool _IsPlaceholder = (is_placeholder<_Arg>::value > 0)>
     278             :     class _Mu;
     279             : 
     280             :   /**
     281             :    *  If the argument is reference_wrapper<_Tp>, returns the
     282             :    *  underlying reference.
     283             :    *  C++11 [func.bind.bind] p10 bullet 1.
     284             :    */
     285             :   template<typename _Tp>
     286             :     class _Mu<reference_wrapper<_Tp>, false, false>
     287             :     {
     288             :     public:
     289             :       /* Note: This won't actually work for const volatile
     290             :        * reference_wrappers, because reference_wrapper::get() is const
     291             :        * but not volatile-qualified. This might be a defect in the TR.
     292             :        */
     293             :       template<typename _CVRef, typename _Tuple>
     294             :         _Tp&
     295             :         operator()(_CVRef& __arg, _Tuple&) const volatile
     296             :         { return __arg.get(); }
     297             :     };
     298             : 
     299             :   /**
     300             :    *  If the argument is a bind expression, we invoke the underlying
     301             :    *  function object with the same cv-qualifiers as we are given and
     302             :    *  pass along all of our arguments (unwrapped).
     303             :    *  C++11 [func.bind.bind] p10 bullet 2.
     304             :    */
     305             :   template<typename _Arg>
     306             :     class _Mu<_Arg, true, false>
     307             :     {
     308             :     public:
     309             :       template<typename _CVArg, typename... _Args>
     310             :         auto
     311             :         operator()(_CVArg& __arg,
     312             :                    tuple<_Args...>& __tuple) const volatile
     313             :         -> decltype(__arg(declval<_Args>()...))
     314             :         {
     315             :           // Construct an index tuple and forward to __call
     316             :           typedef typename _Build_index_tuple<sizeof...(_Args)>::__type
     317             :             _Indexes;
     318             :           return this->__call(__arg, __tuple, _Indexes());
     319             :         }
     320             : 
     321             :     private:
     322             :       // Invokes the underlying function object __arg by unpacking all
     323             :       // of the arguments in the tuple.
     324             :       template<typename _CVArg, typename... _Args, std::size_t... _Indexes>
     325             :         auto
     326             :         __call(_CVArg& __arg, tuple<_Args...>& __tuple,
     327             :                const _Index_tuple<_Indexes...>&) const volatile
     328             :         -> decltype(__arg(declval<_Args>()...))
     329             :         {
     330             :           return __arg(std::get<_Indexes>(std::move(__tuple))...);
     331             :         }
     332             :     };
     333             : 
     334             :   /**
     335             :    *  If the argument is a placeholder for the Nth argument, returns
     336             :    *  a reference to the Nth argument to the bind function object.
     337             :    *  C++11 [func.bind.bind] p10 bullet 3.
     338             :    */
     339             :   template<typename _Arg>
     340             :     class _Mu<_Arg, false, true>
     341             :     {
     342             :     public:
     343             :       template<typename _Tuple>
     344             :         _Safe_tuple_element_t<(is_placeholder<_Arg>::value - 1), _Tuple>&&
     345      385096 :         operator()(const volatile _Arg&, _Tuple& __tuple) const volatile
     346             :         {
     347             :           return
     348      385096 :             ::std::get<(is_placeholder<_Arg>::value - 1)>(std::move(__tuple));
     349             :         }
     350             :     };
     351             : 
     352             :   /**
     353             :    *  If the argument is just a value, returns a reference to that
     354             :    *  value. The cv-qualifiers on the reference are determined by the caller.
     355             :    *  C++11 [func.bind.bind] p10 bullet 4.
     356             :    */
     357             :   template<typename _Arg>
     358             :     class _Mu<_Arg, false, false>
     359             :     {
     360             :     public:
     361             :       template<typename _CVArg, typename _Tuple>
     362             :         _CVArg&&
     363      385096 :         operator()(_CVArg&& __arg, _Tuple&) const volatile
     364      385096 :         { return std::forward<_CVArg>(__arg); }
     365             :     };
     366             : 
     367             :   // std::get<I> for volatile-qualified tuples
     368             :   template<std::size_t _Ind, typename... _Tp>
     369             :     inline auto
     370             :     __volget(volatile tuple<_Tp...>& __tuple)
     371             :     -> __tuple_element_t<_Ind, tuple<_Tp...>> volatile&
     372             :     { return std::get<_Ind>(const_cast<tuple<_Tp...>&>(__tuple)); }
     373             : 
     374             :   // std::get<I> for const-volatile-qualified tuples
     375             :   template<std::size_t _Ind, typename... _Tp>
     376             :     inline auto
     377             :     __volget(const volatile tuple<_Tp...>& __tuple)
     378             :     -> __tuple_element_t<_Ind, tuple<_Tp...>> const volatile&
     379             :     { return std::get<_Ind>(const_cast<const tuple<_Tp...>&>(__tuple)); }
     380             : 
     381             :   /// Type of the function object returned from bind().
     382             :   template<typename _Signature>
     383             :     struct _Bind;
     384             : 
     385             :    template<typename _Functor, typename... _Bound_args>
     386           0 :     class _Bind<_Functor(_Bound_args...)>
     387             :     : public _Weak_result_type<_Functor>
     388             :     {
     389             :       typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type
     390             :         _Bound_indexes;
     391             : 
     392             :       _Functor _M_f;
     393             :       tuple<_Bound_args...> _M_bound_args;
     394             : 
     395             :       // Call unqualified
     396             :       template<typename _Result, typename... _Args, std::size_t... _Indexes>
     397             :         _Result
     398      385096 :         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)
     399             :         {
     400      385096 :           return std::__invoke(_M_f,
     401      385096 :               _Mu<_Bound_args>()(std::get<_Indexes>(_M_bound_args), __args)...
     402           0 :               );
     403             :         }
     404             : 
     405             :       // Call as const
     406             :       template<typename _Result, typename... _Args, std::size_t... _Indexes>
     407             :         _Result
     408             :         __call_c(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const
     409             :         {
     410             :           return std::__invoke(_M_f,
     411             :               _Mu<_Bound_args>()(std::get<_Indexes>(_M_bound_args), __args)...
     412             :               );
     413             :         }
     414             : 
     415             :       // Call as volatile
     416             :       template<typename _Result, typename... _Args, std::size_t... _Indexes>
     417             :         _Result
     418             :         __call_v(tuple<_Args...>&& __args,
     419             :                  _Index_tuple<_Indexes...>) volatile
     420             :         {
     421             :           return std::__invoke(_M_f,
     422             :               _Mu<_Bound_args>()(__volget<_Indexes>(_M_bound_args), __args)...
     423             :               );
     424             :         }
     425             : 
     426             :       // Call as const volatile
     427             :       template<typename _Result, typename... _Args, std::size_t... _Indexes>
     428             :         _Result
     429             :         __call_c_v(tuple<_Args...>&& __args,
     430             :                    _Index_tuple<_Indexes...>) const volatile
     431             :         {
     432             :           return std::__invoke(_M_f,
     433             :               _Mu<_Bound_args>()(__volget<_Indexes>(_M_bound_args), __args)...
     434             :               );
     435             :         }
     436             : 
     437             :       template<typename _BoundArg, typename _CallArgs>
     438             :         using _Mu_type = decltype(
     439             :             _Mu<typename remove_cv<_BoundArg>::type>()(
     440             :               std::declval<_BoundArg&>(), std::declval<_CallArgs&>()) );
     441             : 
     442             :       template<typename _Fn, typename _CallArgs, typename... _BArgs>
     443             :         using _Res_type_impl
     444             :           = typename result_of< _Fn&(_Mu_type<_BArgs, _CallArgs>&&...) >::type;
     445             : 
     446             :       template<typename _CallArgs>
     447             :         using _Res_type = _Res_type_impl<_Functor, _CallArgs, _Bound_args...>;
     448             : 
     449             :       template<typename _CallArgs>
     450             :         using __dependent = typename
     451             :           enable_if<bool(tuple_size<_CallArgs>::value+1), _Functor>::type;
     452             : 
     453             :       template<typename _CallArgs, template<class> class __cv_quals>
     454             :         using _Res_type_cv = _Res_type_impl<
     455             :           typename __cv_quals<__dependent<_CallArgs>>::type,
     456             :           _CallArgs,
     457             :           typename __cv_quals<_Bound_args>::type...>;
     458             : 
     459             :      public:
     460             :       template<typename... _Args>
     461         326 :         explicit _Bind(const _Functor& __f, _Args&&... __args)
     462         326 :         : _M_f(__f), _M_bound_args(std::forward<_Args>(__args)...)
     463             :         { }
     464             : 
     465             :       template<typename... _Args>
     466           0 :         explicit _Bind(_Functor&& __f, _Args&&... __args)
     467           0 :         : _M_f(std::move(__f)), _M_bound_args(std::forward<_Args>(__args)...)
     468           0 :         { }
     469             : 
     470             :       _Bind(const _Bind&) = default;
     471             : 
     472             :       _Bind(_Bind&& __b)
     473             :       : _M_f(std::move(__b._M_f)), _M_bound_args(std::move(__b._M_bound_args))
     474             :       { }
     475             : 
     476             :       // Call unqualified
     477             :       template<typename... _Args,
     478             :                typename _Result = _Res_type<tuple<_Args...>>>
     479             :         _Result
     480      385096 :         operator()(_Args&&... __args)
     481             :         {
     482             :           return this->__call<_Result>(
     483             :               std::forward_as_tuple(std::forward<_Args>(__args)...),
     484      385096 :               _Bound_indexes());
     485             :         }
     486             : 
     487             :       // Call as const
     488             :       template<typename... _Args,
     489             :                typename _Result = _Res_type_cv<tuple<_Args...>, add_const>>
     490             :         _Result
     491             :         operator()(_Args&&... __args) const
     492             :         {
     493             :           return this->__call_c<_Result>(
     494             :               std::forward_as_tuple(std::forward<_Args>(__args)...),
     495             :               _Bound_indexes());
     496             :         }
     497             : 
     498             : #if __cplusplus > 201402L
     499             : # define _GLIBCXX_DEPR_BIND \
     500             :       [[deprecated("std::bind does not support volatile in C++17")]]
     501             : #else
     502             : # define _GLIBCXX_DEPR_BIND
     503             : #endif
     504             :       // Call as volatile
     505             :       template<typename... _Args,
     506             :                typename _Result = _Res_type_cv<tuple<_Args...>, add_volatile>>
     507             :         _GLIBCXX_DEPR_BIND
     508             :         _Result
     509             :         operator()(_Args&&... __args) volatile
     510             :         {
     511             :           return this->__call_v<_Result>(
     512             :               std::forward_as_tuple(std::forward<_Args>(__args)...),
     513             :               _Bound_indexes());
     514             :         }
     515             : 
     516             :       // Call as const volatile
     517             :       template<typename... _Args,
     518             :                typename _Result = _Res_type_cv<tuple<_Args...>, add_cv>>
     519             :         _GLIBCXX_DEPR_BIND
     520             :         _Result
     521             :         operator()(_Args&&... __args) const volatile
     522             :         {
     523             :           return this->__call_c_v<_Result>(
     524             :               std::forward_as_tuple(std::forward<_Args>(__args)...),
     525             :               _Bound_indexes());
     526             :         }
     527             :     };
     528             : 
     529             :   /// Type of the function object returned from bind<R>().
     530             :   template<typename _Result, typename _Signature>
     531             :     struct _Bind_result;
     532             : 
     533             :   template<typename _Result, typename _Functor, typename... _Bound_args>
     534             :     class _Bind_result<_Result, _Functor(_Bound_args...)>
     535             :     {
     536             :       typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type
     537             :         _Bound_indexes;
     538             : 
     539             :       _Functor _M_f;
     540             :       tuple<_Bound_args...> _M_bound_args;
     541             : 
     542             :       // sfinae types
     543             :       template<typename _Res>
     544             :         using __enable_if_void
     545             :           = typename enable_if<is_void<_Res>{}>::type;
     546             : 
     547             :       template<typename _Res>
     548             :         using __disable_if_void
     549             :           = typename enable_if<!is_void<_Res>{}, _Result>::type;
     550             : 
     551             :       // Call unqualified
     552             :       template<typename _Res, typename... _Args, std::size_t... _Indexes>
     553             :         __disable_if_void<_Res>
     554             :         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)
     555             :         {
     556             :           return std::__invoke(_M_f, _Mu<_Bound_args>()
     557             :                       (std::get<_Indexes>(_M_bound_args), __args)...);
     558             :         }
     559             : 
     560             :       // Call unqualified, return void
     561             :       template<typename _Res, typename... _Args, std::size_t... _Indexes>
     562             :         __enable_if_void<_Res>
     563             :         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)
     564             :         {
     565             :           std::__invoke(_M_f, _Mu<_Bound_args>()
     566             :                (std::get<_Indexes>(_M_bound_args), __args)...);
     567             :         }
     568             : 
     569             :       // Call as const
     570             :       template<typename _Res, typename... _Args, std::size_t... _Indexes>
     571             :         __disable_if_void<_Res>
     572             :         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const
     573             :         {
     574             :           return std::__invoke(_M_f, _Mu<_Bound_args>()
     575             :                       (std::get<_Indexes>(_M_bound_args), __args)...);
     576             :         }
     577             : 
     578             :       // Call as const, return void
     579             :       template<typename _Res, typename... _Args, std::size_t... _Indexes>
     580             :         __enable_if_void<_Res>
     581             :         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const
     582             :         {
     583             :           std::__invoke(_M_f, _Mu<_Bound_args>()
     584             :                (std::get<_Indexes>(_M_bound_args),  __args)...);
     585             :         }
     586             : 
     587             :       // Call as volatile
     588             :       template<typename _Res, typename... _Args, std::size_t... _Indexes>
     589             :         __disable_if_void<_Res>
     590             :         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) volatile
     591             :         {
     592             :           return std::__invoke(_M_f, _Mu<_Bound_args>()
     593             :                       (__volget<_Indexes>(_M_bound_args), __args)...);
     594             :         }
     595             : 
     596             :       // Call as volatile, return void
     597             :       template<typename _Res, typename... _Args, std::size_t... _Indexes>
     598             :         __enable_if_void<_Res>
     599             :         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) volatile
     600             :         {
     601             :           std::__invoke(_M_f, _Mu<_Bound_args>()
     602             :                (__volget<_Indexes>(_M_bound_args), __args)...);
     603             :         }
     604             : 
     605             :       // Call as const volatile
     606             :       template<typename _Res, typename... _Args, std::size_t... _Indexes>
     607             :         __disable_if_void<_Res>
     608             :         __call(tuple<_Args...>&& __args,
     609             :                _Index_tuple<_Indexes...>) const volatile
     610             :         {
     611             :           return std::__invoke(_M_f, _Mu<_Bound_args>()
     612             :                       (__volget<_Indexes>(_M_bound_args), __args)...);
     613             :         }
     614             : 
     615             :       // Call as const volatile, return void
     616             :       template<typename _Res, typename... _Args, std::size_t... _Indexes>
     617             :         __enable_if_void<_Res>
     618             :         __call(tuple<_Args...>&& __args,
     619             :                _Index_tuple<_Indexes...>) const volatile
     620             :         {
     621             :           std::__invoke(_M_f, _Mu<_Bound_args>()
     622             :                (__volget<_Indexes>(_M_bound_args), __args)...);
     623             :         }
     624             : 
     625             :     public:
     626             :       typedef _Result result_type;
     627             : 
     628             :       template<typename... _Args>
     629             :         explicit _Bind_result(const _Functor& __f, _Args&&... __args)
     630             :         : _M_f(__f), _M_bound_args(std::forward<_Args>(__args)...)
     631             :         { }
     632             : 
     633             :       template<typename... _Args>
     634             :         explicit _Bind_result(_Functor&& __f, _Args&&... __args)
     635             :         : _M_f(std::move(__f)), _M_bound_args(std::forward<_Args>(__args)...)
     636             :         { }
     637             : 
     638             :       _Bind_result(const _Bind_result&) = default;
     639             : 
     640             :       _Bind_result(_Bind_result&& __b)
     641             :       : _M_f(std::move(__b._M_f)), _M_bound_args(std::move(__b._M_bound_args))
     642             :       { }
     643             : 
     644             :       // Call unqualified
     645             :       template<typename... _Args>
     646             :         result_type
     647             :         operator()(_Args&&... __args)
     648             :         {
     649             :           return this->__call<_Result>(
     650             :               std::forward_as_tuple(std::forward<_Args>(__args)...),
     651             :               _Bound_indexes());
     652             :         }
     653             : 
     654             :       // Call as const
     655             :       template<typename... _Args>
     656             :         result_type
     657             :         operator()(_Args&&... __args) const
     658             :         {
     659             :           return this->__call<_Result>(
     660             :               std::forward_as_tuple(std::forward<_Args>(__args)...),
     661             :               _Bound_indexes());
     662             :         }
     663             : 
     664             :       // Call as volatile
     665             :       template<typename... _Args>
     666             :         _GLIBCXX_DEPR_BIND
     667             :         result_type
     668             :         operator()(_Args&&... __args) volatile
     669             :         {
     670             :           return this->__call<_Result>(
     671             :               std::forward_as_tuple(std::forward<_Args>(__args)...),
     672             :               _Bound_indexes());
     673             :         }
     674             : 
     675             :       // Call as const volatile
     676             :       template<typename... _Args>
     677             :         _GLIBCXX_DEPR_BIND
     678             :         result_type
     679             :         operator()(_Args&&... __args) const volatile
     680             :         {
     681             :           return this->__call<_Result>(
     682             :               std::forward_as_tuple(std::forward<_Args>(__args)...),
     683             :               _Bound_indexes());
     684             :         }
     685             :     };
     686             : #undef _GLIBCXX_DEPR_BIND
     687             : 
     688             :   /**
     689             :    *  @brief Class template _Bind is always a bind expression.
     690             :    *  @ingroup binders
     691             :    */
     692             :   template<typename _Signature>
     693             :     struct is_bind_expression<_Bind<_Signature> >
     694             :     : public true_type { };
     695             : 
     696             :   /**
     697             :    *  @brief Class template _Bind is always a bind expression.
     698             :    *  @ingroup binders
     699             :    */
     700             :   template<typename _Signature>
     701             :     struct is_bind_expression<const _Bind<_Signature> >
     702             :     : public true_type { };
     703             : 
     704             :   /**
     705             :    *  @brief Class template _Bind is always a bind expression.
     706             :    *  @ingroup binders
     707             :    */
     708             :   template<typename _Signature>
     709             :     struct is_bind_expression<volatile _Bind<_Signature> >
     710             :     : public true_type { };
     711             : 
     712             :   /**
     713             :    *  @brief Class template _Bind is always a bind expression.
     714             :    *  @ingroup binders
     715             :    */
     716             :   template<typename _Signature>
     717             :     struct is_bind_expression<const volatile _Bind<_Signature>>
     718             :     : public true_type { };
     719             : 
     720             :   /**
     721             :    *  @brief Class template _Bind_result is always a bind expression.
     722             :    *  @ingroup binders
     723             :    */
     724             :   template<typename _Result, typename _Signature>
     725             :     struct is_bind_expression<_Bind_result<_Result, _Signature>>
     726             :     : public true_type { };
     727             : 
     728             :   /**
     729             :    *  @brief Class template _Bind_result is always a bind expression.
     730             :    *  @ingroup binders
     731             :    */
     732             :   template<typename _Result, typename _Signature>
     733             :     struct is_bind_expression<const _Bind_result<_Result, _Signature>>
     734             :     : public true_type { };
     735             : 
     736             :   /**
     737             :    *  @brief Class template _Bind_result is always a bind expression.
     738             :    *  @ingroup binders
     739             :    */
     740             :   template<typename _Result, typename _Signature>
     741             :     struct is_bind_expression<volatile _Bind_result<_Result, _Signature>>
     742             :     : public true_type { };
     743             : 
     744             :   /**
     745             :    *  @brief Class template _Bind_result is always a bind expression.
     746             :    *  @ingroup binders
     747             :    */
     748             :   template<typename _Result, typename _Signature>
     749             :     struct is_bind_expression<const volatile _Bind_result<_Result, _Signature>>
     750             :     : public true_type { };
     751             : 
     752             :   template<typename _Func, typename... _BoundArgs>
     753             :     struct _Bind_check_arity { };
     754             : 
     755             :   template<typename _Ret, typename... _Args, typename... _BoundArgs>
     756             :     struct _Bind_check_arity<_Ret (*)(_Args...), _BoundArgs...>
     757             :     {
     758             :       static_assert(sizeof...(_BoundArgs) == sizeof...(_Args),
     759             :                    "Wrong number of arguments for function");
     760             :     };
     761             : 
     762             :   template<typename _Ret, typename... _Args, typename... _BoundArgs>
     763             :     struct _Bind_check_arity<_Ret (*)(_Args......), _BoundArgs...>
     764             :     {
     765             :       static_assert(sizeof...(_BoundArgs) >= sizeof...(_Args),
     766             :                    "Wrong number of arguments for function");
     767             :     };
     768             : 
     769             :   template<typename _Tp, typename _Class, typename... _BoundArgs>
     770             :     struct _Bind_check_arity<_Tp _Class::*, _BoundArgs...>
     771             :     {
     772             :       using _Arity = typename _Mem_fn<_Tp _Class::*>::_Arity;
     773             :       using _Varargs = typename _Mem_fn<_Tp _Class::*>::_Varargs;
     774             :       static_assert(_Varargs::value
     775             :                     ? sizeof...(_BoundArgs) >= _Arity::value + 1
     776             :                     : sizeof...(_BoundArgs) == _Arity::value + 1,
     777             :                     "Wrong number of arguments for pointer-to-member");
     778             :     };
     779             : 
     780             :   // Trait type used to remove std::bind() from overload set via SFINAE
     781             :   // when first argument has integer type, so that std::bind() will
     782             :   // not be a better match than ::bind() from the BSD Sockets API.
     783             :   template<typename _Tp, typename _Tp2 = typename decay<_Tp>::type>
     784             :     using __is_socketlike = __or_<is_integral<_Tp2>, is_enum<_Tp2>>;
     785             : 
     786             :   template<bool _SocketLike, typename _Func, typename... _BoundArgs>
     787             :     struct _Bind_helper
     788             :     : _Bind_check_arity<typename decay<_Func>::type, _BoundArgs...>
     789             :     {
     790             :       typedef typename decay<_Func>::type __func_type;
     791             :       typedef _Bind<__func_type(typename decay<_BoundArgs>::type...)> type;
     792             :     };
     793             : 
     794             :   // Partial specialization for is_socketlike == true, does not define
     795             :   // nested type so std::bind() will not participate in overload resolution
     796             :   // when the first argument might be a socket file descriptor.
     797             :   template<typename _Func, typename... _BoundArgs>
     798             :     struct _Bind_helper<true, _Func, _BoundArgs...>
     799             :     { };
     800             : 
     801             :   /**
     802             :    *  @brief Function template for std::bind.
     803             :    *  @ingroup binders
     804             :    */
     805             :   template<typename _Func, typename... _BoundArgs>
     806             :     inline typename
     807             :     _Bind_helper<__is_socketlike<_Func>::value, _Func, _BoundArgs...>::type
     808         326 :     bind(_Func&& __f, _BoundArgs&&... __args)
     809             :     {
     810             :       typedef _Bind_helper<false, _Func, _BoundArgs...> __helper_type;
     811         326 :       return typename __helper_type::type(std::forward<_Func>(__f),
     812         326 :                                           std::forward<_BoundArgs>(__args)...);
     813             :     }
     814             : 
     815             :   template<typename _Result, typename _Func, typename... _BoundArgs>
     816             :     struct _Bindres_helper
     817             :     : _Bind_check_arity<typename decay<_Func>::type, _BoundArgs...>
     818             :     {
     819             :       typedef typename decay<_Func>::type __functor_type;
     820             :       typedef _Bind_result<_Result,
     821             :                            __functor_type(typename decay<_BoundArgs>::type...)>
     822             :         type;
     823             :     };
     824             : 
     825             :   /**
     826             :    *  @brief Function template for std::bind<R>.
     827             :    *  @ingroup binders
     828             :    */
     829             :   template<typename _Result, typename _Func, typename... _BoundArgs>
     830             :     inline
     831             :     typename _Bindres_helper<_Result, _Func, _BoundArgs...>::type
     832             :     bind(_Func&& __f, _BoundArgs&&... __args)
     833             :     {
     834             :       typedef _Bindres_helper<_Result, _Func, _BoundArgs...> __helper_type;
     835             :       return typename __helper_type::type(std::forward<_Func>(__f),
     836             :                                           std::forward<_BoundArgs>(__args)...);
     837             :     }
     838             : 
     839             : #if __cplusplus > 201703L
     840             : #define __cpp_lib_bind_front 201907L
     841             : 
     842             :   template<typename _Fd, typename... _BoundArgs>
     843             :     struct _Bind_front
     844             :     {
     845             :       static_assert(is_move_constructible_v<_Fd>);
     846             :       static_assert((is_move_constructible_v<_BoundArgs> && ...));
     847             : 
     848             :       // First parameter is to ensure this constructor is never used
     849             :       // instead of the copy/move constructor.
     850             :       template<typename _Fn, typename... _Args>
     851             :         explicit constexpr
     852             :         _Bind_front(int, _Fn&& __fn, _Args&&... __args)
     853             :         noexcept(__and_<is_nothrow_constructible<_Fd, _Fn>,
     854             :                         is_nothrow_constructible<_BoundArgs, _Args>...>::value)
     855             :         : _M_fd(std::forward<_Fn>(__fn)),
     856             :           _M_bound_args(std::forward<_Args>(__args)...)
     857             :         { static_assert(sizeof...(_Args) == sizeof...(_BoundArgs)); }
     858             : 
     859             :       _Bind_front(const _Bind_front&) = default;
     860             :       _Bind_front(_Bind_front&&) = default;
     861             :       _Bind_front& operator=(const _Bind_front&) = default;
     862             :       _Bind_front& operator=(_Bind_front&&) = default;
     863             :       ~_Bind_front() = default;
     864             : 
     865             :       template<typename... _CallArgs>
     866             :         constexpr
     867             :         invoke_result_t<_Fd&, _BoundArgs&..., _CallArgs...>
     868             :         operator()(_CallArgs&&... __call_args) &
     869             :         noexcept(is_nothrow_invocable_v<_Fd&, _BoundArgs&..., _CallArgs...>)
     870             :         {
     871             :           return _S_call(*this, _BoundIndices(),
     872             :               std::forward<_CallArgs>(__call_args)...);
     873             :         }
     874             : 
     875             :       template<typename... _CallArgs>
     876             :         constexpr
     877             :         invoke_result_t<const _Fd&, const _BoundArgs&..., _CallArgs...>
     878             :         operator()(_CallArgs&&... __call_args) const &
     879             :         noexcept(is_nothrow_invocable_v<const _Fd&, const _BoundArgs&...,
     880             :                                         _CallArgs...>)
     881             :         {
     882             :           return _S_call(*this, _BoundIndices(),
     883             :               std::forward<_CallArgs>(__call_args)...);
     884             :         }
     885             : 
     886             :       template<typename... _CallArgs>
     887             :         constexpr
     888             :         invoke_result_t<_Fd, _BoundArgs..., _CallArgs...>
     889             :         operator()(_CallArgs&&... __call_args) &&
     890             :         noexcept(is_nothrow_invocable_v<_Fd, _BoundArgs..., _CallArgs...>)
     891             :         {
     892             :           return _S_call(std::move(*this), _BoundIndices(),
     893             :               std::forward<_CallArgs>(__call_args)...);
     894             :         }
     895             : 
     896             :       template<typename... _CallArgs>
     897             :         constexpr
     898             :         invoke_result_t<const _Fd, const _BoundArgs..., _CallArgs...>
     899             :         operator()(_CallArgs&&... __call_args) const &&
     900             :         noexcept(is_nothrow_invocable_v<const _Fd, const _BoundArgs...,
     901             :                                         _CallArgs...>)
     902             :         {
     903             :           return _S_call(std::move(*this), _BoundIndices(),
     904             :               std::forward<_CallArgs>(__call_args)...);
     905             :         }
     906             : 
     907             :     private:
     908             :       using _BoundIndices = index_sequence_for<_BoundArgs...>;
     909             : 
     910             :       template<typename _Tp, size_t... _Ind, typename... _CallArgs>
     911             :         static constexpr
     912             :         decltype(auto)
     913             :         _S_call(_Tp&& __g, index_sequence<_Ind...>, _CallArgs&&... __call_args)
     914             :         {
     915             :           return std::invoke(std::forward<_Tp>(__g)._M_fd,
     916             :               std::get<_Ind>(std::forward<_Tp>(__g)._M_bound_args)...,
     917             :               std::forward<_CallArgs>(__call_args)...);
     918             :         }
     919             : 
     920             :       _Fd _M_fd;
     921             :       std::tuple<_BoundArgs...> _M_bound_args;
     922             :     };
     923             : 
     924             :   template<typename _Fn, typename... _Args>
     925             :     using _Bind_front_t
     926             :       = _Bind_front<decay_t<_Fn>, decay_t<_Args>...>;
     927             : 
     928             :   template<typename _Fn, typename... _Args>
     929             :     _Bind_front_t<_Fn, _Args...>
     930             :     bind_front(_Fn&& __fn, _Args&&... __args)
     931             :     noexcept(is_nothrow_constructible_v<_Bind_front_t<_Fn, _Args...>,
     932             :                                         int, _Fn, _Args...>)
     933             :     {
     934             :       return _Bind_front_t<_Fn, _Args...>(0, std::forward<_Fn>(__fn),
     935             :                                           std::forward<_Args>(__args)...);
     936             :     }
     937             : #endif
     938             : 
     939             : #if __cplusplus >= 201402L
     940             :   /// Generalized negator.
     941             :   template<typename _Fn>
     942             :     class _Not_fn
     943             :     {
     944             :       template<typename _Fn2, typename... _Args>
     945             :         using __inv_res_t = typename __invoke_result<_Fn2, _Args...>::type;
     946             : 
     947             :       template<typename _Tp>
     948             :         static decltype(!std::declval<_Tp>())
     949             :         _S_not() noexcept(noexcept(!std::declval<_Tp>()));
     950             : 
     951             :     public:
     952             :       template<typename _Fn2>
     953             :         _Not_fn(_Fn2&& __fn, int)
     954             :         : _M_fn(std::forward<_Fn2>(__fn)) { }
     955             : 
     956             :       _Not_fn(const _Not_fn& __fn) = default;
     957             :       _Not_fn(_Not_fn&& __fn) = default;
     958             :       ~_Not_fn() = default;
     959             : 
     960             :       // Macro to define operator() with given cv-qualifiers ref-qualifiers,
     961             :       // forwarding _M_fn and the function arguments with the same qualifiers,
     962             :       // and deducing the return type and exception-specification.
     963             : #define _GLIBCXX_NOT_FN_CALL_OP( _QUALS )                               \
     964             :       template<typename... _Args>                                 \
     965             :         decltype(_S_not<__inv_res_t<_Fn _QUALS, _Args...>>())               \
     966             :         operator()(_Args&&... __args) _QUALS                            \
     967             :         noexcept(__is_nothrow_invocable<_Fn _QUALS, _Args...>::value      \
     968             :             && noexcept(_S_not<__inv_res_t<_Fn _QUALS, _Args...>>()))       \
     969             :         {                                                               \
     970             :           return !std::__invoke(std::forward< _Fn _QUALS >(_M_fn),        \
     971             :                                 std::forward<_Args>(__args)...);  \
     972             :         }
     973             :       _GLIBCXX_NOT_FN_CALL_OP( & )
     974             :       _GLIBCXX_NOT_FN_CALL_OP( const & )
     975             :       _GLIBCXX_NOT_FN_CALL_OP( && )
     976             :       _GLIBCXX_NOT_FN_CALL_OP( const && )
     977             : #undef _GLIBCXX_NOT_FN_CALL_OP
     978             : 
     979             :     private:
     980             :       _Fn _M_fn;
     981             :     };
     982             : 
     983             :   template<typename _Tp, typename _Pred>
     984             :     struct __is_byte_like : false_type { };
     985             : 
     986             :   template<typename _Tp>
     987             :     struct __is_byte_like<_Tp, equal_to<_Tp>>
     988             :     : __bool_constant<sizeof(_Tp) == 1 && is_integral<_Tp>::value> { };
     989             : 
     990             :   template<typename _Tp>
     991             :     struct __is_byte_like<_Tp, equal_to<void>>
     992             :     : __bool_constant<sizeof(_Tp) == 1 && is_integral<_Tp>::value> { };
     993             : 
     994             : #if __cplusplus >= 201703L
     995             :   // Declare std::byte (full definition is in <cstddef>).
     996             :   enum class byte : unsigned char;
     997             : 
     998             :   template<>
     999             :     struct __is_byte_like<byte, equal_to<byte>>
    1000             :     : true_type { };
    1001             : 
    1002             :   template<>
    1003             :     struct __is_byte_like<byte, equal_to<void>>
    1004             :     : true_type { };
    1005             : 
    1006             : #define __cpp_lib_not_fn 201603
    1007             :   /// [func.not_fn] Function template not_fn
    1008             :   template<typename _Fn>
    1009             :     inline auto
    1010             :     not_fn(_Fn&& __fn)
    1011             :     noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
    1012             :     {
    1013             :       return _Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0};
    1014             :     }
    1015             : 
    1016             :   // Searchers
    1017             : #define __cpp_lib_boyer_moore_searcher 201603
    1018             : 
    1019             :   template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>
    1020             :     class default_searcher
    1021             :     {
    1022             :     public:
    1023             :       default_searcher(_ForwardIterator1 __pat_first,
    1024             :                        _ForwardIterator1 __pat_last,
    1025             :                        _BinaryPredicate __pred = _BinaryPredicate())
    1026             :       : _M_m(__pat_first, __pat_last, std::move(__pred))
    1027             :       { }
    1028             : 
    1029             :       template<typename _ForwardIterator2>
    1030             :         pair<_ForwardIterator2, _ForwardIterator2>
    1031             :         operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
    1032             :         {
    1033             :           _ForwardIterator2 __first_ret =
    1034             :             std::search(__first, __last, std::get<0>(_M_m), std::get<1>(_M_m),
    1035             :                         std::get<2>(_M_m));
    1036             :           auto __ret = std::make_pair(__first_ret, __first_ret);
    1037             :           if (__ret.first != __last)
    1038             :             std::advance(__ret.second, std::distance(std::get<0>(_M_m),
    1039             :                                                      std::get<1>(_M_m)));
    1040             :           return __ret;
    1041             :         }
    1042             : 
    1043             :     private:
    1044             :       tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m;
    1045             :     };
    1046             : 
    1047             :   template<typename _Key, typename _Tp, typename _Hash, typename _Pred>
    1048             :     struct __boyer_moore_map_base
    1049             :     {
    1050             :       template<typename _RAIter>
    1051             :         __boyer_moore_map_base(_RAIter __pat, size_t __patlen,
    1052             :                                _Hash&& __hf, _Pred&& __pred)
    1053             :         : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
    1054             :         {
    1055             :           if (__patlen > 0)
    1056             :             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
    1057             :               _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
    1058             :         }
    1059             : 
    1060             :       using __diff_type = _Tp;
    1061             : 
    1062             :       __diff_type
    1063             :       _M_lookup(_Key __key, __diff_type __not_found) const
    1064             :       {
    1065             :         auto __iter = _M_bad_char.find(__key);
    1066             :         if (__iter == _M_bad_char.end())
    1067             :           return __not_found;
    1068             :         return __iter->second;
    1069             :       }
    1070             : 
    1071             :       _Pred
    1072             :       _M_pred() const { return _M_bad_char.key_eq(); }
    1073             : 
    1074             :       _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
    1075             :     };
    1076             : 
    1077             :   template<typename _Tp, size_t _Len, typename _Pred>
    1078             :     struct __boyer_moore_array_base
    1079             :     {
    1080             :       template<typename _RAIter, typename _Unused>
    1081             :         __boyer_moore_array_base(_RAIter __pat, size_t __patlen,
    1082             :                                  _Unused&&, _Pred&& __pred)
    1083             :         : _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) }
    1084             :         {
    1085             :           std::get<0>(_M_bad_char).fill(__patlen);
    1086             :           if (__patlen > 0)
    1087             :             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
    1088             :               {
    1089             :                 auto __ch = __pat[__i];
    1090             :                 using _UCh = make_unsigned_t<decltype(__ch)>;
    1091             :                 auto __uch = static_cast<_UCh>(__ch);
    1092             :                 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
    1093             :               }
    1094             :         }
    1095             : 
    1096             :       using __diff_type = _Tp;
    1097             : 
    1098             :       template<typename _Key>
    1099             :         __diff_type
    1100             :         _M_lookup(_Key __key, __diff_type __not_found) const
    1101             :         {
    1102             :           auto __ukey = static_cast<make_unsigned_t<_Key>>(__key);
    1103             :           if (__ukey >= _Len)
    1104             :             return __not_found;
    1105             :           return std::get<0>(_M_bad_char)[__ukey];
    1106             :         }
    1107             : 
    1108             :       const _Pred&
    1109             :       _M_pred() const { return std::get<1>(_M_bad_char); }
    1110             : 
    1111             :       tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char;
    1112             :     };
    1113             : 
    1114             :   // Use __boyer_moore_array_base when pattern consists of narrow characters
    1115             :   // (or std::byte) and uses std::equal_to as the predicate.
    1116             :   template<typename _RAIter, typename _Hash, typename _Pred,
    1117             :            typename _Val = typename iterator_traits<_RAIter>::value_type,
    1118             :            typename _Diff = typename iterator_traits<_RAIter>::difference_type>
    1119             :     using __boyer_moore_base_t
    1120             :       = conditional_t<__is_byte_like<_Val, _Pred>::value,
    1121             :                       __boyer_moore_array_base<_Diff, 256, _Pred>,
    1122             :                       __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
    1123             : 
    1124             :   template<typename _RAIter, typename _Hash
    1125             :              = hash<typename iterator_traits<_RAIter>::value_type>,
    1126             :            typename _BinaryPredicate = equal_to<>>
    1127             :     class boyer_moore_searcher
    1128             :     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
    1129             :     {
    1130             :       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
    1131             :       using typename _Base::__diff_type;
    1132             : 
    1133             :     public:
    1134             :       boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
    1135             :                            _Hash __hf = _Hash(),
    1136             :                            _BinaryPredicate __pred = _BinaryPredicate());
    1137             : 
    1138             :       template<typename _RandomAccessIterator2>
    1139             :         pair<_RandomAccessIterator2, _RandomAccessIterator2>
    1140             :         operator()(_RandomAccessIterator2 __first,
    1141             :                    _RandomAccessIterator2 __last) const;
    1142             : 
    1143             :     private:
    1144             :       bool
    1145             :       _M_is_prefix(_RAIter __word, __diff_type __len,
    1146             :                    __diff_type __pos)
    1147             :       {
    1148             :         const auto& __pred = this->_M_pred();
    1149             :         __diff_type __suffixlen = __len - __pos;
    1150             :         for (__diff_type __i = 0; __i < __suffixlen; ++__i)
    1151             :           if (!__pred(__word[__i], __word[__pos + __i]))
    1152             :             return false;
    1153             :         return true;
    1154             :       }
    1155             : 
    1156             :       __diff_type
    1157             :       _M_suffix_length(_RAIter __word, __diff_type __len,
    1158             :                        __diff_type __pos)
    1159             :       {
    1160             :         const auto& __pred = this->_M_pred();
    1161             :         __diff_type __i = 0;
    1162             :         while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
    1163             :                && __i < __pos)
    1164             :           {
    1165             :             ++__i;
    1166             :           }
    1167             :         return __i;
    1168             :       }
    1169             : 
    1170             :       template<typename _Tp>
    1171             :         __diff_type
    1172             :         _M_bad_char_shift(_Tp __c) const
    1173             :         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
    1174             : 
    1175             :       _RAIter _M_pat;
    1176             :       _RAIter _M_pat_end;
    1177             :       _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
    1178             :     };
    1179             : 
    1180             :   template<typename _RAIter, typename _Hash
    1181             :              = hash<typename iterator_traits<_RAIter>::value_type>,
    1182             :            typename _BinaryPredicate = equal_to<>>
    1183             :     class boyer_moore_horspool_searcher
    1184             :     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
    1185             :     {
    1186             :       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
    1187             :       using typename _Base::__diff_type;
    1188             : 
    1189             :     public:
    1190             :       boyer_moore_horspool_searcher(_RAIter __pat,
    1191             :                                     _RAIter __pat_end,
    1192             :                                     _Hash __hf = _Hash(),
    1193             :                                     _BinaryPredicate __pred
    1194             :                                     = _BinaryPredicate())
    1195             :       : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
    1196             :         _M_pat(__pat), _M_pat_end(__pat_end)
    1197             :       { }
    1198             : 
    1199             :       template<typename _RandomAccessIterator2>
    1200             :         pair<_RandomAccessIterator2, _RandomAccessIterator2>
    1201             :         operator()(_RandomAccessIterator2 __first,
    1202             :                    _RandomAccessIterator2 __last) const
    1203             :         {
    1204             :           const auto& __pred = this->_M_pred();
    1205             :           auto __patlen = _M_pat_end - _M_pat;
    1206             :           if (__patlen == 0)
    1207             :             return std::make_pair(__first, __first);
    1208             :           auto __len = __last - __first;
    1209             :           while (__len >= __patlen)
    1210             :             {
    1211             :               for (auto __scan = __patlen - 1;
    1212             :                    __pred(__first[__scan], _M_pat[__scan]); --__scan)
    1213             :                 if (__scan == 0)
    1214             :                   return std::make_pair(__first, __first + __patlen);
    1215             :               auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
    1216             :               __len -= __shift;
    1217             :               __first += __shift;
    1218             :             }
    1219             :           return std::make_pair(__last, __last);
    1220             :         }
    1221             : 
    1222             :     private:
    1223             :       template<typename _Tp>
    1224             :         __diff_type
    1225             :         _M_bad_char_shift(_Tp __c) const
    1226             :         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
    1227             : 
    1228             :       _RAIter _M_pat;
    1229             :       _RAIter _M_pat_end;
    1230             :     };
    1231             : 
    1232             :   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
    1233             :     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
    1234             :     boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
    1235             :                          _Hash __hf, _BinaryPredicate __pred)
    1236             :     : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
    1237             :       _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
    1238             :     {
    1239             :       auto __patlen = __pat_end - __pat;
    1240             :       if (__patlen == 0)
    1241             :         return;
    1242             :       __diff_type __last_prefix = __patlen - 1;
    1243             :       for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
    1244             :         {
    1245             :           if (_M_is_prefix(__pat, __patlen, __p + 1))
    1246             :             __last_prefix = __p + 1;
    1247             :           _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
    1248             :         }
    1249             :       for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
    1250             :         {
    1251             :           auto __slen = _M_suffix_length(__pat, __patlen, __p);
    1252             :           auto __pos = __patlen - 1 - __slen;
    1253             :           if (!__pred(__pat[__p - __slen], __pat[__pos]))
    1254             :             _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
    1255             :         }
    1256             :     }
    1257             : 
    1258             :   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
    1259             :   template<typename _RandomAccessIterator2>
    1260             :     pair<_RandomAccessIterator2, _RandomAccessIterator2>
    1261             :     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
    1262             :     operator()(_RandomAccessIterator2 __first,
    1263             :                _RandomAccessIterator2 __last) const
    1264             :     {
    1265             :       auto __patlen = _M_pat_end - _M_pat;
    1266             :       if (__patlen == 0)
    1267             :         return std::make_pair(__first, __first);
    1268             :       const auto& __pred = this->_M_pred();
    1269             :       __diff_type __i = __patlen - 1;
    1270             :       auto __stringlen = __last - __first;
    1271             :       while (__i < __stringlen)
    1272             :         {
    1273             :           __diff_type __j = __patlen - 1;
    1274             :           while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
    1275             :             {
    1276             :               --__i;
    1277             :               --__j;
    1278             :             }
    1279             :           if (__j < 0)
    1280             :             {
    1281             :               const auto __match = __first + __i + 1;
    1282             :               return std::make_pair(__match, __match + __patlen);
    1283             :             }
    1284             :           __i += std::max(_M_bad_char_shift(__first[__i]),
    1285             :                           _M_good_suffix[__j]);
    1286             :         }
    1287             :       return std::make_pair(__last, __last);
    1288             :     }
    1289             : 
    1290             : #endif // C++17
    1291             : #endif // C++14
    1292             : 
    1293             : _GLIBCXX_END_NAMESPACE_VERSION
    1294             : } // namespace std
    1295             : 
    1296             : #endif // C++11
    1297             : 
    1298             : #endif // _GLIBCXX_FUNCTIONAL

Generated by: LCOV version 1.14