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