2 // { dg-options "-O -fstrict-aliasing -ftree-pre -fno-tree-fre -fno-tree-sra" }
4 typedef __SIZE_TYPE__ size_t;
7 template < class _T1, class > struct pair
14 template < typename _Tp > class new_allocator
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
24 typedef new_allocator < _Tp1 > other;
30 template < typename _Tp > class allocator:
31 public __gnu_cxx::new_allocator < _Tp >
33 template < typename, typename, typename > struct binary_function;
34 template < typename _Tp > struct less:binary_function < _Tp, _Tp, bool >
42 template < typename Root > struct node
46 template < typename, typename > struct chain;
49 template < typename, int >struct chain_at_index_;
53 Hd, typename Tl > struct chain_at_index_ <chain < Hd, Tl >, 0 >
60 Hd, typename Tl, int i > struct chain_at_index_ <chain < Hd, Tl >, i >
62 typedef typename chain_at_index_ < Tl, i - 1 >::type type;
65 template < typename Typelist, int i > struct at_index
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;
71 template < typename T1, typename T2 > struct create2
73 typedef node < chain < T1, chain < T2, null_type > > >type;
81 template < typename _Tp, _Tp __v > struct integral_constant
83 static const _Tp value = __v;
85 typedef integral_constant < bool, false > false_type;
86 template < typename, typename > struct is_same:false_type
90 using std::tr1::is_same;
93 struct null_mapped_type;
97 template < typename, typename, typename > struct basic_tree_policy_base;
106 basic_tree_policy_base
107 <Const_Node_Iterator, Const_Node_Iterator, Allocator >
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 >
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;
124 allocator_type::template
125 rebind < metadata_type >::other::reference metadata_reference;
126 void operator () (node_iterator, const_node_iterator) const;
141 tree_order_statistics_node_update
148 () (node_iterator node_it, const_node_iterator end_nd_it) const
150 node_iterator l_child_it;
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 ();
155 r_rank = (r_child_it == end_nd_it) ? : r_child_it.get_metadata ();
157 < metadata_reference > (node_it.get_metadata ()) = l_rank + r_rank;
161 template < typename, typename, typename, bool > struct value_type_base;
168 > struct value_type_base <Key, null_mapped_type, Allocator, false >
170 typedef Key value_type;
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;
184 Mapped, typename Alloc, bool Store_Extra > struct vt_base_selector
186 typedef value_type_base < Key, Mapped, Alloc, Store_Extra > type;
200 types_traits:vt_base_selector < Key, Mapped, Alloc, Store_Extra >::type
202 template < typename, class, class > struct dumconst_node_iterator;
211 Node_And_It_Traits, class Allocator > class bin_search_tree_no_data_
218 < typename Node_And_It_Traits::node >::other::pointer node_pointer;
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);
229 Node_Update_ > void apply_update (node_pointer, Node_Update_ *);
245 bin_search_tree_no_data_
249 Cmp_Fn, Node_And_It_Traits, Allocator >::rotate_right (node_pointer p_x)
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);
275 bin_search_tree_no_data_
281 Allocator >::apply_update (node_pointer p_nd, Node_Update_ *)
283 node_update ()((p_nd), ((0)));
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 >
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;
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);
332 Cmp_Fn, Node_And_It_Traits, Allocator >::insert (const_reference)
334 std::pair < point_iterator, bool > ins_pair;
336 insert_fixup (ins_pair.first.m_p_nd);
358 Node_And_It_Traits, Allocator >::insert_fixup (node_pointer p_nd)
363 this->rotate_right (p_nd);
371 typename, typename, typename, typename > struct container_base_dispatch;
382 container_base_dispatch
383 <Key, null_mapped_type, rb_tree_tag, Policy_Tl, Alloc >
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;
390 rb_tree_no_data_ < Key, null_mapped_type, at0t, at1t, Alloc > type;
399 typename, typename, bool, class > class bin_search_tree_const_it_
410 class Iterator, class Allocator > class bin_search_tree_const_node_it_
414 Allocator::template rebind < Node >::other::pointer node_pointer;
416 typedef typename Node::metadata_type metadata_type;
421 < metadata_type >::other::const_reference const_metadata_reference;
422 bin_search_tree_const_node_it_ (node_pointer p_nd):
425 const_metadata_reference get_metadata ()
427 return (m_p_nd->get_metadata ());
429 bin_search_tree_const_node_it_ ()
431 bin_search_tree_const_node_it_
432 < Node, Const_Iterator, Iterator, Allocator > get_r_child ()
434 return ((m_p_nd->m_p_right));
436 bool operator == (bin_search_tree_const_node_it_)
449 class, class > class, class, class > struct bin_search_tree_traits;
471 bin_search_tree_traits
472 <Key, null_mapped_type, Cmp_Fn, Node_Update, Node, Allocator >
475 types_traits < Key, null_mapped_type, Allocator, false > type_traits;
478 bin_search_tree_const_it_
487 type_traits::value_type,
489 type_traits::pointer,
491 type_traits::const_pointer,
493 type_traits::reference,
495 type_traits::const_reference, true, Allocator > const_point_iterator;
496 typedef const_point_iterator point_iterator;
498 bin_search_tree_const_node_it_
501 const_point_iterator, point_iterator, Allocator > const_node_iterator;
502 typedef const_node_iterator node_iterator;
505 < const_node_iterator, node_iterator, Cmp_Fn, Allocator > node_update;
507 template < typename Node_Update, bool > struct tree_metadata_helper
509 typedef typename Node_Update::metadata_type type;
526 class Node_Update, class Allocator > struct tree_node_metadata_selector
529 dumconst_node_iterator < Key, Data, Allocator > dumconst_node_it;
532 null_update = is_same < Node_Update < dumconst_node_it,
536 null_tree_node_update < dumconst_node_it,
548 dumconst_node_it, Cmp_Fn, Allocator >, null_update >::type type;
558 class, class, class > class, class, class > struct tree_traits;
559 template < typename Value_Type, class Metadata, class Allocator > struct rb_tree_node_
561 typedef Metadata metadata_type;
568 < Value_Type, Metadata, Allocator > >::other::pointer node_pointer;
572 rebind < metadata_type >::other::reference metadata_reference;
573 metadata_reference get_metadata ()
577 node_pointer m_p_right;
578 node_pointer m_p_parent;
579 metadata_type m_metadata;
609 >:bin_search_tree_traits
626 tree_node_metadata_selector
629 Mapped, Cmp_Fn, Node_Update, Allocator >::type, Allocator >, Allocator >
632 template < typename Key, typename Mapped, typename Tag, typename Policy_Tl, typename Allocator > class container_base:
634 detail::container_base_dispatch
635 < Key, Mapped, Tag, Policy_Tl, Allocator >::type
637 template < typename Key, typename Mapped, typename Tag, typename, typename Policy_Tl, typename Allocator > class basic_tree:
639 container_base < Key, Mapped, Tag, Policy_Tl, Allocator >
668 null_tree_node_update,
692 __gnu_cxx::typelist::create2
696 < Key, Mapped, Cmp_Fn, Node_Update, Tag, Allocator > >::type, Allocator >
700 using namespace __gnu_pbds;
706 less < int >, rb_tree_tag, tree_order_statistics_node_update > set_t;