OSDN Git Service

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