gcc/testsuite/g++.dg/opt/pr47615.C

   1 // { dg-do compile }
   2 // { dg-options "-O -fstrict-aliasing -ftree-pre -fno-tree-fre -fno-tree-sra" }
   3 // { dg-additional-options "-Wno-return-type" }
   4
   5 typedef __SIZE_TYPE__ size_t;
   6 namespace std
   7 {
   8   template < class _T1, class > struct pair
   9   {
  10     _T1 first;
  11   };
  12 }
  13 namespace __gnu_cxx
  14 {
  15   template < typename _Tp > class new_allocator
  16   {
  17   public:
  18     typedef size_t size_type;
  19     typedef _Tp * pointer;
  20     typedef _Tp const_pointer;
  21     typedef _Tp & reference;
  22     typedef const _Tp & const_reference;
  23     template < typename _Tp1 > struct rebind
  24     {
  25       typedef new_allocator < _Tp1 > other;
  26     };
  27   };
  28 }
  29 namespace std
  30 {
  31 template < typename _Tp > class allocator:
  32   public __gnu_cxx::new_allocator < _Tp >
  33   {};
  34   template < typename, typename, typename > struct binary_function;
  35   template < typename _Tp > struct less:binary_function < _Tp, _Tp, bool >
  36   {};
  37 }
  38 namespace __gnu_cxx
  39 {
  40   namespace typelist
  41   {
  42     struct null_type;
  43     template < typename Root > struct node
  44     {
  45       typedef Root root;
  46     };
  47     template < typename, typename > struct chain;
  48     namespace detail
  49     {
  50       template < typename, int >struct chain_at_index_;
  51       template
  52         <
  53         typename
  54         Hd, typename Tl > struct chain_at_index_ <chain < Hd, Tl >, 0 >
  55       {
  56         typedef Hd type;
  57       };
  58       template
  59         <
  60         typename
  61         Hd, typename Tl, int i > struct chain_at_index_ <chain < Hd, Tl >, i >
  62       {
  63         typedef typename chain_at_index_ < Tl, i - 1 >::type type;
  64       };
  65     }
  66     template < typename Typelist, int i > struct at_index
  67     {
  68       typedef typename Typelist::root root_type;
  69       typedef detail::chain_at_index_ < root_type, i > index_type;
  70       typedef typename index_type::type type;
  71     };
  72     template < typename T1, typename T2 > struct create2
  73     {
  74       typedef node < chain < T1, chain < T2, null_type > > >type;
  75     };
  76   }
  77 }
  78 namespace std
  79 {
  80   namespace tr1
  81   {
  82     template < typename _Tp, _Tp __v > struct integral_constant
  83     {
  84       static const _Tp value = __v;
  85     };
  86     typedef integral_constant < bool, false > false_type;
  87     template < typename, typename > struct is_same:false_type
  88     {};
  89   }
  90 }
  91 using std::tr1::is_same;
  92 namespace __gnu_pbds
  93 {
  94   struct null_mapped_type;
  95   struct rb_tree_tag;
  96   namespace detail
  97   {
  98     template < typename, typename, typename > struct basic_tree_policy_base;
  99     template
 100       <
 101       typename
 102       Const_Node_Iterator,
 103       typename
 104       Allocator
 105       >
 106       struct
 107       basic_tree_policy_base
 108       <Const_Node_Iterator, Const_Node_Iterator, Allocator >
 109     {};
 110   }
 111   template
 112     < typename, typename, typename, typename > struct null_tree_node_update;
 113 template < typename Const_Node_Iterator, typename Node_Iterator, typename, typename Allocator > class tree_order_statistics_node_update:
 114   detail::basic_tree_policy_base
 115     < Const_Node_Iterator, Node_Iterator, Allocator >
 116   {
 117   public:
 118     typedef Allocator allocator_type;
 119     typedef typename allocator_type::size_type size_type;
 120     typedef size_type metadata_type;
 121     typedef Const_Node_Iterator const_node_iterator;
 122     typedef Node_Iterator node_iterator;
 123     typedef
 124       typename
 125       allocator_type::template
 126       rebind < metadata_type >::other::reference metadata_reference;
 127     void operator () (node_iterator, const_node_iterator) const;
 128   };
 129   template
 130     <
 131     typename
 132     Const_Node_Iterator,
 133     class
 134     Node_Iterator,
 135     class
 136     Cmp_Fn,
 137     class
 138     Allocator
 139     >
 140     inline
 141     void
 142     tree_order_statistics_node_update
 143     <
 144     Const_Node_Iterator,
 145     Node_Iterator,
 146     Cmp_Fn,
 147     Allocator
 148     >::operator
 149     () (node_iterator node_it, const_node_iterator end_nd_it) const
 150   {
 151     node_iterator l_child_it;
 152     size_type
 153       l_rank = (l_child_it == end_nd_it) ? : l_child_it.get_metadata ();
 154     node_iterator r_child_it = node_it.get_r_child ();
 155     size_type
 156       r_rank = (r_child_it == end_nd_it) ? : r_child_it.get_metadata ();
 157     const_cast
 158       < metadata_reference > (node_it.get_metadata ()) = l_rank + r_rank;
 159   }
 160   namespace
 161   {
 162     template < typename, typename, typename, bool > struct value_type_base;
 163     template
 164       <
 165       typename
 166       Key,
 167       typename
 168       Allocator
 169       > struct value_type_base <Key, null_mapped_type, Allocator, false >
 170     {
 171       typedef Key value_type;
 172       typedef
 173         typename
 174         Allocator::template rebind < value_type >::other value_type_allocator;
 175       typedef typename value_type_allocator::pointer pointer;
 176       typedef typename value_type_allocator::const_pointer const_pointer;
 177       typedef typename value_type_allocator::reference reference;
 178       typedef typename value_type_allocator::const_reference const_reference;
 179     };
 180     template
 181       <
 182       typename
 183       Key,
 184       typename
 185       Mapped, typename Alloc, bool Store_Extra > struct vt_base_selector
 186     {
 187       typedef value_type_base < Key, Mapped, Alloc, Store_Extra > type;
 188     };
 189     template
 190       <
 191       typename
 192       Key,
 193       typename
 194       Mapped,
 195       typename
 196       Alloc,
 197       bool
 198       Store_Extra
 199       >
 200       struct
 201       types_traits:vt_base_selector < Key, Mapped, Alloc, Store_Extra >::type
 202     {};
 203     template < typename, class, class > struct dumconst_node_iterator;
 204     template
 205       <
 206       typename
 207       Key,
 208       typename
 209       Mapped,
 210       class,
 211       class
 212       Node_And_It_Traits, class Allocator > class bin_search_tree_no_data_
 213     {
 214     protected:
 215       typedef
 216         typename
 217         Allocator::template
 218         rebind
 219         < typename Node_And_It_Traits::node >::other::pointer node_pointer;
 220       typedef
 221         typename
 222         types_traits
 223         < Key, Mapped, Allocator, false >::const_reference const_reference;
 224       typedef typename Node_And_It_Traits::point_iterator point_iterator;
 225       typedef typename Node_And_It_Traits::node_update node_update;
 226       void rotate_right (node_pointer);
 227       template
 228         <
 229         typename
 230         Node_Update_ > void apply_update (node_pointer, Node_Update_ *);
 231     };
 232     template
 233       <
 234       typename
 235       Key,
 236       typename
 237       Mapped,
 238       class
 239       Cmp_Fn,
 240       class
 241       Node_And_It_Traits,
 242       class
 243       Allocator
 244       >
 245       void
 246       bin_search_tree_no_data_
 247       <
 248       Key,
 249       Mapped,
 250       Cmp_Fn, Node_And_It_Traits, Allocator >::rotate_right (node_pointer p_x)
 251     {
 252       node_pointer p_y = p_x->m_p_parent;
 253       p_y->m_p_right = p_x;
 254       apply_update (p_x, this);
 255       apply_update (p_x->m_p_parent, (node_update *) this);
 256     }
 257     template
 258       <
 259       typename
 260       Key,
 261       typename
 262       Mapped,
 263       class
 264       Cmp_Fn,
 265       class
 266       Node_And_It_Traits,
 267       class
 268       Allocator
 269       >
 270       template
 271       <
 272       typename
 273       Node_Update_
 274       >
 275       void
 276       bin_search_tree_no_data_
 277       <
 278       Key,
 279       Mapped,
 280       Cmp_Fn,
 281       Node_And_It_Traits,
 282       Allocator >::apply_update (node_pointer p_nd, Node_Update_ *)
 283     {
 284       node_update ()((p_nd), ((0)));
 285     }
 286   }
 287   namespace detail
 288   {
 289   template < typename Key, typename Mapped, typename Cmp_Fn, typename Node_And_It_Traits, typename Allocator > class rb_tree_no_data_:
 290     bin_search_tree_no_data_
 291       < Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator >
 292     {
 293       typedef
 294         bin_search_tree_no_data_
 295         < Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator > base_type;
 296       typedef typename base_type::node_pointer node_pointer;
 297     public:
 298       typedef typename base_type::const_reference const_reference;
 299       typedef typename base_type::point_iterator point_iterator;
 300       std::pair < point_iterator, bool > insert (const_reference);
 301       void insert_fixup (node_pointer);
 302     };
 303     template
 304       <
 305       typename
 306       Key,
 307       typename
 308       Mapped,
 309       typename
 310       Cmp_Fn,
 311       typename
 312       Node_And_It_Traits,
 313       typename
 314       Allocator
 315       >
 316       std::pair
 317       <
 318       typename
 319       rb_tree_no_data_
 320       <
 321       Key,
 322       Mapped,
 323       Cmp_Fn,
 324       Node_And_It_Traits,
 325       Allocator
 326       >::point_iterator,
 327       bool
 328       >
 329       rb_tree_no_data_
 330       <
 331       Key,
 332       Mapped,
 333       Cmp_Fn, Node_And_It_Traits, Allocator >::insert (const_reference)
 334     {
 335       std::pair < point_iterator, bool > ins_pair;
 336 {
 337         insert_fixup (ins_pair.first.m_p_nd);
 338       }
 339     }
 340     template
 341       <
 342       typename
 343       Key,
 344       typename
 345       Mapped,
 346       typename
 347       Cmp_Fn,
 348       typename
 349       Node_And_It_Traits,
 350       typename
 351       Allocator
 352       >
 353       void
 354       rb_tree_no_data_
 355       <
 356       Key,
 357       Mapped,
 358       Cmp_Fn,
 359       Node_And_It_Traits, Allocator >::insert_fixup (node_pointer p_nd)
 360     {
 361 {
 362 {
 363 {
 364             this->rotate_right (p_nd);
 365           }
 366         }
 367       }
 368     }
 369     template
 370       <
 371       typename,
 372       typename, typename, typename, typename > struct container_base_dispatch;
 373     template
 374       <
 375       typename
 376       Key,
 377       typename
 378       Policy_Tl,
 379       typename
 380       Alloc
 381       >
 382       struct
 383       container_base_dispatch
 384       <Key, null_mapped_type, rb_tree_tag, Policy_Tl, Alloc >
 385     {
 386       typedef __gnu_cxx::typelist::at_index < Policy_Tl, 0 > at0;
 387       typedef typename at0::type at0t;
 388       typedef __gnu_cxx::typelist::at_index < Policy_Tl, 1 > at1;
 389       typedef typename at1::type at1t;
 390       typedef
 391         rb_tree_no_data_ < Key, null_mapped_type, at0t, at1t, Alloc > type;
 392     };
 393     template
 394       <
 395       typename
 396       Node_Pointer,
 397       typename,
 398       typename,
 399       typename,
 400       typename, typename, bool, class > class bin_search_tree_const_it_
 401     {
 402     public:
 403       Node_Pointer m_p_nd;
 404     };
 405     template
 406       <
 407       typename
 408       Node,
 409       class
 410       Const_Iterator,
 411       class Iterator, class Allocator > class bin_search_tree_const_node_it_
 412     {
 413       typedef
 414         typename
 415         Allocator::template rebind < Node >::other::pointer node_pointer;
 416     public:
 417       typedef typename Node::metadata_type metadata_type;
 418       typedef
 419         typename
 420         Allocator::template
 421         rebind
 422         < metadata_type >::other::const_reference const_metadata_reference;
 423     bin_search_tree_const_node_it_ (node_pointer p_nd):
 424       m_p_nd ((p_nd))
 425       {}
 426       const_metadata_reference get_metadata ()
 427       {
 428         return (m_p_nd->get_metadata ());
 429       }
 430       bin_search_tree_const_node_it_ ()
 431       {}
 432       bin_search_tree_const_node_it_
 433         < Node, Const_Iterator, Iterator, Allocator > get_r_child ()
 434       {
 435         return ((m_p_nd->m_p_right));
 436       }
 437       bool operator == (bin_search_tree_const_node_it_)
 438       { return true; }
 439       node_pointer m_p_nd;
 440     };
 441     template
 442       <
 443       typename,
 444       typename,
 445       class,
 446       template
 447       <
 448       typename,
 449       class,
 450       class, class > class, class, class > struct bin_search_tree_traits;
 451     template
 452       <
 453       typename
 454       Key,
 455       class
 456       Cmp_Fn,
 457       template
 458       <
 459       typename,
 460       class,
 461       class,
 462       class
 463       >
 464       class
 465       Node_Update,
 466       class
 467       Node,
 468       class
 469       Allocator
 470       >
 471       struct
 472       bin_search_tree_traits
 473       <Key, null_mapped_type, Cmp_Fn, Node_Update, Node, Allocator >
 474     {
 475       typedef
 476         types_traits < Key, null_mapped_type, Allocator, false > type_traits;
 477       typedef Node node;
 478       typedef
 479         bin_search_tree_const_it_
 480         <
 481         typename
 482         Allocator::template
 483         rebind
 484         <
 485         node
 486         >::other::pointer,
 487         typename
 488         type_traits::value_type,
 489         typename
 490         type_traits::pointer,
 491         typename
 492         type_traits::const_pointer,
 493         typename
 494         type_traits::reference,
 495         typename
 496         type_traits::const_reference, true, Allocator > const_point_iterator;
 497       typedef const_point_iterator point_iterator;
 498       typedef
 499         bin_search_tree_const_node_it_
 500         <
 501         Node,
 502         const_point_iterator, point_iterator, Allocator > const_node_iterator;
 503       typedef const_node_iterator node_iterator;
 504       typedef
 505         Node_Update
 506         < const_node_iterator, node_iterator, Cmp_Fn, Allocator > node_update;
 507     };
 508     template < typename Node_Update, bool > struct tree_metadata_helper
 509     {
 510       typedef typename Node_Update::metadata_type type;
 511     };
 512     template
 513       <
 514       typename
 515       Key,
 516       typename
 517       Data,
 518       class
 519       Cmp_Fn,
 520       template
 521       <
 522       typename,
 523       class,
 524       class,
 525       class
 526       >
 527       class Node_Update, class Allocator > struct tree_node_metadata_selector
 528     {
 529       typedef
 530         dumconst_node_iterator < Key, Data, Allocator > dumconst_node_it;
 531       enum
 532       {
 533         null_update = is_same < Node_Update < dumconst_node_it,
 534         dumconst_node_it,
 535         Cmp_Fn,
 536         Allocator >,
 537         null_tree_node_update < dumconst_node_it,
 538         dumconst_node_it,
 539         Cmp_Fn,
 540         Allocator > >::value
 541       };
 542       typedef
 543         typename
 544         tree_metadata_helper
 545         <
 546         Node_Update
 547         <
 548         dumconst_node_it,
 549         dumconst_node_it, Cmp_Fn, Allocator >, null_update >::type type;
 550     };
 551     template
 552       <
 553       typename,
 554       typename,
 555       class,
 556       template
 557       <
 558       typename,
 559       class, class, class > class, class, class > struct tree_traits;
 560     template < typename Value_Type, class Metadata, class Allocator > struct rb_tree_node_
 561     {
 562       typedef Metadata metadata_type;
 563       typedef
 564         typename
 565         Allocator::template
 566         rebind
 567         <
 568         rb_tree_node_
 569         < Value_Type, Metadata, Allocator > >::other::pointer node_pointer;
 570       typedef
 571         typename
 572         Allocator::template
 573         rebind < metadata_type >::other::reference metadata_reference;
 574         metadata_reference get_metadata ()
 575       {
 576         return m_metadata;
 577       }
 578       node_pointer m_p_right;
 579       node_pointer m_p_parent;
 580       metadata_type m_metadata;
 581     };
 582     template
 583       <
 584       typename
 585       Key,
 586       typename
 587       Mapped,
 588       typename
 589       Cmp_Fn,
 590       template
 591       <
 592       typename,
 593       class,
 594       class,
 595       class
 596       >
 597       class
 598       Node_Update,
 599       typename
 600       Allocator
 601       >
 602       struct
 603       tree_traits
 604       <Key,
 605       Mapped,
 606       Cmp_Fn,
 607       Node_Update,
 608       rb_tree_tag,
 609       Allocator
 610       >:bin_search_tree_traits
 611       <
 612       Key,
 613       Mapped,
 614       Cmp_Fn,
 615       Node_Update,
 616       rb_tree_node_
 617       <
 618       typename
 619       types_traits
 620       <
 621       Key,
 622       Mapped,
 623       Allocator,
 624       false
 625       >::value_type,
 626       typename
 627       tree_node_metadata_selector
 628       <
 629       Key,
 630       Mapped, Cmp_Fn, Node_Update, Allocator >::type, Allocator >, Allocator >
 631     {};
 632   }
 633 template < typename Key, typename Mapped, typename Tag, typename Policy_Tl, typename Allocator > class container_base:
 634   public
 635     detail::container_base_dispatch
 636     < Key, Mapped, Tag, Policy_Tl, Allocator >::type
 637   {};
 638 template < typename Key, typename Mapped, typename Tag, typename, typename Policy_Tl, typename Allocator > class basic_tree:
 639   public
 640     container_base < Key, Mapped, Tag, Policy_Tl, Allocator >
 641   {};
 642   template
 643     <
 644     typename
 645     Key,
 646     typename
 647     Mapped,
 648     typename
 649     Cmp_Fn
 650     =
 651     std::less
 652     <
 653     Key
 654     >,
 655     typename
 656     Tag
 657     =
 658     rb_tree_tag,
 659     template
 660     <
 661     typename,
 662     typename,
 663     typename,
 664     typename
 665     >
 666     class
 667     Node_Update
 668     =
 669     null_tree_node_update,
 670     typename
 671     Allocator
 672     =
 673     std::allocator
 674     <
 675     char
 676     > >class
 677     tree:public
 678     basic_tree
 679     <
 680     Key,
 681     Mapped,
 682     Tag,
 683     detail::tree_traits
 684     <
 685     Key,
 686     Mapped,
 687     Cmp_Fn,
 688     Node_Update,
 689     Tag,
 690     Allocator
 691     >,
 692     typename
 693     __gnu_cxx::typelist::create2
 694     <
 695     Cmp_Fn,
 696     detail::tree_traits
 697     < Key, Mapped, Cmp_Fn, Node_Update, Tag, Allocator > >::type, Allocator >
 698   {};
 699 }
 700 using namespace std;
 701 using namespace __gnu_pbds;
 702 typedef
 703   tree
 704   <
 705   int,
 706   null_mapped_type,
 707   less < int >, rb_tree_tag, tree_order_statistics_node_update > set_t;
 708 int main ()
 709 {
 710   set_t s;
 711   s.insert (12);
 712 }