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 insert_join_fn_imps.hpp
38 * Contains an implementation class for bin_search_tree_.
44 join(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 if (!join_prep(other, bag))
51 _GLIBCXX_DEBUG_ONLY(assert_valid(););
52 _GLIBCXX_DEBUG_ONLY(other.assert_valid(););
56 m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent,
57 other.m_p_head->m_p_parent, 0, bag);
59 m_p_head->m_p_parent->m_p_parent = m_p_head;
60 m_size += other.m_size;
62 _GLIBCXX_DEBUG_ONLY(other.assert_valid(););
63 m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent);
64 m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent);
65 _GLIBCXX_DEBUG_ONLY(assert_valid(););
71 join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag)
73 _GLIBCXX_DEBUG_ONLY(assert_valid();)
74 _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
75 if (other.m_size == 0)
84 const bool greater = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(
85 m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>(
86 other.m_p_head->m_p_min)->value()));
88 const bool lesser = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(
89 other.m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value()));
91 if (!greater && !lesser)
94 rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag);
95 _GLIBCXX_DEBUG_ONLY(debug_base::join(other);)
102 rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag)
104 if (p_l->m_type == pat_trie_leaf_node_type)
106 if (p_r->m_type == pat_trie_leaf_node_type)
108 rec_join_prep(static_cast<const_leaf_pointer>(p_l),
109 static_cast<const_leaf_pointer>(p_r), r_bag);
113 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
114 rec_join_prep(static_cast<const_leaf_pointer>(p_l),
115 static_cast<const_internal_node_pointer>(p_r), r_bag);
119 _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type);
120 if (p_r->m_type == pat_trie_leaf_node_type)
122 rec_join_prep(static_cast<const_internal_node_pointer>(p_l),
123 static_cast<const_leaf_pointer>(p_r), r_bag);
127 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
129 rec_join_prep(static_cast<const_internal_node_pointer>(p_l),
130 static_cast<const_internal_node_pointer>(p_r), r_bag);
136 rec_join_prep(const_leaf_pointer /*p_l*/, const_leaf_pointer /*p_r*/,
137 split_join_branch_bag& r_bag)
138 { r_bag.add_branch(); }
143 rec_join_prep(const_leaf_pointer /*p_l*/, const_internal_node_pointer /*p_r*/,
144 split_join_branch_bag& r_bag)
145 { r_bag.add_branch(); }
150 rec_join_prep(const_internal_node_pointer /*p_l*/, const_leaf_pointer /*p_r*/,
151 split_join_branch_bag& r_bag)
152 { r_bag.add_branch(); }
157 rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r,
158 split_join_branch_bag& r_bag)
160 if (p_l->get_e_ind() == p_r->get_e_ind() &&
161 synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(),
162 p_r->pref_b_it(), p_r->pref_e_it()))
164 for (typename internal_node::const_iterator it = p_r->begin();
165 it != p_r->end(); ++ it)
167 const_node_pointer p_l_join_child = p_l->get_join_child(*it, this);
168 if (p_l_join_child != NULL)
169 rec_join_prep(p_l_join_child, * it, r_bag);
174 if (p_r->get_e_ind() < p_l->get_e_ind() &&
175 p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
177 const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this);
178 if (p_r_join_child != NULL)
179 rec_join_prep(p_r_join_child, p_l, r_bag);
183 if (p_r->get_e_ind() < p_l->get_e_ind() &&
184 p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
186 const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this);
187 if (p_r_join_child != NULL)
188 rec_join_prep(p_r_join_child, p_l, r_bag);
195 typename PB_DS_CLASS_C_DEC::node_pointer
197 rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag)
199 _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
202 apply_update(p_r, (node_update* )this);
206 if (p_l->m_type == pat_trie_leaf_node_type)
208 if (p_r->m_type == pat_trie_leaf_node_type)
210 node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l),
211 static_cast<leaf_pointer>(p_r), r_bag);
212 apply_update(p_ret, (node_update* )this);
216 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
217 node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l),
218 static_cast<internal_node_pointer>(p_r),
220 apply_update(p_ret, (node_update* )this);
224 _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type);
225 if (p_r->m_type == pat_trie_leaf_node_type)
227 node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l),
228 static_cast<leaf_pointer>(p_r),
230 apply_update(p_ret, (node_update* )this);
234 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
235 node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l),
236 static_cast<internal_node_pointer>(p_r),
239 apply_update(p_ret, (node_update* )this);
244 typename PB_DS_CLASS_C_DEC::node_pointer
246 rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag)
248 _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
251 node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
252 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == 2);
257 typename PB_DS_CLASS_C_DEC::node_pointer
259 rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind,
260 split_join_branch_bag& r_bag)
262 #ifdef _GLIBCXX_DEBUG
263 const size_type lhs_leafs = recursive_count_leafs(p_l);
264 const size_type rhs_leafs = recursive_count_leafs(p_r);
267 _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
268 node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag);
269 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs);
274 typename PB_DS_CLASS_C_DEC::node_pointer
276 rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag)
278 _GLIBCXX_DEBUG_ASSERT(p_l != NULL);
279 _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
281 #ifdef _GLIBCXX_DEBUG
282 const size_type lhs_leafs = recursive_count_leafs(p_l);
283 const size_type rhs_leafs = recursive_count_leafs(p_r);
286 if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this))
288 node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
289 _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);)
290 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) ==
291 lhs_leafs + rhs_leafs);
295 node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r),
296 pref_end(p_r), this);
297 if (p_pot_child != p_r)
299 node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(),
302 p_l->replace_child(p_new_child, pref_begin(p_new_child),
303 pref_end(p_new_child), this);
306 _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this));
307 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs);
312 typename PB_DS_CLASS_C_DEC::node_pointer
314 rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag)
316 _GLIBCXX_DEBUG_ASSERT(p_l != NULL);
317 _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
319 #ifdef _GLIBCXX_DEBUG
320 const size_type lhs_leafs = recursive_count_leafs(p_l);
321 const size_type rhs_leafs = recursive_count_leafs(p_r);
324 if (p_l->get_e_ind() == p_r->get_e_ind() &&
325 synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(),
326 p_r->pref_b_it(), p_r->pref_e_it()))
328 for (typename internal_node::iterator it = p_r->begin();
329 it != p_r->end(); ++ it)
331 node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this),
333 p_l->replace_child(p_new_child, pref_begin(p_new_child),
334 pref_end(p_new_child), this);
337 p_r->~internal_node();
338 s_internal_node_allocator.deallocate(p_r, 1);
339 _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);)
340 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs);
344 if (p_l->get_e_ind() < p_r->get_e_ind() &&
345 p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this))
347 node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this),
349 p_l->replace_child(p_new_child, pref_begin(p_new_child),
350 pref_end(p_new_child), this);
351 _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);)
355 if (p_r->get_e_ind() < p_l->get_e_ind() &&
356 p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
358 node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l,
361 p_r->replace_child(p_new_child, pref_begin(p_new_child),
362 pref_end(p_new_child), this);
364 _GLIBCXX_DEBUG_ONLY(p_r->assert_valid(this);)
365 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_r) == lhs_leafs + rhs_leafs);
369 node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
370 _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);)
371 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs);
376 inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool>
378 insert(const_reference r_val)
380 node_pointer p_lf = find_imp(PB_DS_V2F(r_val));
381 if (p_lf != NULL && p_lf->m_type == pat_trie_leaf_node_type &&
382 synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val)))
384 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(PB_DS_V2F(r_val)));
385 _GLIBCXX_DEBUG_ONLY(assert_valid();)
386 return std::make_pair(iterator(p_lf), false);
389 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(PB_DS_V2F(r_val)));
391 leaf_pointer p_new_lf = s_leaf_allocator.allocate(1);
392 cond_dealtor cond(p_new_lf);
394 new (p_new_lf) leaf(r_val);
395 apply_update(p_new_lf, (node_update* )this);
396 cond.set_call_destructor();
397 split_join_branch_bag bag;
399 m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag);
400 m_p_head->m_p_parent->m_p_parent = m_p_head;
401 cond.set_no_action_dtor();
403 update_min_max_for_inserted_leaf(p_new_lf);
404 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));)
405 _GLIBCXX_DEBUG_ONLY(assert_valid();)
406 return std::make_pair(point_iterator(p_new_lf), true);
410 typename PB_DS_CLASS_C_DEC::size_type
412 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)
414 size_type diff_pos = 0;
419 if (e_access_traits::e_pos(*b_l) != e_access_traits::e_pos(*b_r))
425 _GLIBCXX_DEBUG_ASSERT(b_r != e_r);
430 typename PB_DS_CLASS_C_DEC::internal_node_pointer
432 insert_branch(node_pointer p_l, node_pointer p_r, split_join_branch_bag& r_bag)
434 typename synth_e_access_traits::const_iterator left_b_it = pref_begin(p_l);
435 typename synth_e_access_traits::const_iterator left_e_it = pref_end(p_l);
436 typename synth_e_access_traits::const_iterator right_b_it = pref_begin(p_r);
437 typename synth_e_access_traits::const_iterator right_e_it = pref_end(p_r);
439 const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it,
440 right_b_it, right_e_it);
442 internal_node_pointer p_new_nd = r_bag.get_branch();
443 new (p_new_nd) internal_node(diff_ind, left_b_it);
444 p_new_nd->add_child(p_l, left_b_it, left_e_it, this);
445 p_new_nd->add_child(p_r, right_b_it, right_e_it, this);
446 p_l->m_p_parent = p_new_nd;
447 p_r->m_p_parent = p_new_nd;
448 _GLIBCXX_DEBUG_ONLY(p_new_nd->assert_valid(this);)
455 update_min_max_for_inserted_leaf(leaf_pointer p_new_lf)
457 if (m_p_head->m_p_min == m_p_head ||
458 synth_e_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()),
459 PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value())))
460 m_p_head->m_p_min = p_new_lf;
462 if (m_p_head->m_p_max == m_p_head ||
463 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())))
464 m_p_head->m_p_max = p_new_lf;