libstdc++-v3/include/tr1/functional

   1 // TR1 functional header -*- C++ -*-
   2
   3 // Copyright (C) 2004, 2005, 2006 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     { static const bool value = false; };
 518
 519   template<typename _Tp>
 520     const bool is_bind_expression<_Tp>::value;
 521
 522   /**
 523    *  @brief Determines if the given type _Tp is a placeholder in a
 524    *  bind() expression and, if so, which placeholder it is. [TR1 3.6.2]
 525    */
 526   template<typename _Tp>
 527     struct is_placeholder
 528     { static const int value = 0; };
 529
 530   template<typename _Tp>
 531     const int is_placeholder<_Tp>::value;
 532
 533   /**
 534    *  @if maint
 535    *  The type of placeholder objects defined by libstdc++.
 536    *  @endif
 537    */
 538   template<int _Num> struct _Placeholder { };
 539
 540   /**
 541    *  @if maint
 542    *  Partial specialization of is_placeholder that provides the placeholder
 543    *  number for the placeholder objects defined by libstdc++.
 544    *  @endif
 545    */
 546   template<int _Num>
 547     struct is_placeholder<_Placeholder<_Num> >
 548     { static const int value = _Num; };
 549
 550   template<int _Num>
 551     const int is_placeholder<_Placeholder<_Num> >::value;
 552
 553   /**
 554    *  @if maint
 555    *  Maps an argument to bind() into an actual argument to the bound
 556    *  function object [TR1 3.6.3/5]. Only the first parameter should
 557    *  be specified: the rest are used to determine among the various
 558    *  implementations. Note that, although this class is a function
 559    *  object, isn't not entirely normal because it takes only two
 560    *  parameters regardless of the number of parameters passed to the
 561    *  bind expression. The first parameter is the bound argument and
 562    *  the second parameter is a tuple containing references to the
 563    *  rest of the arguments.
 564    *  @endif
 565    */
 566   template<typename _Arg,
 567            bool _IsBindExp = is_bind_expression<_Arg>::value,
 568            bool _IsPlaceholder = (is_placeholder<_Arg>::value > 0)>
 569     class _Mu;
 570
 571   /**
 572    *  @if maint
 573    *  If the argument is reference_wrapper<_Tp>, returns the
 574    *  underlying reference. [TR1 3.6.3/5 bullet 1]
 575    *  @endif
 576    */
 577   template<typename _Tp>
 578     class _Mu<reference_wrapper<_Tp>, false, false>
 579     {
 580     public:
 581       typedef _Tp& result_type;
 582
 583       /* Note: This won't actually work for const volatile
 584        * reference_wrappers, because reference_wrapper::get() is const
 585        * but not volatile-qualified. This might be a defect in the TR.
 586        */
 587       template<typename _CVRef, typename _Tuple>
 588       result_type
 589       operator()(_CVRef& __arg, const _Tuple&) const volatile
 590       { return __arg.get(); }
 591     };
 592
 593   /**
 594    *  @if maint
 595    *  If the argument is a bind expression, we invoke the underlying
 596    *  function object with the same cv-qualifiers as we are given and
 597    *  pass along all of our arguments (unwrapped). [TR1 3.6.3/5 bullet 2]
 598    *  @endif
 599    */
 600   template<typename _Arg>
 601     class _Mu<_Arg, true, false>
 602     {
 603     public:
 604       template<typename _Signature> class result;
 605
 606 #define _GLIBCXX_REPEAT_HEADER <tr1/mu_iterate.h>
 607 #  include <tr1/repeat.h>
 608 #undef _GLIBCXX_REPEAT_HEADER
 609     };
 610
 611   /**
 612    *  @if maint
 613    *  If the argument is a placeholder for the Nth argument, returns
 614    *  a reference to the Nth argument to the bind function object.
 615    *  [TR1 3.6.3/5 bullet 3]
 616    *  @endif
 617    */
 618   template<typename _Arg>
 619     class _Mu<_Arg, false, true>
 620     {
 621     public:
 622       template<typename _Signature> class result;
 623
 624       template<typename _CVMu, typename _CVArg, typename _Tuple>
 625       class result<_CVMu(_CVArg, _Tuple)>
 626       {
 627         // Add a reference, if it hasn't already been done for us.
 628         // This allows us to be a little bit sloppy in constructing
 629         // the tuple that we pass to result_of<...>.
 630         typedef typename tuple_element<(is_placeholder<_Arg>::value - 1),
 631                                        _Tuple>::type __base_type;
 632
 633       public:
 634         typedef typename add_reference<__base_type>::type type;
 635       };
 636
 637       template<typename _Tuple>
 638       typename result<_Mu(_Arg, _Tuple)>::type
 639       operator()(const volatile _Arg&, const _Tuple& __tuple) const volatile
 640       {
 641         return ::std::tr1::get<(is_placeholder<_Arg>::value - 1)>(__tuple);
 642       }
 643     };
 644
 645   /**
 646    *  @if maint
 647    *  If the argument is just a value, returns a reference to that
 648    *  value. The cv-qualifiers on the reference are the same as the
 649    *  cv-qualifiers on the _Mu object. [TR1 3.6.3/5 bullet 4]
 650    *  @endif
 651    */
 652   template<typename _Arg>
 653     class _Mu<_Arg, false, false>
 654     {
 655     public:
 656       template<typename _Signature> struct result;
 657
 658       template<typename _CVMu, typename _CVArg, typename _Tuple>
 659       struct result<_CVMu(_CVArg, _Tuple)>
 660       {
 661         typedef typename add_reference<_CVArg>::type type;
 662       };
 663
 664       // Pick up the cv-qualifiers of the argument
 665       template<typename _CVArg, typename _Tuple>
 666       _CVArg& operator()(_CVArg& __arg, const _Tuple&) const volatile
 667       { return __arg; }
 668     };
 669
 670   /**
 671    *  @if maint
 672    *  Maps member pointers into instances of _Mem_fn but leaves all
 673    *  other function objects untouched. Used by tr1::bind(). The
 674    *  primary template handles the non--member-pointer case.
 675    *  @endif
 676    */
 677   template<typename _Tp>
 678     struct _Maybe_wrap_member_pointer
 679     {
 680       typedef _Tp type;
 681       static const _Tp& __do_wrap(const _Tp& __x) { return __x; }
 682     };
 683
 684   /**
 685    *  @if maint
 686    *  Maps member pointers into instances of _Mem_fn but leaves all
 687    *  other function objects untouched. Used by tr1::bind(). This
 688    *  partial specialization handles the member pointer case.
 689    *  @endif
 690    */
 691   template<typename _Tp, typename _Class>
 692     struct _Maybe_wrap_member_pointer<_Tp _Class::*>
 693     {
 694       typedef _Mem_fn<_Tp _Class::*> type;
 695       static type __do_wrap(_Tp _Class::* __pm) { return type(__pm); }
 696     };
 697
 698   /**
 699    *  @if maint
 700    *  Type of the function object returned from bind().
 701    *  @endif
 702    */
 703    template<typename _Signature>
 704      struct _Bind;
 705
 706   /**
 707    *  @if maint
 708    *  Type of the function object returned from bind<R>().
 709    *  @endif
 710    */
 711    template<typename _Result, typename _Signature>
 712      struct _Bind_result;
 713
 714   /**
 715    *  @if maint
 716    *  Class template _Bind is always a bind expression.
 717    *  @endif
 718    */
 719    template<typename _Signature>
 720      struct is_bind_expression<_Bind<_Signature> >
 721      { static const bool value = true; };
 722
 723    template<typename _Signature>
 724      const bool is_bind_expression<_Bind<_Signature> >::value;
 725
 726   /**
 727    *  @if maint
 728    *  Class template _Bind_result is always a bind expression.
 729    *  @endif
 730    */
 731    template<typename _Result, typename _Signature>
 732      struct is_bind_expression<_Bind_result<_Result, _Signature> >
 733      { static const bool value = true; };
 734
 735    template<typename _Result, typename _Signature>
 736      const bool is_bind_expression<_Bind_result<_Result, _Signature> >::value;
 737
 738   /**
 739    *  @brief Exception class thrown when class template function's
 740    *  operator() is called with an empty target.
 741    *
 742    */
 743   class bad_function_call : public std::exception { };
 744
 745   /**
 746    *  @if maint
 747    *  The integral constant expression 0 can be converted into a
 748    *  pointer to this type. It is used by the function template to
 749    *  accept NULL pointers.
 750    *  @endif
 751    */
 752   struct _M_clear_type;
 753
 754   /**
 755    *  @if maint
 756    *  Trait identifying "location-invariant" types, meaning that the
 757    *  address of the object (or any of its members) will not escape.
 758    *  Also implies a trivial copy constructor and assignment operator.
 759    *   @endif
 760    */
 761   template<typename _Tp>
 762     struct __is_location_invariant
 763     : integral_constant<bool,
 764                         (is_pointer<_Tp>::value
 765                          || is_member_pointer<_Tp>::value)>
 766     {
 767     };
 768
 769   class _Undefined_class;
 770
 771   union _Nocopy_types
 772   {
 773     void*       _M_object;
 774     const void* _M_const_object;
 775     void (*_M_function_pointer)();
 776     void (_Undefined_class::*_M_member_pointer)();
 777   };
 778
 779   union _Any_data {
 780     void*       _M_access()       { return &_M_pod_data[0]; }
 781     const void* _M_access() const { return &_M_pod_data[0]; }
 782
 783     template<typename _Tp> _Tp& _M_access()
 784     { return *static_cast<_Tp*>(_M_access()); }
 785
 786     template<typename _Tp> const _Tp& _M_access() const
 787     { return *static_cast<const _Tp*>(_M_access()); }
 788
 789     _Nocopy_types _M_unused;
 790     char _M_pod_data[sizeof(_Nocopy_types)];
 791   };
 792
 793   enum _Manager_operation
 794   {
 795     __get_type_info,
 796     __get_functor_ptr,
 797     __clone_functor,
 798     __destroy_functor
 799   };
 800
 801   /* Simple type wrapper that helps avoid annoying const problems
 802      when casting between void pointers and pointers-to-pointers. */
 803   template<typename _Tp>
 804     struct _Simple_type_wrapper
 805     {
 806       _Simple_type_wrapper(_Tp __value) : __value(__value) { }
 807
 808       _Tp __value;
 809     };
 810
 811   template<typename _Tp>
 812     struct __is_location_invariant<_Simple_type_wrapper<_Tp> >
 813       : __is_location_invariant<_Tp>
 814     {
 815     };
 816
 817   // Converts a reference to a function object into a callable
 818   // function object.
 819   template<typename _Functor>
 820     inline _Functor& __callable_functor(_Functor& __f) { return __f; }
 821
 822   template<typename _Member, typename _Class>
 823     inline _Mem_fn<_Member _Class::*>
 824     __callable_functor(_Member _Class::* &__p)
 825     { return mem_fn(__p); }
 826
 827   template<typename _Member, typename _Class>
 828     inline _Mem_fn<_Member _Class::*>
 829     __callable_functor(_Member _Class::* const &__p)
 830     { return mem_fn(__p); }
 831
 832   template<typename _Signature, typename _Functor>
 833     class _Function_handler;
 834
 835   template<typename _Signature>
 836     class function;
 837
 838
 839   /**
 840    *  @if maint
 841    *  Base class of all polymorphic function object wrappers.
 842    *  @endif
 843    */
 844   class _Function_base
 845   {
 846   public:
 847     static const std::size_t _M_max_size = sizeof(_Nocopy_types);
 848     static const std::size_t _M_max_align = __alignof__(_Nocopy_types);
 849
 850     template<typename _Functor>
 851     class _Base_manager
 852     {
 853     protected:
 854       static const bool __stored_locally =
 855         (__is_location_invariant<_Functor>::value
 856          && sizeof(_Functor) <= _M_max_size
 857          && __alignof__(_Functor) <= _M_max_align
 858          && (_M_max_align % __alignof__(_Functor) == 0));
 859       typedef integral_constant<bool, __stored_locally> _Local_storage;
 860
 861       // Retrieve a pointer to the function object
 862       static _Functor* _M_get_pointer(const _Any_data& __source)
 863       {
 864         const _Functor* __ptr =
 865           __stored_locally? &__source._M_access<_Functor>()
 866           /* have stored a pointer */ : __source._M_access<_Functor*>();
 867         return const_cast<_Functor*>(__ptr);
 868       }
 869
 870       // Clone a location-invariant function object that fits within
 871       // an _Any_data structure.
 872       static void
 873       _M_clone(_Any_data& __dest, const _Any_data& __source, true_type)
 874       {
 875         new (__dest._M_access()) _Functor(__source._M_access<_Functor>());
 876       }
 877
 878       // Clone a function object that is not location-invariant or
 879       // that cannot fit into an _Any_data structure.
 880       static void
 881       _M_clone(_Any_data& __dest, const _Any_data& __source, false_type)
 882       {
 883         __dest._M_access<_Functor*>() =
 884           new _Functor(*__source._M_access<_Functor*>());
 885       }
 886
 887       // Destroying a location-invariant object may still require
 888       // destruction.
 889       static void
 890       _M_destroy(_Any_data& __victim, true_type)
 891       {
 892         __victim._M_access<_Functor>().~_Functor();
 893       }
 894
 895       // Destroying an object located on the heap.
 896       static void
 897       _M_destroy(_Any_data& __victim, false_type)
 898       {
 899         delete __victim._M_access<_Functor*>();
 900       }
 901
 902     public:
 903       static bool
 904       _M_manager(_Any_data& __dest, const _Any_data& __source,
 905                  _Manager_operation __op)
 906       {
 907         switch (__op) {
 908         case __get_type_info:
 909           __dest._M_access<const type_info*>() = &typeid(_Functor);
 910           break;
 911
 912         case __get_functor_ptr:
 913           __dest._M_access<_Functor*>() = _M_get_pointer(__source);
 914           break;
 915
 916         case __clone_functor:
 917           _M_clone(__dest, __source, _Local_storage());
 918           break;
 919
 920         case __destroy_functor:
 921           _M_destroy(__dest, _Local_storage());
 922           break;
 923         }
 924         return false;
 925       }
 926
 927       static void
 928       _M_init_functor(_Any_data& __functor, const _Functor& __f)
 929       {
 930         _M_init_functor(__functor, __f, _Local_storage());
 931       }
 932
 933       template<typename _Signature>
 934       static bool
 935       _M_not_empty_function(const function<_Signature>& __f)
 936       {
 937         return __f;
 938       }
 939
 940       template<typename _Tp>
 941       static bool
 942       _M_not_empty_function(const _Tp*& __fp)
 943       {
 944         return __fp;
 945       }
 946
 947       template<typename _Class, typename _Tp>
 948       static bool
 949       _M_not_empty_function(_Tp _Class::* const& __mp)
 950       {
 951         return __mp;
 952       }
 953
 954       template<typename _Tp>
 955       static bool
 956       _M_not_empty_function(const _Tp&)
 957       {
 958         return true;
 959       }
 960
 961     private:
 962       static void
 963       _M_init_functor(_Any_data& __functor, const _Functor& __f, true_type)
 964       {
 965         new (__functor._M_access()) _Functor(__f);
 966       }
 967
 968       static void
 969       _M_init_functor(_Any_data& __functor, const _Functor& __f, false_type)
 970       {
 971         __functor._M_access<_Functor*>() = new _Functor(__f);
 972       }
 973     };
 974
 975     template<typename _Functor>
 976     class _Ref_manager : public _Base_manager<_Functor*>
 977     {
 978       typedef _Function_base::_Base_manager<_Functor*> _Base;
 979
 980     public:
 981       static bool
 982       _M_manager(_Any_data& __dest, const _Any_data& __source,
 983                  _Manager_operation __op)
 984       {
 985         switch (__op) {
 986         case __get_type_info:
 987           __dest._M_access<const type_info*>() = &typeid(_Functor);
 988           break;
 989
 990         case __get_functor_ptr:
 991           __dest._M_access<_Functor*>() = *_Base::_M_get_pointer(__source);
 992           return is_const<_Functor>::value;
 993           break;
 994
 995         default:
 996           _Base::_M_manager(__dest, __source, __op);
 997         }
 998         return false;
 999       }
1000
1001       static void
1002       _M_init_functor(_Any_data& __functor, reference_wrapper<_Functor> __f)
1003       {
1004         // TBD: Use address_of function instead
1005         _Base::_M_init_functor(__functor, &__f.get());
1006       }
1007     };
1008
1009     _Function_base() : _M_manager(0) { }
1010
1011     ~_Function_base()
1012     {
1013       if (_M_manager)
1014         {
1015           _M_manager(_M_functor, _M_functor, __destroy_functor);
1016         }
1017     }
1018
1019
1020     bool _M_empty() const { return !_M_manager; }
1021
1022     typedef bool (*_Manager_type)(_Any_data&, const _Any_data&,
1023                                   _Manager_operation);
1024
1025     _Any_data     _M_functor;
1026     _Manager_type _M_manager;
1027   };
1028
1029   // [3.7.2.7] null pointer comparisons
1030
1031   /**
1032    *  @brief Compares a polymorphic function object wrapper against 0
1033    *  (the NULL pointer).
1034    *  @returns @c true if the wrapper has no target, @c false otherwise
1035    *
1036    *  This function will not throw an exception.
1037    */
1038   template<typename _Signature>
1039     inline bool
1040     operator==(const function<_Signature>& __f, _M_clear_type*)
1041     {
1042       return !__f;
1043     }
1044
1045   /**
1046    *  @overload
1047    */
1048   template<typename _Signature>
1049     inline bool
1050     operator==(_M_clear_type*, const function<_Signature>& __f)
1051     {
1052       return !__f;
1053     }
1054
1055   /**
1056    *  @brief Compares a polymorphic function object wrapper against 0
1057    *  (the NULL pointer).
1058    *  @returns @c false if the wrapper has no target, @c true otherwise
1059    *
1060    *  This function will not throw an exception.
1061    */
1062   template<typename _Signature>
1063     inline bool
1064     operator!=(const function<_Signature>& __f, _M_clear_type*)
1065     {
1066       return __f;
1067     }
1068
1069   /**
1070    *  @overload
1071    */
1072   template<typename _Signature>
1073     inline bool
1074     operator!=(_M_clear_type*, const function<_Signature>& __f)
1075     {
1076       return __f;
1077     }
1078
1079   // [3.7.2.8] specialized algorithms
1080
1081   /**
1082    *  @brief Swap the targets of two polymorphic function object wrappers.
1083    *
1084    *  This function will not throw an exception.
1085    */
1086   template<typename _Signature>
1087     inline void
1088     swap(function<_Signature>& __x, function<_Signature>& __y)
1089     {
1090       __x.swap(__y);
1091     }
1092
1093 #define _GLIBCXX_JOIN(X,Y) _GLIBCXX_JOIN2( X , Y )
1094 #define _GLIBCXX_JOIN2(X,Y) _GLIBCXX_JOIN3(X,Y)
1095 #define _GLIBCXX_JOIN3(X,Y) X##Y
1096 #define _GLIBCXX_REPEAT_HEADER <tr1/functional_iterate.h>
1097 #include <tr1/repeat.h>
1098 #undef _GLIBCXX_REPEAT_HEADER
1099 #undef _GLIBCXX_JOIN3
1100 #undef _GLIBCXX_JOIN2
1101 #undef _GLIBCXX_JOIN
1102
1103   // Definition of default hash function std::tr1::hash<>.  The types for
1104   // which std::tr1::hash<T> is defined is in clause 6.3.3. of the PDTR.
1105   template<typename T>
1106     struct hash;
1107
1108 #define _TR1_hashtable_define_trivial_hash(_Tp)         \
1109   template<>                                            \
1110     struct hash<_Tp>                                    \
1111     : public std::unary_function<_Tp, std::size_t>      \
1112     {                                                   \
1113       std::size_t                                       \
1114       operator()(_Tp __val) const                       \
1115       { return static_cast<std::size_t>(__val); }       \
1116     }
1117
1118   _TR1_hashtable_define_trivial_hash(bool);
1119   _TR1_hashtable_define_trivial_hash(char);
1120   _TR1_hashtable_define_trivial_hash(signed char);
1121   _TR1_hashtable_define_trivial_hash(unsigned char);
1122   _TR1_hashtable_define_trivial_hash(wchar_t);
1123   _TR1_hashtable_define_trivial_hash(short);
1124   _TR1_hashtable_define_trivial_hash(int);
1125   _TR1_hashtable_define_trivial_hash(long);
1126   _TR1_hashtable_define_trivial_hash(unsigned short);
1127   _TR1_hashtable_define_trivial_hash(unsigned int);
1128   _TR1_hashtable_define_trivial_hash(unsigned long);
1129
1130 #undef _TR1_hashtable_define_trivial_hash
1131
1132   template<typename _Tp>
1133     struct hash<_Tp*>
1134     : public std::unary_function<_Tp*, std::size_t>
1135     {
1136       std::size_t
1137       operator()(_Tp* __p) const
1138       { return reinterpret_cast<std::size_t>(__p); }
1139     };
1140
1141   // Fowler / Noll / Vo (FNV) Hash (type FNV-1a)
1142   // (used by the next specializations of std::tr1::hash<>)
1143
1144   // Dummy generic implementation (for sizeof(size_t) != 4, 8).
1145   template<std::size_t = sizeof(std::size_t)>
1146     struct _Fnv_hash
1147     {
1148       static std::size_t
1149       hash(const char* __first, std::size_t __length)
1150       {
1151         std::size_t __result = 0;
1152         for (; __length > 0; --__length)
1153           __result = (__result * 131) + *__first++;
1154         return __result;
1155       }
1156     };
1157
1158   template<>
1159     struct _Fnv_hash<4>
1160     {
1161       static std::size_t
1162       hash(const char* __first, std::size_t __length)
1163       {
1164         std::size_t __result = static_cast<std::size_t>(2166136261UL);
1165         for (; __length > 0; --__length)
1166           {
1167             __result ^= (std::size_t)*__first++;
1168             __result *= 16777619UL;
1169           }
1170         return __result;
1171       }
1172     };
1173
1174   template<>
1175     struct _Fnv_hash<8>
1176     {
1177       static std::size_t
1178       hash(const char* __first, std::size_t __length)
1179       {
1180         std::size_t __result =
1181           static_cast<std::size_t>(14695981039346656037ULL);
1182         for (; __length > 0; --__length)
1183           {
1184             __result ^= (std::size_t)*__first++;
1185             __result *= 1099511628211ULL;
1186           }
1187         return __result;
1188       }
1189     };
1190
1191   // XXX String and floating point hashes probably shouldn't be inline
1192   // member functions, since are nontrivial.  Once we have the framework
1193   // for TR1 .cc files, these should go in one.
1194   template<>
1195     struct hash<std::string>
1196     : public std::unary_function<std::string, std::size_t>
1197     {
1198       std::size_t
1199       operator()(const std::string& __s) const
1200       { return _Fnv_hash<>::hash(__s.data(), __s.length()); }
1201     };
1202
1203 #ifdef _GLIBCXX_USE_WCHAR_T
1204   template<>
1205     struct hash<std::wstring>
1206     : public std::unary_function<std::wstring, std::size_t>
1207     {
1208       std::size_t
1209       operator()(const std::wstring& __s) const
1210       {
1211         return _Fnv_hash<>::hash(reinterpret_cast<const char*>(__s.data()),
1212                                  __s.length() * sizeof(wchar_t));
1213       }
1214     };
1215 #endif
1216
1217   template<>
1218     struct hash<float>
1219     : public std::unary_function<float, std::size_t>
1220     {
1221       std::size_t
1222       operator()(float __fval) const
1223       {
1224         std::size_t __result = 0;
1225
1226         // 0 and -0 both hash to zero.
1227         if (__fval != 0.0f)
1228           __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__fval),
1229                                        sizeof(__fval));
1230         return __result;
1231       }
1232     };
1233
1234   template<>
1235     struct hash<double>
1236     : public std::unary_function<double, std::size_t>
1237     {
1238       std::size_t
1239       operator()(double __dval) const
1240       {
1241         std::size_t __result = 0;
1242
1243         // 0 and -0 both hash to zero.
1244         if (__dval != 0.0)
1245           __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__dval),
1246                                        sizeof(__dval));
1247         return __result;
1248       }
1249     };
1250
1251   // For long double, careful with random padding bits (e.g., on x86,
1252   // 10 bytes -> 12 bytes) and resort to frexp.
1253   template<>
1254     struct hash<long double>
1255     : public std::unary_function<long double, std::size_t>
1256     {
1257       std::size_t
1258       operator()(long double __ldval) const
1259       {
1260         std::size_t __result = 0;
1261
1262         int __exponent;
1263         __ldval = std::frexp(__ldval, &__exponent);
1264         __ldval = __ldval < 0.0l ? -(__ldval + 0.5l) : __ldval;
1265
1266         const long double __mult =
1267           std::numeric_limits<std::size_t>::max() + 1.0l;
1268         __ldval *= __mult;
1269
1270         // Try to use all the bits of the mantissa (really necessary only
1271         // on 32-bit targets, at least for 80-bit floating point formats).
1272         const std::size_t __hibits = (std::size_t)__ldval;
1273         __ldval = (__ldval - (long double)__hibits) * __mult;
1274
1275         const std::size_t __coeff =
1276           (std::numeric_limits<std::size_t>::max()
1277            / std::numeric_limits<long double>::max_exponent);
1278
1279         __result = __hibits + (std::size_t)__ldval + __coeff * __exponent;
1280
1281         return __result;
1282       }
1283     };
1284
1285 _GLIBCXX_END_NAMESPACE
1286 }
1287
1288 #endif