1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4// 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 9// version. 10 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. 15 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. 20 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 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 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 40// warranty. 41 42/** 43 * @file insert_join_fn_imps.hpp 44 * Contains an implementation class for bin_search_tree_. 45 */ 46 47PB_DS_CLASS_T_DEC 48void 49PB_DS_CLASS_C_DEC:: 50join(PB_DS_CLASS_C_DEC& other) 51{ 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)) 56 { 57 _GLIBCXX_DEBUG_ONLY(assert_valid();); 58 _GLIBCXX_DEBUG_ONLY(other.assert_valid();); 59 return; 60 } 61 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); 64 65 m_p_head->m_p_parent->m_p_parent = m_p_head; 66 m_size += other.m_size; 67 other.initialize(); 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();); 72} 73 74PB_DS_CLASS_T_DEC 75bool 76PB_DS_CLASS_C_DEC:: 77join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag) 78{ 79 _GLIBCXX_DEBUG_ONLY(assert_valid();) 80 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 81 if (other.m_size == 0) 82 return false; 83 84 if (m_size == 0) 85 { 86 value_swap(other); 87 return false; 88 } 89 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())); 93 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())); 96 97 if (!greater && !lesser) 98 __throw_join_error(); 99 100 rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag); 101 _GLIBCXX_DEBUG_ONLY(map_debug_base::join(other);) 102 return true; 103} 104 105PB_DS_CLASS_T_DEC 106void 107PB_DS_CLASS_C_DEC:: 108rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag) 109{ 110 if (p_l->m_type == pat_trie_leaf_node_type) 111 { 112 if (p_r->m_type == pat_trie_leaf_node_type) 113 { 114 rec_join_prep(static_cast<const_leaf_pointer>(p_l), 115 static_cast<const_leaf_pointer>(p_r), r_bag); 116 return; 117 } 118 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); 122 return; 123 } 124 125 _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); 126 if (p_r->m_type == pat_trie_leaf_node_type) 127 { 128 rec_join_prep(static_cast<const_internal_node_pointer>(p_l), 129 static_cast<const_leaf_pointer>(p_r), r_bag); 130 return; 131 } 132 133 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); 134 135 rec_join_prep(static_cast<const_internal_node_pointer>(p_l), 136 static_cast<const_internal_node_pointer>(p_r), r_bag); 137} 138 139PB_DS_CLASS_T_DEC 140void 141PB_DS_CLASS_C_DEC:: 142rec_join_prep(const_leaf_pointer /*p_l*/, const_leaf_pointer /*p_r*/, 143 split_join_branch_bag& r_bag) 144{ r_bag.add_branch(); } 145 146PB_DS_CLASS_T_DEC 147void 148PB_DS_CLASS_C_DEC:: 149rec_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(); } 152 153PB_DS_CLASS_T_DEC 154void 155PB_DS_CLASS_C_DEC:: 156rec_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(); } 159 160PB_DS_CLASS_T_DEC 161void 162PB_DS_CLASS_C_DEC:: 163rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r, 164 split_join_branch_bag& r_bag) 165{ 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())) 169 { 170 for (typename internal_node::const_iterator it = p_r->begin(); 171 it != p_r->end(); ++ it) 172 { 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); 176 } 177 return; 178 } 179 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)) 182 { 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); 186 return; 187 } 188 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)) 191 { 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); 195 return; 196 } 197 r_bag.add_branch(); 198} 199 200PB_DS_CLASS_T_DEC 201typename PB_DS_CLASS_C_DEC::node_pointer 202PB_DS_CLASS_C_DEC:: 203rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) 204{ 205 _GLIBCXX_DEBUG_ASSERT(p_r != NULL); 206 if (p_l == NULL) 207 { 208 apply_update(p_r, (node_update* )this); 209 return (p_r); 210 } 211 212 if (p_l->m_type == pat_trie_leaf_node_type) 213 { 214 if (p_r->m_type == pat_trie_leaf_node_type) 215 { 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); 219 return p_ret; 220 } 221 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), 225 checked_ind, r_bag); 226 apply_update(p_ret, (node_update* )this); 227 return p_ret; 228 } 229 230 _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); 231 if (p_r->m_type == pat_trie_leaf_node_type) 232 { 233 node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l), 234 static_cast<leaf_pointer>(p_r), 235 checked_ind, r_bag); 236 apply_update(p_ret, (node_update* )this); 237 return p_ret; 238 } 239 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), 243 r_bag); 244 245 apply_update(p_ret, (node_update* )this); 246 return p_ret; 247} 248 249PB_DS_CLASS_T_DEC 250typename PB_DS_CLASS_C_DEC::node_pointer 251PB_DS_CLASS_C_DEC:: 252rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag) 253{ 254 _GLIBCXX_DEBUG_ASSERT(p_r != NULL); 255 if (p_l == NULL) 256 return (p_r); 257 node_pointer p_ret = insert_branch(p_l, p_r, r_bag); 258 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == 2); 259 return p_ret; 260} 261 262PB_DS_CLASS_T_DEC 263typename PB_DS_CLASS_C_DEC::node_pointer 264PB_DS_CLASS_C_DEC:: 265rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind, 266 split_join_branch_bag& r_bag) 267{ 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); 271#endif 272 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); 276 return p_ret; 277} 278 279PB_DS_CLASS_T_DEC 280typename PB_DS_CLASS_C_DEC::node_pointer 281PB_DS_CLASS_C_DEC:: 282rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) 283{ 284 _GLIBCXX_DEBUG_ASSERT(p_l != NULL); 285 _GLIBCXX_DEBUG_ASSERT(p_r != NULL); 286 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); 290#endif 291 292 if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this)) 293 { 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); 298 return p_ret; 299 } 300 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) 304 { 305 node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(), 306 r_bag); 307 308 p_l->replace_child(p_new_child, pref_begin(p_new_child), 309 pref_end(p_new_child), this); 310 } 311 312 _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this)); 313 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs); 314 return p_l; 315} 316 317PB_DS_CLASS_T_DEC 318typename PB_DS_CLASS_C_DEC::node_pointer 319PB_DS_CLASS_C_DEC:: 320rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag) 321{ 322 _GLIBCXX_DEBUG_ASSERT(p_l != NULL); 323 _GLIBCXX_DEBUG_ASSERT(p_r != NULL); 324 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); 328#endif 329 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())) 333 { 334 for (typename internal_node::iterator it = p_r->begin(); 335 it != p_r->end(); ++ it) 336 { 337 node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this), 338 * it, 0, r_bag); 339 p_l->replace_child(p_new_child, pref_begin(p_new_child), 340 pref_end(p_new_child), this); 341 } 342 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); 347 return p_l; 348 } 349 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)) 352 { 353 node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this), 354 p_r, 0, r_bag); 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);) 358 return p_l; 359 } 360 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)) 363 { 364 node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l, 365 0, r_bag); 366 367 p_r->replace_child(p_new_child, pref_begin(p_new_child), 368 pref_end(p_new_child), this); 369 370 _GLIBCXX_DEBUG_ONLY(p_r->assert_valid(this);) 371 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_r) == lhs_leafs + rhs_leafs); 372 return p_r; 373 } 374 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); 378 return p_ret; 379} 380 381PB_DS_CLASS_T_DEC 382inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool> 383PB_DS_CLASS_C_DEC:: 384insert(const_reference r_val) 385{ 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))) 389 { 390 _GLIBCXX_DEBUG_ONLY(map_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); 393 } 394 395 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(PB_DS_V2F(r_val))); 396 397 leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); 398 cond_dealtor cond(p_new_lf); 399 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; 404 bag.add_branch(); 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(); 408 ++m_size; 409 update_min_max_for_inserted_leaf(p_new_lf); 410 _GLIBCXX_DEBUG_ONLY(map_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); 413} 414 415PB_DS_CLASS_T_DEC 416typename PB_DS_CLASS_C_DEC::size_type 417PB_DS_CLASS_C_DEC:: 418keys_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) 419{ 420 size_type diff_pos = 0; 421 while (b_l != e_l) 422 { 423 if (b_r == e_r) 424 return (diff_pos); 425 if (e_access_traits::e_pos(*b_l) != e_access_traits::e_pos(*b_r)) 426 return (diff_pos); 427 ++b_l; 428 ++b_r; 429 ++diff_pos; 430 } 431 _GLIBCXX_DEBUG_ASSERT(b_r != e_r); 432 return diff_pos; 433} 434 435PB_DS_CLASS_T_DEC 436typename PB_DS_CLASS_C_DEC::internal_node_pointer 437PB_DS_CLASS_C_DEC:: 438insert_branch(node_pointer p_l, node_pointer p_r, split_join_branch_bag& r_bag) 439{ 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); 444 445 const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it, 446 right_b_it, right_e_it); 447 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);) 455 return (p_new_nd); 456} 457 458PB_DS_CLASS_T_DEC 459void 460PB_DS_CLASS_C_DEC:: 461update_min_max_for_inserted_leaf(leaf_pointer p_new_lf) 462{ 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; 467 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; 471} 472