1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2018 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 41 PB_DS_CLASS_T_DEC 42 void 43 PB_DS_CLASS_C_DEC:: 44 join(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 68 PB_DS_CLASS_T_DEC 69 bool 70 PB_DS_CLASS_C_DEC:: 71 join_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 100 PB_DS_CLASS_T_DEC 101 void 102 PB_DS_CLASS_C_DEC:: 103 rec_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 135 PB_DS_CLASS_T_DEC 136 void 137 PB_DS_CLASS_C_DEC:: 138 rec_join_prep(leaf_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/, 139 branch_bag& r_bag) 140 { r_bag.add_branch(); } 141 142 PB_DS_CLASS_T_DEC 143 void 144 PB_DS_CLASS_C_DEC:: 145 rec_join_prep(leaf_const_pointer /*p_l*/, inode_const_pointer /*p_r*/, 146 branch_bag& r_bag) 147 { r_bag.add_branch(); } 148 149 PB_DS_CLASS_T_DEC 150 void 151 PB_DS_CLASS_C_DEC:: 152 rec_join_prep(inode_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/, 153 branch_bag& r_bag) 154 { r_bag.add_branch(); } 155 156 PB_DS_CLASS_T_DEC 157 void 158 PB_DS_CLASS_C_DEC:: 159 rec_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 196 PB_DS_CLASS_T_DEC 197 typename PB_DS_CLASS_C_DEC::node_pointer 198 PB_DS_CLASS_C_DEC:: 199 rec_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 246 PB_DS_CLASS_T_DEC 247 typename PB_DS_CLASS_C_DEC::node_pointer 248 PB_DS_CLASS_C_DEC:: 249 rec_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 259 PB_DS_CLASS_T_DEC 260 typename PB_DS_CLASS_C_DEC::node_pointer 261 PB_DS_CLASS_C_DEC:: 262 rec_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 276 PB_DS_CLASS_T_DEC 277 typename PB_DS_CLASS_C_DEC::node_pointer 278 PB_DS_CLASS_C_DEC:: 279 rec_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 314 PB_DS_CLASS_T_DEC 315 typename PB_DS_CLASS_C_DEC::node_pointer 316 PB_DS_CLASS_C_DEC:: 317 rec_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 379 PB_DS_CLASS_T_DEC 380 inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool> 381 PB_DS_CLASS_C_DEC:: 382 insert(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 413 PB_DS_CLASS_T_DEC 414 typename PB_DS_CLASS_C_DEC::size_type 415 PB_DS_CLASS_C_DEC:: 416 keys_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 436 PB_DS_CLASS_T_DEC 437 typename PB_DS_CLASS_C_DEC::inode_pointer 438 PB_DS_CLASS_C_DEC:: 439 insert_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 459 PB_DS_CLASS_T_DEC 460 void 461 PB_DS_CLASS_C_DEC:: 462 update_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