1// -*- C++ -*- 2 3// Copyright (C) 2005-2014 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 pat_trie_/insert_join_fn_imps.hpp 38 * Contains an implementation class for pat_trie. 39 */ 40 41PB_DS_CLASS_T_DEC 42void 43PB_DS_CLASS_C_DEC:: 44join(PB_DS_CLASS_C_DEC& other) 45{ 46 PB_DS_ASSERT_VALID((*this)) 47 PB_DS_ASSERT_VALID(other) 48 branch_bag bag; 49 if (!join_prep(other, bag)) 50 { 51 PB_DS_ASSERT_VALID((*this)) 52 PB_DS_ASSERT_VALID(other) 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 PB_DS_ASSERT_VALID(other) 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 PB_DS_ASSERT_VALID((*this)) 66} 67 68PB_DS_CLASS_T_DEC 69bool 70PB_DS_CLASS_C_DEC:: 71join_prep(PB_DS_CLASS_C_DEC& other, branch_bag& r_bag) 72{ 73 PB_DS_ASSERT_VALID((*this)) 74 PB_DS_ASSERT_VALID(other) 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 = 85 synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()), 86 PB_DS_V2F(static_cast<leaf_const_pointer>(other.m_p_head->m_p_min)->value())); 87 88 const bool lesser = 89 synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(other.m_p_head->m_p_max)->value()), 90 PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value())); 91 92 if (!greater && !lesser) 93 __throw_join_error(); 94 95 rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag); 96 _GLIBCXX_DEBUG_ONLY(debug_base::join(other, false);) 97 return true; 98} 99 100PB_DS_CLASS_T_DEC 101void 102PB_DS_CLASS_C_DEC:: 103rec_join_prep(node_const_pointer p_l, node_const_pointer p_r, 104 branch_bag& r_bag) 105{ 106 if (p_l->m_type == leaf_node) 107 { 108 if (p_r->m_type == leaf_node) 109 { 110 rec_join_prep(static_cast<leaf_const_pointer>(p_l), 111 static_cast<leaf_const_pointer>(p_r), r_bag); 112 return; 113 } 114 115 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); 116 rec_join_prep(static_cast<leaf_const_pointer>(p_l), 117 static_cast<inode_const_pointer>(p_r), r_bag); 118 return; 119 } 120 121 _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node); 122 if (p_r->m_type == leaf_node) 123 { 124 rec_join_prep(static_cast<inode_const_pointer>(p_l), 125 static_cast<leaf_const_pointer>(p_r), r_bag); 126 return; 127 } 128 129 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); 130 131 rec_join_prep(static_cast<inode_const_pointer>(p_l), 132 static_cast<inode_const_pointer>(p_r), r_bag); 133} 134 135PB_DS_CLASS_T_DEC 136void 137PB_DS_CLASS_C_DEC:: 138rec_join_prep(leaf_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/, 139 branch_bag& r_bag) 140{ r_bag.add_branch(); } 141 142PB_DS_CLASS_T_DEC 143void 144PB_DS_CLASS_C_DEC:: 145rec_join_prep(leaf_const_pointer /*p_l*/, inode_const_pointer /*p_r*/, 146 branch_bag& r_bag) 147{ r_bag.add_branch(); } 148 149PB_DS_CLASS_T_DEC 150void 151PB_DS_CLASS_C_DEC:: 152rec_join_prep(inode_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/, 153 branch_bag& r_bag) 154{ r_bag.add_branch(); } 155 156PB_DS_CLASS_T_DEC 157void 158PB_DS_CLASS_C_DEC:: 159rec_join_prep(inode_const_pointer p_l, inode_const_pointer p_r, 160 branch_bag& r_bag) 161{ 162 if (p_l->get_e_ind() == p_r->get_e_ind() && 163 synth_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), 164 p_r->pref_b_it(), p_r->pref_e_it())) 165 { 166 for (typename inode::const_iterator it = p_r->begin(); 167 it != p_r->end(); ++ it) 168 { 169 node_const_pointer p_l_join_child = p_l->get_join_child(*it, this); 170 if (p_l_join_child != 0) 171 rec_join_prep(p_l_join_child, * it, r_bag); 172 } 173 return; 174 } 175 176 if (p_r->get_e_ind() < p_l->get_e_ind() && 177 p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) 178 { 179 node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this); 180 if (p_r_join_child != 0) 181 rec_join_prep(p_r_join_child, p_l, r_bag); 182 return; 183 } 184 185 if (p_r->get_e_ind() < p_l->get_e_ind() && 186 p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) 187 { 188 node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this); 189 if (p_r_join_child != 0) 190 rec_join_prep(p_r_join_child, p_l, r_bag); 191 return; 192 } 193 r_bag.add_branch(); 194} 195 196PB_DS_CLASS_T_DEC 197typename PB_DS_CLASS_C_DEC::node_pointer 198PB_DS_CLASS_C_DEC:: 199rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, 200 branch_bag& r_bag) 201{ 202 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 203 if (p_l == 0) 204 { 205 apply_update(p_r, (node_update*)this); 206 return (p_r); 207 } 208 209 if (p_l->m_type == leaf_node) 210 { 211 if (p_r->m_type == leaf_node) 212 { 213 node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), 214 static_cast<leaf_pointer>(p_r), r_bag); 215 apply_update(p_ret, (node_update*)this); 216 return p_ret; 217 } 218 219 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); 220 node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), 221 static_cast<inode_pointer>(p_r), 222 checked_ind, r_bag); 223 apply_update(p_ret, (node_update*)this); 224 return p_ret; 225 } 226 227 _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node); 228 if (p_r->m_type == leaf_node) 229 { 230 node_pointer p_ret = rec_join(static_cast<inode_pointer>(p_l), 231 static_cast<leaf_pointer>(p_r), 232 checked_ind, r_bag); 233 apply_update(p_ret, (node_update*)this); 234 return p_ret; 235 } 236 237 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); 238 node_pointer p_ret = rec_join(static_cast<inode_pointer>(p_l), 239 static_cast<inode_pointer>(p_r), 240 r_bag); 241 242 apply_update(p_ret, (node_update*)this); 243 return p_ret; 244} 245 246PB_DS_CLASS_T_DEC 247typename PB_DS_CLASS_C_DEC::node_pointer 248PB_DS_CLASS_C_DEC:: 249rec_join(leaf_pointer p_l, leaf_pointer p_r, branch_bag& r_bag) 250{ 251 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 252 if (p_l == 0) 253 return (p_r); 254 node_pointer p_ret = insert_branch(p_l, p_r, r_bag); 255 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == 2); 256 return p_ret; 257} 258 259PB_DS_CLASS_T_DEC 260typename PB_DS_CLASS_C_DEC::node_pointer 261PB_DS_CLASS_C_DEC:: 262rec_join(leaf_pointer p_l, inode_pointer p_r, size_type checked_ind, 263 branch_bag& r_bag) 264{ 265#ifdef _GLIBCXX_DEBUG 266 const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l); 267 const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r); 268#endif 269 270 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 271 node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag); 272 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == lhs_leafs + rhs_leafs); 273 return p_ret; 274} 275 276PB_DS_CLASS_T_DEC 277typename PB_DS_CLASS_C_DEC::node_pointer 278PB_DS_CLASS_C_DEC:: 279rec_join(inode_pointer p_l, leaf_pointer p_r, size_type checked_ind, branch_bag& r_bag) 280{ 281 _GLIBCXX_DEBUG_ASSERT(p_l != 0); 282 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 283 284#ifdef _GLIBCXX_DEBUG 285 const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l); 286 const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r); 287#endif 288 289 if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this)) 290 { 291 node_pointer p_ret = insert_branch(p_l, p_r, r_bag); 292 PB_DS_ASSERT_NODE_VALID(p_ret) 293 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == 294 lhs_leafs + rhs_leafs); 295 return p_ret; 296 } 297 298 node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r), 299 pref_end(p_r), this); 300 if (p_pot_child != p_r) 301 { 302 node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(), 303 r_bag); 304 305 p_l->replace_child(p_new_child, pref_begin(p_new_child), 306 pref_end(p_new_child), this); 307 } 308 309 PB_DS_ASSERT_NODE_VALID(p_l) 310 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_l) == lhs_leafs + rhs_leafs); 311 return p_l; 312} 313 314PB_DS_CLASS_T_DEC 315typename PB_DS_CLASS_C_DEC::node_pointer 316PB_DS_CLASS_C_DEC:: 317rec_join(inode_pointer p_l, inode_pointer p_r, 318 branch_bag& r_bag) 319{ 320 _GLIBCXX_DEBUG_ASSERT(p_l != 0); 321 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 322 323#ifdef _GLIBCXX_DEBUG 324 const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l); 325 const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r); 326#endif 327 328 if (p_l->get_e_ind() == p_r->get_e_ind() && 329 synth_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), 330 p_r->pref_b_it(), p_r->pref_e_it())) 331 { 332 for (typename inode::iterator it = p_r->begin(); 333 it != p_r->end(); ++ it) 334 { 335 node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this), 336 * it, 0, r_bag); 337 p_l->replace_child(p_new_child, pref_begin(p_new_child), 338 pref_end(p_new_child), this); 339 } 340 341 p_r->~inode(); 342 s_inode_allocator.deallocate(p_r, 1); 343 PB_DS_ASSERT_NODE_VALID(p_l) 344 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_l) == lhs_leafs + rhs_leafs); 345 return p_l; 346 } 347 348 if (p_l->get_e_ind() < p_r->get_e_ind() && 349 p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this)) 350 { 351 node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this), 352 p_r, 0, r_bag); 353 p_l->replace_child(p_new_child, pref_begin(p_new_child), 354 pref_end(p_new_child), this); 355 PB_DS_ASSERT_NODE_VALID(p_l) 356 return p_l; 357 } 358 359 if (p_r->get_e_ind() < p_l->get_e_ind() && 360 p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) 361 { 362 node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l, 363 0, r_bag); 364 365 p_r->replace_child(p_new_child, pref_begin(p_new_child), 366 pref_end(p_new_child), this); 367 368 PB_DS_ASSERT_NODE_VALID(p_r) 369 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_r) == lhs_leafs + rhs_leafs); 370 return p_r; 371 } 372 373 node_pointer p_ret = insert_branch(p_l, p_r, r_bag); 374 PB_DS_ASSERT_NODE_VALID(p_ret) 375 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == lhs_leafs + rhs_leafs); 376 return p_ret; 377} 378 379PB_DS_CLASS_T_DEC 380inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool> 381PB_DS_CLASS_C_DEC:: 382insert(const_reference r_val) 383{ 384 node_pointer p_lf = find_imp(PB_DS_V2F(r_val)); 385 if (p_lf != 0 && p_lf->m_type == leaf_node && 386 synth_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val))) 387 { 388 PB_DS_CHECK_KEY_EXISTS(PB_DS_V2F(r_val)) 389 PB_DS_ASSERT_VALID((*this)) 390 return std::make_pair(iterator(p_lf), false); 391 } 392 393 PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_val)) 394 395 leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); 396 cond_dealtor cond(p_new_lf); 397 398 new (p_new_lf) leaf(r_val); 399 apply_update(p_new_lf, (node_update*)this); 400 cond.set_call_destructor(); 401 branch_bag bag; 402 bag.add_branch(); 403 m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag); 404 m_p_head->m_p_parent->m_p_parent = m_p_head; 405 cond.set_no_action_dtor(); 406 ++m_size; 407 update_min_max_for_inserted_leaf(p_new_lf); 408 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) 409 PB_DS_ASSERT_VALID((*this)) 410 return std::make_pair(point_iterator(p_new_lf), true); 411} 412 413PB_DS_CLASS_T_DEC 414typename PB_DS_CLASS_C_DEC::size_type 415PB_DS_CLASS_C_DEC:: 416keys_diff_ind(typename access_traits::const_iterator b_l, 417 typename access_traits::const_iterator e_l, 418 typename access_traits::const_iterator b_r, 419 typename access_traits::const_iterator e_r) 420{ 421 size_type diff_pos = 0; 422 while (b_l != e_l) 423 { 424 if (b_r == e_r) 425 return (diff_pos); 426 if (access_traits::e_pos(*b_l) != access_traits::e_pos(*b_r)) 427 return (diff_pos); 428 ++b_l; 429 ++b_r; 430 ++diff_pos; 431 } 432 _GLIBCXX_DEBUG_ASSERT(b_r != e_r); 433 return diff_pos; 434} 435 436PB_DS_CLASS_T_DEC 437typename PB_DS_CLASS_C_DEC::inode_pointer 438PB_DS_CLASS_C_DEC:: 439insert_branch(node_pointer p_l, node_pointer p_r, branch_bag& r_bag) 440{ 441 typename synth_access_traits::const_iterator left_b_it = pref_begin(p_l); 442 typename synth_access_traits::const_iterator left_e_it = pref_end(p_l); 443 typename synth_access_traits::const_iterator right_b_it = pref_begin(p_r); 444 typename synth_access_traits::const_iterator right_e_it = pref_end(p_r); 445 446 const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it, 447 right_b_it, right_e_it); 448 449 inode_pointer p_new_nd = r_bag.get_branch(); 450 new (p_new_nd) inode(diff_ind, left_b_it); 451 p_new_nd->add_child(p_l, left_b_it, left_e_it, this); 452 p_new_nd->add_child(p_r, right_b_it, right_e_it, this); 453 p_l->m_p_parent = p_new_nd; 454 p_r->m_p_parent = p_new_nd; 455 PB_DS_ASSERT_NODE_VALID(p_new_nd) 456 return (p_new_nd); 457} 458 459PB_DS_CLASS_T_DEC 460void 461PB_DS_CLASS_C_DEC:: 462update_min_max_for_inserted_leaf(leaf_pointer p_new_lf) 463{ 464 if (m_p_head->m_p_min == m_p_head || 465 synth_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()), 466 PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value()))) 467 m_p_head->m_p_min = p_new_lf; 468 469 if (m_p_head->m_p_max == m_p_head || 470 synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()), PB_DS_V2F(p_new_lf->value()))) 471 m_p_head->m_p_max = p_new_lf; 472} 473