libstdc++-v3/include/tr1/functional

   1 // TR1 functional header -*- C++ -*-
   2
   3 // Copyright (C) 2004, 2005 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 2, 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 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /** @file
  31  *  This is a TR1 C++ Library header.
  32  */
  33
  34 #ifndef _TR1_FUNCTIONAL
  35 #define _TR1_FUNCTIONAL 1
  36
  37 #pragma GCC system_header
  38
  39 #include "../functional"
  40 #include <typeinfo>
  41 #include <tr1/type_traits>
  42 #include <ext/type_traits.h>
  43 #include <string>               // for std::tr1::hash
  44 #include <cstdlib>              // for std::abort
  45 #include <cmath>                // for std::frexp
  46 #include <tr1/tuple>
  47
  48 namespace std
  49 {
  50 _GLIBCXX_BEGIN_NAMESPACE(tr1)
  51
  52   template<typename _MemberPointer>
  53     class _Mem_fn;
  54
  55   /**
  56    *  @if maint
  57    *  Actual implementation of _Has_result_type, which uses SFINAE to
  58    *  determine if the type _Tp has a publicly-accessible member type
  59    *  result_type.
  60    *  @endif
  61   */
  62   template<typename _Tp>
  63     class _Has_result_type_helper : __sfinae_types
  64     {
  65       template<typename _Up>
  66       struct _Wrap_type
  67       { };
  68
  69       template<typename _Up>
  70         static __one __test(_Wrap_type<typename _Up::result_type>*);
  71
  72       template<typename _Up>
  73         static __two __test(...);
  74
  75     public:
  76       static const bool value = sizeof(__test<_Tp>(0)) == 1;
  77     };
  78
  79   template<typename _Tp>
  80     struct _Has_result_type
  81        : integral_constant<
  82            bool,
  83            _Has_result_type_helper<typename remove_cv<_Tp>::type>::value>
  84     { };
  85
  86   /**
  87    *  @if maint
  88    *  If we have found a result_type, extract it.
  89    *  @endif
  90   */
  91   template<bool _Has_result_type, typename _Functor>
  92     struct _Maybe_get_result_type
  93     { };
  94
  95   template<typename _Functor>
  96     struct _Maybe_get_result_type<true, _Functor>
  97     {
  98       typedef typename _Functor::result_type result_type;
  99     };
 100
 101   /**
 102    *  @if maint
 103    *  Base class for any function object that has a weak result type, as
 104    *  defined in 3.3/3 of TR1.
 105    *  @endif
 106   */
 107   template<typename _Functor>
 108     struct _Weak_result_type_impl
 109       : _Maybe_get_result_type<_Has_result_type<_Functor>::value, _Functor>
 110     {
 111     };
 112
 113   /**
 114    *  @if maint
 115    *  Strip top-level cv-qualifiers from the function object and let
 116    *  _Weak_result_type_impl perform the real work.
 117    *  @endif
 118   */
 119   template<typename _Functor>
 120     struct _Weak_result_type
 121     : _Weak_result_type_impl<typename remove_cv<_Functor>::type>
 122     {
 123     };
 124
 125   template<typename _Signature>
 126     class result_of;
 127
 128   /**
 129    *  @if maint
 130    *  Actual implementation of result_of. When _Has_result_type is
 131    *  true, gets its result from _Weak_result_type. Otherwise, uses
 132    *  the function object's member template result to extract the
 133    *  result type.
 134    *  @endif
 135   */
 136   template<bool _Has_result_type, typename _Signature>
 137     struct _Result_of_impl;
 138
 139   // Handle member data pointers using _Mem_fn's logic
 140   template<typename _Res, typename _Class, typename _T1>
 141     struct _Result_of_impl<false, _Res _Class::*(_T1)>
 142     {
 143       typedef typename _Mem_fn<_Res _Class::*>
 144                 ::template _Result_type<_T1>::type type;
 145     };
 146
 147   /**
 148    *  @if maint
 149    *  Determines if the type _Tp derives from unary_function.
 150    *  @endif
 151   */
 152   template<typename _Tp>
 153     struct _Derives_from_unary_function : __sfinae_types
 154     {
 155     private:
 156       template<typename _T1, typename _Res>
 157         static __one __test(const volatile unary_function<_T1, _Res>*);
 158
 159       // It's tempting to change "..." to const volatile void*, but
 160       // that fails when _Tp is a function type.
 161       static __two __test(...);
 162
 163     public:
 164       static const bool value = sizeof(__test((_Tp*)0)) == 1;
 165     };
 166
 167   /**
 168    *  @if maint
 169    *  Determines if the type _Tp derives from binary_function.
 170    *  @endif
 171   */
 172   template<typename _Tp>
 173     struct _Derives_from_binary_function : __sfinae_types
 174     {
 175     private:
 176       template<typename _T1, typename _T2, typename _Res>
 177         static __one __test(const volatile binary_function<_T1, _T2, _Res>*);
 178
 179       // It's tempting to change "..." to const volatile void*, but
 180       // that fails when _Tp is a function type.
 181       static __two __test(...);
 182
 183     public:
 184       static const bool value = sizeof(__test((_Tp*)0)) == 1;
 185     };
 186
 187   /**
 188    *  @if maint
 189    *  Turns a function type into a function pointer type
 190    *  @endif
 191   */
 192   template<typename _Tp, bool _IsFunctionType = is_function<_Tp>::value>
 193     struct _Function_to_function_pointer
 194     {
 195       typedef _Tp type;
 196     };
 197
 198   template<typename _Tp>
 199     struct _Function_to_function_pointer<_Tp, true>
 200     {
 201       typedef _Tp* type;
 202     };
 203
 204   /**
 205    *  @if maint
 206    *  Knowing which of unary_function and binary_function _Tp derives
 207    *  from, derives from the same and ensures that reference_wrapper
 208    *  will have a weak result type. See cases below.
 209    *  @endif
 210    */
 211   template<bool _Unary, bool _Binary, typename _Tp>
 212     struct _Reference_wrapper_base_impl;
 213
 214   // Not a unary_function or binary_function, so try a weak result type
 215   template<typename _Tp>
 216     struct _Reference_wrapper_base_impl<false, false, _Tp>
 217       : _Weak_result_type<_Tp>
 218     { };
 219
 220   // unary_function but not binary_function
 221   template<typename _Tp>
 222     struct _Reference_wrapper_base_impl<true, false, _Tp>
 223       : unary_function<typename _Tp::argument_type,
 224                        typename _Tp::result_type>
 225     { };
 226
 227   // binary_function but not unary_function
 228   template<typename _Tp>
 229     struct _Reference_wrapper_base_impl<false, true, _Tp>
 230       : binary_function<typename _Tp::first_argument_type,
 231                         typename _Tp::second_argument_type,
 232                         typename _Tp::result_type>
 233     { };
 234
 235   // both unary_function and binary_function. import result_type to
 236   // avoid conflicts.
 237    template<typename _Tp>
 238     struct _Reference_wrapper_base_impl<true, true, _Tp>
 239       : unary_function<typename _Tp::argument_type,
 240                        typename _Tp::result_type>,
 241         binary_function<typename _Tp::first_argument_type,
 242                         typename _Tp::second_argument_type,
 243                         typename _Tp::result_type>
 244     {
 245       typedef typename _Tp::result_type result_type;
 246     };
 247
 248   /**
 249    *  @if maint
 250    *  Derives from unary_function or binary_function when it
 251    *  can. Specializations handle all of the easy cases. The primary
 252    *  template determines what to do with a class type, which may
 253    *  derive from both unary_function and binary_function.
 254    *  @endif
 255   */
 256   template<typename _Tp>
 257     struct _Reference_wrapper_base
 258       : _Reference_wrapper_base_impl<
 259           _Derives_from_unary_function<_Tp>::value,
 260           _Derives_from_binary_function<_Tp>::value,
 261           _Tp>
 262     { };
 263
 264   // - a function type (unary)
 265   template<typename _Res, typename _T1>
 266     struct _Reference_wrapper_base<_Res(_T1)>
 267       : unary_function<_T1, _Res>
 268     { };
 269
 270   // - a function type (binary)
 271   template<typename _Res, typename _T1, typename _T2>
 272     struct _Reference_wrapper_base<_Res(_T1, _T2)>
 273       : binary_function<_T1, _T2, _Res>
 274     { };
 275
 276   // - a function pointer type (unary)
 277   template<typename _Res, typename _T1>
 278     struct _Reference_wrapper_base<_Res(*)(_T1)>
 279       : unary_function<_T1, _Res>
 280     { };
 281
 282   // - a function pointer type (binary)
 283   template<typename _Res, typename _T1, typename _T2>
 284     struct _Reference_wrapper_base<_Res(*)(_T1, _T2)>
 285       : binary_function<_T1, _T2, _Res>
 286     { };
 287
 288   // - a pointer to member function type (unary, no qualifiers)
 289   template<typename _Res, typename _T1>
 290     struct _Reference_wrapper_base<_Res (_T1::*)()>
 291       : unary_function<_T1*, _Res>
 292     { };
 293
 294   // - a pointer to member function type (binary, no qualifiers)
 295   template<typename _Res, typename _T1, typename _T2>
 296     struct _Reference_wrapper_base<_Res (_T1::*)(_T2)>
 297       : binary_function<_T1*, _T2, _Res>
 298     { };
 299
 300   // - a pointer to member function type (unary, const)
 301   template<typename _Res, typename _T1>
 302     struct _Reference_wrapper_base<_Res (_T1::*)() const>
 303       : unary_function<const _T1*, _Res>
 304     { };
 305
 306   // - a pointer to member function type (binary, const)
 307   template<typename _Res, typename _T1, typename _T2>
 308     struct _Reference_wrapper_base<_Res (_T1::*)(_T2) const>
 309       : binary_function<const _T1*, _T2, _Res>
 310     { };
 311
 312   // - a pointer to member function type (unary, volatile)
 313   template<typename _Res, typename _T1>
 314     struct _Reference_wrapper_base<_Res (_T1::*)() volatile>
 315       : unary_function<volatile _T1*, _Res>
 316     { };
 317
 318   // - a pointer to member function type (binary, volatile)
 319   template<typename _Res, typename _T1, typename _T2>
 320     struct _Reference_wrapper_base<_Res (_T1::*)(_T2) volatile>
 321       : binary_function<volatile _T1*, _T2, _Res>
 322     { };
 323
 324   // - a pointer to member function type (unary, const volatile)
 325   template<typename _Res, typename _T1>
 326     struct _Reference_wrapper_base<_Res (_T1::*)() const volatile>
 327       : unary_function<const volatile _T1*, _Res>
 328     { };
 329
 330   // - a pointer to member function type (binary, const volatile)
 331   template<typename _Res, typename _T1, typename _T2>
 332     struct _Reference_wrapper_base<_Res (_T1::*)(_T2) const volatile>
 333       : binary_function<const volatile _T1*, _T2, _Res>
 334     { };
 335
 336   template<typename _Tp>
 337     class reference_wrapper
 338       : public _Reference_wrapper_base<typename remove_cv<_Tp>::type>
 339     {
 340       // If _Tp is a function type, we can't form result_of<_Tp(...)>,
 341       // so turn it into a function pointer type.
 342       typedef typename _Function_to_function_pointer<_Tp>::type
 343         _M_func_type;
 344
 345       _Tp* _M_data;
 346     public:
 347       typedef _Tp type;
 348       explicit reference_wrapper(_Tp& __indata): _M_data(&__indata)
 349       { }
 350
 351       reference_wrapper(const reference_wrapper<_Tp>& __inref):
 352       _M_data(__inref._M_data)
 353       { }
 354
 355       reference_wrapper&
 356       operator=(const reference_wrapper<_Tp>& __inref)
 357       {
 358         _M_data = __inref._M_data;
 359         return *this;
 360       }
 361
 362       operator _Tp&() const
 363       { return this->get(); }
 364
 365       _Tp&
 366       get() const
 367       { return *_M_data; }
 368
 369 #define _GLIBCXX_REPEAT_HEADER <tr1/ref_wrap_iterate.h>
 370 #include <tr1/repeat.h>
 371 #undef _GLIBCXX_REPEAT_HEADER
 372     };
 373
 374
 375   // Denotes a reference should be taken to a variable.
 376   template<typename _Tp>
 377     inline reference_wrapper<_Tp>
 378     ref(_Tp& __t)
 379     { return reference_wrapper<_Tp>(__t); }
 380
 381   // Denotes a const reference should be taken to a variable.
 382   template<typename _Tp>
 383     inline reference_wrapper<const _Tp>
 384     cref(const _Tp& __t)
 385     { return reference_wrapper<const _Tp>(__t); }
 386
 387   template<typename _Tp>
 388     inline reference_wrapper<_Tp>
 389     ref(reference_wrapper<_Tp> __t)
 390     { return ref(__t.get()); }
 391
 392   template<typename _Tp>
 393     inline reference_wrapper<const _Tp>
 394     cref(reference_wrapper<_Tp> __t)
 395     { return cref(__t.get()); }
 396
 397    template<typename _Tp, bool>
 398      struct _Mem_fn_const_or_non
 399      {
 400        typedef const _Tp& type;
 401      };
 402
 403     template<typename _Tp>
 404       struct _Mem_fn_const_or_non<_Tp, false>
 405       {
 406         typedef _Tp& type;
 407       };
 408
 409   template<typename _Res, typename _Class>
 410   class _Mem_fn<_Res _Class::*>
 411   {
 412     // This bit of genius is due to Peter Dimov, improved slightly by
 413     // Douglas Gregor.
 414     template<typename _Tp>
 415       _Res&
 416       _M_call(_Tp& __object, _Class *) const
 417       { return __object.*__pm; }
 418
 419     template<typename _Tp, typename _Up>
 420       _Res&
 421       _M_call(_Tp& __object, _Up * const *) const
 422       { return (*__object).*__pm; }
 423
 424     template<typename _Tp, typename _Up>
 425       const _Res&
 426       _M_call(_Tp& __object, const _Up * const *) const
 427       { return (*__object).*__pm; }
 428
 429     template<typename _Tp>
 430       const _Res&
 431       _M_call(_Tp& __object, const _Class *) const
 432       { return __object.*__pm; }
 433
 434     template<typename _Tp>
 435       const _Res&
 436       _M_call(_Tp& __ptr, const volatile void*) const
 437       { return (*__ptr).*__pm; }
 438
 439     template<typename _Tp> static _Tp& __get_ref();
 440
 441     template<typename _Tp>
 442       static __sfinae_types::__one __check_const(_Tp&, _Class*);
 443     template<typename _Tp, typename _Up>
 444       static __sfinae_types::__one __check_const(_Tp&, _Up * const *);
 445     template<typename _Tp, typename _Up>
 446       static __sfinae_types::__two __check_const(_Tp&, const _Up * const *);
 447     template<typename _Tp>
 448       static __sfinae_types::__two __check_const(_Tp&, const _Class*);
 449     template<typename _Tp>
 450       static __sfinae_types::__two __check_const(_Tp&, const volatile void*);
 451
 452   public:
 453     template<typename _Tp>
 454       struct _Result_type
 455         : _Mem_fn_const_or_non<
 456             _Res,
 457             (sizeof(__sfinae_types::__two)
 458              == sizeof(__check_const<_Tp>(__get_ref<_Tp>(), (_Tp*)0)))>
 459       { };
 460
 461     template<typename _Signature>
 462       struct result;
 463
 464     template<typename _CVMem, typename _Tp>
 465       struct result<_CVMem(_Tp)>
 466         : public _Result_type<_Tp> { };
 467
 468     template<typename _CVMem, typename _Tp>
 469       struct result<_CVMem(_Tp&)>
 470         : public _Result_type<_Tp> { };
 471
 472     explicit _Mem_fn(_Res _Class::*__pm) : __pm(__pm) { }
 473
 474     // Handle objects
 475     _Res&       operator()(_Class& __object)       const
 476     { return __object.*__pm; }
 477
 478     const _Res& operator()(const _Class& __object) const
 479     { return __object.*__pm; }
 480
 481     // Handle pointers
 482     _Res&       operator()(_Class* __object)       const
 483     { return __object->*__pm; }
 484
 485     const _Res&
 486     operator()(const _Class* __object) const
 487     { return __object->*__pm; }
 488
 489     // Handle smart pointers and derived
 490     template<typename _Tp>
 491       typename _Result_type<_Tp>::type
 492       operator()(_Tp& __unknown) const
 493       { return _M_call(__unknown, &__unknown); }
 494
 495   private:
 496     _Res _Class::*__pm;
 497   };
 498
 499   /**
 500    *  @brief Returns a function object that forwards to the member
 501    *  pointer @a pm.
 502    */
 503   template<typename _Tp, typename _Class>
 504     inline _Mem_fn<_Tp _Class::*>
 505     mem_fn(_Tp _Class::* __pm)
 506     {
 507       return _Mem_fn<_Tp _Class::*>(__pm);
 508     }
 509
 510   /**
 511    *  @brief Determines if the given type _Tp is a function object
 512    *  should be treated as a subexpression when evaluating calls to
 513    *  function objects returned by bind(). [TR1 3.6.1]
 514    */
 515   template<typename _Tp>
 516     struct is_bind_expression
 517     {
 518       static const bool value = false;
 519     };
 520
 521   /**
 522    *  @brief Determines if the given type _Tp is a placeholder in a
 523    *  bind() expression and, if so, which placeholder it is. [TR1 3.6.2]
 524    */
 525   template<typename _Tp>
 526     struct is_placeholder
 527     {
 528       static const int value = 0;
 529     };
 530
 531   /**
 532    *  @if maint
 533    *  The type of placeholder objects defined by libstdc++.
 534    *  @endif
 535    */
 536   template<int _Num> struct _Placeholder { };
 537
 538   /**
 539    *  @if maint
 540    *  Partial specialization of is_placeholder that provides the placeholder
 541    *  number for the placeholder objects defined by libstdc++.
 542    *  @endif
 543    */
 544   template<int _Num>
 545     struct is_placeholder<_Placeholder<_Num> >
 546     {
 547       static const int value = _Num;
 548     };
 549
 550   /**
 551    *  @if maint
 552    *  Maps an argument to bind() into an actual argument to the bound
 553    *  function object [TR1 3.6.3/5]. Only the first parameter should
 554    *  be specified: the rest are used to determine among the various
 555    *  implementations. Note that, although this class is a function
 556    *  object, isn't not entirely normal because it takes only two
 557    *  parameters regardless of the number of parameters passed to the
 558    *  bind expression. The first parameter is the bound argument and
 559    *  the second parameter is a tuple containing references to the
 560    *  rest of the arguments.
 561    *  @endif
 562    */
 563   template<typename _Arg,
 564            bool _IsBindExp = is_bind_expression<_Arg>::value,
 565            bool _IsPlaceholder = (is_placeholder<_Arg>::value > 0)>
 566     class _Mu;
 567
 568   /**
 569    *  @if maint
 570    *  If the argument is reference_wrapper<_Tp>, returns the
 571    *  underlying reference. [TR1 3.6.3/5 bullet 1]
 572    *  @endif
 573    */
 574   template<typename _Tp>
 575     class _Mu<reference_wrapper<_Tp>, false, false>
 576     {
 577     public:
 578       typedef _Tp& result_type;
 579
 580       /* Note: This won't actually work for const volatile
 581        * reference_wrappers, because reference_wrapper::get() is const
 582        * but not volatile-qualified. This might be a defect in the TR.
 583        */
 584       template<typename _CVRef, typename _Tuple>
 585       result_type
 586       operator()(_CVRef& __arg, const _Tuple&) const volatile
 587       { return __arg.get(); }
 588     };
 589
 590   /**
 591    *  @if maint
 592    *  If the argument is a bind expression, we invoke the underlying
 593    *  function object with the same cv-qualifiers as we are given and
 594    *  pass along all of our arguments (unwrapped). [TR1 3.6.3/5 bullet 2]
 595    *  @endif
 596    */
 597   template<typename _Arg>
 598     class _Mu<_Arg, true, false>
 599     {
 600     public:
 601       template<typename _Signature> class result;
 602
 603 #define _GLIBCXX_REPEAT_HEADER <tr1/mu_iterate.h>
 604 #  include <tr1/repeat.h>
 605 #undef _GLIBCXX_REPEAT_HEADER
 606     };
 607
 608   /**
 609    *  @if maint
 610    *  If the argument is a placeholder for the Nth argument, returns
 611    *  a reference to the Nth argument to the bind function object.
 612    *  [TR1 3.6.3/5 bullet 3]
 613    *  @endif
 614    */
 615   template<typename _Arg>
 616     class _Mu<_Arg, false, true>
 617     {
 618     public:
 619       template<typename _Signature> class result;
 620
 621       template<typename _CVMu, typename _CVArg, typename _Tuple>
 622       class result<_CVMu(_CVArg, _Tuple)>
 623       {
 624         // Add a reference, if it hasn't already been done for us.
 625         // This allows us to be a little bit sloppy in constructing
 626         // the tuple that we pass to result_of<...>.
 627         typedef typename tuple_element<(is_placeholder<_Arg>::value - 1),
 628                                        _Tuple>::type __base_type;
 629
 630       public:
 631         typedef typename add_reference<__base_type>::type type;
 632       };
 633
 634       template<typename _Tuple>
 635       typename result<_Mu(_Arg, _Tuple)>::type
 636       operator()(const volatile _Arg&, const _Tuple& __tuple) const volatile
 637       {
 638         return ::std::tr1::get<(is_placeholder<_Arg>::value - 1)>(__tuple);
 639       }
 640     };
 641
 642   /**
 643    *  @if maint
 644    *  If the argument is just a value, returns a reference to that
 645    *  value. The cv-qualifiers on the reference are the same as the
 646    *  cv-qualifiers on the _Mu object. [TR1 3.6.3/5 bullet 4]
 647    *  @endif
 648    */
 649   template<typename _Arg>
 650     class _Mu<_Arg, false, false>
 651     {
 652     public:
 653       template<typename _Signature> struct result;
 654
 655       template<typename _CVMu, typename _CVArg, typename _Tuple>
 656       struct result<_CVMu(_CVArg, _Tuple)>
 657       {
 658         typedef typename add_reference<_CVArg>::type type;
 659       };
 660
 661       // Pick up the cv-qualifiers of the argument
 662       template<typename _CVArg, typename _Tuple>
 663       _CVArg& operator()(_CVArg& __arg, const _Tuple&) const volatile
 664       { return __arg; }
 665     };
 666
 667   /**
 668    *  @if maint
 669    *  Maps member pointers into instances of _Mem_fn but leaves all
 670    *  other function objects untouched. Used by tr1::bind(). The
 671    *  primary template handles the non--member-pointer case.
 672    *  @endif
 673    */
 674   template<typename _Tp>
 675     struct _Maybe_wrap_member_pointer
 676     {
 677       typedef _Tp type;
 678       static const _Tp& __do_wrap(const _Tp& __x) { return __x; }
 679     };
 680
 681   /**
 682    *  @if maint
 683    *  Maps member pointers into instances of _Mem_fn but leaves all
 684    *  other function objects untouched. Used by tr1::bind(). This
 685    *  partial specialization handles the member pointer case.
 686    *  @endif
 687    */
 688   template<typename _Tp, typename _Class>
 689     struct _Maybe_wrap_member_pointer<_Tp _Class::*>
 690     {
 691       typedef _Mem_fn<_Tp _Class::*> type;
 692       static type __do_wrap(_Tp _Class::* __pm) { return type(__pm); }
 693     };
 694
 695   /**
 696    *  @if maint
 697    *  Type of the function object returned from bind().
 698    *  @endif
 699    */
 700    template<typename _Signature>
 701      struct _Bind;
 702
 703   /**
 704    *  @if maint
 705    *  Type of the function object returned from bind<R>().
 706    *  @endif
 707    */
 708    template<typename _Result, typename _Signature>
 709      struct _Bind_result;
 710
 711   /**
 712    *  @if maint
 713    *  Class template _Bind is always a bind expression.
 714    *  @endif
 715    */
 716    template<typename _Signature>
 717     struct is_bind_expression<_Bind<_Signature> >
 718     {
 719       static const bool value = true;
 720     };
 721
 722   /**
 723    *  @if maint
 724    *  Class template _Bind_result is always a bind expression.
 725    *  @endif
 726    */
 727    template<typename _Result, typename _Signature>
 728    struct is_bind_expression<_Bind_result<_Result, _Signature> >
 729     {
 730       static const bool value = true;
 731     };
 732
 733   /**
 734    *  @brief Exception class thrown when class template function's
 735    *  operator() is called with an empty target.
 736    *
 737    */
 738   class bad_function_call : public std::exception { };
 739
 740   /**
 741    *  @if maint
 742    *  The integral constant expression 0 can be converted into a
 743    *  pointer to this type. It is used by the function template to
 744    *  accept NULL pointers.
 745    *  @endif
 746    */
 747   struct _M_clear_type;
 748
 749   /**
 750    *  @if maint
 751    *  Trait identifying "location-invariant" types, meaning that the
 752    *  address of the object (or any of its members) will not escape.
 753    *  Also implies a trivial copy constructor and assignment operator.
 754    *   @endif
 755    */
 756   template<typename _Tp>
 757     struct __is_location_invariant
 758     : integral_constant<bool,
 759                         (is_pointer<_Tp>::value
 760                          || is_member_pointer<_Tp>::value)>
 761     {
 762     };
 763
 764   class _Undefined_class;
 765
 766   union _Nocopy_types
 767   {
 768     void*       _M_object;
 769     const void* _M_const_object;
 770     void (*_M_function_pointer)();
 771     void (_Undefined_class::*_M_member_pointer)();
 772   };
 773
 774   union _Any_data {
 775     void*       _M_access()       { return &_M_pod_data[0]; }
 776     const void* _M_access() const { return &_M_pod_data[0]; }
 777
 778     template<typename _Tp> _Tp& _M_access()
 779     { return *static_cast<_Tp*>(_M_access()); }
 780
 781     template<typename _Tp> const _Tp& _M_access() const
 782     { return *static_cast<const _Tp*>(_M_access()); }
 783
 784     _Nocopy_types _M_unused;
 785     char _M_pod_data[sizeof(_Nocopy_types)];
 786   };
 787
 788   enum _Manager_operation
 789   {
 790     __get_type_info,
 791     __get_functor_ptr,
 792     __clone_functor,
 793     __destroy_functor
 794   };
 795
 796   /* Simple type wrapper that helps avoid annoying const problems
 797      when casting between void pointers and pointers-to-pointers. */
 798   template<typename _Tp>
 799     struct _Simple_type_wrapper
 800     {
 801       _Simple_type_wrapper(_Tp __value) : __value(__value) { }
 802
 803       _Tp __value;
 804     };
 805
 806   template<typename _Tp>
 807     struct __is_location_invariant<_Simple_type_wrapper<_Tp> >
 808       : __is_location_invariant<_Tp>
 809     {
 810     };
 811
 812   // Converts a reference to a function object into a callable
 813   // function object.
 814   template<typename _Functor>
 815     inline _Functor& __callable_functor(_Functor& __f) { return __f; }
 816
 817   template<typename _Member, typename _Class>
 818     inline _Mem_fn<_Member _Class::*>
 819     __callable_functor(_Member _Class::* &__p)
 820     { return mem_fn(__p); }
 821
 822   template<typename _Member, typename _Class>
 823     inline _Mem_fn<_Member _Class::*>
 824     __callable_functor(_Member _Class::* const &__p)
 825     { return mem_fn(__p); }
 826
 827   template<typename _Signature, typename _Functor>
 828     class _Function_handler;
 829
 830   template<typename _Signature>
 831     class function;
 832
 833
 834   /**
 835    *  @if maint
 836    *  Base class of all polymorphic function object wrappers.
 837    *  @endif
 838    */
 839   class _Function_base
 840   {
 841   public:
 842     static const std::size_t _M_max_size = sizeof(_Nocopy_types);
 843     static const std::size_t _M_max_align = __alignof__(_Nocopy_types);
 844
 845     template<typename _Functor>
 846     class _Base_manager
 847     {
 848     protected:
 849       static const bool __stored_locally =
 850         (__is_location_invariant<_Functor>::value
 851          && sizeof(_Functor) <= _M_max_size
 852          && __alignof__(_Functor) <= _M_max_align
 853          && (_M_max_align % __alignof__(_Functor) == 0));
 854       typedef integral_constant<bool, __stored_locally> _Local_storage;
 855
 856       // Retrieve a pointer to the function object
 857       static _Functor* _M_get_pointer(const _Any_data& __source)
 858       {
 859         const _Functor* __ptr =
 860           __stored_locally? &__source._M_access<_Functor>()
 861           /* have stored a pointer */ : __source._M_access<_Functor*>();
 862         return const_cast<_Functor*>(__ptr);
 863       }
 864
 865       // Clone a location-invariant function object that fits within
 866       // an _Any_data structure.
 867       static void
 868       _M_clone(_Any_data& __dest, const _Any_data& __source, true_type)
 869       {
 870         new (__dest._M_access()) _Functor(__source._M_access<_Functor>());
 871       }
 872
 873       // Clone a function object that is not location-invariant or
 874       // that cannot fit into an _Any_data structure.
 875       static void
 876       _M_clone(_Any_data& __dest, const _Any_data& __source, false_type)
 877       {
 878         __dest._M_access<_Functor*>() =
 879           new _Functor(*__source._M_access<_Functor*>());
 880       }
 881
 882       // Destroying a location-invariant object may still require
 883       // destruction.
 884       static void
 885       _M_destroy(_Any_data& __victim, true_type)
 886       {
 887         __victim._M_access<_Functor>().~_Functor();
 888       }
 889
 890       // Destroying an object located on the heap.
 891       static void
 892       _M_destroy(_Any_data& __victim, false_type)
 893       {
 894         delete __victim._M_access<_Functor*>();
 895       }
 896
 897     public:
 898       static bool
 899       _M_manager(_Any_data& __dest, const _Any_data& __source,
 900                  _Manager_operation __op)
 901       {
 902         switch (__op) {
 903         case __get_type_info:
 904           __dest._M_access<const type_info*>() = &typeid(_Functor);
 905           break;
 906
 907         case __get_functor_ptr:
 908           __dest._M_access<_Functor*>() = _M_get_pointer(__source);
 909           break;
 910
 911         case __clone_functor:
 912           _M_clone(__dest, __source, _Local_storage());
 913           break;
 914
 915         case __destroy_functor:
 916           _M_destroy(__dest, _Local_storage());
 917           break;
 918         }
 919         return false;
 920       }
 921
 922       static void
 923       _M_init_functor(_Any_data& __functor, const _Functor& __f)
 924       {
 925         _M_init_functor(__functor, __f, _Local_storage());
 926       }
 927
 928       template<typename _Signature>
 929       static bool
 930       _M_not_empty_function(const function<_Signature>& __f)
 931       {
 932         return __f;
 933       }
 934
 935       template<typename _Tp>
 936       static bool
 937       _M_not_empty_function(const _Tp*& __fp)
 938       {
 939         return __fp;
 940       }
 941
 942       template<typename _Class, typename _Tp>
 943       static bool
 944       _M_not_empty_function(_Tp _Class::* const& __mp)
 945       {
 946         return __mp;
 947       }
 948
 949       template<typename _Tp>
 950       static bool
 951       _M_not_empty_function(const _Tp&)
 952       {
 953         return true;
 954       }
 955
 956     private:
 957       static void
 958       _M_init_functor(_Any_data& __functor, const _Functor& __f, true_type)
 959       {
 960         new (__functor._M_access()) _Functor(__f);
 961       }
 962
 963       static void
 964       _M_init_functor(_Any_data& __functor, const _Functor& __f, false_type)
 965       {
 966         __functor._M_access<_Functor*>() = new _Functor(__f);
 967       }
 968     };
 969
 970     template<typename _Functor>
 971     class _Ref_manager : public _Base_manager<_Functor*>
 972     {
 973       typedef _Function_base::_Base_manager<_Functor*> _Base;
 974
 975     public:
 976       static bool
 977       _M_manager(_Any_data& __dest, const _Any_data& __source,
 978                  _Manager_operation __op)
 979       {
 980         switch (__op) {
 981         case __get_type_info:
 982           __dest._M_access<const type_info*>() = &typeid(_Functor);
 983           break;
 984
 985         case __get_functor_ptr:
 986           __dest._M_access<_Functor*>() = *_Base::_M_get_pointer(__source);
 987           return is_const<_Functor>::value;
 988           break;
 989
 990         default:
 991           _Base::_M_manager(__dest, __source, __op);
 992         }
 993         return false;
 994       }
 995
 996       static void
 997       _M_init_functor(_Any_data& __functor, reference_wrapper<_Functor> __f)
 998       {
 999         // TBD: Use address_of function instead
1000         _Base::_M_init_functor(__functor, &__f.get());
1001       }
1002     };
1003
1004     _Function_base() : _M_manager(0) { }
1005
1006     ~_Function_base()
1007     {
1008       if (_M_manager)
1009         {
1010           _M_manager(_M_functor, _M_functor, __destroy_functor);
1011         }
1012     }
1013
1014
1015     bool _M_empty() const { return !_M_manager; }
1016
1017     typedef bool (*_Manager_type)(_Any_data&, const _Any_data&,
1018                                   _Manager_operation);
1019
1020     _Any_data     _M_functor;
1021     _Manager_type _M_manager;
1022   };
1023
1024   // [3.7.2.7] null pointer comparisons
1025
1026   /**
1027    *  @brief Compares a polymorphic function object wrapper against 0
1028    *  (the NULL pointer).
1029    *  @returns @c true if the wrapper has no target, @c false otherwise
1030    *
1031    *  This function will not throw an exception.
1032    */
1033   template<typename _Signature>
1034     inline bool
1035     operator==(const function<_Signature>& __f, _M_clear_type*)
1036     {
1037       return !__f;
1038     }
1039
1040   /**
1041    *  @overload
1042    */
1043   template<typename _Signature>
1044     inline bool
1045     operator==(_M_clear_type*, const function<_Signature>& __f)
1046     {
1047       return !__f;
1048     }
1049
1050   /**
1051    *  @brief Compares a polymorphic function object wrapper against 0
1052    *  (the NULL pointer).
1053    *  @returns @c false if the wrapper has no target, @c true otherwise
1054    *
1055    *  This function will not throw an exception.
1056    */
1057   template<typename _Signature>
1058     inline bool
1059     operator!=(const function<_Signature>& __f, _M_clear_type*)
1060     {
1061       return __f;
1062     }
1063
1064   /**
1065    *  @overload
1066    */
1067   template<typename _Signature>
1068     inline bool
1069     operator!=(_M_clear_type*, const function<_Signature>& __f)
1070     {
1071       return __f;
1072     }
1073
1074   // [3.7.2.8] specialized algorithms
1075
1076   /**
1077    *  @brief Swap the targets of two polymorphic function object wrappers.
1078    *
1079    *  This function will not throw an exception.
1080    */
1081   template<typename _Signature>
1082     inline void
1083     swap(function<_Signature>& __x, function<_Signature>& __y)
1084     {
1085       __x.swap(__y);
1086     }
1087
1088 #define _GLIBCXX_JOIN(X,Y) _GLIBCXX_JOIN2( X , Y )
1089 #define _GLIBCXX_JOIN2(X,Y) _GLIBCXX_JOIN3(X,Y)
1090 #define _GLIBCXX_JOIN3(X,Y) X##Y
1091 #define _GLIBCXX_REPEAT_HEADER <tr1/functional_iterate.h>
1092 #include <tr1/repeat.h>
1093 #undef _GLIBCXX_REPEAT_HEADER
1094 #undef _GLIBCXX_JOIN3
1095 #undef _GLIBCXX_JOIN2
1096 #undef _GLIBCXX_JOIN
1097
1098   // Definition of default hash function std::tr1::hash<>.  The types for
1099   // which std::tr1::hash<T> is defined is in clause 6.3.3. of the PDTR.
1100   template<typename T>
1101     struct hash;
1102
1103 #define tr1_hashtable_define_trivial_hash(T)            \
1104   template<>                                            \
1105     struct hash<T>                                      \
1106     : public std::unary_function<T, std::size_t>        \
1107     {                                                   \
1108       std::size_t                                       \
1109       operator()(T val) const                           \
1110       { return static_cast<std::size_t>(val); }         \
1111     }
1112
1113   tr1_hashtable_define_trivial_hash(bool);
1114   tr1_hashtable_define_trivial_hash(char);
1115   tr1_hashtable_define_trivial_hash(signed char);
1116   tr1_hashtable_define_trivial_hash(unsigned char);
1117   tr1_hashtable_define_trivial_hash(wchar_t);
1118   tr1_hashtable_define_trivial_hash(short);
1119   tr1_hashtable_define_trivial_hash(int);
1120   tr1_hashtable_define_trivial_hash(long);
1121   tr1_hashtable_define_trivial_hash(unsigned short);
1122   tr1_hashtable_define_trivial_hash(unsigned int);
1123   tr1_hashtable_define_trivial_hash(unsigned long);
1124
1125 #undef tr1_hashtable_define_trivial_hash
1126
1127   template<typename T>
1128     struct hash<T*>
1129     : public std::unary_function<T*, std::size_t>
1130     {
1131       std::size_t
1132       operator()(T* p) const
1133       { return reinterpret_cast<std::size_t>(p); }
1134     };
1135
1136   // Fowler / Noll / Vo (FNV) Hash (type FNV-1a)
1137   // (used by the next specializations of std::tr1::hash<>)
1138
1139   // Dummy generic implementation (for sizeof(size_t) != 4, 8).
1140   template<std::size_t = sizeof(std::size_t)>
1141     struct Fnv_hash
1142     {
1143       static std::size_t
1144       hash(const char* first, std::size_t length)
1145       {
1146         std::size_t result = 0;
1147         for (; length > 0; --length)
1148           result = (result * 131) + *first++;
1149         return result;
1150       }
1151     };
1152
1153   template<>
1154     struct Fnv_hash<4>
1155     {
1156       static std::size_t
1157       hash(const char* first, std::size_t length)
1158       {
1159         std::size_t result = static_cast<std::size_t>(2166136261UL);
1160         for (; length > 0; --length)
1161           {
1162             result ^= (std::size_t)*first++;
1163             result *= 16777619UL;
1164           }
1165         return result;
1166       }
1167     };
1168
1169   template<>
1170     struct Fnv_hash<8>
1171     {
1172       static std::size_t
1173       hash(const char* first, std::size_t length)
1174       {
1175         std::size_t result = static_cast<std::size_t>(14695981039346656037ULL);
1176         for (; length > 0; --length)
1177           {
1178             result ^= (std::size_t)*first++;
1179             result *= 1099511628211ULL;
1180           }
1181         return result;
1182       }
1183     };
1184
1185   // XXX String and floating point hashes probably shouldn't be inline
1186   // member functions, since are nontrivial.  Once we have the framework
1187   // for TR1 .cc files, these should go in one.
1188   template<>
1189     struct hash<std::string>
1190     : public std::unary_function<std::string, std::size_t>
1191     {
1192       std::size_t
1193       operator()(const std::string& s) const
1194       { return Fnv_hash<>::hash(s.data(), s.length()); }
1195     };
1196
1197 #ifdef _GLIBCXX_USE_WCHAR_T
1198   template<>
1199     struct hash<std::wstring>
1200     : public std::unary_function<std::wstring, std::size_t>
1201     {
1202       std::size_t
1203       operator()(const std::wstring& s) const
1204       {
1205         return Fnv_hash<>::hash(reinterpret_cast<const char*>(s.data()),
1206                                 s.length() * sizeof(wchar_t));
1207       }
1208     };
1209 #endif
1210
1211   template<>
1212     struct hash<float>
1213     : public std::unary_function<float, std::size_t>
1214     {
1215       std::size_t
1216       operator()(float fval) const
1217       {
1218         std::size_t result = 0;
1219
1220         // 0 and -0 both hash to zero.
1221         if (fval != 0.0f)
1222           result = Fnv_hash<>::hash(reinterpret_cast<const char*>(&fval),
1223                                     sizeof(fval));
1224         return result;
1225       }
1226     };
1227
1228   template<>
1229     struct hash<double>
1230     : public std::unary_function<double, std::size_t>
1231     {
1232       std::size_t
1233       operator()(double dval) const
1234       {
1235         std::size_t result = 0;
1236
1237         // 0 and -0 both hash to zero.
1238         if (dval != 0.0)
1239           result = Fnv_hash<>::hash(reinterpret_cast<const char*>(&dval),
1240                                     sizeof(dval));
1241         return result;
1242       }
1243     };
1244
1245   // For long double, careful with random padding bits (e.g., on x86,
1246   // 10 bytes -> 12 bytes) and resort to frexp.
1247   template<>
1248     struct hash<long double>
1249     : public std::unary_function<long double, std::size_t>
1250     {
1251       std::size_t
1252       operator()(long double ldval) const
1253       {
1254         std::size_t result = 0;
1255
1256         int exponent;
1257         ldval = std::frexp(ldval, &exponent);
1258         ldval = ldval < 0.0l ? -(ldval + 0.5l) : ldval;
1259
1260         const long double mult = std::numeric_limits<std::size_t>::max() + 1.0l;
1261         ldval *= mult;
1262
1263         // Try to use all the bits of the mantissa (really necessary only
1264         // on 32-bit targets, at least for 80-bit floating point formats).
1265         const std::size_t hibits = (std::size_t)ldval;
1266         ldval = (ldval - (long double)hibits) * mult;
1267
1268         const std::size_t coeff =
1269           (std::numeric_limits<std::size_t>::max()
1270            / std::numeric_limits<long double>::max_exponent);
1271
1272         result = hibits + (std::size_t)ldval + coeff * exponent;
1273
1274         return result;
1275       }
1276     };
1277
1278 _GLIBCXX_END_NAMESPACE
1279 }
1280
1281 #endif