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_join_fn_imps.hpp
44 * Contains an implementation class for bin_search_tree_.
50 join(PB_DS_CLASS_C_DEC
& other
)
52 _GLIBCXX_DEBUG_ONLY(assert_valid(););
53 _GLIBCXX_DEBUG_ONLY(other
.assert_valid(););
54 split_join_branch_bag bag
;
55 if (!join_prep(other
, bag
))
57 _GLIBCXX_DEBUG_ONLY(assert_valid(););
58 _GLIBCXX_DEBUG_ONLY(other
.assert_valid(););
62 m_p_head
->m_p_parent
= rec_join(m_p_head
->m_p_parent
,
63 other
.m_p_head
->m_p_parent
, 0, bag
);
65 m_p_head
->m_p_parent
->m_p_parent
= m_p_head
;
66 m_size
+= other
.m_size
;
68 _GLIBCXX_DEBUG_ONLY(other
.assert_valid(););
69 m_p_head
->m_p_min
= leftmost_descendant(m_p_head
->m_p_parent
);
70 m_p_head
->m_p_max
= rightmost_descendant(m_p_head
->m_p_parent
);
71 _GLIBCXX_DEBUG_ONLY(assert_valid(););
77 join_prep(PB_DS_CLASS_C_DEC
& other
, split_join_branch_bag
& r_bag
)
79 _GLIBCXX_DEBUG_ONLY(assert_valid();)
80 _GLIBCXX_DEBUG_ONLY(other
.assert_valid();)
81 if (other
.m_size
== 0)
90 const bool greater
= synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer
>(
91 m_p_head
->m_p_max
)->value()),PB_DS_V2F(static_cast<const_leaf_pointer
>(
92 other
.m_p_head
->m_p_min
)->value()));
94 const bool lesser
= synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer
>(
95 other
.m_p_head
->m_p_max
)->value()),PB_DS_V2F(static_cast<const_leaf_pointer
>(m_p_head
->m_p_min
)->value()));
97 if (!greater
&& !lesser
)
100 rec_join_prep(m_p_head
->m_p_parent
, other
.m_p_head
->m_p_parent
, r_bag
);
101 _GLIBCXX_DEBUG_ONLY(debug_base::join(other
);)
108 rec_join_prep(const_node_pointer p_l
, const_node_pointer p_r
, split_join_branch_bag
& r_bag
)
110 if (p_l
->m_type
== pat_trie_leaf_node_type
)
112 if (p_r
->m_type
== pat_trie_leaf_node_type
)
114 rec_join_prep(static_cast<const_leaf_pointer
>(p_l
),
115 static_cast<const_leaf_pointer
>(p_r
), r_bag
);
119 _GLIBCXX_DEBUG_ASSERT(p_r
->m_type
== pat_trie_internal_node_type
);
120 rec_join_prep(static_cast<const_leaf_pointer
>(p_l
),
121 static_cast<const_internal_node_pointer
>(p_r
), r_bag
);
125 _GLIBCXX_DEBUG_ASSERT(p_l
->m_type
== pat_trie_internal_node_type
);
126 if (p_r
->m_type
== pat_trie_leaf_node_type
)
128 rec_join_prep(static_cast<const_internal_node_pointer
>(p_l
),
129 static_cast<const_leaf_pointer
>(p_r
), r_bag
);
133 _GLIBCXX_DEBUG_ASSERT(p_r
->m_type
== pat_trie_internal_node_type
);
135 rec_join_prep(static_cast<const_internal_node_pointer
>(p_l
),
136 static_cast<const_internal_node_pointer
>(p_r
), r_bag
);
142 rec_join_prep(const_leaf_pointer
/*p_l*/, const_leaf_pointer
/*p_r*/,
143 split_join_branch_bag
& r_bag
)
144 { r_bag
.add_branch(); }
149 rec_join_prep(const_leaf_pointer
/*p_l*/, const_internal_node_pointer
/*p_r*/,
150 split_join_branch_bag
& r_bag
)
151 { r_bag
.add_branch(); }
156 rec_join_prep(const_internal_node_pointer
/*p_l*/, const_leaf_pointer
/*p_r*/,
157 split_join_branch_bag
& r_bag
)
158 { r_bag
.add_branch(); }
163 rec_join_prep(const_internal_node_pointer p_l
, const_internal_node_pointer p_r
,
164 split_join_branch_bag
& r_bag
)
166 if (p_l
->get_e_ind() == p_r
->get_e_ind() &&
167 synth_e_access_traits::equal_prefixes(p_l
->pref_b_it(), p_l
->pref_e_it(),
168 p_r
->pref_b_it(), p_r
->pref_e_it()))
170 for (typename
internal_node::const_iterator it
= p_r
->begin();
171 it
!= p_r
->end(); ++ it
)
173 const_node_pointer p_l_join_child
= p_l
->get_join_child(*it
, this);
174 if (p_l_join_child
!= NULL
)
175 rec_join_prep(p_l_join_child
, * it
, r_bag
);
180 if (p_r
->get_e_ind() < p_l
->get_e_ind() &&
181 p_r
->should_be_mine(p_l
->pref_b_it(), p_l
->pref_e_it(), 0, this))
183 const_node_pointer p_r_join_child
= p_r
->get_join_child(p_l
, this);
184 if (p_r_join_child
!= NULL
)
185 rec_join_prep(p_r_join_child
, p_l
, r_bag
);
189 if (p_r
->get_e_ind() < p_l
->get_e_ind() &&
190 p_r
->should_be_mine(p_l
->pref_b_it(), p_l
->pref_e_it(), 0, this))
192 const_node_pointer p_r_join_child
= p_r
->get_join_child(p_l
, this);
193 if (p_r_join_child
!= NULL
)
194 rec_join_prep(p_r_join_child
, p_l
, r_bag
);
201 typename
PB_DS_CLASS_C_DEC::node_pointer
203 rec_join(node_pointer p_l
, node_pointer p_r
, size_type checked_ind
, split_join_branch_bag
& r_bag
)
205 _GLIBCXX_DEBUG_ASSERT(p_r
!= NULL
);
208 apply_update(p_r
, (node_update
* )this);
212 if (p_l
->m_type
== pat_trie_leaf_node_type
)
214 if (p_r
->m_type
== pat_trie_leaf_node_type
)
216 node_pointer p_ret
= rec_join(static_cast<leaf_pointer
>(p_l
),
217 static_cast<leaf_pointer
>(p_r
), r_bag
);
218 apply_update(p_ret
, (node_update
* )this);
222 _GLIBCXX_DEBUG_ASSERT(p_r
->m_type
== pat_trie_internal_node_type
);
223 node_pointer p_ret
= rec_join(static_cast<leaf_pointer
>(p_l
),
224 static_cast<internal_node_pointer
>(p_r
),
226 apply_update(p_ret
, (node_update
* )this);
230 _GLIBCXX_DEBUG_ASSERT(p_l
->m_type
== pat_trie_internal_node_type
);
231 if (p_r
->m_type
== pat_trie_leaf_node_type
)
233 node_pointer p_ret
= rec_join(static_cast<internal_node_pointer
>(p_l
),
234 static_cast<leaf_pointer
>(p_r
),
236 apply_update(p_ret
, (node_update
* )this);
240 _GLIBCXX_DEBUG_ASSERT(p_r
->m_type
== pat_trie_internal_node_type
);
241 node_pointer p_ret
= rec_join(static_cast<internal_node_pointer
>(p_l
),
242 static_cast<internal_node_pointer
>(p_r
),
245 apply_update(p_ret
, (node_update
* )this);
250 typename
PB_DS_CLASS_C_DEC::node_pointer
252 rec_join(leaf_pointer p_l
, leaf_pointer p_r
, split_join_branch_bag
& r_bag
)
254 _GLIBCXX_DEBUG_ASSERT(p_r
!= NULL
);
257 node_pointer p_ret
= insert_branch(p_l
, p_r
, r_bag
);
258 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret
) == 2);
263 typename
PB_DS_CLASS_C_DEC::node_pointer
265 rec_join(leaf_pointer p_l
, internal_node_pointer p_r
, size_type checked_ind
,
266 split_join_branch_bag
& r_bag
)
268 #ifdef _GLIBCXX_DEBUG
269 const size_type lhs_leafs
= recursive_count_leafs(p_l
);
270 const size_type rhs_leafs
= recursive_count_leafs(p_r
);
273 _GLIBCXX_DEBUG_ASSERT(p_r
!= NULL
);
274 node_pointer p_ret
= rec_join(p_r
, p_l
, checked_ind
, r_bag
);
275 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret
) == lhs_leafs
+ rhs_leafs
);
280 typename
PB_DS_CLASS_C_DEC::node_pointer
282 rec_join(internal_node_pointer p_l
, leaf_pointer p_r
, size_type checked_ind
, split_join_branch_bag
& r_bag
)
284 _GLIBCXX_DEBUG_ASSERT(p_l
!= NULL
);
285 _GLIBCXX_DEBUG_ASSERT(p_r
!= NULL
);
287 #ifdef _GLIBCXX_DEBUG
288 const size_type lhs_leafs
= recursive_count_leafs(p_l
);
289 const size_type rhs_leafs
= recursive_count_leafs(p_r
);
292 if (!p_l
->should_be_mine(pref_begin(p_r
), pref_end(p_r
), checked_ind
, this))
294 node_pointer p_ret
= insert_branch(p_l
, p_r
, r_bag
);
295 _GLIBCXX_DEBUG_ONLY(p_ret
->assert_valid(this);)
296 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret
) ==
297 lhs_leafs
+ rhs_leafs
);
301 node_pointer p_pot_child
= p_l
->add_child(p_r
, pref_begin(p_r
),
302 pref_end(p_r
), this);
303 if (p_pot_child
!= p_r
)
305 node_pointer p_new_child
= rec_join(p_pot_child
, p_r
, p_l
->get_e_ind(),
308 p_l
->replace_child(p_new_child
, pref_begin(p_new_child
),
309 pref_end(p_new_child
), this);
312 _GLIBCXX_DEBUG_ONLY(p_l
->assert_valid(this));
313 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l
) == lhs_leafs
+ rhs_leafs
);
318 typename
PB_DS_CLASS_C_DEC::node_pointer
320 rec_join(internal_node_pointer p_l
, internal_node_pointer p_r
, split_join_branch_bag
& r_bag
)
322 _GLIBCXX_DEBUG_ASSERT(p_l
!= NULL
);
323 _GLIBCXX_DEBUG_ASSERT(p_r
!= NULL
);
325 #ifdef _GLIBCXX_DEBUG
326 const size_type lhs_leafs
= recursive_count_leafs(p_l
);
327 const size_type rhs_leafs
= recursive_count_leafs(p_r
);
330 if (p_l
->get_e_ind() == p_r
->get_e_ind() &&
331 synth_e_access_traits::equal_prefixes(p_l
->pref_b_it(), p_l
->pref_e_it(),
332 p_r
->pref_b_it(), p_r
->pref_e_it()))
334 for (typename
internal_node::iterator it
= p_r
->begin();
335 it
!= p_r
->end(); ++ it
)
337 node_pointer p_new_child
= rec_join(p_l
->get_join_child(*it
, this),
339 p_l
->replace_child(p_new_child
, pref_begin(p_new_child
),
340 pref_end(p_new_child
), this);
343 p_r
->~internal_node();
344 s_internal_node_allocator
.deallocate(p_r
, 1);
345 _GLIBCXX_DEBUG_ONLY(p_l
->assert_valid(this);)
346 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l
) == lhs_leafs
+ rhs_leafs
);
350 if (p_l
->get_e_ind() < p_r
->get_e_ind() &&
351 p_l
->should_be_mine(p_r
->pref_b_it(), p_r
->pref_e_it(), 0, this))
353 node_pointer p_new_child
= rec_join(p_l
->get_join_child(p_r
, this),
355 p_l
->replace_child(p_new_child
, pref_begin(p_new_child
),
356 pref_end(p_new_child
), this);
357 _GLIBCXX_DEBUG_ONLY(p_l
->assert_valid(this);)
361 if (p_r
->get_e_ind() < p_l
->get_e_ind() &&
362 p_r
->should_be_mine(p_l
->pref_b_it(), p_l
->pref_e_it(), 0, this))
364 node_pointer p_new_child
= rec_join(p_r
->get_join_child(p_l
, this), p_l
,
367 p_r
->replace_child(p_new_child
, pref_begin(p_new_child
),
368 pref_end(p_new_child
), this);
370 _GLIBCXX_DEBUG_ONLY(p_r
->assert_valid(this);)
371 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_r
) == lhs_leafs
+ rhs_leafs
);
375 node_pointer p_ret
= insert_branch(p_l
, p_r
, r_bag
);
376 _GLIBCXX_DEBUG_ONLY(p_ret
->assert_valid(this);)
377 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret
) == lhs_leafs
+ rhs_leafs
);
382 inline std::pair
<typename
PB_DS_CLASS_C_DEC::iterator
, bool>
384 insert(const_reference r_val
)
386 node_pointer p_lf
= find_imp(PB_DS_V2F(r_val
));
387 if (p_lf
!= NULL
&& p_lf
->m_type
== pat_trie_leaf_node_type
&&
388 synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer
>(p_lf
)->value()), PB_DS_V2F(r_val
)))
390 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(PB_DS_V2F(r_val
)));
391 _GLIBCXX_DEBUG_ONLY(assert_valid();)
392 return std::make_pair(iterator(p_lf
), false);
395 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(PB_DS_V2F(r_val
)));
397 leaf_pointer p_new_lf
= s_leaf_allocator
.allocate(1);
398 cond_dealtor
cond(p_new_lf
);
400 new (p_new_lf
) leaf(r_val
);
401 apply_update(p_new_lf
, (node_update
* )this);
402 cond
.set_call_destructor();
403 split_join_branch_bag bag
;
405 m_p_head
->m_p_parent
= rec_join(m_p_head
->m_p_parent
, p_new_lf
, 0, bag
);
406 m_p_head
->m_p_parent
->m_p_parent
= m_p_head
;
407 cond
.set_no_action_dtor();
409 update_min_max_for_inserted_leaf(p_new_lf
);
410 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val
));)
411 _GLIBCXX_DEBUG_ONLY(assert_valid();)
412 return std::make_pair(point_iterator(p_new_lf
), true);
416 typename
PB_DS_CLASS_C_DEC::size_type
418 keys_diff_ind(typename
e_access_traits::const_iterator b_l
, typename
e_access_traits::const_iterator e_l
, typename
e_access_traits::const_iterator b_r
, typename
e_access_traits::const_iterator e_r
)
420 size_type diff_pos
= 0;
425 if (e_access_traits::e_pos(*b_l
) != e_access_traits::e_pos(*b_r
))
431 _GLIBCXX_DEBUG_ASSERT(b_r
!= e_r
);
436 typename
PB_DS_CLASS_C_DEC::internal_node_pointer
438 insert_branch(node_pointer p_l
, node_pointer p_r
, split_join_branch_bag
& r_bag
)
440 typename
synth_e_access_traits::const_iterator left_b_it
= pref_begin(p_l
);
441 typename
synth_e_access_traits::const_iterator left_e_it
= pref_end(p_l
);
442 typename
synth_e_access_traits::const_iterator right_b_it
= pref_begin(p_r
);
443 typename
synth_e_access_traits::const_iterator right_e_it
= pref_end(p_r
);
445 const size_type diff_ind
= keys_diff_ind(left_b_it
, left_e_it
,
446 right_b_it
, right_e_it
);
448 internal_node_pointer p_new_nd
= r_bag
.get_branch();
449 new (p_new_nd
) internal_node(diff_ind
, left_b_it
);
450 p_new_nd
->add_child(p_l
, left_b_it
, left_e_it
, this);
451 p_new_nd
->add_child(p_r
, right_b_it
, right_e_it
, this);
452 p_l
->m_p_parent
= p_new_nd
;
453 p_r
->m_p_parent
= p_new_nd
;
454 _GLIBCXX_DEBUG_ONLY(p_new_nd
->assert_valid(this);)
461 update_min_max_for_inserted_leaf(leaf_pointer p_new_lf
)
463 if (m_p_head
->m_p_min
== m_p_head
||
464 synth_e_access_traits::cmp_keys(PB_DS_V2F(p_new_lf
->value()),
465 PB_DS_V2F(static_cast<const_leaf_pointer
>(m_p_head
->m_p_min
)->value())))
466 m_p_head
->m_p_min
= p_new_lf
;
468 if (m_p_head
->m_p_max
== m_p_head
||
469 synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer
>(m_p_head
->m_p_max
)->value()), PB_DS_V2F(p_new_lf
->value())))
470 m_p_head
->m_p_max
= p_new_lf
;