1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2009, 2010 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 3, 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 // 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. 19 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/>. 24 25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 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 34 // warranty. 35 36 /** 37 * @file insert_join_fn_imps.hpp 38 * Contains an implementation class for bin_search_tree_. 39 */ 40 41 PB_DS_CLASS_T_DEC 42 void 43 PB_DS_CLASS_C_DEC:: 44 join(PB_DS_CLASS_C_DEC& other) 45 { 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)) 50 { 51 _GLIBCXX_DEBUG_ONLY(assert_valid();); 52 _GLIBCXX_DEBUG_ONLY(other.assert_valid();); 53 return; 54 } 55 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); 58 59 m_p_head->m_p_parent->m_p_parent = m_p_head; 60 m_size += other.m_size; 61 other.initialize(); 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();); 66 } 67 68 PB_DS_CLASS_T_DEC 69 bool 70 PB_DS_CLASS_C_DEC:: 71 join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag) 72 { 73 _GLIBCXX_DEBUG_ONLY(assert_valid();) 74 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 75 if (other.m_size == 0) 76 return false; 77 78 if (m_size == 0) 79 { 80 value_swap(other); 81 return false; 82 } 83 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())); 87 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())); 90 91 if (!greater && !lesser) 92 __throw_join_error(); 93 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);) 96 return true; 97 } 98 99 PB_DS_CLASS_T_DEC 100 void 101 PB_DS_CLASS_C_DEC:: 102 rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag) 103 { 104 if (p_l->m_type == pat_trie_leaf_node_type) 105 { 106 if (p_r->m_type == pat_trie_leaf_node_type) 107 { 108 rec_join_prep(static_cast<const_leaf_pointer>(p_l), 109 static_cast<const_leaf_pointer>(p_r), r_bag); 110 return; 111 } 112 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); 116 return; 117 } 118 119 _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); 120 if (p_r->m_type == pat_trie_leaf_node_type) 121 { 122 rec_join_prep(static_cast<const_internal_node_pointer>(p_l), 123 static_cast<const_leaf_pointer>(p_r), r_bag); 124 return; 125 } 126 127 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); 128 129 rec_join_prep(static_cast<const_internal_node_pointer>(p_l), 130 static_cast<const_internal_node_pointer>(p_r), r_bag); 131 } 132 133 PB_DS_CLASS_T_DEC 134 void 135 PB_DS_CLASS_C_DEC:: 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(); } 139 140 PB_DS_CLASS_T_DEC 141 void 142 PB_DS_CLASS_C_DEC:: 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(); } 146 147 PB_DS_CLASS_T_DEC 148 void 149 PB_DS_CLASS_C_DEC:: 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(); } 153 154 PB_DS_CLASS_T_DEC 155 void 156 PB_DS_CLASS_C_DEC:: 157 rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r, 158 split_join_branch_bag& r_bag) 159 { 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())) 163 { 164 for (typename internal_node::const_iterator it = p_r->begin(); 165 it != p_r->end(); ++ it) 166 { 167 const_node_pointer p_l_join_child = p_l->get_join_child(*it, this); 168 if (p_l_join_child != 0) 169 rec_join_prep(p_l_join_child, * it, r_bag); 170 } 171 return; 172 } 173 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)) 176 { 177 const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this); 178 if (p_r_join_child != 0) 179 rec_join_prep(p_r_join_child, p_l, r_bag); 180 return; 181 } 182 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)) 185 { 186 const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this); 187 if (p_r_join_child != 0) 188 rec_join_prep(p_r_join_child, p_l, r_bag); 189 return; 190 } 191 r_bag.add_branch(); 192 } 193 194 PB_DS_CLASS_T_DEC 195 typename PB_DS_CLASS_C_DEC::node_pointer 196 PB_DS_CLASS_C_DEC:: 197 rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) 198 { 199 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 200 if (p_l == 0) 201 { 202 apply_update(p_r, (node_update* )this); 203 return (p_r); 204 } 205 206 if (p_l->m_type == pat_trie_leaf_node_type) 207 { 208 if (p_r->m_type == pat_trie_leaf_node_type) 209 { 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); 213 return p_ret; 214 } 215 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), 219 checked_ind, r_bag); 220 apply_update(p_ret, (node_update* )this); 221 return p_ret; 222 } 223 224 _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); 225 if (p_r->m_type == pat_trie_leaf_node_type) 226 { 227 node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l), 228 static_cast<leaf_pointer>(p_r), 229 checked_ind, r_bag); 230 apply_update(p_ret, (node_update* )this); 231 return p_ret; 232 } 233 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), 237 r_bag); 238 239 apply_update(p_ret, (node_update* )this); 240 return p_ret; 241 } 242 243 PB_DS_CLASS_T_DEC 244 typename PB_DS_CLASS_C_DEC::node_pointer 245 PB_DS_CLASS_C_DEC:: 246 rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag) 247 { 248 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 249 if (p_l == 0) 250 return (p_r); 251 node_pointer p_ret = insert_branch(p_l, p_r, r_bag); 252 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == 2); 253 return p_ret; 254 } 255 256 PB_DS_CLASS_T_DEC 257 typename PB_DS_CLASS_C_DEC::node_pointer 258 PB_DS_CLASS_C_DEC:: 259 rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind, 260 split_join_branch_bag& r_bag) 261 { 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); 265 #endif 266 267 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 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); 270 return p_ret; 271 } 272 273 PB_DS_CLASS_T_DEC 274 typename PB_DS_CLASS_C_DEC::node_pointer 275 PB_DS_CLASS_C_DEC:: 276 rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) 277 { 278 _GLIBCXX_DEBUG_ASSERT(p_l != 0); 279 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 280 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); 284 #endif 285 286 if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this)) 287 { 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); 292 return p_ret; 293 } 294 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) 298 { 299 node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(), 300 r_bag); 301 302 p_l->replace_child(p_new_child, pref_begin(p_new_child), 303 pref_end(p_new_child), this); 304 } 305 306 _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this)); 307 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs); 308 return p_l; 309 } 310 311 PB_DS_CLASS_T_DEC 312 typename PB_DS_CLASS_C_DEC::node_pointer 313 PB_DS_CLASS_C_DEC:: 314 rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag) 315 { 316 _GLIBCXX_DEBUG_ASSERT(p_l != 0); 317 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 318 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); 322 #endif 323 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())) 327 { 328 for (typename internal_node::iterator it = p_r->begin(); 329 it != p_r->end(); ++ it) 330 { 331 node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this), 332 * it, 0, r_bag); 333 p_l->replace_child(p_new_child, pref_begin(p_new_child), 334 pref_end(p_new_child), this); 335 } 336 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); 341 return p_l; 342 } 343 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)) 346 { 347 node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this), 348 p_r, 0, r_bag); 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);) 352 return p_l; 353 } 354 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)) 357 { 358 node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l, 359 0, r_bag); 360 361 p_r->replace_child(p_new_child, pref_begin(p_new_child), 362 pref_end(p_new_child), this); 363 364 _GLIBCXX_DEBUG_ONLY(p_r->assert_valid(this);) 365 _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_r) == lhs_leafs + rhs_leafs); 366 return p_r; 367 } 368 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); 372 return p_ret; 373 } 374 375 PB_DS_CLASS_T_DEC 376 inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool> 377 PB_DS_CLASS_C_DEC:: 378 insert(const_reference r_val) 379 { 380 node_pointer p_lf = find_imp(PB_DS_V2F(r_val)); 381 if (p_lf != 0 && 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))) 383 { 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); 387 } 388 389 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(PB_DS_V2F(r_val))); 390 391 leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); 392 cond_dealtor cond(p_new_lf); 393 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; 398 bag.add_branch(); 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(); 402 ++m_size; 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); 407 } 408 409 PB_DS_CLASS_T_DEC 410 typename PB_DS_CLASS_C_DEC::size_type 411 PB_DS_CLASS_C_DEC:: 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) 413 { 414 size_type diff_pos = 0; 415 while (b_l != e_l) 416 { 417 if (b_r == e_r) 418 return (diff_pos); 419 if (e_access_traits::e_pos(*b_l) != e_access_traits::e_pos(*b_r)) 420 return (diff_pos); 421 ++b_l; 422 ++b_r; 423 ++diff_pos; 424 } 425 _GLIBCXX_DEBUG_ASSERT(b_r != e_r); 426 return diff_pos; 427 } 428 429 PB_DS_CLASS_T_DEC 430 typename PB_DS_CLASS_C_DEC::internal_node_pointer 431 PB_DS_CLASS_C_DEC:: 432 insert_branch(node_pointer p_l, node_pointer p_r, split_join_branch_bag& r_bag) 433 { 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); 438 439 const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it, 440 right_b_it, right_e_it); 441 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);) 449 return (p_new_nd); 450 } 451 452 PB_DS_CLASS_T_DEC 453 void 454 PB_DS_CLASS_C_DEC:: 455 update_min_max_for_inserted_leaf(leaf_pointer p_new_lf) 456 { 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; 461 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; 465 } 466
