3 // Copyright (C) 2005, 2006, 2009 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
37 * @file split_fn_imps.hpp
38 * Contains an implementation class for bin_search_tree_.
44 split(const_key_reference r_key
, PB_DS_CLASS_C_DEC
& other
)
46 _GLIBCXX_DEBUG_ONLY(assert_valid(););
47 _GLIBCXX_DEBUG_ONLY(other
.assert_valid(););
48 split_join_branch_bag bag
;
49 leaf_pointer p_split_lf
= split_prep(r_key
, other
, bag
);
50 if (p_split_lf
== NULL
)
52 _GLIBCXX_DEBUG_ASSERT(bag
.empty());
53 _GLIBCXX_DEBUG_ONLY(assert_valid();)
54 _GLIBCXX_DEBUG_ONLY(other
.assert_valid();)
58 _GLIBCXX_DEBUG_ASSERT(!bag
.empty());
60 m_p_head
->m_p_parent
= rec_split(m_p_head
->m_p_parent
,
61 pref_begin(p_split_lf
),
66 m_p_head
->m_p_parent
->m_p_parent
= m_p_head
;
68 other
.m_p_head
->m_p_max
= m_p_head
->m_p_max
;
69 m_p_head
->m_p_max
= rightmost_descendant(m_p_head
->m_p_parent
);
70 other
.m_p_head
->m_p_min
=
71 other
.leftmost_descendant(other
.m_p_head
->m_p_parent
);
73 other
.m_size
= std::distance(other
.PB_DS_CLASS_C_DEC::begin(),
74 other
.PB_DS_CLASS_C_DEC::end());
75 m_size
-= other
.m_size
;
76 _GLIBCXX_DEBUG_ONLY(assert_valid(););
77 _GLIBCXX_DEBUG_ONLY(other
.assert_valid(););
81 typename
PB_DS_CLASS_C_DEC::leaf_pointer
83 split_prep(const_key_reference r_key
, PB_DS_CLASS_C_DEC
& other
, split_join_branch_bag
& r_bag
)
85 _GLIBCXX_DEBUG_ASSERT(r_bag
.empty());
89 _GLIBCXX_DEBUG_ONLY(assert_valid(););
90 _GLIBCXX_DEBUG_ONLY(other
.assert_valid(););
94 if (synth_e_access_traits::cmp_keys(r_key
,
95 PB_DS_V2F(static_cast<const_leaf_pointer
>(m_p_head
->m_p_min
)->value())))
99 _GLIBCXX_DEBUG_ONLY(assert_valid(););
100 _GLIBCXX_DEBUG_ONLY(other
.assert_valid(););
104 if (!synth_e_access_traits::cmp_keys(r_key
,
105 PB_DS_V2F(static_cast<const_leaf_pointer
>(m_p_head
->m_p_max
)->value())))
107 _GLIBCXX_DEBUG_ONLY(assert_valid(););
108 _GLIBCXX_DEBUG_ONLY(other
.assert_valid(););
112 iterator it
= lower_bound(r_key
);
114 if (!synth_e_access_traits::equal_keys(PB_DS_V2F(*it
), r_key
))
117 node_pointer p_nd
= it
.m_p_nd
;
118 _GLIBCXX_DEBUG_ASSERT(p_nd
->m_type
== pat_trie_leaf_node_type
);
119 leaf_pointer p_ret_l
= static_cast<leaf_pointer
>(p_nd
);
120 while (p_nd
->m_type
!= pat_trie_head_node_type
)
123 p_nd
= p_nd
->m_p_parent
;
125 _GLIBCXX_DEBUG_ONLY(debug_base::split(r_key
,(synth_e_access_traits
& )(*this), other
);)
131 typename
PB_DS_CLASS_C_DEC::node_pointer
133 rec_split(node_pointer p_nd
, const_e_iterator b_it
, const_e_iterator e_it
, PB_DS_CLASS_C_DEC
& other
, split_join_branch_bag
& r_bag
)
135 if (p_nd
->m_type
== pat_trie_leaf_node_type
)
137 _GLIBCXX_DEBUG_ASSERT(other
.m_p_head
->m_p_parent
== NULL
);
141 _GLIBCXX_DEBUG_ASSERT(p_nd
->m_type
== pat_trie_internal_node_type
);
142 internal_node_pointer p_internal_nd
= static_cast<internal_node_pointer
>(p_nd
);
144 node_pointer p_child_ret
= rec_split(p_internal_nd
->get_child_node(b_it
, e_it
, this), b_it
, e_it
, other
, r_bag
);
146 _GLIBCXX_DEBUG_ONLY(p_child_ret
->assert_valid(this);)
147 p_internal_nd
->replace_child(p_child_ret
, b_it
, e_it
, this);
148 apply_update(p_internal_nd
, (node_update
* )this);
150 typename
internal_node::iterator child_it
=
151 p_internal_nd
->get_child_it(b_it
, e_it
, this);
153 const size_type lhs_num_children
=
154 std::distance(p_internal_nd
->begin(), child_it
) + 1;
156 _GLIBCXX_DEBUG_ASSERT(lhs_num_children
> 0);
158 size_type rhs_num_children
=
159 std::distance(p_internal_nd
->begin(), p_internal_nd
->end()) -
162 if (rhs_num_children
== 0)
164 apply_update(p_internal_nd
, (node_update
* )this);
165 return (p_internal_nd
);
169 other
.split_insert_branch(p_internal_nd
->get_e_ind(),
170 b_it
, child_it
, rhs_num_children
, r_bag
);
172 child_it
= p_internal_nd
->get_child_it(b_it
, e_it
, this);
174 while (rhs_num_children
!= 0)
176 child_it
= p_internal_nd
->remove_child(child_it
);
180 apply_update(p_internal_nd
, (node_update
* )this);
181 _GLIBCXX_DEBUG_ASSERT(std::distance(p_internal_nd
->begin(),
182 p_internal_nd
->end()) >= 1);
184 if (std::distance(p_internal_nd
->begin(), p_internal_nd
->end()) > 1)
186 p_internal_nd
->update_prefixes(this);
187 _GLIBCXX_DEBUG_ONLY(p_internal_nd
->assert_valid(this);)
188 apply_update(p_internal_nd
, (node_update
* )this);
189 return (p_internal_nd
);
192 node_pointer p_ret
=* p_internal_nd
->begin();
193 p_internal_nd
->~internal_node();
194 s_internal_node_allocator
.deallocate(p_internal_nd
, 1);
195 apply_update(p_ret
, (node_update
* )this);
202 split_insert_branch(size_type e_ind
, const_e_iterator b_it
, typename
internal_node::iterator child_b_it
, size_type num_children
, split_join_branch_bag
& r_bag
)
204 #ifdef _GLIBCXX_DEBUG
205 if (m_p_head
->m_p_parent
!= NULL
)
206 m_p_head
->m_p_parent
->assert_valid(this);
209 const size_type total_num_children
=((m_p_head
->m_p_parent
== NULL
)? 0 : 1) + num_children
;
211 if (total_num_children
== 0)
213 _GLIBCXX_DEBUG_ASSERT(m_p_head
->m_p_parent
== NULL
);
217 if (total_num_children
== 1)
219 if (m_p_head
->m_p_parent
!= NULL
)
221 _GLIBCXX_DEBUG_ONLY(m_p_head
->m_p_parent
->assert_valid(this);)
225 _GLIBCXX_DEBUG_ASSERT(m_p_head
->m_p_parent
== NULL
);
226 m_p_head
->m_p_parent
=* child_b_it
;
227 m_p_head
->m_p_parent
->m_p_parent
= m_p_head
;
228 apply_update(m_p_head
->m_p_parent
, (node_update
* )this);
229 _GLIBCXX_DEBUG_ONLY(m_p_head
->m_p_parent
->assert_valid(this);)
233 _GLIBCXX_DEBUG_ASSERT(total_num_children
> 1);
234 internal_node_pointer p_new_root
= r_bag
.get_branch();
235 new (p_new_root
) internal_node(e_ind
, b_it
);
236 size_type num_inserted
= 0;
237 while (num_inserted
++ < num_children
)
239 _GLIBCXX_DEBUG_ONLY((*child_b_it
)->assert_valid(this);)
240 p_new_root
->add_child(*child_b_it
, pref_begin(*child_b_it
),
241 pref_end(*child_b_it
), this);
245 if (m_p_head
->m_p_parent
!= NULL
)
246 p_new_root
->add_child(m_p_head
->m_p_parent
,
247 pref_begin(m_p_head
->m_p_parent
),
248 pref_end(m_p_head
->m_p_parent
), this);
250 m_p_head
->m_p_parent
= p_new_root
;
251 p_new_root
->m_p_parent
= m_p_head
;
252 apply_update(m_p_head
->m_p_parent
, (node_update
* )this);
253 _GLIBCXX_DEBUG_ONLY(m_p_head
->m_p_parent
->assert_valid(this);)