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