URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [testsuite/] [g++.dg/] [opt/] [pr47615.C] - Blame information for rev 749

Go to most recent revision | Details | Compare with Previous | View Log


// { dg-do compile }
// { dg-options "-O -fstrict-aliasing -ftree-pre -fno-tree-fre -fno-tree-sra" }
 
typedef __SIZE_TYPE__ size_t;
namespace std
{
  template < class _T1, class > struct pair
  {
    _T1 first;
  };
}
namespace __gnu_cxx
{
  template < typename _Tp > class new_allocator
  {
  public:
    typedef size_t size_type;
    typedef _Tp * pointer;
    typedef _Tp const_pointer;
    typedef _Tp & reference;
    typedef const _Tp & const_reference;
    template < typename _Tp1 > struct rebind
    {
      typedef new_allocator < _Tp1 > other;
    };
  };
}
namespace std
{
template < typename _Tp > class allocator:
  public __gnu_cxx::new_allocator < _Tp >
  {};
  template < typename, typename, typename > struct binary_function;
  template < typename _Tp > struct less:binary_function < _Tp, _Tp, bool >
  {};
}
namespace __gnu_cxx
{
  namespace typelist
  {
    struct null_type;
    template < typename Root > struct node
    {
      typedef Root root;
    };
    template < typename, typename > struct chain;
    namespace detail
    {
      template < typename, int >struct chain_at_index_;
      template
        <
        typename
        Hd, typename Tl > struct chain_at_index_ , 0 >
      {
        typedef Hd type;
      };
      template
        <
        typename
        Hd, typename Tl, int i > struct chain_at_index_ , i >
      {
        typedef typename chain_at_index_ < Tl, i - 1 >::type type;
      };
    }
    template < typename Typelist, int i > struct at_index
    {
      typedef typename Typelist::root root_type;
      typedef detail::chain_at_index_ < root_type, i > index_type;
      typedef typename index_type::type type;
    };
    template < typename T1, typename T2 > struct create2
    {
      typedef node < chain < T1, chain < T2, null_type > > >type;
    };
  }
}
namespace std
{
  namespace tr1
  {
    template < typename _Tp, _Tp __v > struct integral_constant
    {
      static const _Tp value = __v;
    };
    typedef integral_constant < bool, false > false_type;
    template < typename, typename > struct is_same:false_type
    {};
  }
}
using std::tr1::is_same;
namespace __gnu_pbds
{
  struct null_mapped_type;
  struct rb_tree_tag;
  namespace detail
  {
    template < typename, typename, typename > struct basic_tree_policy_base;
    template
      <
      typename
      Const_Node_Iterator,
      typename
      Allocator
      >
      struct
      basic_tree_policy_base
      
    {};
  }
  template
    < typename, typename, typename, typename > struct null_tree_node_update;
template < typename Const_Node_Iterator, typename Node_Iterator, typename, typename Allocator > class tree_order_statistics_node_update:
  detail::basic_tree_policy_base
    < Const_Node_Iterator, Node_Iterator, Allocator >
  {
  public:
    typedef Allocator allocator_type;
    typedef typename allocator_type::size_type size_type;
    typedef size_type metadata_type;
    typedef Const_Node_Iterator const_node_iterator;
    typedef Node_Iterator node_iterator;
    typedef
      typename
      allocator_type::template
      rebind < metadata_type >::other::reference metadata_reference;
    void operator () (node_iterator, const_node_iterator) const;
  };
  template
    <
    typename
    Const_Node_Iterator,
    class
    Node_Iterator,
    class
    Cmp_Fn,
    class
    Allocator
    >
    inline
    void
    tree_order_statistics_node_update
    <
    Const_Node_Iterator,
    Node_Iterator,
    Cmp_Fn,
    Allocator
    >::operator
    () (node_iterator node_it, const_node_iterator end_nd_it) const
  {
    node_iterator l_child_it;
    size_type
      l_rank = (l_child_it == end_nd_it) ? : l_child_it.get_metadata ();
    node_iterator r_child_it = node_it.get_r_child ();
    size_type
      r_rank = (r_child_it == end_nd_it) ? : r_child_it.get_metadata ();
    const_cast
      < metadata_reference > (node_it.get_metadata ()) = l_rank + r_rank;
  }
  namespace
  {
    template < typename, typename, typename, bool > struct value_type_base;
    template
      <
      typename
      Key,
      typename
      Allocator
      > struct value_type_base 
    {
      typedef Key value_type;
      typedef
        typename
        Allocator::template rebind < value_type >::other value_type_allocator;
      typedef typename value_type_allocator::pointer pointer;
      typedef typename value_type_allocator::const_pointer const_pointer;
      typedef typename value_type_allocator::reference reference;
      typedef typename value_type_allocator::const_reference const_reference;
    };
    template
      <
      typename
      Key,
      typename
      Mapped, typename Alloc, bool Store_Extra > struct vt_base_selector
    {
      typedef value_type_base < Key, Mapped, Alloc, Store_Extra > type;
    };
    template
      <
      typename
      Key,
      typename
      Mapped,
      typename
      Alloc,
      bool
      Store_Extra
      >
      struct
      types_traits:vt_base_selector < Key, Mapped, Alloc, Store_Extra >::type
    {};
    template < typename, class, class > struct dumconst_node_iterator;
    template
      <
      typename
      Key,
      typename
      Mapped,
      class,
      class
      Node_And_It_Traits, class Allocator > class bin_search_tree_no_data_
    {
    protected:
      typedef
        typename
        Allocator::template
        rebind
        < typename Node_And_It_Traits::node >::other::pointer node_pointer;
      typedef
        typename
        types_traits
        < Key, Mapped, Allocator, false >::const_reference const_reference;
      typedef typename Node_And_It_Traits::point_iterator point_iterator;
      typedef typename Node_And_It_Traits::node_update node_update;
      void rotate_right (node_pointer);
      template
        <
        typename
        Node_Update_ > void apply_update (node_pointer, Node_Update_ *);
    };
    template
      <
      typename
      Key,
      typename
      Mapped,
      class
      Cmp_Fn,
      class
      Node_And_It_Traits,
      class
      Allocator
      >
      void
      bin_search_tree_no_data_
      <
      Key,
      Mapped,
      Cmp_Fn, Node_And_It_Traits, Allocator >::rotate_right (node_pointer p_x)
    {
      node_pointer p_y = p_x->m_p_parent;
      p_y->m_p_right = p_x;
      apply_update (p_x, this);
      apply_update (p_x->m_p_parent, (node_update *) this);
    }
    template
      <
      typename
      Key,
      typename
      Mapped,
      class
      Cmp_Fn,
      class
      Node_And_It_Traits,
      class
      Allocator
      >
      template
      <
      typename
      Node_Update_
      >
      void
      bin_search_tree_no_data_
      <
      Key,
      Mapped,
      Cmp_Fn,
      Node_And_It_Traits,
      Allocator >::apply_update (node_pointer p_nd, Node_Update_ *)
    {
      node_update ()((p_nd), ((0)));
    }
  }
  namespace detail
  {
  template < typename Key, typename Mapped, typename Cmp_Fn, typename Node_And_It_Traits, typename Allocator > class rb_tree_no_data_:
    bin_search_tree_no_data_
      < Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator >
    {
      typedef
        bin_search_tree_no_data_
        < Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator > base_type;
      typedef typename base_type::node_pointer node_pointer;
    public:
      typedef typename base_type::const_reference const_reference;
      typedef typename base_type::point_iterator point_iterator;
      std::pair < point_iterator, bool > insert (const_reference);
      void insert_fixup (node_pointer);
    };
    template
      <
      typename
      Key,
      typename
      Mapped,
      typename
      Cmp_Fn,
      typename
      Node_And_It_Traits,
      typename
      Allocator
      >
      std::pair
      <
      typename
      rb_tree_no_data_
      <
      Key,
      Mapped,
      Cmp_Fn,
      Node_And_It_Traits,
      Allocator
      >::point_iterator,
      bool
      >
      rb_tree_no_data_
      <
      Key,
      Mapped,
      Cmp_Fn, Node_And_It_Traits, Allocator >::insert (const_reference)
    {
      std::pair < point_iterator, bool > ins_pair;
{
        insert_fixup (ins_pair.first.m_p_nd);
      }
    }
    template
      <
      typename
      Key,
      typename
      Mapped,
      typename
      Cmp_Fn,
      typename
      Node_And_It_Traits,
      typename
      Allocator
      >
      void
      rb_tree_no_data_
      <
      Key,
      Mapped,
      Cmp_Fn,
      Node_And_It_Traits, Allocator >::insert_fixup (node_pointer p_nd)
    {
{
{
{
            this->rotate_right (p_nd);
          }
        }
      }
    }
    template
      <
      typename,
      typename, typename, typename, typename > struct container_base_dispatch;
    template
      <
      typename
      Key,
      typename
      Policy_Tl,
      typename
      Alloc
      >
      struct
      container_base_dispatch
      
    {
      typedef __gnu_cxx::typelist::at_index < Policy_Tl, 0 > at0;
      typedef typename at0::type at0t;
      typedef __gnu_cxx::typelist::at_index < Policy_Tl, 1 > at1;
      typedef typename at1::type at1t;
      typedef
        rb_tree_no_data_ < Key, null_mapped_type, at0t, at1t, Alloc > type;
    };
    template
      <
      typename
      Node_Pointer,
      typename,
      typename,
      typename,
      typename, typename, bool, class > class bin_search_tree_const_it_
    {
    public:
      Node_Pointer m_p_nd;
    };
    template
      <
      typename
      Node,
      class
      Const_Iterator,
      class Iterator, class Allocator > class bin_search_tree_const_node_it_
    {
      typedef
        typename
        Allocator::template rebind < Node >::other::pointer node_pointer;
    public:
      typedef typename Node::metadata_type metadata_type;
      typedef
        typename
        Allocator::template
        rebind
        < metadata_type >::other::const_reference const_metadata_reference;
    bin_search_tree_const_node_it_ (node_pointer p_nd):
      m_p_nd ((p_nd))
      {}
      const_metadata_reference get_metadata ()
      {
        return (m_p_nd->get_metadata ());
      }
      bin_search_tree_const_node_it_ ()
      {}
      bin_search_tree_const_node_it_
        < Node, Const_Iterator, Iterator, Allocator > get_r_child ()
      {
        return ((m_p_nd->m_p_right));
      }
      bool operator == (bin_search_tree_const_node_it_)
      {}
      node_pointer m_p_nd;
    };
    template
      <
      typename,
      typename,
      class,
      template
      <
      typename,
      class,
      class, class > class, class, class > struct bin_search_tree_traits;
    template
      <
      typename
      Key,
      class
      Cmp_Fn,
      template
      <
      typename,
      class,
      class,
      class
      >
      class
      Node_Update,
      class
      Node,
      class
      Allocator
      >
      struct
      bin_search_tree_traits
      
    {
      typedef
        types_traits < Key, null_mapped_type, Allocator, false > type_traits;
      typedef Node node;
      typedef
        bin_search_tree_const_it_
        <
        typename
        Allocator::template
        rebind
        <
        node
        >::other::pointer,
        typename
        type_traits::value_type,
        typename
        type_traits::pointer,
        typename
        type_traits::const_pointer,
        typename
        type_traits::reference,
        typename
        type_traits::const_reference, true, Allocator > const_point_iterator;
      typedef const_point_iterator point_iterator;
      typedef
        bin_search_tree_const_node_it_
        <
        Node,
        const_point_iterator, point_iterator, Allocator > const_node_iterator;
      typedef const_node_iterator node_iterator;
      typedef
        Node_Update
        < const_node_iterator, node_iterator, Cmp_Fn, Allocator > node_update;
    };
    template < typename Node_Update, bool > struct tree_metadata_helper
    {
      typedef typename Node_Update::metadata_type type;
    };
    template
      <
      typename
      Key,
      typename
      Data,
      class
      Cmp_Fn,
      template
      <
      typename,
      class,
      class,
      class
      >
      class Node_Update, class Allocator > struct tree_node_metadata_selector
    {
      typedef
        dumconst_node_iterator < Key, Data, Allocator > dumconst_node_it;
      enum
      {
        null_update = is_same < Node_Update < dumconst_node_it,
        dumconst_node_it,
        Cmp_Fn,
        Allocator >,
        null_tree_node_update < dumconst_node_it,
        dumconst_node_it,
        Cmp_Fn,
        Allocator > >::value
      };
      typedef
        typename
        tree_metadata_helper
        <
        Node_Update
        <
        dumconst_node_it,
        dumconst_node_it, Cmp_Fn, Allocator >, null_update >::type type;
    };
    template
      <
      typename,
      typename,
      class,
      template
      <
      typename,
      class, class, class > class, class, class > struct tree_traits;
    template < typename Value_Type, class Metadata, class Allocator > struct rb_tree_node_
    {
      typedef Metadata metadata_type;
      typedef
        typename
        Allocator::template
        rebind
        <
        rb_tree_node_
        < Value_Type, Metadata, Allocator > >::other::pointer node_pointer;
      typedef
        typename
        Allocator::template
        rebind < metadata_type >::other::reference metadata_reference;
        metadata_reference get_metadata ()
      {
        return m_metadata;
      }
      node_pointer m_p_right;
      node_pointer m_p_parent;
      metadata_type m_metadata;
    };
    template
      <
      typename
      Key,
      typename
      Mapped,
      typename
      Cmp_Fn,
      template
      <
      typename,
      class,
      class,
      class
      >
      class
      Node_Update,
      typename
      Allocator
      >
      struct
      tree_traits
      
      Mapped,
      Cmp_Fn,
      Node_Update,
      rb_tree_tag,
      Allocator
      >:bin_search_tree_traits
      <
      Key,
      Mapped,
      Cmp_Fn,
      Node_Update,
      rb_tree_node_
      <
      typename
      types_traits
      <
      Key,
      Mapped,
      Allocator,
      false
      >::value_type,
      typename
      tree_node_metadata_selector
      <
      Key,
      Mapped, Cmp_Fn, Node_Update, Allocator >::type, Allocator >, Allocator >
    {};
  }
template < typename Key, typename Mapped, typename Tag, typename Policy_Tl, typename Allocator > class container_base:
  public
    detail::container_base_dispatch
    < Key, Mapped, Tag, Policy_Tl, Allocator >::type
  {};
template < typename Key, typename Mapped, typename Tag, typename, typename Policy_Tl, typename Allocator > class basic_tree:
  public
    container_base < Key, Mapped, Tag, Policy_Tl, Allocator >
  {};
  template
    <
    typename
    Key,
    typename
    Mapped,
    typename
    Cmp_Fn
    =
    std::less
    <
    Key
    >,
    typename
    Tag
    =
    rb_tree_tag,
    template
    <
    typename,
    typename,
    typename,
    typename
    >
    class
    Node_Update
    =
    null_tree_node_update,
    typename
    Allocator
    =
    std::allocator
    <
    char
    > >class
    tree:public
    basic_tree
    <
    Key,
    Mapped,
    Tag,
    detail::tree_traits
    <
    Key,
    Mapped,
    Cmp_Fn,
    Node_Update,
    Tag,
    Allocator
    >,
    typename
    __gnu_cxx::typelist::create2
    <
    Cmp_Fn,
    detail::tree_traits
    < Key, Mapped, Cmp_Fn, Node_Update, Tag, Allocator > >::type, Allocator >
  {};
}
using namespace std;
using namespace __gnu_pbds;
typedef
  tree
  <
  int,
  null_mapped_type,
  less < int >, rb_tree_tag, tree_order_statistics_node_update > set_t;
main ()
{
  set_t s;
  s.insert (12);
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [testsuite/] [g++.dg/] [opt/] [pr47615.C] - Blame information for rev 749

Line No.	Rev	Author	Line
1	693	jeremybenn	`// { 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_ , 0 >`
54			`{`
55			`typedef Hd type;`
56			`};`
57			`template`
58			`<`
59			`typename`
60			`Hd, typename Tl, int i > struct chain_at_index_ , 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
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`
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
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
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
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			`}`