1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file insert_join_fn_imps.hpp 44169691Skan * Contains an implementation class for bin_search_tree_. 45169691Skan */ 46169691Skan 47169691SkanPB_DS_CLASS_T_DEC 48169691Skanvoid 49169691SkanPB_DS_CLASS_C_DEC:: 50169691Skanjoin(PB_DS_CLASS_C_DEC& other) 51169691Skan{ 52169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();); 53169691Skan _GLIBCXX_DEBUG_ONLY(other.assert_valid();); 54169691Skan split_join_branch_bag bag; 55169691Skan if (!join_prep(other, bag)) 56169691Skan { 57169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();); 58169691Skan _GLIBCXX_DEBUG_ONLY(other.assert_valid();); 59169691Skan return; 60169691Skan } 61169691Skan 62169691Skan m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, 63169691Skan other.m_p_head->m_p_parent, 0, bag); 64169691Skan 65169691Skan m_p_head->m_p_parent->m_p_parent = m_p_head; 66169691Skan m_size += other.m_size; 67169691Skan other.initialize(); 68169691Skan _GLIBCXX_DEBUG_ONLY(other.assert_valid();); 69169691Skan m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent); 70169691Skan m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); 71169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();); 72169691Skan} 73169691Skan 74169691SkanPB_DS_CLASS_T_DEC 75169691Skanbool 76169691SkanPB_DS_CLASS_C_DEC:: 77169691Skanjoin_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag) 78169691Skan{ 79169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 80169691Skan _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 81169691Skan if (other.m_size == 0) 82169691Skan return false; 83169691Skan 84169691Skan if (m_size == 0) 85169691Skan { 86169691Skan value_swap(other); 87169691Skan return false; 88169691Skan } 89169691Skan 90169691Skan const bool greater = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>( 91169691Skan m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>( 92169691Skan other.m_p_head->m_p_min)->value())); 93169691Skan 94169691Skan const bool lesser = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>( 95169691Skan other.m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value())); 96169691Skan 97169691Skan if (!greater && !lesser) 98169691Skan __throw_join_error(); 99169691Skan 100169691Skan rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag); 101169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::join(other);) 102169691Skan return true; 103169691Skan} 104169691Skan 105169691SkanPB_DS_CLASS_T_DEC 106169691Skanvoid 107169691SkanPB_DS_CLASS_C_DEC:: 108169691Skanrec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag) 109169691Skan{ 110169691Skan if (p_l->m_type == pat_trie_leaf_node_type) 111169691Skan { 112169691Skan if (p_r->m_type == pat_trie_leaf_node_type) 113169691Skan { 114169691Skan rec_join_prep(static_cast<const_leaf_pointer>(p_l), 115169691Skan static_cast<const_leaf_pointer>(p_r), r_bag); 116169691Skan return; 117169691Skan } 118169691Skan 119169691Skan _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); 120169691Skan rec_join_prep(static_cast<const_leaf_pointer>(p_l), 121169691Skan static_cast<const_internal_node_pointer>(p_r), r_bag); 122169691Skan return; 123169691Skan } 124169691Skan 125169691Skan _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); 126169691Skan if (p_r->m_type == pat_trie_leaf_node_type) 127169691Skan { 128169691Skan rec_join_prep(static_cast<const_internal_node_pointer>(p_l), 129169691Skan static_cast<const_leaf_pointer>(p_r), r_bag); 130169691Skan return; 131169691Skan } 132169691Skan 133169691Skan _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); 134169691Skan 135169691Skan rec_join_prep(static_cast<const_internal_node_pointer>(p_l), 136169691Skan static_cast<const_internal_node_pointer>(p_r), r_bag); 137169691Skan} 138169691Skan 139169691SkanPB_DS_CLASS_T_DEC 140169691Skanvoid 141169691SkanPB_DS_CLASS_C_DEC:: 142169691Skanrec_join_prep(const_leaf_pointer /*p_l*/, const_leaf_pointer /*p_r*/, 143169691Skan split_join_branch_bag& r_bag) 144169691Skan{ r_bag.add_branch(); } 145169691Skan 146169691SkanPB_DS_CLASS_T_DEC 147169691Skanvoid 148169691SkanPB_DS_CLASS_C_DEC:: 149169691Skanrec_join_prep(const_leaf_pointer /*p_l*/, const_internal_node_pointer /*p_r*/, 150169691Skan split_join_branch_bag& r_bag) 151169691Skan{ r_bag.add_branch(); } 152169691Skan 153169691SkanPB_DS_CLASS_T_DEC 154169691Skanvoid 155169691SkanPB_DS_CLASS_C_DEC:: 156169691Skanrec_join_prep(const_internal_node_pointer /*p_l*/, const_leaf_pointer /*p_r*/, 157169691Skan split_join_branch_bag& r_bag) 158169691Skan{ r_bag.add_branch(); } 159169691Skan 160169691SkanPB_DS_CLASS_T_DEC 161169691Skanvoid 162169691SkanPB_DS_CLASS_C_DEC:: 163169691Skanrec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r, 164169691Skan split_join_branch_bag& r_bag) 165169691Skan{ 166169691Skan if (p_l->get_e_ind() == p_r->get_e_ind() && 167169691Skan synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), 168169691Skan p_r->pref_b_it(), p_r->pref_e_it())) 169169691Skan { 170169691Skan for (typename internal_node::const_iterator it = p_r->begin(); 171169691Skan it != p_r->end(); ++ it) 172169691Skan { 173169691Skan const_node_pointer p_l_join_child = p_l->get_join_child(*it, this); 174169691Skan if (p_l_join_child != NULL) 175169691Skan rec_join_prep(p_l_join_child, * it, r_bag); 176169691Skan } 177169691Skan return; 178169691Skan } 179169691Skan 180169691Skan if (p_r->get_e_ind() < p_l->get_e_ind() && 181169691Skan p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) 182169691Skan { 183169691Skan const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this); 184169691Skan if (p_r_join_child != NULL) 185169691Skan rec_join_prep(p_r_join_child, p_l, r_bag); 186169691Skan return; 187169691Skan } 188169691Skan 189169691Skan if (p_r->get_e_ind() < p_l->get_e_ind() && 190169691Skan p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) 191169691Skan { 192169691Skan const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this); 193169691Skan if (p_r_join_child != NULL) 194169691Skan rec_join_prep(p_r_join_child, p_l, r_bag); 195169691Skan return; 196169691Skan } 197169691Skan r_bag.add_branch(); 198169691Skan} 199169691Skan 200169691SkanPB_DS_CLASS_T_DEC 201169691Skantypename PB_DS_CLASS_C_DEC::node_pointer 202169691SkanPB_DS_CLASS_C_DEC:: 203169691Skanrec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) 204169691Skan{ 205169691Skan _GLIBCXX_DEBUG_ASSERT(p_r != NULL); 206169691Skan if (p_l == NULL) 207169691Skan { 208169691Skan apply_update(p_r, (node_update* )this); 209169691Skan return (p_r); 210169691Skan } 211169691Skan 212169691Skan if (p_l->m_type == pat_trie_leaf_node_type) 213169691Skan { 214169691Skan if (p_r->m_type == pat_trie_leaf_node_type) 215169691Skan { 216169691Skan node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), 217169691Skan static_cast<leaf_pointer>(p_r), r_bag); 218169691Skan apply_update(p_ret, (node_update* )this); 219169691Skan return p_ret; 220169691Skan } 221169691Skan 222169691Skan _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); 223169691Skan node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), 224169691Skan static_cast<internal_node_pointer>(p_r), 225169691Skan checked_ind, r_bag); 226169691Skan apply_update(p_ret, (node_update* )this); 227169691Skan return p_ret; 228169691Skan } 229169691Skan 230169691Skan _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); 231169691Skan if (p_r->m_type == pat_trie_leaf_node_type) 232169691Skan { 233169691Skan node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l), 234169691Skan static_cast<leaf_pointer>(p_r), 235169691Skan checked_ind, r_bag); 236169691Skan apply_update(p_ret, (node_update* )this); 237169691Skan return p_ret; 238169691Skan } 239169691Skan 240169691Skan _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); 241169691Skan node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l), 242169691Skan static_cast<internal_node_pointer>(p_r), 243169691Skan r_bag); 244169691Skan 245169691Skan apply_update(p_ret, (node_update* )this); 246169691Skan return p_ret; 247169691Skan} 248169691Skan 249169691SkanPB_DS_CLASS_T_DEC 250169691Skantypename PB_DS_CLASS_C_DEC::node_pointer 251169691SkanPB_DS_CLASS_C_DEC:: 252169691Skanrec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag) 253169691Skan{ 254169691Skan _GLIBCXX_DEBUG_ASSERT(p_r != NULL); 255169691Skan if (p_l == NULL) 256169691Skan return (p_r); 257169691Skan node_pointer p_ret = insert_branch(p_l, p_r, r_bag); 258169691Skan _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == 2); 259169691Skan return p_ret; 260169691Skan} 261169691Skan 262169691SkanPB_DS_CLASS_T_DEC 263169691Skantypename PB_DS_CLASS_C_DEC::node_pointer 264169691SkanPB_DS_CLASS_C_DEC:: 265169691Skanrec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind, 266169691Skan split_join_branch_bag& r_bag) 267169691Skan{ 268169691Skan#ifdef _GLIBCXX_DEBUG 269169691Skan const size_type lhs_leafs = recursive_count_leafs(p_l); 270169691Skan const size_type rhs_leafs = recursive_count_leafs(p_r); 271169691Skan#endif 272169691Skan 273169691Skan _GLIBCXX_DEBUG_ASSERT(p_r != NULL); 274169691Skan node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag); 275169691Skan _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs); 276169691Skan return p_ret; 277169691Skan} 278169691Skan 279169691SkanPB_DS_CLASS_T_DEC 280169691Skantypename PB_DS_CLASS_C_DEC::node_pointer 281169691SkanPB_DS_CLASS_C_DEC:: 282169691Skanrec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) 283169691Skan{ 284169691Skan _GLIBCXX_DEBUG_ASSERT(p_l != NULL); 285169691Skan _GLIBCXX_DEBUG_ASSERT(p_r != NULL); 286169691Skan 287169691Skan#ifdef _GLIBCXX_DEBUG 288169691Skan const size_type lhs_leafs = recursive_count_leafs(p_l); 289169691Skan const size_type rhs_leafs = recursive_count_leafs(p_r); 290169691Skan#endif 291169691Skan 292169691Skan if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this)) 293169691Skan { 294169691Skan node_pointer p_ret = insert_branch(p_l, p_r, r_bag); 295169691Skan _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);) 296169691Skan _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == 297169691Skan lhs_leafs + rhs_leafs); 298169691Skan return p_ret; 299169691Skan } 300169691Skan 301169691Skan node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r), 302169691Skan pref_end(p_r), this); 303169691Skan if (p_pot_child != p_r) 304169691Skan { 305169691Skan node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(), 306169691Skan r_bag); 307169691Skan 308169691Skan p_l->replace_child(p_new_child, pref_begin(p_new_child), 309169691Skan pref_end(p_new_child), this); 310169691Skan } 311169691Skan 312169691Skan _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this)); 313169691Skan _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs); 314169691Skan return p_l; 315169691Skan} 316169691Skan 317169691SkanPB_DS_CLASS_T_DEC 318169691Skantypename PB_DS_CLASS_C_DEC::node_pointer 319169691SkanPB_DS_CLASS_C_DEC:: 320169691Skanrec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag) 321169691Skan{ 322169691Skan _GLIBCXX_DEBUG_ASSERT(p_l != NULL); 323169691Skan _GLIBCXX_DEBUG_ASSERT(p_r != NULL); 324169691Skan 325169691Skan#ifdef _GLIBCXX_DEBUG 326169691Skan const size_type lhs_leafs = recursive_count_leafs(p_l); 327169691Skan const size_type rhs_leafs = recursive_count_leafs(p_r); 328169691Skan#endif 329169691Skan 330169691Skan if (p_l->get_e_ind() == p_r->get_e_ind() && 331169691Skan synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), 332169691Skan p_r->pref_b_it(), p_r->pref_e_it())) 333169691Skan { 334169691Skan for (typename internal_node::iterator it = p_r->begin(); 335169691Skan it != p_r->end(); ++ it) 336169691Skan { 337169691Skan node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this), 338169691Skan * it, 0, r_bag); 339169691Skan p_l->replace_child(p_new_child, pref_begin(p_new_child), 340169691Skan pref_end(p_new_child), this); 341169691Skan } 342169691Skan 343169691Skan p_r->~internal_node(); 344169691Skan s_internal_node_allocator.deallocate(p_r, 1); 345169691Skan _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);) 346169691Skan _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs); 347169691Skan return p_l; 348169691Skan } 349169691Skan 350169691Skan if (p_l->get_e_ind() < p_r->get_e_ind() && 351169691Skan p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this)) 352169691Skan { 353169691Skan node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this), 354169691Skan p_r, 0, r_bag); 355169691Skan p_l->replace_child(p_new_child, pref_begin(p_new_child), 356169691Skan pref_end(p_new_child), this); 357169691Skan _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);) 358169691Skan return p_l; 359169691Skan } 360169691Skan 361169691Skan if (p_r->get_e_ind() < p_l->get_e_ind() && 362169691Skan p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) 363169691Skan { 364169691Skan node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l, 365169691Skan 0, r_bag); 366169691Skan 367169691Skan p_r->replace_child(p_new_child, pref_begin(p_new_child), 368169691Skan pref_end(p_new_child), this); 369169691Skan 370169691Skan _GLIBCXX_DEBUG_ONLY(p_r->assert_valid(this);) 371169691Skan _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_r) == lhs_leafs + rhs_leafs); 372169691Skan return p_r; 373169691Skan } 374169691Skan 375169691Skan node_pointer p_ret = insert_branch(p_l, p_r, r_bag); 376169691Skan _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);) 377169691Skan _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs); 378169691Skan return p_ret; 379169691Skan} 380169691Skan 381169691SkanPB_DS_CLASS_T_DEC 382169691Skaninline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool> 383169691SkanPB_DS_CLASS_C_DEC:: 384169691Skaninsert(const_reference r_val) 385169691Skan{ 386169691Skan node_pointer p_lf = find_imp(PB_DS_V2F(r_val)); 387169691Skan if (p_lf != NULL && p_lf->m_type == pat_trie_leaf_node_type && 388169691Skan synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val))) 389169691Skan { 390169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(PB_DS_V2F(r_val))); 391169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 392169691Skan return std::make_pair(iterator(p_lf), false); 393169691Skan } 394169691Skan 395169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(PB_DS_V2F(r_val))); 396169691Skan 397169691Skan leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); 398169691Skan cond_dealtor cond(p_new_lf); 399169691Skan 400169691Skan new (p_new_lf) leaf(r_val); 401169691Skan apply_update(p_new_lf, (node_update* )this); 402169691Skan cond.set_call_destructor(); 403169691Skan split_join_branch_bag bag; 404169691Skan bag.add_branch(); 405169691Skan m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag); 406169691Skan m_p_head->m_p_parent->m_p_parent = m_p_head; 407169691Skan cond.set_no_action_dtor(); 408169691Skan ++m_size; 409169691Skan update_min_max_for_inserted_leaf(p_new_lf); 410169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_val));) 411169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 412169691Skan return std::make_pair(point_iterator(p_new_lf), true); 413169691Skan} 414169691Skan 415169691SkanPB_DS_CLASS_T_DEC 416169691Skantypename PB_DS_CLASS_C_DEC::size_type 417169691SkanPB_DS_CLASS_C_DEC:: 418169691Skankeys_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) 419169691Skan{ 420169691Skan size_type diff_pos = 0; 421169691Skan while (b_l != e_l) 422169691Skan { 423169691Skan if (b_r == e_r) 424169691Skan return (diff_pos); 425169691Skan if (e_access_traits::e_pos(*b_l) != e_access_traits::e_pos(*b_r)) 426169691Skan return (diff_pos); 427169691Skan ++b_l; 428169691Skan ++b_r; 429169691Skan ++diff_pos; 430169691Skan } 431169691Skan _GLIBCXX_DEBUG_ASSERT(b_r != e_r); 432169691Skan return diff_pos; 433169691Skan} 434169691Skan 435169691SkanPB_DS_CLASS_T_DEC 436169691Skantypename PB_DS_CLASS_C_DEC::internal_node_pointer 437169691SkanPB_DS_CLASS_C_DEC:: 438169691Skaninsert_branch(node_pointer p_l, node_pointer p_r, split_join_branch_bag& r_bag) 439169691Skan{ 440169691Skan typename synth_e_access_traits::const_iterator left_b_it = pref_begin(p_l); 441169691Skan typename synth_e_access_traits::const_iterator left_e_it = pref_end(p_l); 442169691Skan typename synth_e_access_traits::const_iterator right_b_it = pref_begin(p_r); 443169691Skan typename synth_e_access_traits::const_iterator right_e_it = pref_end(p_r); 444169691Skan 445169691Skan const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it, 446169691Skan right_b_it, right_e_it); 447169691Skan 448169691Skan internal_node_pointer p_new_nd = r_bag.get_branch(); 449169691Skan new (p_new_nd) internal_node(diff_ind, left_b_it); 450169691Skan p_new_nd->add_child(p_l, left_b_it, left_e_it, this); 451169691Skan p_new_nd->add_child(p_r, right_b_it, right_e_it, this); 452169691Skan p_l->m_p_parent = p_new_nd; 453169691Skan p_r->m_p_parent = p_new_nd; 454169691Skan _GLIBCXX_DEBUG_ONLY(p_new_nd->assert_valid(this);) 455169691Skan return (p_new_nd); 456169691Skan} 457169691Skan 458169691SkanPB_DS_CLASS_T_DEC 459169691Skanvoid 460169691SkanPB_DS_CLASS_C_DEC:: 461169691Skanupdate_min_max_for_inserted_leaf(leaf_pointer p_new_lf) 462169691Skan{ 463169691Skan if (m_p_head->m_p_min == m_p_head || 464169691Skan synth_e_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()), 465169691Skan PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value()))) 466169691Skan m_p_head->m_p_min = p_new_lf; 467169691Skan 468169691Skan if (m_p_head->m_p_max == m_p_head || 469169691Skan 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()))) 470169691Skan m_p_head->m_p_max = p_new_lf; 471169691Skan} 472