OSDN Git Service

980061d69027c003412ff6e86e4de69e2db70d42
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / tr1_impl / functional
1 // TR1 functional header -*- C++ -*-
2
3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /** @file tr1_impl/functional
26  *  This is an internal header file, included by other library headers.
27  *  You should not attempt to use it directly.
28  */
29
30 namespace std
31 {
32 _GLIBCXX_BEGIN_NAMESPACE_TR1
33
34   template<typename _MemberPointer>
35     class _Mem_fn;
36
37   /**
38    *  Actual implementation of _Has_result_type, which uses SFINAE to
39    *  determine if the type _Tp has a publicly-accessible member type
40    *  result_type.
41   */
42   template<typename _Tp>
43     class _Has_result_type_helper : __sfinae_types
44     {
45       template<typename _Up>
46         struct _Wrap_type
47         { };
48
49       template<typename _Up>
50         static __one __test(_Wrap_type<typename _Up::result_type>*);
51
52       template<typename _Up>
53         static __two __test(...);
54
55     public:
56       static const bool value = sizeof(__test<_Tp>(0)) == 1;
57     };
58
59   template<typename _Tp>
60     struct _Has_result_type
61     : integral_constant<bool,
62               _Has_result_type_helper<typename remove_cv<_Tp>::type>::value>
63     { };
64
65   /**
66    *  
67   */
68   /// If we have found a result_type, extract it.
69   template<bool _Has_result_type, typename _Functor>
70     struct _Maybe_get_result_type
71     { };
72
73   template<typename _Functor>
74     struct _Maybe_get_result_type<true, _Functor>
75     {
76       typedef typename _Functor::result_type result_type;
77     };
78
79   /**
80    *  Base class for any function object that has a weak result type, as
81    *  defined in 3.3/3 of TR1.
82   */
83   template<typename _Functor>
84     struct _Weak_result_type_impl
85     : _Maybe_get_result_type<_Has_result_type<_Functor>::value, _Functor>
86     {
87     };
88
89   /// Retrieve the result type for a function type.
90   template<typename _Res, typename... _ArgTypes> 
91     struct _Weak_result_type_impl<_Res(_ArgTypes...)>
92     {
93       typedef _Res result_type;
94     };
95
96   /// Retrieve the result type for a function reference.
97   template<typename _Res, typename... _ArgTypes> 
98     struct _Weak_result_type_impl<_Res(&)(_ArgTypes...)>
99     {
100       typedef _Res result_type;
101     };
102
103   /// Retrieve the result type for a function pointer.
104   template<typename _Res, typename... _ArgTypes> 
105     struct _Weak_result_type_impl<_Res(*)(_ArgTypes...)>
106     {
107       typedef _Res result_type;
108     };
109
110   /// Retrieve result type for a member function pointer. 
111   template<typename _Res, typename _Class, typename... _ArgTypes> 
112     struct _Weak_result_type_impl<_Res (_Class::*)(_ArgTypes...)>
113     {
114       typedef _Res result_type;
115     };
116
117   /// Retrieve result type for a const member function pointer. 
118   template<typename _Res, typename _Class, typename... _ArgTypes> 
119     struct _Weak_result_type_impl<_Res (_Class::*)(_ArgTypes...) const>
120     {
121       typedef _Res result_type;
122     };
123
124   /// Retrieve result type for a volatile member function pointer. 
125   template<typename _Res, typename _Class, typename... _ArgTypes> 
126     struct _Weak_result_type_impl<_Res (_Class::*)(_ArgTypes...) volatile>
127     {
128       typedef _Res result_type;
129     };
130
131   /// Retrieve result type for a const volatile member function pointer. 
132   template<typename _Res, typename _Class, typename... _ArgTypes> 
133     struct _Weak_result_type_impl<_Res (_Class::*)(_ArgTypes...)const volatile>
134     {
135       typedef _Res result_type;
136     };
137
138   /**
139    *  Strip top-level cv-qualifiers from the function object and let
140    *  _Weak_result_type_impl perform the real work.
141   */
142   template<typename _Functor>
143     struct _Weak_result_type
144     : _Weak_result_type_impl<typename remove_cv<_Functor>::type>
145     {
146     };
147
148   template<typename _Signature>
149     class result_of;
150
151   /**
152    *  Actual implementation of result_of. When _Has_result_type is
153    *  true, gets its result from _Weak_result_type. Otherwise, uses
154    *  the function object's member template result to extract the
155    *  result type.
156   */
157   template<bool _Has_result_type, typename _Signature>
158     struct _Result_of_impl;
159
160   // Handle member data pointers using _Mem_fn's logic
161   template<typename _Res, typename _Class, typename _T1>
162     struct _Result_of_impl<false, _Res _Class::*(_T1)>
163     {
164       typedef typename _Mem_fn<_Res _Class::*>
165                 ::template _Result_type<_T1>::type type;
166     };
167
168   /**
169    * Determine whether we can determine a result type from @c Functor 
170    * alone.
171    */ 
172   template<typename _Functor, typename... _ArgTypes>
173     class result_of<_Functor(_ArgTypes...)>
174     : public _Result_of_impl<
175                _Has_result_type<_Weak_result_type<_Functor> >::value,
176                _Functor(_ArgTypes...)>
177     {
178     };
179
180   /// We already know the result type for @c Functor; use it.
181   template<typename _Functor, typename... _ArgTypes>
182     struct _Result_of_impl<true, _Functor(_ArgTypes...)>
183     {
184       typedef typename _Weak_result_type<_Functor>::result_type type;
185     };
186
187   /**
188    * We need to compute the result type for this invocation the hard 
189    * way.
190    */
191   template<typename _Functor, typename... _ArgTypes>
192     struct _Result_of_impl<false, _Functor(_ArgTypes...)>
193     {
194       typedef typename _Functor
195                 ::template result<_Functor(_ArgTypes...)>::type type;
196     };
197
198   /**
199    * It is unsafe to access ::result when there are zero arguments, so we 
200    * return @c void instead.
201    */
202   template<typename _Functor>
203     struct _Result_of_impl<false, _Functor()>
204     {
205       typedef void type;
206     };
207
208   /// Determines if the type _Tp derives from unary_function.
209   template<typename _Tp>
210     struct _Derives_from_unary_function : __sfinae_types
211     {
212     private:
213       template<typename _T1, typename _Res>
214         static __one __test(const volatile unary_function<_T1, _Res>*);
215
216       // It's tempting to change "..." to const volatile void*, but
217       // that fails when _Tp is a function type.
218       static __two __test(...);
219
220     public:
221       static const bool value = sizeof(__test((_Tp*)0)) == 1;
222     };
223
224   /// Determines if the type _Tp derives from binary_function.
225   template<typename _Tp>
226     struct _Derives_from_binary_function : __sfinae_types
227     {
228     private:
229       template<typename _T1, typename _T2, typename _Res>
230         static __one __test(const volatile binary_function<_T1, _T2, _Res>*);
231
232       // It's tempting to change "..." to const volatile void*, but
233       // that fails when _Tp is a function type.
234       static __two __test(...);
235
236     public:
237       static const bool value = sizeof(__test((_Tp*)0)) == 1;
238     };
239
240   /// Turns a function type into a function pointer type
241   template<typename _Tp, bool _IsFunctionType = is_function<_Tp>::value>
242     struct _Function_to_function_pointer
243     {
244       typedef _Tp type;
245     };
246
247   template<typename _Tp>
248     struct _Function_to_function_pointer<_Tp, true>
249     {
250       typedef _Tp* type;
251     };
252
253   /**
254    * Invoke a function object, which may be either a member pointer or a
255    * function object. The first parameter will tell which.
256    */
257   template<typename _Functor, typename... _Args>
258     inline
259     typename __gnu_cxx::__enable_if<
260              (!is_member_pointer<_Functor>::value
261               && !is_function<_Functor>::value
262               && !is_function<typename remove_pointer<_Functor>::type>::value),
263              typename result_of<_Functor(_Args...)>::type
264            >::__type
265     __invoke(_Functor& __f, _Args&... __args)
266     {
267       return __f(__args...);
268     }
269
270   template<typename _Functor, typename... _Args>
271     inline
272     typename __gnu_cxx::__enable_if<
273              (is_member_pointer<_Functor>::value
274               && !is_function<_Functor>::value
275               && !is_function<typename remove_pointer<_Functor>::type>::value),
276              typename result_of<_Functor(_Args...)>::type
277            >::__type
278     __invoke(_Functor& __f, _Args&... __args)
279     {
280       return mem_fn(__f)(__args...);
281     }
282
283   // To pick up function references (that will become function pointers)
284   template<typename _Functor, typename... _Args>
285     inline
286     typename __gnu_cxx::__enable_if<
287              (is_pointer<_Functor>::value
288               && is_function<typename remove_pointer<_Functor>::type>::value),
289              typename result_of<_Functor(_Args...)>::type
290            >::__type
291     __invoke(_Functor __f, _Args&... __args)
292     {
293       return __f(__args...);
294     }
295
296   /**
297    *  Knowing which of unary_function and binary_function _Tp derives
298    *  from, derives from the same and ensures that reference_wrapper
299    *  will have a weak result type. See cases below.
300    */
301   template<bool _Unary, bool _Binary, typename _Tp>
302     struct _Reference_wrapper_base_impl;
303
304   // Not a unary_function or binary_function, so try a weak result type.
305   template<typename _Tp>
306     struct _Reference_wrapper_base_impl<false, false, _Tp>
307     : _Weak_result_type<_Tp>
308     { };
309
310   // unary_function but not binary_function
311   template<typename _Tp>
312     struct _Reference_wrapper_base_impl<true, false, _Tp>
313     : unary_function<typename _Tp::argument_type,
314                      typename _Tp::result_type>
315     { };
316
317   // binary_function but not unary_function
318   template<typename _Tp>
319     struct _Reference_wrapper_base_impl<false, true, _Tp>
320     : binary_function<typename _Tp::first_argument_type,
321                       typename _Tp::second_argument_type,
322                       typename _Tp::result_type>
323     { };
324
325   // Both unary_function and binary_function. Import result_type to
326   // avoid conflicts.
327    template<typename _Tp>
328     struct _Reference_wrapper_base_impl<true, true, _Tp>
329     : unary_function<typename _Tp::argument_type,
330                      typename _Tp::result_type>,
331       binary_function<typename _Tp::first_argument_type,
332                       typename _Tp::second_argument_type,
333                       typename _Tp::result_type>
334     {
335       typedef typename _Tp::result_type result_type;
336     };
337
338   /**
339    *  Derives from unary_function or binary_function when it
340    *  can. Specializations handle all of the easy cases. The primary
341    *  template determines what to do with a class type, which may
342    *  derive from both unary_function and binary_function.
343   */
344   template<typename _Tp>
345     struct _Reference_wrapper_base
346     : _Reference_wrapper_base_impl<
347       _Derives_from_unary_function<_Tp>::value,
348       _Derives_from_binary_function<_Tp>::value,
349       _Tp>
350     { };
351
352   // - a function type (unary)
353   template<typename _Res, typename _T1>
354     struct _Reference_wrapper_base<_Res(_T1)>
355     : unary_function<_T1, _Res>
356     { };
357
358   // - a function type (binary)
359   template<typename _Res, typename _T1, typename _T2>
360     struct _Reference_wrapper_base<_Res(_T1, _T2)>
361     : binary_function<_T1, _T2, _Res>
362     { };
363
364   // - a function pointer type (unary)
365   template<typename _Res, typename _T1>
366     struct _Reference_wrapper_base<_Res(*)(_T1)>
367     : unary_function<_T1, _Res>
368     { };
369
370   // - a function pointer type (binary)
371   template<typename _Res, typename _T1, typename _T2>
372     struct _Reference_wrapper_base<_Res(*)(_T1, _T2)>
373     : binary_function<_T1, _T2, _Res>
374     { };
375
376   // - a pointer to member function type (unary, no qualifiers)
377   template<typename _Res, typename _T1>
378     struct _Reference_wrapper_base<_Res (_T1::*)()>
379     : unary_function<_T1*, _Res>
380     { };
381
382   // - a pointer to member function type (binary, no qualifiers)
383   template<typename _Res, typename _T1, typename _T2>
384     struct _Reference_wrapper_base<_Res (_T1::*)(_T2)>
385     : binary_function<_T1*, _T2, _Res>
386     { };
387
388   // - a pointer to member function type (unary, const)
389   template<typename _Res, typename _T1>
390     struct _Reference_wrapper_base<_Res (_T1::*)() const>
391     : unary_function<const _T1*, _Res>
392     { };
393
394   // - a pointer to member function type (binary, const)
395   template<typename _Res, typename _T1, typename _T2>
396     struct _Reference_wrapper_base<_Res (_T1::*)(_T2) const>
397     : binary_function<const _T1*, _T2, _Res>
398     { };
399
400   // - a pointer to member function type (unary, volatile)
401   template<typename _Res, typename _T1>
402     struct _Reference_wrapper_base<_Res (_T1::*)() volatile>
403     : unary_function<volatile _T1*, _Res>
404     { };
405
406   // - a pointer to member function type (binary, volatile)
407   template<typename _Res, typename _T1, typename _T2>
408     struct _Reference_wrapper_base<_Res (_T1::*)(_T2) volatile>
409     : binary_function<volatile _T1*, _T2, _Res>
410     { };
411
412   // - a pointer to member function type (unary, const volatile)
413   template<typename _Res, typename _T1>
414     struct _Reference_wrapper_base<_Res (_T1::*)() const volatile>
415     : unary_function<const volatile _T1*, _Res>
416     { };
417
418   // - a pointer to member function type (binary, const volatile)
419   template<typename _Res, typename _T1, typename _T2>
420     struct _Reference_wrapper_base<_Res (_T1::*)(_T2) const volatile>
421     : binary_function<const volatile _T1*, _T2, _Res>
422     { };
423
424   /// reference_wrapper
425   template<typename _Tp>
426     class reference_wrapper
427     : public _Reference_wrapper_base<typename remove_cv<_Tp>::type>
428     {
429       // If _Tp is a function type, we can't form result_of<_Tp(...)>,
430       // so turn it into a function pointer type.
431       typedef typename _Function_to_function_pointer<_Tp>::type
432         _M_func_type;
433
434       _Tp* _M_data;
435     public:
436       typedef _Tp type;
437
438       explicit
439       reference_wrapper(_Tp& __indata): _M_data(&__indata)
440       { }
441
442       reference_wrapper(const reference_wrapper<_Tp>& __inref):
443       _M_data(__inref._M_data)
444       { }
445
446       reference_wrapper&
447       operator=(const reference_wrapper<_Tp>& __inref)
448       {
449         _M_data = __inref._M_data;
450         return *this;
451       }
452
453       operator _Tp&() const
454       { return this->get(); }
455
456       _Tp&
457       get() const
458       { return *_M_data; }
459
460       template<typename... _Args>
461         typename result_of<_M_func_type(_Args...)>::type
462         operator()(_Args&... __args) const
463         {
464           return __invoke(get(), __args...);
465         }
466     };
467
468
469   // Denotes a reference should be taken to a variable.
470   template<typename _Tp>
471     inline reference_wrapper<_Tp>
472     ref(_Tp& __t)
473     { return reference_wrapper<_Tp>(__t); }
474
475   // Denotes a const reference should be taken to a variable.
476   template<typename _Tp>
477     inline reference_wrapper<const _Tp>
478     cref(const _Tp& __t)
479     { return reference_wrapper<const _Tp>(__t); }
480
481   template<typename _Tp>
482     inline reference_wrapper<_Tp>
483     ref(reference_wrapper<_Tp> __t)
484     { return ref(__t.get()); }
485
486   template<typename _Tp>
487     inline reference_wrapper<const _Tp>
488     cref(reference_wrapper<_Tp> __t)
489     { return cref(__t.get()); }
490
491   template<typename _Tp, bool>
492     struct _Mem_fn_const_or_non
493     {
494       typedef const _Tp& type;
495     };
496
497   template<typename _Tp>
498     struct _Mem_fn_const_or_non<_Tp, false>
499     {
500       typedef _Tp& type;
501     };
502
503   /**
504    * Derives from @c unary_function or @c binary_function, or perhaps
505    * nothing, depending on the number of arguments provided. The
506    * primary template is the basis case, which derives nothing.
507    */
508   template<typename _Res, typename... _ArgTypes> 
509     struct _Maybe_unary_or_binary_function { };
510
511   /// Derives from @c unary_function, as appropriate. 
512   template<typename _Res, typename _T1> 
513     struct _Maybe_unary_or_binary_function<_Res, _T1>
514     : std::unary_function<_T1, _Res> { };
515
516   /// Derives from @c binary_function, as appropriate. 
517   template<typename _Res, typename _T1, typename _T2> 
518     struct _Maybe_unary_or_binary_function<_Res, _T1, _T2>
519     : std::binary_function<_T1, _T2, _Res> { };
520
521   /// Implementation of @c mem_fn for member function pointers.
522   template<typename _Res, typename _Class, typename... _ArgTypes>
523     class _Mem_fn<_Res (_Class::*)(_ArgTypes...)>
524     : public _Maybe_unary_or_binary_function<_Res, _Class*, _ArgTypes...>
525     {
526       typedef _Res (_Class::*_Functor)(_ArgTypes...);
527
528       template<typename _Tp>
529         _Res
530         _M_call(_Tp& __object, const volatile _Class *, 
531                 _ArgTypes... __args) const
532         { return (__object.*__pmf)(__args...); }
533
534       template<typename _Tp>
535         _Res
536         _M_call(_Tp& __ptr, const volatile void *, _ArgTypes... __args) const
537         { return ((*__ptr).*__pmf)(__args...); }
538
539     public:
540       typedef _Res result_type;
541
542       explicit _Mem_fn(_Functor __pmf) : __pmf(__pmf) { }
543
544       // Handle objects
545       _Res
546       operator()(_Class& __object, _ArgTypes... __args) const
547       { return (__object.*__pmf)(__args...); }
548
549       // Handle pointers
550       _Res
551       operator()(_Class* __object, _ArgTypes... __args) const
552       { return (__object->*__pmf)(__args...); }
553
554       // Handle smart pointers, references and pointers to derived
555       template<typename _Tp>
556         _Res
557         operator()(_Tp& __object, _ArgTypes... __args) const
558         { return _M_call(__object, &__object, __args...); }
559
560     private:
561       _Functor __pmf;
562     };
563
564   /// Implementation of @c mem_fn for const member function pointers.
565   template<typename _Res, typename _Class, typename... _ArgTypes>
566     class _Mem_fn<_Res (_Class::*)(_ArgTypes...) const>
567     : public _Maybe_unary_or_binary_function<_Res, const _Class*, 
568                                              _ArgTypes...>
569     {
570       typedef _Res (_Class::*_Functor)(_ArgTypes...) const;
571
572       template<typename _Tp>
573         _Res
574         _M_call(_Tp& __object, const volatile _Class *, 
575                 _ArgTypes... __args) const
576         { return (__object.*__pmf)(__args...); }
577
578       template<typename _Tp>
579         _Res
580         _M_call(_Tp& __ptr, const volatile void *, _ArgTypes... __args) const
581         { return ((*__ptr).*__pmf)(__args...); }
582
583     public:
584       typedef _Res result_type;
585
586       explicit _Mem_fn(_Functor __pmf) : __pmf(__pmf) { }
587
588       // Handle objects
589       _Res
590       operator()(const _Class& __object, _ArgTypes... __args) const
591       { return (__object.*__pmf)(__args...); }
592
593       // Handle pointers
594       _Res
595       operator()(const _Class* __object, _ArgTypes... __args) const
596       { return (__object->*__pmf)(__args...); }
597
598       // Handle smart pointers, references and pointers to derived
599       template<typename _Tp>
600         _Res operator()(_Tp& __object, _ArgTypes... __args) const
601         { return _M_call(__object, &__object, __args...); }
602
603     private:
604       _Functor __pmf;
605     };
606
607   /// Implementation of @c mem_fn for volatile member function pointers.
608   template<typename _Res, typename _Class, typename... _ArgTypes>
609     class _Mem_fn<_Res (_Class::*)(_ArgTypes...) volatile>
610     : public _Maybe_unary_or_binary_function<_Res, volatile _Class*, 
611                                              _ArgTypes...>
612     {
613       typedef _Res (_Class::*_Functor)(_ArgTypes...) volatile;
614
615       template<typename _Tp>
616         _Res
617         _M_call(_Tp& __object, const volatile _Class *, 
618                 _ArgTypes... __args) const
619         { return (__object.*__pmf)(__args...); }
620
621       template<typename _Tp>
622         _Res
623         _M_call(_Tp& __ptr, const volatile void *, _ArgTypes... __args) const
624         { return ((*__ptr).*__pmf)(__args...); }
625
626     public:
627       typedef _Res result_type;
628
629       explicit _Mem_fn(_Functor __pmf) : __pmf(__pmf) { }
630
631       // Handle objects
632       _Res
633       operator()(volatile _Class& __object, _ArgTypes... __args) const
634       { return (__object.*__pmf)(__args...); }
635
636       // Handle pointers
637       _Res
638       operator()(volatile _Class* __object, _ArgTypes... __args) const
639       { return (__object->*__pmf)(__args...); }
640
641       // Handle smart pointers, references and pointers to derived
642       template<typename _Tp>
643         _Res
644         operator()(_Tp& __object, _ArgTypes... __args) const
645         { return _M_call(__object, &__object, __args...); }
646
647     private:
648       _Functor __pmf;
649     };
650
651   /// Implementation of @c mem_fn for const volatile member function pointers.
652   template<typename _Res, typename _Class, typename... _ArgTypes>
653     class _Mem_fn<_Res (_Class::*)(_ArgTypes...) const volatile>
654     : public _Maybe_unary_or_binary_function<_Res, const volatile _Class*, 
655                                              _ArgTypes...>
656     {
657       typedef _Res (_Class::*_Functor)(_ArgTypes...) const volatile;
658
659       template<typename _Tp>
660         _Res
661         _M_call(_Tp& __object, const volatile _Class *, 
662                 _ArgTypes... __args) const
663         { return (__object.*__pmf)(__args...); }
664
665       template<typename _Tp>
666         _Res
667         _M_call(_Tp& __ptr, const volatile void *, _ArgTypes... __args) const
668         { return ((*__ptr).*__pmf)(__args...); }
669
670     public:
671       typedef _Res result_type;
672
673       explicit _Mem_fn(_Functor __pmf) : __pmf(__pmf) { }
674
675       // Handle objects
676       _Res 
677       operator()(const volatile _Class& __object, _ArgTypes... __args) const
678       { return (__object.*__pmf)(__args...); }
679
680       // Handle pointers
681       _Res 
682       operator()(const volatile _Class* __object, _ArgTypes... __args) const
683       { return (__object->*__pmf)(__args...); }
684
685       // Handle smart pointers, references and pointers to derived
686       template<typename _Tp>
687         _Res operator()(_Tp& __object, _ArgTypes... __args) const
688         { return _M_call(__object, &__object, __args...); }
689
690     private:
691       _Functor __pmf;
692     };
693
694
695   template<typename _Res, typename _Class>
696     class _Mem_fn<_Res _Class::*>
697     {
698       // This bit of genius is due to Peter Dimov, improved slightly by
699       // Douglas Gregor.
700       template<typename _Tp>
701         _Res&
702         _M_call(_Tp& __object, _Class *) const
703         { return __object.*__pm; }
704
705       template<typename _Tp, typename _Up>
706         _Res&
707         _M_call(_Tp& __object, _Up * const *) const
708         { return (*__object).*__pm; }
709
710       template<typename _Tp, typename _Up>
711         const _Res&
712         _M_call(_Tp& __object, const _Up * const *) const
713         { return (*__object).*__pm; }
714
715       template<typename _Tp>
716         const _Res&
717         _M_call(_Tp& __object, const _Class *) const
718         { return __object.*__pm; }
719
720       template<typename _Tp>
721         const _Res&
722         _M_call(_Tp& __ptr, const volatile void*) const
723         { return (*__ptr).*__pm; }
724
725       template<typename _Tp> static _Tp& __get_ref();
726
727       template<typename _Tp>
728         static __sfinae_types::__one __check_const(_Tp&, _Class*);
729       template<typename _Tp, typename _Up>
730         static __sfinae_types::__one __check_const(_Tp&, _Up * const *);
731       template<typename _Tp, typename _Up>
732         static __sfinae_types::__two __check_const(_Tp&, const _Up * const *);
733       template<typename _Tp>
734         static __sfinae_types::__two __check_const(_Tp&, const _Class*);
735       template<typename _Tp>
736         static __sfinae_types::__two __check_const(_Tp&, const volatile void*);
737
738     public:
739       template<typename _Tp>
740         struct _Result_type
741         : _Mem_fn_const_or_non<_Res,
742           (sizeof(__sfinae_types::__two)
743            == sizeof(__check_const<_Tp>(__get_ref<_Tp>(), (_Tp*)0)))>
744         { };
745
746       template<typename _Signature>
747         struct result;
748
749       template<typename _CVMem, typename _Tp>
750         struct result<_CVMem(_Tp)>
751         : public _Result_type<_Tp> { };
752
753       template<typename _CVMem, typename _Tp>
754         struct result<_CVMem(_Tp&)>
755         : public _Result_type<_Tp> { };
756
757       explicit
758       _Mem_fn(_Res _Class::*__pm) : __pm(__pm) { }
759
760       // Handle objects
761       _Res&
762       operator()(_Class& __object) const
763       { return __object.*__pm; }
764
765       const _Res&
766       operator()(const _Class& __object) const
767       { return __object.*__pm; }
768
769       // Handle pointers
770       _Res&
771       operator()(_Class* __object) const
772       { return __object->*__pm; }
773
774       const _Res&
775       operator()(const _Class* __object) const
776       { return __object->*__pm; }
777
778       // Handle smart pointers and derived
779       template<typename _Tp>
780         typename _Result_type<_Tp>::type
781         operator()(_Tp& __unknown) const
782         { return _M_call(__unknown, &__unknown); }
783
784     private:
785       _Res _Class::*__pm;
786     };
787
788   /**
789    *  @brief Returns a function object that forwards to the member
790    *  pointer @a pm.
791    */
792   template<typename _Tp, typename _Class>
793     inline _Mem_fn<_Tp _Class::*>
794     mem_fn(_Tp _Class::* __pm)
795     {
796       return _Mem_fn<_Tp _Class::*>(__pm);
797     }
798
799   /**
800    *  @brief Determines if the given type _Tp is a function object
801    *  should be treated as a subexpression when evaluating calls to
802    *  function objects returned by bind(). [TR1 3.6.1]
803    */
804   template<typename _Tp>
805     struct is_bind_expression
806     { static const bool value = false; };
807
808   template<typename _Tp>
809     const bool is_bind_expression<_Tp>::value;
810
811   /**
812    *  @brief Determines if the given type _Tp is a placeholder in a
813    *  bind() expression and, if so, which placeholder it is. [TR1 3.6.2]
814    */
815   template<typename _Tp>
816     struct is_placeholder
817     { static const int value = 0; };
818
819   template<typename _Tp>
820     const int is_placeholder<_Tp>::value;
821
822   /// The type of placeholder objects defined by libstdc++.
823   template<int _Num> struct _Placeholder { };
824
825   /** @namespace std::placeholders
826    *  @brief ISO C++ 0x entities sub namespace for functional.
827    *
828    *  Define a large number of placeholders. There is no way to
829    *  simplify this with variadic templates, because we're introducing
830    *  unique names for each.
831    */
832   namespace placeholders 
833   { 
834     namespace 
835     {
836       _Placeholder<1> _1;
837       _Placeholder<2> _2;
838       _Placeholder<3> _3;
839       _Placeholder<4> _4;
840       _Placeholder<5> _5;
841       _Placeholder<6> _6;
842       _Placeholder<7> _7;
843       _Placeholder<8> _8;
844       _Placeholder<9> _9;
845       _Placeholder<10> _10;
846       _Placeholder<11> _11;
847       _Placeholder<12> _12;
848       _Placeholder<13> _13;
849       _Placeholder<14> _14;
850       _Placeholder<15> _15;
851       _Placeholder<16> _16;
852       _Placeholder<17> _17;
853       _Placeholder<18> _18;
854       _Placeholder<19> _19;
855       _Placeholder<20> _20;
856       _Placeholder<21> _21;
857       _Placeholder<22> _22;
858       _Placeholder<23> _23;
859       _Placeholder<24> _24;
860       _Placeholder<25> _25;
861       _Placeholder<26> _26;
862       _Placeholder<27> _27;
863       _Placeholder<28> _28;
864       _Placeholder<29> _29;
865     } 
866   }
867
868   /**
869    *  Partial specialization of is_placeholder that provides the placeholder
870    *  number for the placeholder objects defined by libstdc++.
871    */
872   template<int _Num>
873     struct is_placeholder<_Placeholder<_Num> >
874     { static const int value = _Num; };
875
876   template<int _Num>
877     const int is_placeholder<_Placeholder<_Num> >::value;
878
879   /**
880    * Stores a tuple of indices. Used by bind() to extract the elements
881    * in a tuple. 
882    */
883   template<int... _Indexes>
884     struct _Index_tuple { };
885
886   /// Builds an _Index_tuple<0, 1, 2, ..., _Num-1>.
887   template<std::size_t _Num, typename _Tuple = _Index_tuple<> >
888     struct _Build_index_tuple;
889  
890   template<std::size_t _Num, int... _Indexes> 
891     struct _Build_index_tuple<_Num, _Index_tuple<_Indexes...> >
892     : _Build_index_tuple<_Num - 1, 
893                          _Index_tuple<_Indexes..., sizeof...(_Indexes)> >
894     {
895     };
896
897   template<int... _Indexes>
898     struct _Build_index_tuple<0, _Index_tuple<_Indexes...> >
899     {
900       typedef _Index_tuple<_Indexes...> __type;
901     };
902
903   /** 
904    * Used by _Safe_tuple_element to indicate that there is no tuple
905    * element at this position.
906    */
907   struct _No_tuple_element;
908
909   /**
910    * Implementation helper for _Safe_tuple_element. This primary
911    * template handles the case where it is safe to use @c
912    * tuple_element.
913    */
914   template<int __i, typename _Tuple, bool _IsSafe>
915     struct _Safe_tuple_element_impl
916     : tuple_element<__i, _Tuple> { };
917
918   /**
919    * Implementation helper for _Safe_tuple_element. This partial
920    * specialization handles the case where it is not safe to use @c
921    * tuple_element. We just return @c _No_tuple_element.
922    */
923   template<int __i, typename _Tuple>
924     struct _Safe_tuple_element_impl<__i, _Tuple, false>
925     {
926       typedef _No_tuple_element type;
927     };
928
929   /**
930    * Like tuple_element, but returns @c _No_tuple_element when
931    * tuple_element would return an error.
932    */
933  template<int __i, typename _Tuple>
934    struct _Safe_tuple_element
935    : _Safe_tuple_element_impl<__i, _Tuple, 
936                               (__i >= 0 && __i < tuple_size<_Tuple>::value)>
937    {
938    };
939
940   /**
941    *  Maps an argument to bind() into an actual argument to the bound
942    *  function object [TR1 3.6.3/5]. Only the first parameter should
943    *  be specified: the rest are used to determine among the various
944    *  implementations. Note that, although this class is a function
945    *  object, it isn't entirely normal because it takes only two
946    *  parameters regardless of the number of parameters passed to the
947    *  bind expression. The first parameter is the bound argument and
948    *  the second parameter is a tuple containing references to the
949    *  rest of the arguments.
950    */
951   template<typename _Arg,
952            bool _IsBindExp = is_bind_expression<_Arg>::value,
953            bool _IsPlaceholder = (is_placeholder<_Arg>::value > 0)>
954     class _Mu;
955
956   /**
957    *  If the argument is reference_wrapper<_Tp>, returns the
958    *  underlying reference. [TR1 3.6.3/5 bullet 1]
959    */
960   template<typename _Tp>
961     class _Mu<reference_wrapper<_Tp>, false, false>
962     {
963     public:
964       typedef _Tp& result_type;
965
966       /* Note: This won't actually work for const volatile
967        * reference_wrappers, because reference_wrapper::get() is const
968        * but not volatile-qualified. This might be a defect in the TR.
969        */
970       template<typename _CVRef, typename _Tuple>
971         result_type
972         operator()(_CVRef& __arg, const _Tuple&) const volatile
973         { return __arg.get(); }
974     };
975
976   /**
977    *  If the argument is a bind expression, we invoke the underlying
978    *  function object with the same cv-qualifiers as we are given and
979    *  pass along all of our arguments (unwrapped). [TR1 3.6.3/5 bullet 2]
980    */
981   template<typename _Arg>
982     class _Mu<_Arg, true, false>
983     {
984     public:
985       template<typename _Signature> class result;
986
987       // Determine the result type when we pass the arguments along. This
988       // involves passing along the cv-qualifiers placed on _Mu and
989       // unwrapping the argument bundle.
990       template<typename _CVMu, typename _CVArg, typename... _Args>
991         class result<_CVMu(_CVArg, tuple<_Args...>)>
992         : public result_of<_CVArg(_Args...)> { };
993
994       template<typename _CVArg, typename... _Args>
995         typename result_of<_CVArg(_Args...)>::type
996         operator()(_CVArg& __arg,
997                    const tuple<_Args...>& __tuple) const volatile
998         {
999           // Construct an index tuple and forward to __call
1000           typedef typename _Build_index_tuple<sizeof...(_Args)>::__type
1001             _Indexes;
1002           return this->__call(__arg, __tuple, _Indexes());
1003         }
1004
1005     private:
1006       // Invokes the underlying function object __arg by unpacking all
1007       // of the arguments in the tuple. 
1008       template<typename _CVArg, typename... _Args, int... _Indexes>
1009         typename result_of<_CVArg(_Args...)>::type
1010         __call(_CVArg& __arg, const tuple<_Args...>& __tuple,
1011                const _Index_tuple<_Indexes...>&) const volatile
1012         {
1013           return __arg(_GLIBCXX_TR1 get<_Indexes>(__tuple)...);
1014         }
1015     };
1016
1017   /**
1018    *  If the argument is a placeholder for the Nth argument, returns
1019    *  a reference to the Nth argument to the bind function object.
1020    *  [TR1 3.6.3/5 bullet 3]
1021    */
1022   template<typename _Arg>
1023     class _Mu<_Arg, false, true>
1024     {
1025     public:
1026       template<typename _Signature> class result;
1027
1028       template<typename _CVMu, typename _CVArg, typename _Tuple>
1029         class result<_CVMu(_CVArg, _Tuple)>
1030         {
1031           // Add a reference, if it hasn't already been done for us.
1032           // This allows us to be a little bit sloppy in constructing
1033           // the tuple that we pass to result_of<...>.
1034           typedef typename _Safe_tuple_element<(is_placeholder<_Arg>::value
1035                                                 - 1), _Tuple>::type
1036             __base_type;
1037
1038         public:
1039 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
1040           typedef typename add_lvalue_reference<__base_type>::type type;
1041 #else
1042           typedef typename add_reference<__base_type>::type type;
1043 #endif
1044         };
1045
1046       template<typename _Tuple>
1047         typename result<_Mu(_Arg, _Tuple)>::type
1048         operator()(const volatile _Arg&, const _Tuple& __tuple) const volatile
1049         {
1050           return ::std::_GLIBCXX_TR1 get<(is_placeholder<_Arg>::value
1051                                           - 1)>(__tuple);
1052         }
1053     };
1054
1055   /**
1056    *  If the argument is just a value, returns a reference to that
1057    *  value. The cv-qualifiers on the reference are the same as the
1058    *  cv-qualifiers on the _Mu object. [TR1 3.6.3/5 bullet 4]
1059    */
1060   template<typename _Arg>
1061     class _Mu<_Arg, false, false>
1062     {
1063     public:
1064       template<typename _Signature> struct result;
1065
1066       template<typename _CVMu, typename _CVArg, typename _Tuple>
1067         struct result<_CVMu(_CVArg, _Tuple)>
1068         {
1069 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
1070           typedef typename add_lvalue_reference<_CVArg>::type type;
1071 #else
1072           typedef typename add_reference<_CVArg>::type type;
1073 #endif
1074         };
1075
1076       // Pick up the cv-qualifiers of the argument
1077       template<typename _CVArg, typename _Tuple>
1078         _CVArg&
1079         operator()(_CVArg& __arg, const _Tuple&) const volatile
1080         { return __arg; }
1081     };
1082
1083   /**
1084    *  Maps member pointers into instances of _Mem_fn but leaves all
1085    *  other function objects untouched. Used by tr1::bind(). The
1086    *  primary template handles the non--member-pointer case.
1087    */
1088   template<typename _Tp>
1089     struct _Maybe_wrap_member_pointer
1090     {
1091       typedef _Tp type;
1092       
1093       static const _Tp&
1094       __do_wrap(const _Tp& __x)
1095       { return __x; }
1096     };
1097
1098   /**
1099    *  Maps member pointers into instances of _Mem_fn but leaves all
1100    *  other function objects untouched. Used by tr1::bind(). This
1101    *  partial specialization handles the member pointer case.
1102    */
1103   template<typename _Tp, typename _Class>
1104     struct _Maybe_wrap_member_pointer<_Tp _Class::*>
1105     {
1106       typedef _Mem_fn<_Tp _Class::*> type;
1107       
1108       static type
1109       __do_wrap(_Tp _Class::* __pm)
1110       { return type(__pm); }
1111     };
1112
1113   /// Type of the function object returned from bind().
1114   template<typename _Signature>
1115     struct _Bind;
1116
1117    template<typename _Functor, typename... _Bound_args>
1118     class _Bind<_Functor(_Bound_args...)>
1119     : public _Weak_result_type<_Functor>
1120     {
1121       typedef _Bind __self_type;
1122       typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type 
1123         _Bound_indexes;
1124
1125       _Functor _M_f;
1126       tuple<_Bound_args...> _M_bound_args;
1127
1128       // Call unqualified
1129       template<typename... _Args, int... _Indexes>
1130         typename result_of<
1131                    _Functor(typename result_of<_Mu<_Bound_args> 
1132                             (_Bound_args, tuple<_Args...>)>::type...)
1133                  >::type
1134         __call(const tuple<_Args...>& __args, _Index_tuple<_Indexes...>)
1135         {
1136           return _M_f(_Mu<_Bound_args>()
1137                       (_GLIBCXX_TR1 get<_Indexes>(_M_bound_args), __args)...);
1138         }
1139
1140       // Call as const
1141       template<typename... _Args, int... _Indexes>
1142         typename result_of<
1143                    const _Functor(typename result_of<_Mu<_Bound_args> 
1144                                     (const _Bound_args, tuple<_Args...>)
1145                                   >::type...)>::type
1146         __call(const tuple<_Args...>& __args, _Index_tuple<_Indexes...>) const
1147         {
1148           return _M_f(_Mu<_Bound_args>()
1149                       (_GLIBCXX_TR1 get<_Indexes>(_M_bound_args), __args)...);
1150         }
1151
1152       // Call as volatile
1153       template<typename... _Args, int... _Indexes>
1154         typename result_of<
1155                    volatile _Functor(typename result_of<_Mu<_Bound_args> 
1156                                     (volatile _Bound_args, tuple<_Args...>)
1157                                   >::type...)>::type
1158         __call(const tuple<_Args...>& __args, 
1159                _Index_tuple<_Indexes...>) volatile
1160         {
1161           return _M_f(_Mu<_Bound_args>()
1162                       (_GLIBCXX_TR1 get<_Indexes>(_M_bound_args), __args)...);
1163         }
1164
1165       // Call as const volatile
1166       template<typename... _Args, int... _Indexes>
1167         typename result_of<
1168                    const volatile _Functor(typename result_of<_Mu<_Bound_args> 
1169                                     (const volatile _Bound_args, 
1170                                      tuple<_Args...>)
1171                                   >::type...)>::type
1172         __call(const tuple<_Args...>& __args, 
1173                _Index_tuple<_Indexes...>) const volatile
1174         {
1175           return _M_f(_Mu<_Bound_args>()
1176                       (_GLIBCXX_TR1 get<_Indexes>(_M_bound_args), __args)...);
1177         }
1178
1179      public:
1180       explicit _Bind(_Functor __f, _Bound_args... __bound_args)
1181         : _M_f(__f), _M_bound_args(__bound_args...) { }
1182
1183       // Call unqualified
1184       template<typename... _Args>
1185         typename result_of<
1186                    _Functor(typename result_of<_Mu<_Bound_args> 
1187                             (_Bound_args, tuple<_Args...>)>::type...)
1188                  >::type
1189         operator()(_Args&... __args)
1190         {
1191           return this->__call(_GLIBCXX_TR1 tie(__args...), _Bound_indexes());
1192         }
1193
1194       // Call as const
1195       template<typename... _Args>
1196         typename result_of<
1197                    const _Functor(typename result_of<_Mu<_Bound_args> 
1198                             (const _Bound_args, tuple<_Args...>)>::type...)
1199                  >::type
1200         operator()(_Args&... __args) const
1201         {
1202           return this->__call(_GLIBCXX_TR1 tie(__args...), _Bound_indexes());
1203         }
1204
1205
1206       // Call as volatile
1207       template<typename... _Args>
1208         typename result_of<
1209                    volatile _Functor(typename result_of<_Mu<_Bound_args> 
1210                             (volatile _Bound_args, tuple<_Args...>)>::type...)
1211                  >::type
1212         operator()(_Args&... __args) volatile
1213         {
1214           return this->__call(_GLIBCXX_TR1 tie(__args...), _Bound_indexes());
1215         }
1216
1217
1218       // Call as const volatile
1219       template<typename... _Args>
1220         typename result_of<
1221                    const volatile _Functor(typename result_of<_Mu<_Bound_args> 
1222                             (const volatile _Bound_args, 
1223                              tuple<_Args...>)>::type...)
1224                  >::type
1225         operator()(_Args&... __args) const volatile
1226         {
1227           return this->__call(_GLIBCXX_TR1 tie(__args...), _Bound_indexes());
1228         }
1229     };
1230
1231   /// Type of the function object returned from bind<R>().
1232   template<typename _Result, typename _Signature>
1233     struct _Bind_result;
1234
1235   template<typename _Result, typename _Functor, typename... _Bound_args>
1236     class _Bind_result<_Result, _Functor(_Bound_args...)>
1237     {
1238       typedef _Bind_result __self_type;
1239       typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type 
1240         _Bound_indexes;
1241
1242       _Functor _M_f;
1243       tuple<_Bound_args...> _M_bound_args;
1244
1245       // Call unqualified
1246       template<typename... _Args, int... _Indexes>
1247         _Result
1248         __call(const tuple<_Args...>& __args, _Index_tuple<_Indexes...>)
1249         {
1250           return _M_f(_Mu<_Bound_args>()
1251                       (_GLIBCXX_TR1 get<_Indexes>(_M_bound_args), __args)...);
1252         }
1253
1254       // Call as const
1255       template<typename... _Args, int... _Indexes>
1256         _Result
1257         __call(const tuple<_Args...>& __args, _Index_tuple<_Indexes...>) const
1258         {
1259           return _M_f(_Mu<_Bound_args>()
1260                       (_GLIBCXX_TR1 get<_Indexes>(_M_bound_args), __args)...);
1261         }
1262
1263       // Call as volatile
1264       template<typename... _Args, int... _Indexes>
1265         _Result
1266         __call(const tuple<_Args...>& __args, 
1267                _Index_tuple<_Indexes...>) volatile
1268         {
1269           return _M_f(_Mu<_Bound_args>()
1270                       (_GLIBCXX_TR1 get<_Indexes>(_M_bound_args), __args)...);
1271         }
1272
1273       // Call as const volatile
1274       template<typename... _Args, int... _Indexes>
1275         _Result
1276         __call(const tuple<_Args...>& __args, 
1277                _Index_tuple<_Indexes...>) const volatile
1278         {
1279           return _M_f(_Mu<_Bound_args>()
1280                       (_GLIBCXX_TR1 get<_Indexes>(_M_bound_args), __args)...);
1281         }
1282
1283     public:
1284       typedef _Result result_type;
1285
1286       explicit
1287       _Bind_result(_Functor __f, _Bound_args... __bound_args)
1288       : _M_f(__f), _M_bound_args(__bound_args...) { }
1289
1290       // Call unqualified
1291       template<typename... _Args>
1292         result_type
1293         operator()(_Args&... __args)
1294         {
1295           return this->__call(_GLIBCXX_TR1 tie(__args...), _Bound_indexes());
1296         }
1297
1298       // Call as const
1299       template<typename... _Args>
1300         result_type
1301         operator()(_Args&... __args) const
1302         {
1303           return this->__call(_GLIBCXX_TR1 tie(__args...), _Bound_indexes());
1304         }
1305
1306       // Call as volatile
1307       template<typename... _Args>
1308         result_type
1309         operator()(_Args&... __args) volatile
1310         {
1311           return this->__call(_GLIBCXX_TR1 tie(__args...), _Bound_indexes());
1312         }
1313
1314       // Call as const volatile
1315       template<typename... _Args>
1316         result_type
1317         operator()(_Args&... __args) const volatile
1318         {
1319           return this->__call(_GLIBCXX_TR1 tie(__args...), _Bound_indexes());
1320         }
1321     };
1322
1323   /// Class template _Bind is always a bind expression.
1324   template<typename _Signature>
1325     struct is_bind_expression<_Bind<_Signature> >
1326     { static const bool value = true; };
1327
1328   template<typename _Signature>
1329     const bool is_bind_expression<_Bind<_Signature> >::value;
1330
1331   /// Class template _Bind_result is always a bind expression.
1332   template<typename _Result, typename _Signature>
1333     struct is_bind_expression<_Bind_result<_Result, _Signature> >
1334     { static const bool value = true; };
1335
1336   template<typename _Result, typename _Signature>
1337     const bool is_bind_expression<_Bind_result<_Result, _Signature> >::value;
1338
1339   /// bind
1340   template<typename _Functor, typename... _ArgTypes>
1341     inline
1342     _Bind<typename _Maybe_wrap_member_pointer<_Functor>::type(_ArgTypes...)>
1343     bind(_Functor __f, _ArgTypes... __args)
1344     {
1345       typedef _Maybe_wrap_member_pointer<_Functor> __maybe_type;
1346       typedef typename __maybe_type::type __functor_type;
1347       typedef _Bind<__functor_type(_ArgTypes...)> __result_type;
1348       return __result_type(__maybe_type::__do_wrap(__f), __args...);
1349     } 
1350
1351   template<typename _Result, typename _Functor, typename... _ArgTypes>
1352     inline
1353     _Bind_result<_Result,
1354                  typename _Maybe_wrap_member_pointer<_Functor>::type
1355                             (_ArgTypes...)>
1356     bind(_Functor __f, _ArgTypes... __args)
1357     {
1358       typedef _Maybe_wrap_member_pointer<_Functor> __maybe_type;
1359       typedef typename __maybe_type::type __functor_type;
1360       typedef _Bind_result<_Result, __functor_type(_ArgTypes...)>
1361         __result_type;
1362       return __result_type(__maybe_type::__do_wrap(__f), __args...);
1363     }
1364
1365   /**
1366    *  @brief Exception class thrown when class template function's
1367    *  operator() is called with an empty target.
1368    *
1369    */
1370   class bad_function_call : public std::exception { };
1371
1372   /**
1373    *  The integral constant expression 0 can be converted into a
1374    *  pointer to this type. It is used by the function template to
1375    *  accept NULL pointers.
1376    */
1377   struct _M_clear_type;
1378
1379   /**
1380    *  Trait identifying "location-invariant" types, meaning that the
1381    *  address of the object (or any of its members) will not escape.
1382    *  Also implies a trivial copy constructor and assignment operator.
1383    */
1384   template<typename _Tp>
1385     struct __is_location_invariant
1386     : integral_constant<bool,
1387                         (is_pointer<_Tp>::value
1388                          || is_member_pointer<_Tp>::value)>
1389     {
1390     };
1391
1392   class _Undefined_class;
1393
1394   union _Nocopy_types
1395   {
1396     void*       _M_object;
1397     const void* _M_const_object;
1398     void (*_M_function_pointer)();
1399     void (_Undefined_class::*_M_member_pointer)();
1400   };
1401
1402   union _Any_data
1403   {
1404     void*       _M_access()       { return &_M_pod_data[0]; }
1405     const void* _M_access() const { return &_M_pod_data[0]; }
1406
1407     template<typename _Tp>
1408       _Tp&
1409       _M_access()
1410       { return *static_cast<_Tp*>(_M_access()); }
1411
1412     template<typename _Tp>
1413       const _Tp&
1414       _M_access() const
1415       { return *static_cast<const _Tp*>(_M_access()); }
1416
1417     _Nocopy_types _M_unused;
1418     char _M_pod_data[sizeof(_Nocopy_types)];
1419   };
1420
1421   enum _Manager_operation
1422   {
1423     __get_type_info,
1424     __get_functor_ptr,
1425     __clone_functor,
1426     __destroy_functor
1427   };
1428
1429   // Simple type wrapper that helps avoid annoying const problems
1430   // when casting between void pointers and pointers-to-pointers.
1431   template<typename _Tp>
1432     struct _Simple_type_wrapper
1433     {
1434       _Simple_type_wrapper(_Tp __value) : __value(__value) { }
1435
1436       _Tp __value;
1437     };
1438
1439   template<typename _Tp>
1440     struct __is_location_invariant<_Simple_type_wrapper<_Tp> >
1441     : __is_location_invariant<_Tp>
1442     {
1443     };
1444
1445   // Converts a reference to a function object into a callable
1446   // function object.
1447   template<typename _Functor>
1448     inline _Functor&
1449     __callable_functor(_Functor& __f)
1450     { return __f; }
1451
1452   template<typename _Member, typename _Class>
1453     inline _Mem_fn<_Member _Class::*>
1454     __callable_functor(_Member _Class::* &__p)
1455     { return mem_fn(__p); }
1456
1457   template<typename _Member, typename _Class>
1458     inline _Mem_fn<_Member _Class::*>
1459     __callable_functor(_Member _Class::* const &__p)
1460     { return mem_fn(__p); }
1461
1462   template<typename _Signature>
1463     class function;
1464
1465   /// Base class of all polymorphic function object wrappers.
1466   class _Function_base
1467   {
1468   public:
1469     static const std::size_t _M_max_size = sizeof(_Nocopy_types);
1470     static const std::size_t _M_max_align = __alignof__(_Nocopy_types);
1471
1472     template<typename _Functor>
1473       class _Base_manager
1474       {
1475       protected:
1476         static const bool __stored_locally =
1477         (__is_location_invariant<_Functor>::value
1478          && sizeof(_Functor) <= _M_max_size
1479          && __alignof__(_Functor) <= _M_max_align
1480          && (_M_max_align % __alignof__(_Functor) == 0));
1481         
1482         typedef integral_constant<bool, __stored_locally> _Local_storage;
1483
1484         // Retrieve a pointer to the function object
1485         static _Functor*
1486         _M_get_pointer(const _Any_data& __source)
1487         {
1488           const _Functor* __ptr =
1489             __stored_locally? &__source._M_access<_Functor>()
1490             /* have stored a pointer */ : __source._M_access<_Functor*>();
1491           return const_cast<_Functor*>(__ptr);
1492         }
1493
1494         // Clone a location-invariant function object that fits within
1495         // an _Any_data structure.
1496         static void
1497         _M_clone(_Any_data& __dest, const _Any_data& __source, true_type)
1498         {
1499           new (__dest._M_access()) _Functor(__source._M_access<_Functor>());
1500         }
1501
1502         // Clone a function object that is not location-invariant or
1503         // that cannot fit into an _Any_data structure.
1504         static void
1505         _M_clone(_Any_data& __dest, const _Any_data& __source, false_type)
1506         {
1507           __dest._M_access<_Functor*>() =
1508             new _Functor(*__source._M_access<_Functor*>());
1509         }
1510
1511         // Destroying a location-invariant object may still require
1512         // destruction.
1513         static void
1514         _M_destroy(_Any_data& __victim, true_type)
1515         {
1516           __victim._M_access<_Functor>().~_Functor();
1517         }
1518         
1519         // Destroying an object located on the heap.
1520         static void
1521         _M_destroy(_Any_data& __victim, false_type)
1522         {
1523           delete __victim._M_access<_Functor*>();
1524         }
1525         
1526       public:
1527         static bool
1528         _M_manager(_Any_data& __dest, const _Any_data& __source,
1529                    _Manager_operation __op)
1530         {
1531           switch (__op)
1532             {
1533 #ifdef __GXX_RTTI
1534             case __get_type_info:
1535               __dest._M_access<const type_info*>() = &typeid(_Functor);
1536               break;
1537 #endif
1538             case __get_functor_ptr:
1539               __dest._M_access<_Functor*>() = _M_get_pointer(__source);
1540               break;
1541               
1542             case __clone_functor:
1543               _M_clone(__dest, __source, _Local_storage());
1544               break;
1545
1546             case __destroy_functor:
1547               _M_destroy(__dest, _Local_storage());
1548               break;
1549             }
1550           return false;
1551         }
1552
1553         static void
1554         _M_init_functor(_Any_data& __functor, const _Functor& __f)
1555         { _M_init_functor(__functor, __f, _Local_storage()); }
1556         
1557         template<typename _Signature>
1558           static bool
1559           _M_not_empty_function(const function<_Signature>& __f)
1560           { return __f; }
1561
1562         template<typename _Tp>
1563           static bool
1564           _M_not_empty_function(const _Tp*& __fp)
1565           { return __fp; }
1566
1567         template<typename _Class, typename _Tp>
1568           static bool
1569           _M_not_empty_function(_Tp _Class::* const& __mp)
1570           { return __mp; }
1571
1572         template<typename _Tp>
1573           static bool
1574           _M_not_empty_function(const _Tp&)
1575           { return true; }
1576
1577       private:
1578         static void
1579         _M_init_functor(_Any_data& __functor, const _Functor& __f, true_type)
1580         { new (__functor._M_access()) _Functor(__f); }
1581
1582         static void
1583         _M_init_functor(_Any_data& __functor, const _Functor& __f, false_type)
1584         { __functor._M_access<_Functor*>() = new _Functor(__f); }
1585       };
1586
1587     template<typename _Functor>
1588       class _Ref_manager : public _Base_manager<_Functor*>
1589       {
1590         typedef _Function_base::_Base_manager<_Functor*> _Base;
1591
1592     public:
1593         static bool
1594         _M_manager(_Any_data& __dest, const _Any_data& __source,
1595                    _Manager_operation __op)
1596         {
1597           switch (__op)
1598             {
1599 #ifdef __GXX_RTTI
1600             case __get_type_info:
1601               __dest._M_access<const type_info*>() = &typeid(_Functor);
1602               break;
1603 #endif
1604             case __get_functor_ptr:
1605               __dest._M_access<_Functor*>() = *_Base::_M_get_pointer(__source);
1606               return is_const<_Functor>::value;
1607               break;
1608               
1609             default:
1610               _Base::_M_manager(__dest, __source, __op);
1611             }
1612           return false;
1613         }
1614
1615         static void
1616         _M_init_functor(_Any_data& __functor, reference_wrapper<_Functor> __f)
1617         {
1618           // TBD: Use address_of function instead.
1619           _Base::_M_init_functor(__functor, &__f.get());
1620         }
1621       };
1622
1623     _Function_base() : _M_manager(0) { }
1624     
1625     ~_Function_base()
1626     {
1627       if (_M_manager)
1628         _M_manager(_M_functor, _M_functor, __destroy_functor);
1629     }
1630
1631
1632     bool _M_empty() const { return !_M_manager; }
1633
1634     typedef bool (*_Manager_type)(_Any_data&, const _Any_data&,
1635                                   _Manager_operation);
1636
1637     _Any_data     _M_functor;
1638     _Manager_type _M_manager;
1639   };
1640
1641   template<typename _Signature, typename _Functor>
1642     class _Function_handler;
1643
1644   template<typename _Res, typename _Functor, typename... _ArgTypes>
1645     class _Function_handler<_Res(_ArgTypes...), _Functor>
1646     : public _Function_base::_Base_manager<_Functor>
1647     {
1648       typedef _Function_base::_Base_manager<_Functor> _Base;
1649
1650     public:
1651       static _Res
1652       _M_invoke(const _Any_data& __functor, _ArgTypes... __args)
1653       {
1654         return (*_Base::_M_get_pointer(__functor))(__args...);
1655       }
1656     };
1657
1658   template<typename _Functor, typename... _ArgTypes>
1659     class _Function_handler<void(_ArgTypes...), _Functor>
1660     : public _Function_base::_Base_manager<_Functor>
1661     {
1662       typedef _Function_base::_Base_manager<_Functor> _Base;
1663
1664      public:
1665       static void
1666       _M_invoke(const _Any_data& __functor, _ArgTypes... __args)
1667       {
1668         (*_Base::_M_get_pointer(__functor))(__args...);
1669       }
1670     };
1671
1672   template<typename _Res, typename _Functor, typename... _ArgTypes>
1673     class _Function_handler<_Res(_ArgTypes...), reference_wrapper<_Functor> >
1674     : public _Function_base::_Ref_manager<_Functor>
1675     {
1676       typedef _Function_base::_Ref_manager<_Functor> _Base;
1677
1678      public:
1679       static _Res
1680       _M_invoke(const _Any_data& __functor, _ArgTypes... __args)
1681       {
1682         return 
1683           __callable_functor(**_Base::_M_get_pointer(__functor))(__args...);
1684       }
1685     };
1686
1687   template<typename _Functor, typename... _ArgTypes>
1688     class _Function_handler<void(_ArgTypes...), reference_wrapper<_Functor> >
1689     : public _Function_base::_Ref_manager<_Functor>
1690     {
1691       typedef _Function_base::_Ref_manager<_Functor> _Base;
1692
1693      public:
1694       static void
1695       _M_invoke(const _Any_data& __functor, _ArgTypes... __args)
1696       {
1697         __callable_functor(**_Base::_M_get_pointer(__functor))(__args...);
1698       }
1699     };
1700
1701   template<typename _Class, typename _Member, typename _Res, 
1702            typename... _ArgTypes>
1703     class _Function_handler<_Res(_ArgTypes...), _Member _Class::*>
1704     : public _Function_handler<void(_ArgTypes...), _Member _Class::*>
1705     {
1706       typedef _Function_handler<void(_ArgTypes...), _Member _Class::*>
1707         _Base;
1708
1709      public:
1710       static _Res
1711       _M_invoke(const _Any_data& __functor, _ArgTypes... __args)
1712       {
1713         return _GLIBCXX_TR1
1714           mem_fn(_Base::_M_get_pointer(__functor)->__value)(__args...);
1715       }
1716     };
1717
1718   template<typename _Class, typename _Member, typename... _ArgTypes>
1719     class _Function_handler<void(_ArgTypes...), _Member _Class::*>
1720     : public _Function_base::_Base_manager<
1721                  _Simple_type_wrapper< _Member _Class::* > >
1722     {
1723       typedef _Member _Class::* _Functor;
1724       typedef _Simple_type_wrapper<_Functor> _Wrapper;
1725       typedef _Function_base::_Base_manager<_Wrapper> _Base;
1726
1727      public:
1728       static bool
1729       _M_manager(_Any_data& __dest, const _Any_data& __source,
1730                  _Manager_operation __op)
1731       {
1732         switch (__op)
1733           {
1734 #ifdef __GXX_RTTI
1735           case __get_type_info:
1736             __dest._M_access<const type_info*>() = &typeid(_Functor);
1737             break;
1738 #endif      
1739           case __get_functor_ptr:
1740             __dest._M_access<_Functor*>() =
1741               &_Base::_M_get_pointer(__source)->__value;
1742             break;
1743             
1744           default:
1745             _Base::_M_manager(__dest, __source, __op);
1746           }
1747         return false;
1748       }
1749
1750       static void
1751       _M_invoke(const _Any_data& __functor, _ArgTypes... __args)
1752       {
1753         _GLIBCXX_TR1
1754           mem_fn(_Base::_M_get_pointer(__functor)->__value)(__args...);
1755       }
1756     };
1757
1758   /// class function
1759   template<typename _Res, typename... _ArgTypes>
1760     class function<_Res(_ArgTypes...)>
1761     : public _Maybe_unary_or_binary_function<_Res, _ArgTypes...>,
1762       private _Function_base
1763     {
1764 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1765       /// This class is used to implement the safe_bool idiom.
1766       struct _Hidden_type
1767       {
1768         _Hidden_type* _M_bool;
1769       };
1770
1771       /// This typedef is used to implement the safe_bool idiom.
1772       typedef _Hidden_type* _Hidden_type::* _Safe_bool;
1773 #endif
1774
1775       typedef _Res _Signature_type(_ArgTypes...);
1776       
1777       struct _Useless { };
1778       
1779     public:
1780       typedef _Res result_type;
1781       
1782       // [3.7.2.1] construct/copy/destroy
1783       
1784       /**
1785        *  @brief Default construct creates an empty function call wrapper.
1786        *  @post @c !(bool)*this
1787        */
1788       function() : _Function_base() { }
1789       
1790       /**
1791        *  @brief Default construct creates an empty function call wrapper.
1792        *  @post @c !(bool)*this
1793        */
1794       function(_M_clear_type*) : _Function_base() { }
1795       
1796       /**
1797        *  @brief %Function copy constructor.
1798        *  @param x A %function object with identical call signature.
1799        *  @pre @c (bool)*this == (bool)x
1800        *
1801        *  The newly-created %function contains a copy of the target of @a
1802        *  x (if it has one).
1803        */
1804       function(const function& __x);
1805       
1806       /**
1807        *  @brief Builds a %function that targets a copy of the incoming
1808        *  function object.
1809        *  @param f A %function object that is callable with parameters of
1810        *  type @c T1, @c T2, ..., @c TN and returns a value convertible
1811        *  to @c Res.
1812        *
1813        *  The newly-created %function object will target a copy of @a
1814        *  f. If @a f is @c reference_wrapper<F>, then this function
1815        *  object will contain a reference to the function object @c
1816        *  f.get(). If @a f is a NULL function pointer or NULL
1817        *  pointer-to-member, the newly-created object will be empty.
1818        *
1819        *  If @a f is a non-NULL function pointer or an object of type @c
1820        *  reference_wrapper<F>, this function will not throw.
1821        */
1822       template<typename _Functor>
1823         function(_Functor __f,
1824                  typename __gnu_cxx::__enable_if<
1825                            !is_integral<_Functor>::value, _Useless>::__type
1826                    = _Useless());
1827
1828       /**
1829        *  @brief %Function assignment operator.
1830        *  @param x A %function with identical call signature.
1831        *  @post @c (bool)*this == (bool)x
1832        *  @returns @c *this
1833        *
1834        *  The target of @a x is copied to @c *this. If @a x has no
1835        *  target, then @c *this will be empty.
1836        *
1837        *  If @a x targets a function pointer or a reference to a function
1838        *  object, then this operation will not throw an exception.
1839        */
1840       function&
1841       operator=(const function& __x)
1842       {
1843         function(__x).swap(*this);
1844         return *this;
1845       }
1846
1847       /**
1848        *  @brief %Function assignment to zero.
1849        *  @post @c !(bool)*this
1850        *  @returns @c *this
1851        *
1852        *  The target of @a *this is deallocated, leaving it empty.
1853        */
1854       function&
1855       operator=(_M_clear_type*)
1856       {
1857         if (_M_manager)
1858           {
1859             _M_manager(_M_functor, _M_functor, __destroy_functor);
1860             _M_manager = 0;
1861             _M_invoker = 0;
1862           }
1863         return *this;
1864       }
1865
1866       /**
1867        *  @brief %Function assignment to a new target.
1868        *  @param f A %function object that is callable with parameters of
1869        *  type @c T1, @c T2, ..., @c TN and returns a value convertible
1870        *  to @c Res.
1871        *  @return @c *this
1872        *
1873        *  This  %function object wrapper will target a copy of @a
1874        *  f. If @a f is @c reference_wrapper<F>, then this function
1875        *  object will contain a reference to the function object @c
1876        *  f.get(). If @a f is a NULL function pointer or NULL
1877        *  pointer-to-member, @c this object will be empty.
1878        *
1879        *  If @a f is a non-NULL function pointer or an object of type @c
1880        *  reference_wrapper<F>, this function will not throw.
1881        */
1882       template<typename _Functor>
1883         typename __gnu_cxx::__enable_if<!is_integral<_Functor>::value,
1884                                         function&>::__type
1885         operator=(_Functor __f)
1886         {
1887           function(__f).swap(*this);
1888           return *this;
1889         }
1890
1891       // [3.7.2.2] function modifiers
1892       
1893       /**
1894        *  @brief Swap the targets of two %function objects.
1895        *  @param f A %function with identical call signature.
1896        *
1897        *  Swap the targets of @c this function object and @a f. This
1898        *  function will not throw an exception.
1899        */
1900       void swap(function& __x)
1901       {
1902         _Any_data __old_functor = _M_functor;
1903         _M_functor = __x._M_functor;
1904         __x._M_functor = __old_functor;
1905         _Manager_type __old_manager = _M_manager;
1906         _M_manager = __x._M_manager;
1907         __x._M_manager = __old_manager;
1908         _Invoker_type __old_invoker = _M_invoker;
1909         _M_invoker = __x._M_invoker;
1910         __x._M_invoker = __old_invoker;
1911       }
1912       
1913       // [3.7.2.3] function capacity
1914
1915       /**
1916        *  @brief Determine if the %function wrapper has a target.
1917        *
1918        *  @return @c true when this %function object contains a target,
1919        *  or @c false when it is empty.
1920        *
1921        *  This function will not throw an exception.
1922        */
1923 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1924       explicit operator bool() const
1925       { return !_M_empty(); }
1926 #else
1927       operator _Safe_bool() const
1928       {
1929         if (_M_empty())
1930           return 0;
1931         else
1932           return &_Hidden_type::_M_bool;
1933       }
1934 #endif
1935
1936       // [3.7.2.4] function invocation
1937
1938       /**
1939        *  @brief Invokes the function targeted by @c *this.
1940        *  @returns the result of the target.
1941        *  @throws bad_function_call when @c !(bool)*this
1942        *
1943        *  The function call operator invokes the target function object
1944        *  stored by @c this.
1945        */
1946       _Res operator()(_ArgTypes... __args) const;
1947
1948 #ifdef __GXX_RTTI
1949       // [3.7.2.5] function target access
1950       /**
1951        *  @brief Determine the type of the target of this function object
1952        *  wrapper.
1953        *
1954        *  @returns the type identifier of the target function object, or
1955        *  @c typeid(void) if @c !(bool)*this.
1956        *
1957        *  This function will not throw an exception.
1958        */
1959       const type_info& target_type() const;
1960       
1961       /**
1962        *  @brief Access the stored target function object.
1963        *
1964        *  @return Returns a pointer to the stored target function object,
1965        *  if @c typeid(Functor).equals(target_type()); otherwise, a NULL
1966        *  pointer.
1967        *
1968        * This function will not throw an exception.
1969        */
1970       template<typename _Functor>       _Functor* target();
1971       
1972       /// @overload
1973       template<typename _Functor> const _Functor* target() const;
1974 #endif
1975
1976     private:
1977       // [3.7.2.6] undefined operators
1978       template<typename _Function>
1979         void operator==(const function<_Function>&) const;
1980       template<typename _Function>
1981         void operator!=(const function<_Function>&) const;
1982
1983       typedef _Res (*_Invoker_type)(const _Any_data&, _ArgTypes...);
1984       _Invoker_type _M_invoker;
1985   };
1986
1987   template<typename _Res, typename... _ArgTypes>
1988     function<_Res(_ArgTypes...)>::
1989     function(const function& __x)
1990     : _Function_base()
1991     {
1992       if (static_cast<bool>(__x))
1993         {
1994           _M_invoker = __x._M_invoker;
1995           _M_manager = __x._M_manager;
1996           __x._M_manager(_M_functor, __x._M_functor, __clone_functor);
1997         }
1998     }
1999
2000   template<typename _Res, typename... _ArgTypes>
2001     template<typename _Functor>
2002       function<_Res(_ArgTypes...)>::
2003       function(_Functor __f,
2004                typename __gnu_cxx::__enable_if<
2005                        !is_integral<_Functor>::value, _Useless>::__type)
2006       : _Function_base()
2007       {
2008         typedef _Function_handler<_Signature_type, _Functor> _My_handler;
2009
2010         if (_My_handler::_M_not_empty_function(__f))
2011           {
2012             _M_invoker = &_My_handler::_M_invoke;
2013             _M_manager = &_My_handler::_M_manager;
2014             _My_handler::_M_init_functor(_M_functor, __f);
2015           }
2016       }
2017
2018   template<typename _Res, typename... _ArgTypes>
2019     _Res
2020     function<_Res(_ArgTypes...)>::
2021     operator()(_ArgTypes... __args) const
2022     {
2023       if (_M_empty())
2024         {
2025 #if __EXCEPTIONS
2026           throw bad_function_call();
2027 #else
2028           __builtin_abort();
2029 #endif
2030         }
2031       return _M_invoker(_M_functor, __args...);
2032     }
2033
2034 #ifdef __GXX_RTTI
2035   template<typename _Res, typename... _ArgTypes>
2036     const type_info&
2037     function<_Res(_ArgTypes...)>::
2038     target_type() const
2039     {
2040       if (_M_manager)
2041         {
2042           _Any_data __typeinfo_result;
2043           _M_manager(__typeinfo_result, _M_functor, __get_type_info);
2044           return *__typeinfo_result._M_access<const type_info*>();
2045         }
2046       else
2047         return typeid(void);
2048     }
2049
2050   template<typename _Res, typename... _ArgTypes>
2051     template<typename _Functor>
2052       _Functor*
2053       function<_Res(_ArgTypes...)>::
2054       target()
2055       {
2056         if (typeid(_Functor) == target_type() && _M_manager)
2057           {
2058             _Any_data __ptr;
2059             if (_M_manager(__ptr, _M_functor, __get_functor_ptr)
2060                 && !is_const<_Functor>::value)
2061               return 0;
2062             else
2063               return __ptr._M_access<_Functor*>();
2064           }
2065         else
2066           return 0;
2067       }
2068
2069   template<typename _Res, typename... _ArgTypes>
2070     template<typename _Functor>
2071       const _Functor*
2072       function<_Res(_ArgTypes...)>::
2073       target() const
2074       {
2075         if (typeid(_Functor) == target_type() && _M_manager)
2076           {
2077             _Any_data __ptr;
2078             _M_manager(__ptr, _M_functor, __get_functor_ptr);
2079             return __ptr._M_access<const _Functor*>();
2080           }
2081         else
2082           return 0;
2083       }
2084 #endif
2085
2086   // [3.7.2.7] null pointer comparisons
2087
2088   /**
2089    *  @brief Compares a polymorphic function object wrapper against 0
2090    *  (the NULL pointer).
2091    *  @returns @c true if the wrapper has no target, @c false otherwise
2092    *
2093    *  This function will not throw an exception.
2094    */
2095   template<typename _Signature>
2096     inline bool
2097     operator==(const function<_Signature>& __f, _M_clear_type*)
2098     { return !__f; }
2099
2100   /// @overload
2101   template<typename _Signature>
2102     inline bool
2103     operator==(_M_clear_type*, const function<_Signature>& __f)
2104     { return !__f; }
2105
2106   /**
2107    *  @brief Compares a polymorphic function object wrapper against 0
2108    *  (the NULL pointer).
2109    *  @returns @c false if the wrapper has no target, @c true otherwise
2110    *
2111    *  This function will not throw an exception.
2112    */
2113   template<typename _Signature>
2114     inline bool
2115     operator!=(const function<_Signature>& __f, _M_clear_type*)
2116     { return __f; }
2117
2118   /// @overload
2119   template<typename _Signature>
2120     inline bool
2121     operator!=(_M_clear_type*, const function<_Signature>& __f)
2122     { return __f; }
2123
2124   // [3.7.2.8] specialized algorithms
2125
2126   /**
2127    *  @brief Swap the targets of two polymorphic function object wrappers.
2128    *
2129    *  This function will not throw an exception.
2130    */
2131   template<typename _Signature>
2132     inline void
2133     swap(function<_Signature>& __x, function<_Signature>& __y)
2134     { __x.swap(__y); }
2135
2136 _GLIBCXX_END_NAMESPACE_TR1
2137 }