3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 2, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
33 // Permission to use, copy, modify, sell, and distribute this software
34 // is hereby granted without fee, provided that the above copyright
35 // notice appears in all copies, and that both that copyright notice
36 // and this permission notice appear in supporting documentation. None
37 // of the above authors, nor IBM Haifa Research Laboratories, make any
38 // representation about the suitability of this software for any
39 // purpose. It is provided "as is" without express or implied
43 * @file insert_fn_imps.hpp
44 * Contains an implementation class for bin_search_tree_.
48 inline std::pair
<typename
PB_DS_CLASS_C_DEC::point_iterator
, bool>
50 insert_leaf(const_reference r_value
)
52 _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
55 return (std::make_pair(
56 insert_imp_empty(r_value
),
59 node_pointer p_nd
= m_p_head
->m_p_parent
;
60 node_pointer p_pot
= m_p_head
;
63 if (!Cmp_Fn::operator()(
64 PB_DS_V2F(p_nd
->m_value
),
69 p_nd
= p_nd
->m_p_left
;
72 p_nd
= p_nd
->m_p_right
;
74 if (p_pot
== m_p_head
)
75 return (std::make_pair(
76 insert_leaf_new(r_value
, m_p_head
->m_p_right
, false),
79 if (!Cmp_Fn::operator()(
81 PB_DS_V2F(p_pot
->m_value
)))
83 _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
85 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(
88 return (std::make_pair(p_pot
, false));
91 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(
94 p_nd
= p_pot
->m_p_left
;
96 return (std::make_pair(
97 insert_leaf_new(r_value
, p_pot
, true),
100 while (p_nd
->m_p_right
!= NULL
)
101 p_nd
= p_nd
->m_p_right
;
103 return (std::make_pair(
104 insert_leaf_new(r_value
, p_nd
, false),
109 inline typename
PB_DS_CLASS_C_DEC::iterator
111 insert_leaf_new(const_reference r_value
, node_pointer p_nd
, bool left_nd
)
113 node_pointer p_new_nd
=
114 get_new_node_for_leaf_insert( r_value
, traits_base::m_no_throw_copies_indicator
);
118 _GLIBCXX_DEBUG_ASSERT(p_nd
->m_p_left
== NULL
);
119 _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(
121 PB_DS_V2F(p_nd
->m_value
)));
123 p_nd
->m_p_left
= p_new_nd
;
125 if (m_p_head
->m_p_left
== p_nd
)
126 m_p_head
->m_p_left
= p_new_nd
;
130 _GLIBCXX_DEBUG_ASSERT(p_nd
->m_p_right
== NULL
);
131 _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(
132 PB_DS_V2F(p_nd
->m_value
),
133 PB_DS_V2F(r_value
)));
135 p_nd
->m_p_right
= p_new_nd
;
137 if (m_p_head
->m_p_right
== p_nd
)
138 m_p_head
->m_p_right
= p_new_nd
;
141 p_new_nd
->m_p_parent
= p_nd
;
143 p_new_nd
->m_p_left
= p_new_nd
->m_p_right
= NULL
;
145 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_nd
));
147 update_to_top(p_new_nd
, (node_update
* )this);
149 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(
150 PB_DS_V2F(r_value
)));
152 return (iterator(p_new_nd
));
156 inline typename
PB_DS_CLASS_C_DEC::iterator
158 insert_imp_empty(const_reference r_value
)
160 node_pointer p_new_node
=
161 get_new_node_for_leaf_insert( r_value
, traits_base::m_no_throw_copies_indicator
);
163 m_p_head
->m_p_left
= m_p_head
->m_p_right
=
164 m_p_head
->m_p_parent
= p_new_node
;
166 p_new_node
->m_p_parent
= m_p_head
;
168 p_new_node
->m_p_left
= p_new_node
->m_p_right
= NULL
;
170 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(
171 PB_DS_V2F(r_value
)));
173 update_to_top(m_p_head
->m_p_parent
, (node_update
* )this);
175 return (iterator(p_new_node
));
179 inline typename
PB_DS_CLASS_C_DEC::node_pointer
181 get_new_node_for_leaf_insert(const_reference r_val
, false_type
)
183 node_pointer p_new_nd
= s_node_allocator
.allocate(1);
185 cond_dealtor_t
cond(p_new_nd
);
187 new (const_cast<void* >(
188 static_cast<const void* >(&p_new_nd
->m_value
)))
189 typename
node::value_type(r_val
);
191 cond
.set_no_action();
193 p_new_nd
->m_p_left
= p_new_nd
->m_p_right
= NULL
;
201 inline typename
PB_DS_CLASS_C_DEC::node_pointer
203 get_new_node_for_leaf_insert(const_reference r_val
, true_type
)
205 node_pointer p_new_nd
= s_node_allocator
.allocate(1);
207 new (const_cast<void* >(
208 static_cast<const void* >(&p_new_nd
->m_value
)))
209 typename
node::value_type(r_val
);
211 p_new_nd
->m_p_left
= p_new_nd
->m_p_right
= NULL
;