gcc/testsuite/g++.dg/tm/pr46646.C

   1 // { dg-do compile }
   2 // { dg-options "-fgnu-tm -O0"}
   3 // { dg-additional-options "-Wno-return-type" }
   4
   5 namespace std __attribute__ ((__visibility__ ("default"))) {
   6   template<class _T1, class _T2>
   7     struct pair
   8     {
   9       typedef _T1 first_type;
  10       typedef _T2 second_type;
  11       _T1 first;
  12       _T2 second;
  13       pair()
  14       : first(), second() { }
  15       pair(const _T1& __a, const _T2& __b)
  16       : first(__a), second(__b) { }
  17     };
  18 }
  19
  20
  21 typedef long int ptrdiff_t;
  22 typedef __SIZE_TYPE__ size_t;
  23 namespace std __attribute__ ((__visibility__ ("default"))) {
  24   using ::ptrdiff_t;
  25   using ::size_t;
  26 }
  27 namespace std __attribute__ ((__visibility__ ("default"))) {
  28   struct input_iterator_tag { };
  29   struct output_iterator_tag { };
  30   struct forward_iterator_tag : public input_iterator_tag { };
  31   struct bidirectional_iterator_tag : public forward_iterator_tag { };
  32   struct random_access_iterator_tag : public bidirectional_iterator_tag { };
  33   template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
  34            typename _Pointer = _Tp*, typename _Reference = _Tp&>
  35     struct iterator
  36     {
  37       typedef _Category iterator_category;
  38       typedef _Tp value_type;
  39       typedef _Distance difference_type;
  40       typedef _Pointer pointer;
  41       typedef _Reference reference;
  42     };
  43   template<typename _Iterator>
  44     struct iterator_traits
  45     {
  46       typedef typename _Iterator::iterator_category iterator_category;
  47       typedef typename _Iterator::value_type value_type;
  48       typedef typename _Iterator::difference_type difference_type;
  49       typedef typename _Iterator::pointer pointer;
  50       typedef typename _Iterator::reference reference;
  51     };
  52   template<typename _Tp>
  53     struct iterator_traits<_Tp*>
  54     {
  55       typedef random_access_iterator_tag iterator_category;
  56       typedef _Tp value_type;
  57       typedef ptrdiff_t difference_type;
  58       typedef _Tp* pointer;
  59       typedef _Tp& reference;
  60     };
  61   template<typename _Tp>
  62     struct iterator_traits<const _Tp*>
  63     {
  64       typedef random_access_iterator_tag iterator_category;
  65       typedef _Tp value_type;
  66       typedef ptrdiff_t difference_type;
  67       typedef const _Tp* pointer;
  68       typedef const _Tp& reference;
  69     };
  70   template<typename _Iter>
  71     inline typename iterator_traits<_Iter>::iterator_category
  72     __iterator_category(const _Iter&)
  73     { return typename iterator_traits<_Iter>::iterator_category(); }
  74 }
  75 namespace std __attribute__ ((__visibility__ ("default"))) {
  76   template<typename _Iterator>
  77     class reverse_iterator
  78     : public iterator<typename iterator_traits<_Iterator>::iterator_category,
  79         typename iterator_traits<_Iterator>::value_type,
  80         typename iterator_traits<_Iterator>::difference_type,
  81         typename iterator_traits<_Iterator>::pointer,
  82                       typename iterator_traits<_Iterator>::reference>
  83     {
  84     protected:
  85       _Iterator current;
  86       typedef iterator_traits<_Iterator> __traits_type;
  87     public:
  88       typedef _Iterator iterator_type;
  89       typedef typename __traits_type::difference_type difference_type;
  90       typedef typename __traits_type::pointer pointer;
  91       typedef typename __traits_type::reference reference;
  92       reverse_iterator() : current() { }
  93       explicit
  94       reverse_iterator(iterator_type __x) : current(__x) { }
  95       reverse_iterator(const reverse_iterator& __x)
  96       : current(__x.current) { }
  97       template<typename _Iter>
  98         reverse_iterator(const reverse_iterator<_Iter>& __x)
  99  : current(__x.base()) { }
 100       iterator_type
 101       base() const
 102       { return current; }
 103       reference
 104       operator*() const
 105       {
 106  _Iterator __tmp = current;
 107  return *--__tmp;
 108       }
 109       pointer
 110       operator->() const
 111       { return &(operator*()); }
 112       reverse_iterator&
 113       operator++()
 114       {
 115  --current;
 116  return *this;
 117       }
 118       reverse_iterator
 119       operator++(int)
 120       {
 121  reverse_iterator __tmp = *this;
 122  --current;
 123  return __tmp;
 124       }
 125       reverse_iterator&
 126       operator--()
 127       {
 128  ++current;
 129  return *this;
 130       }
 131       reverse_iterator
 132       operator--(int)
 133       {
 134  reverse_iterator __tmp = *this;
 135  ++current;
 136  return __tmp;
 137       }
 138       reverse_iterator
 139       operator+(difference_type __n) const
 140       { return reverse_iterator(current - __n); }
 141       reverse_iterator&
 142       operator+=(difference_type __n)
 143       {
 144  current -= __n;
 145  return *this;
 146       }
 147       reverse_iterator
 148       operator-(difference_type __n) const
 149       { return reverse_iterator(current + __n); }
 150       reverse_iterator&
 151       operator-=(difference_type __n)
 152       {
 153  current += __n;
 154  return *this;
 155       }
 156       reference
 157       operator[](difference_type __n) const
 158       { return *(*this + __n); }
 159     };
 160 }
 161
 162
 163
 164 extern "C++" {
 165 namespace std
 166 {
 167   class exception
 168   {
 169   public:
 170     exception() throw() { }
 171     virtual ~exception() throw();
 172     virtual const char* what() const throw();
 173   };
 174   class bad_exception : public exception
 175   {
 176   public:
 177     bad_exception() throw() { }
 178     virtual ~bad_exception() throw();
 179     virtual const char* what() const throw();
 180   };
 181   typedef void (*terminate_handler) ();
 182   typedef void (*unexpected_handler) ();
 183   terminate_handler set_terminate(terminate_handler) throw();
 184   void terminate() throw() __attribute__ ((__noreturn__));
 185   unexpected_handler set_unexpected(unexpected_handler) throw();
 186   void unexpected() __attribute__ ((__noreturn__));
 187   bool uncaught_exception() throw() __attribute__ ((__pure__));
 188 }
 189 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
 190   void __verbose_terminate_handler();
 191 }
 192 }
 193 extern "C++" {
 194 namespace std
 195 {
 196   class bad_alloc : public exception
 197   {
 198   public:
 199     bad_alloc() throw() { }
 200     virtual ~bad_alloc() throw();
 201     virtual const char* what() const throw();
 202   };
 203   struct nothrow_t { };
 204   extern const nothrow_t nothrow;
 205   typedef void (*new_handler)();
 206   new_handler set_new_handler(new_handler) throw();
 207 }
 208
 209 void* operator new(std::size_t, const std::nothrow_t&) throw();
 210 void* operator new[](std::size_t, const std::nothrow_t&) throw();
 211 void operator delete(void*, const std::nothrow_t&) throw();
 212 void operator delete[](void*, const std::nothrow_t&) throw();
 213 inline void* operator new(std::size_t, void* __p) throw() { return __p; }
 214 inline void* operator new[](std::size_t, void* __p) throw() { return __p; }
 215 inline void operator delete (void*, void*) throw() { }
 216 inline void operator delete[](void*, void*) throw() { }
 217 }
 218 namespace std __attribute__ ((__visibility__ ("default"))) {
 219   void
 220   __throw_bad_exception(void) __attribute__((__noreturn__));
 221   __attribute__((transaction_safe))
 222   void
 223   __throw_bad_alloc(void) __attribute__((__noreturn__));
 224   void
 225   __throw_bad_cast(void) __attribute__((__noreturn__));
 226   void
 227   __throw_bad_typeid(void) __attribute__((__noreturn__));
 228   void
 229   __throw_logic_error(const char*) __attribute__((__noreturn__));
 230   void
 231   __throw_domain_error(const char*) __attribute__((__noreturn__));
 232   void
 233   __throw_invalid_argument(const char*) __attribute__((__noreturn__));
 234   void
 235   __throw_length_error(const char*) __attribute__((__noreturn__));
 236   void
 237   __throw_out_of_range(const char*) __attribute__((__noreturn__));
 238   void
 239   __throw_runtime_error(const char*) __attribute__((__noreturn__));
 240   void
 241   __throw_range_error(const char*) __attribute__((__noreturn__));
 242   void
 243   __throw_overflow_error(const char*) __attribute__((__noreturn__));
 244   void
 245   __throw_underflow_error(const char*) __attribute__((__noreturn__));
 246   void
 247   __throw_ios_failure(const char*) __attribute__((__noreturn__));
 248   void
 249   __throw_system_error(int) __attribute__((__noreturn__));
 250   void
 251   __throw_future_error(int) __attribute__((__noreturn__));
 252   void
 253   __throw_bad_function_call() __attribute__((__noreturn__));
 254 }
 255
 256
 257 namespace std __attribute__ ((__visibility__ ("default"))) {
 258   template<typename _Tp>
 259     inline void
 260     swap(_Tp& __a, _Tp& __b)
 261     {
 262
 263       _Tp __tmp = (__a);
 264       __a = (__b);
 265       __b = (__tmp);
 266     }
 267   template<typename _Tp, size_t _Nm>
 268     inline void
 269     swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
 270     {
 271       for (size_t __n = 0; __n < _Nm; ++__n)
 272  swap(__a[__n], __b[__n]);
 273     }
 274 }
 275 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
 276   using std::size_t;
 277   using std::ptrdiff_t;
 278   template<typename _Tp>
 279     class new_allocator
 280     {
 281     public:
 282       typedef size_t size_type;
 283       typedef ptrdiff_t difference_type;
 284       typedef _Tp* pointer;
 285       typedef const _Tp* const_pointer;
 286       typedef _Tp& reference;
 287       typedef const _Tp& const_reference;
 288       typedef _Tp value_type;
 289       template<typename _Tp1>
 290         struct rebind
 291         { typedef new_allocator<_Tp1> other; };
 292       new_allocator() throw() { }
 293       new_allocator(const new_allocator&) throw() { }
 294       template<typename _Tp1>
 295         new_allocator(const new_allocator<_Tp1>&) throw() { }
 296       ~new_allocator() throw() { }
 297       pointer
 298       address(reference __x) const { return &__x; }
 299       const_pointer
 300       address(const_reference __x) const { return &__x; }
 301       __attribute__((transaction_safe))
 302       pointer
 303       allocate(size_type __n, const void* = 0)
 304       {
 305  if (__n > this->max_size())
 306    std::__throw_bad_alloc();
 307  return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
 308       }
 309 __attribute__((transaction_safe))
 310 void
 311       deallocate(pointer __p, size_type)
 312       { ::operator delete(__p); }
 313       size_type
 314       max_size() const throw()
 315       { return size_t(-1) / sizeof(_Tp); }
 316       void
 317       construct(pointer __p, const _Tp& __val)
 318       { ::new((void *)__p) _Tp(__val); }
 319       void
 320       destroy(pointer __p) { __p->~_Tp(); }
 321     };
 322   template<typename _Tp>
 323     inline bool
 324     operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
 325     { return true; }
 326   template<typename _Tp>
 327     inline bool
 328     operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
 329     { return false; }
 330 }
 331 namespace std __attribute__ ((__visibility__ ("default"))) {
 332   template<typename _Tp>
 333     class allocator;
 334   template<>
 335     class allocator<void>
 336     {
 337     public:
 338       typedef size_t size_type;
 339       typedef ptrdiff_t difference_type;
 340       typedef void* pointer;
 341       typedef const void* const_pointer;
 342       typedef void value_type;
 343       template<typename _Tp1>
 344         struct rebind
 345         { typedef allocator<_Tp1> other; };
 346     };
 347   template<typename _Tp>
 348     class allocator: public __gnu_cxx::new_allocator<_Tp>
 349     {
 350    public:
 351       typedef size_t size_type;
 352       typedef ptrdiff_t difference_type;
 353       typedef _Tp* pointer;
 354       typedef const _Tp* const_pointer;
 355       typedef _Tp& reference;
 356       typedef const _Tp& const_reference;
 357       typedef _Tp value_type;
 358       template<typename _Tp1>
 359         struct rebind
 360         { typedef allocator<_Tp1> other; };
 361       allocator() throw() { }
 362       allocator(const allocator& __a) throw()
 363       : __gnu_cxx::new_allocator<_Tp>(__a) { }
 364       template<typename _Tp1>
 365         allocator(const allocator<_Tp1>&) throw() { }
 366       ~allocator() throw() { }
 367     };
 368   template<typename _T1, typename _T2>
 369     inline bool
 370     operator==(const allocator<_T1>&, const allocator<_T2>&)
 371     { return true; }
 372   template<typename _Tp>
 373     inline bool
 374     operator==(const allocator<_Tp>&, const allocator<_Tp>&)
 375     { return true; }
 376   template<typename _T1, typename _T2>
 377     inline bool
 378     operator!=(const allocator<_T1>&, const allocator<_T2>&)
 379     { return false; }
 380   template<typename _Tp>
 381     inline bool
 382     operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
 383     { return false; }
 384   //extern template class allocator<char>;
 385   //  extern template class allocator<wchar_t>;
 386   template<typename _Alloc, bool = __is_empty(_Alloc)>
 387     struct __alloc_swap
 388     { static void _S_do_it(_Alloc&, _Alloc&) { } };
 389   template<typename _Alloc>
 390     struct __alloc_swap<_Alloc, false>
 391     {
 392       static void
 393       _S_do_it(_Alloc& __one, _Alloc& __two)
 394       {
 395  if (__one != __two)
 396    swap(__one, __two);
 397       }
 398     };
 399   template<typename _Alloc, bool = __is_empty(_Alloc)>
 400     struct __alloc_neq
 401     {
 402       static bool
 403       _S_do_it(const _Alloc&, const _Alloc&)
 404       { return false; }
 405     };
 406   template<typename _Alloc>
 407     struct __alloc_neq<_Alloc, false>
 408     {
 409       static bool
 410       _S_do_it(const _Alloc& __one, const _Alloc& __two)
 411       { return __one != __two; }
 412     };
 413 }
 414 namespace std __attribute__ ((__visibility__ ("default"))) {
 415   template<typename _Arg, typename _Result>
 416     struct unary_function
 417     {
 418       typedef _Arg argument_type;
 419       typedef _Result result_type;
 420     };
 421   template<typename _Arg1, typename _Arg2, typename _Result>
 422     struct binary_function
 423     {
 424       typedef _Arg1 first_argument_type;
 425       typedef _Arg2 second_argument_type;
 426       typedef _Result result_type;
 427     };
 428   template<typename _Tp>
 429     struct equal_to : public binary_function<_Tp, _Tp, bool>
 430     {
 431       bool
 432       operator()(const _Tp& __x, const _Tp& __y) const
 433       { return __x == __y; }
 434     };
 435   template<typename _Tp>
 436     struct not_equal_to : public binary_function<_Tp, _Tp, bool>
 437     {
 438       bool
 439       operator()(const _Tp& __x, const _Tp& __y) const
 440       { return __x != __y; }
 441     };
 442   template<typename _Tp>
 443     struct greater : public binary_function<_Tp, _Tp, bool>
 444     {
 445       bool
 446       operator()(const _Tp& __x, const _Tp& __y) const
 447       { return __x > __y; }
 448     };
 449   template<typename _Tp>
 450     struct less : public binary_function<_Tp, _Tp, bool>
 451     {
 452       bool
 453       operator()(const _Tp& __x, const _Tp& __y) const
 454       { return __x < __y; }
 455     };
 456   template<typename _Tp>
 457     struct _Identity : public unary_function<_Tp,_Tp>
 458     {
 459       _Tp&
 460       operator()(_Tp& __x) const
 461       { return __x; }
 462       const _Tp&
 463       operator()(const _Tp& __x) const
 464       { return __x; }
 465     };
 466 }
 467 namespace std __attribute__ ((__visibility__ ("default"))) {
 468   enum _Rb_tree_color { _S_red = false, _S_black = true };
 469   struct _Rb_tree_node_base
 470   {
 471     typedef _Rb_tree_node_base* _Base_ptr;
 472     typedef const _Rb_tree_node_base* _Const_Base_ptr;
 473     _Rb_tree_color _M_color;
 474     _Base_ptr _M_parent;
 475     _Base_ptr _M_left;
 476     _Base_ptr _M_right;
 477     static _Base_ptr
 478     _S_minimum(_Base_ptr __x)
 479     {
 480       while (__x->_M_left != 0) __x = __x->_M_left;
 481       return __x;
 482     }
 483     static _Const_Base_ptr
 484     _S_minimum(_Const_Base_ptr __x)
 485     {
 486       while (__x->_M_left != 0) __x = __x->_M_left;
 487       return __x;
 488     }
 489     static _Base_ptr
 490     _S_maximum(_Base_ptr __x)
 491     {
 492       while (__x->_M_right != 0) __x = __x->_M_right;
 493       return __x;
 494     }
 495     static _Const_Base_ptr
 496     _S_maximum(_Const_Base_ptr __x)
 497     {
 498       while (__x->_M_right != 0) __x = __x->_M_right;
 499       return __x;
 500     }
 501   };
 502   template<typename _Val>
 503     struct _Rb_tree_node : public _Rb_tree_node_base
 504     {
 505       typedef _Rb_tree_node<_Val>* _Link_type;
 506       _Val _M_value_field;
 507     };
 508   __attribute__ ((__pure__)) _Rb_tree_node_base*
 509   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
 510   __attribute__ ((__pure__)) const _Rb_tree_node_base*
 511   _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
 512   __attribute__ ((__pure__)) _Rb_tree_node_base*
 513   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
 514   __attribute__ ((__pure__)) const _Rb_tree_node_base*
 515   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
 516   template<typename _Tp>
 517     struct _Rb_tree_iterator
 518     {
 519       typedef _Tp value_type;
 520       typedef _Tp& reference;
 521       typedef _Tp* pointer;
 522       typedef bidirectional_iterator_tag iterator_category;
 523       typedef ptrdiff_t difference_type;
 524       typedef _Rb_tree_iterator<_Tp> _Self;
 525       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
 526       typedef _Rb_tree_node<_Tp>* _Link_type;
 527       _Rb_tree_iterator()
 528       : _M_node() { }
 529       explicit
 530       _Rb_tree_iterator(_Link_type __x)
 531       : _M_node(__x) { }
 532       reference
 533       operator*() const
 534       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 535       pointer
 536       operator->() const
 537       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
 538       _Self&
 539       operator++()
 540       {
 541  _M_node = _Rb_tree_increment(_M_node);
 542  return *this;
 543       }
 544       _Self
 545       operator++(int)
 546       {
 547  _Self __tmp = *this;
 548  _M_node = _Rb_tree_increment(_M_node);
 549  return __tmp;
 550       }
 551       _Self&
 552       operator--()
 553       {
 554  _M_node = _Rb_tree_decrement(_M_node);
 555  return *this;
 556       }
 557       _Self
 558       operator--(int)
 559       {
 560  _Self __tmp = *this;
 561  _M_node = _Rb_tree_decrement(_M_node);
 562  return __tmp;
 563       }
 564       bool
 565       operator==(const _Self& __x) const
 566       { return _M_node == __x._M_node; }
 567       bool
 568       operator!=(const _Self& __x) const
 569       { return _M_node != __x._M_node; }
 570       _Base_ptr _M_node;
 571   };
 572   template<typename _Tp>
 573     struct _Rb_tree_const_iterator
 574     {
 575       typedef _Tp value_type;
 576       typedef const _Tp& reference;
 577       typedef const _Tp* pointer;
 578       typedef _Rb_tree_iterator<_Tp> iterator;
 579       typedef bidirectional_iterator_tag iterator_category;
 580       typedef ptrdiff_t difference_type;
 581       typedef _Rb_tree_const_iterator<_Tp> _Self;
 582       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
 583       typedef const _Rb_tree_node<_Tp>* _Link_type;
 584       _Rb_tree_const_iterator()
 585       : _M_node() { }
 586       explicit
 587       _Rb_tree_const_iterator(_Link_type __x)
 588       : _M_node(__x) { }
 589       _Rb_tree_const_iterator(const iterator& __it)
 590       : _M_node(__it._M_node) { }
 591       reference
 592       operator*() const
 593       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
 594       pointer
 595       operator->() const
 596       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
 597       _Self&
 598       operator++()
 599       {
 600  _M_node = _Rb_tree_increment(_M_node);
 601  return *this;
 602       }
 603       _Self
 604       operator++(int)
 605       {
 606  _Self __tmp = *this;
 607  _M_node = _Rb_tree_increment(_M_node);
 608  return __tmp;
 609       }
 610       _Self&
 611       operator--()
 612       {
 613  _M_node = _Rb_tree_decrement(_M_node);
 614  return *this;
 615       }
 616       _Self
 617       operator--(int)
 618       {
 619  _Self __tmp = *this;
 620  _M_node = _Rb_tree_decrement(_M_node);
 621  return __tmp;
 622       }
 623       bool
 624       operator==(const _Self& __x) const
 625       { return _M_node == __x._M_node; }
 626       bool
 627       operator!=(const _Self& __x) const
 628       { return _M_node != __x._M_node; }
 629       _Base_ptr _M_node;
 630     };
 631   void
 632   _Rb_tree_insert_and_rebalance(const bool __insert_left,
 633                                 _Rb_tree_node_base* __x,
 634                                 _Rb_tree_node_base* __p,
 635                                 _Rb_tree_node_base& __header) throw ();
 636   _Rb_tree_node_base*
 637   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 638           _Rb_tree_node_base& __header) throw ();
 639   template<typename _Key, typename _Val, typename _KeyOfValue,
 640            typename _Compare, typename _Alloc = allocator<_Val> >
 641     class _Rb_tree
 642     {
 643       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
 644               _Node_allocator;
 645     protected:
 646       typedef _Rb_tree_node_base* _Base_ptr;
 647       typedef const _Rb_tree_node_base* _Const_Base_ptr;
 648     public:
 649       typedef _Key key_type;
 650       typedef _Val value_type;
 651       typedef value_type* pointer;
 652       typedef const value_type* const_pointer;
 653       typedef value_type& reference;
 654       typedef const value_type& const_reference;
 655       typedef _Rb_tree_node<_Val>* _Link_type;
 656       typedef const _Rb_tree_node<_Val>* _Const_Link_type;
 657       typedef size_t size_type;
 658       typedef ptrdiff_t difference_type;
 659       typedef _Alloc allocator_type;
 660       _Node_allocator&
 661       _M_get_Node_allocator()
 662       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
 663       const _Node_allocator&
 664       _M_get_Node_allocator() const
 665       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
 666       allocator_type
 667       get_allocator() const
 668       { return allocator_type(_M_get_Node_allocator()); }
 669     protected:
 670       _Link_type
 671       _M_get_node()
 672       { return _M_impl._Node_allocator::allocate(1); }
 673       __attribute__((transaction_safe))
 674       void
 675       _M_put_node(_Link_type __p)
 676       { _M_impl._Node_allocator::deallocate(__p, 1); }
 677       __attribute__((transaction_safe))
 678       _Link_type
 679       _M_create_node(const value_type& __x)
 680       {
 681  _Link_type __tmp = _M_get_node();
 682  try
 683    { get_allocator().construct(&__tmp->_M_value_field, __x); }
 684  catch(...)
 685    {
 686      _M_put_node(__tmp);
 687      throw;
 688    }
 689  return __tmp;
 690       }
 691       void
 692       _M_destroy_node(_Link_type __p)
 693       {
 694  get_allocator().destroy(&__p->_M_value_field);
 695  _M_put_node(__p);
 696       }
 697     protected:
 698       template<typename _Key_compare,
 699         bool _Is_pod_comparator = __is_pod(_Key_compare)>
 700         struct _Rb_tree_impl : public _Node_allocator
 701         {
 702    _Key_compare _M_key_compare;
 703    _Rb_tree_node_base _M_header;
 704    size_type _M_node_count;
 705    _Rb_tree_impl()
 706    : _Node_allocator(), _M_key_compare(), _M_header(),
 707      _M_node_count(0)
 708    { _M_initialize(); }
 709    _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
 710    : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
 711      _M_node_count(0)
 712    { _M_initialize(); }
 713  private:
 714    void
 715    _M_initialize()
 716    {
 717      this->_M_header._M_color = _S_red;
 718      this->_M_header._M_parent = 0;
 719      this->_M_header._M_left = &this->_M_header;
 720      this->_M_header._M_right = &this->_M_header;
 721    }
 722  };
 723       _Rb_tree_impl<_Compare> _M_impl;
 724     protected:
 725       _Base_ptr&
 726       _M_root()
 727       { return this->_M_impl._M_header._M_parent; }
 728       _Const_Base_ptr
 729       _M_root() const
 730       { return this->_M_impl._M_header._M_parent; }
 731       _Base_ptr&
 732       _M_leftmost()
 733       { return this->_M_impl._M_header._M_left; }
 734       _Const_Base_ptr
 735       _M_leftmost() const
 736       { return this->_M_impl._M_header._M_left; }
 737       _Base_ptr&
 738       _M_rightmost()
 739       { return this->_M_impl._M_header._M_right; }
 740       _Const_Base_ptr
 741       _M_rightmost() const
 742       { return this->_M_impl._M_header._M_right; }
 743       _Link_type
 744       _M_begin()
 745       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 746       _Const_Link_type
 747       _M_begin() const
 748       {
 749  return static_cast<_Const_Link_type>
 750    (this->_M_impl._M_header._M_parent);
 751       }
 752       _Link_type
 753       _M_end()
 754       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 755       _Const_Link_type
 756       _M_end() const
 757       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 758       static const_reference
 759       _S_value(_Const_Link_type __x)
 760       { return __x->_M_value_field; }
 761       static const _Key&
 762       _S_key(_Const_Link_type __x)
 763       { return _KeyOfValue()(_S_value(__x)); }
 764       static _Link_type
 765       _S_left(_Base_ptr __x)
 766       { return static_cast<_Link_type>(__x->_M_left); }
 767       static _Const_Link_type
 768       _S_left(_Const_Base_ptr __x)
 769       { return static_cast<_Const_Link_type>(__x->_M_left); }
 770       static _Link_type
 771       _S_right(_Base_ptr __x)
 772       { return static_cast<_Link_type>(__x->_M_right); }
 773       static _Const_Link_type
 774       _S_right(_Const_Base_ptr __x)
 775       { return static_cast<_Const_Link_type>(__x->_M_right); }
 776       static const_reference
 777       _S_value(_Const_Base_ptr __x)
 778       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
 779       static const _Key&
 780       _S_key(_Const_Base_ptr __x)
 781       { return _KeyOfValue()(_S_value(__x)); }
 782     public:
 783       typedef _Rb_tree_iterator<value_type> iterator;
 784       typedef _Rb_tree_const_iterator<value_type> const_iterator;
 785       typedef std::reverse_iterator<iterator> reverse_iterator;
 786       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 787     private:
 788       iterator
 789       _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
 790    const value_type& __v);
 791     public:
 792       _Rb_tree() { }
 793       iterator
 794       begin()
 795       {
 796  return iterator(static_cast<_Link_type>
 797    (this->_M_impl._M_header._M_left));
 798       }
 799       const_iterator
 800       begin() const
 801       {
 802  return const_iterator(static_cast<_Const_Link_type>
 803          (this->_M_impl._M_header._M_left));
 804       }
 805       iterator
 806       end()
 807       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
 808       const_iterator
 809       end() const
 810       {
 811  return const_iterator(static_cast<_Const_Link_type>
 812          (&this->_M_impl._M_header));
 813       }
 814       pair<iterator, bool>
 815       _M_insert_unique(const value_type& __x);
 816     };
 817   template<typename _Key, typename _Val, typename _KeyOfValue,
 818            typename _Compare, typename _Alloc>
 819     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 820     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 821     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
 822     {
 823       _Link_type __z = _M_create_node(__v);
 824       return iterator(__z);
 825     }
 826   template<typename _Key, typename _Val, typename _KeyOfValue,
 827            typename _Compare, typename _Alloc>
 828     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
 829       _Compare, _Alloc>::iterator, bool>
 830     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 831     _M_insert_unique(const _Val& __v)
 832     {
 833       _Link_type __x = _M_begin();
 834       _Link_type __y = _M_end();
 835       iterator __j = iterator(__y);
 836  return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
 837     }
 838 }
 839 namespace std __attribute__ ((__visibility__ ("default"))) {
 840   template<typename _Key, typename _Compare = std::less<_Key>,
 841     typename _Alloc = std::allocator<_Key> >
 842     class set
 843     {
 844     public:
 845       typedef _Key key_type;
 846       typedef _Key value_type;
 847       typedef _Compare key_compare;
 848       typedef _Compare value_compare;
 849       typedef _Alloc allocator_type;
 850     private:
 851       typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
 852       typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
 853          key_compare, _Key_alloc_type> _Rep_type;
 854       _Rep_type _M_t;
 855     public:
 856       typedef typename _Key_alloc_type::pointer pointer;
 857       typedef typename _Key_alloc_type::const_pointer const_pointer;
 858       typedef typename _Key_alloc_type::reference reference;
 859       typedef typename _Key_alloc_type::const_reference const_reference;
 860       typedef typename _Rep_type::const_iterator iterator;
 861       typedef typename _Rep_type::const_iterator const_iterator;
 862       typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
 863       typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
 864       typedef typename _Rep_type::size_type size_type;
 865       typedef typename _Rep_type::difference_type difference_type;
 866       std::pair<iterator, bool>
 867       insert(const value_type& __x)
 868       {
 869    _M_t._M_insert_unique(__x);
 870       }
 871     };
 872 }
 873 __attribute__((transaction_pure))
 874 void* operator new(size_t);
 875 __attribute__((transaction_pure))
 876 void operator delete(void*);
 877 class Widget
 878 {
 879 private:
 880 };
 881 class Screen
 882 {
 883 protected:
 884 std::set<Widget *> widgets;
 885 public:
 886 void addWidget(Widget* widget);
 887 };
 888 void Screen::addWidget(Widget* widget)
 889 {
 890 widgets.insert(widget);
 891 }