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