libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file pat_trie_/insert_join_fn_imps.hpp 00038 * Contains an implementation class for pat_trie. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 void 00043 PB_DS_CLASS_C_DEC:: 00044 join(PB_DS_CLASS_C_DEC& other) 00045 { 00046 PB_DS_ASSERT_VALID((*this)) 00047 PB_DS_ASSERT_VALID(other) 00048 branch_bag bag; 00049 if (!join_prep(other, bag)) 00050 { 00051 PB_DS_ASSERT_VALID((*this)) 00052 PB_DS_ASSERT_VALID(other) 00053 return; 00054 } 00055 00056 m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, 00057 other.m_p_head->m_p_parent, 0, bag); 00058 00059 m_p_head->m_p_parent->m_p_parent = m_p_head; 00060 m_size += other.m_size; 00061 other.initialize(); 00062 PB_DS_ASSERT_VALID(other) 00063 m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent); 00064 m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); 00065 PB_DS_ASSERT_VALID((*this)) 00066 } 00067 00068 PB_DS_CLASS_T_DEC 00069 bool 00070 PB_DS_CLASS_C_DEC:: 00071 join_prep(PB_DS_CLASS_C_DEC& other, branch_bag& r_bag) 00072 { 00073 PB_DS_ASSERT_VALID((*this)) 00074 PB_DS_ASSERT_VALID(other) 00075 if (other.m_size == 0) 00076 return false; 00077 00078 if (m_size == 0) 00079 { 00080 value_swap(other); 00081 return false; 00082 } 00083 00084 const bool greater = 00085 synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()), 00086 PB_DS_V2F(static_cast<leaf_const_pointer>(other.m_p_head->m_p_min)->value())); 00087 00088 const bool lesser = 00089 synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(other.m_p_head->m_p_max)->value()), 00090 PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value())); 00091 00092 if (!greater && !lesser) 00093 __throw_join_error(); 00094 00095 rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag); 00096 _GLIBCXX_DEBUG_ONLY(debug_base::join(other, false);) 00097 return true; 00098 } 00099 00100 PB_DS_CLASS_T_DEC 00101 void 00102 PB_DS_CLASS_C_DEC:: 00103 rec_join_prep(node_const_pointer p_l, node_const_pointer p_r, 00104 branch_bag& r_bag) 00105 { 00106 if (p_l->m_type == leaf_node) 00107 { 00108 if (p_r->m_type == leaf_node) 00109 { 00110 rec_join_prep(static_cast<leaf_const_pointer>(p_l), 00111 static_cast<leaf_const_pointer>(p_r), r_bag); 00112 return; 00113 } 00114 00115 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); 00116 rec_join_prep(static_cast<leaf_const_pointer>(p_l), 00117 static_cast<inode_const_pointer>(p_r), r_bag); 00118 return; 00119 } 00120 00121 _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node); 00122 if (p_r->m_type == leaf_node) 00123 { 00124 rec_join_prep(static_cast<inode_const_pointer>(p_l), 00125 static_cast<leaf_const_pointer>(p_r), r_bag); 00126 return; 00127 } 00128 00129 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); 00130 00131 rec_join_prep(static_cast<inode_const_pointer>(p_l), 00132 static_cast<inode_const_pointer>(p_r), r_bag); 00133 } 00134 00135 PB_DS_CLASS_T_DEC 00136 void 00137 PB_DS_CLASS_C_DEC:: 00138 rec_join_prep(leaf_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/, 00139 branch_bag& r_bag) 00140 { r_bag.add_branch(); } 00141 00142 PB_DS_CLASS_T_DEC 00143 void 00144 PB_DS_CLASS_C_DEC:: 00145 rec_join_prep(leaf_const_pointer /*p_l*/, inode_const_pointer /*p_r*/, 00146 branch_bag& r_bag) 00147 { r_bag.add_branch(); } 00148 00149 PB_DS_CLASS_T_DEC 00150 void 00151 PB_DS_CLASS_C_DEC:: 00152 rec_join_prep(inode_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/, 00153 branch_bag& r_bag) 00154 { r_bag.add_branch(); } 00155 00156 PB_DS_CLASS_T_DEC 00157 void 00158 PB_DS_CLASS_C_DEC:: 00159 rec_join_prep(inode_const_pointer p_l, inode_const_pointer p_r, 00160 branch_bag& r_bag) 00161 { 00162 if (p_l->get_e_ind() == p_r->get_e_ind() && 00163 synth_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), 00164 p_r->pref_b_it(), p_r->pref_e_it())) 00165 { 00166 for (typename inode::const_iterator it = p_r->begin(); 00167 it != p_r->end(); ++ it) 00168 { 00169 node_const_pointer p_l_join_child = p_l->get_join_child(*it, this); 00170 if (p_l_join_child != 0) 00171 rec_join_prep(p_l_join_child, * it, r_bag); 00172 } 00173 return; 00174 } 00175 00176 if (p_r->get_e_ind() < p_l->get_e_ind() && 00177 p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) 00178 { 00179 node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this); 00180 if (p_r_join_child != 0) 00181 rec_join_prep(p_r_join_child, p_l, r_bag); 00182 return; 00183 } 00184 00185 if (p_r->get_e_ind() < p_l->get_e_ind() && 00186 p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) 00187 { 00188 node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this); 00189 if (p_r_join_child != 0) 00190 rec_join_prep(p_r_join_child, p_l, r_bag); 00191 return; 00192 } 00193 r_bag.add_branch(); 00194 } 00195 00196 PB_DS_CLASS_T_DEC 00197 typename PB_DS_CLASS_C_DEC::node_pointer 00198 PB_DS_CLASS_C_DEC:: 00199 rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, 00200 branch_bag& r_bag) 00201 { 00202 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 00203 if (p_l == 0) 00204 { 00205 apply_update(p_r, (node_update*)this); 00206 return (p_r); 00207 } 00208 00209 if (p_l->m_type == leaf_node) 00210 { 00211 if (p_r->m_type == leaf_node) 00212 { 00213 node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), 00214 static_cast<leaf_pointer>(p_r), r_bag); 00215 apply_update(p_ret, (node_update*)this); 00216 return p_ret; 00217 } 00218 00219 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); 00220 node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), 00221 static_cast<inode_pointer>(p_r), 00222 checked_ind, r_bag); 00223 apply_update(p_ret, (node_update*)this); 00224 return p_ret; 00225 } 00226 00227 _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node); 00228 if (p_r->m_type == leaf_node) 00229 { 00230 node_pointer p_ret = rec_join(static_cast<inode_pointer>(p_l), 00231 static_cast<leaf_pointer>(p_r), 00232 checked_ind, r_bag); 00233 apply_update(p_ret, (node_update*)this); 00234 return p_ret; 00235 } 00236 00237 _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); 00238 node_pointer p_ret = rec_join(static_cast<inode_pointer>(p_l), 00239 static_cast<inode_pointer>(p_r), 00240 r_bag); 00241 00242 apply_update(p_ret, (node_update*)this); 00243 return p_ret; 00244 } 00245 00246 PB_DS_CLASS_T_DEC 00247 typename PB_DS_CLASS_C_DEC::node_pointer 00248 PB_DS_CLASS_C_DEC:: 00249 rec_join(leaf_pointer p_l, leaf_pointer p_r, branch_bag& r_bag) 00250 { 00251 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 00252 if (p_l == 0) 00253 return (p_r); 00254 node_pointer p_ret = insert_branch(p_l, p_r, r_bag); 00255 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == 2); 00256 return p_ret; 00257 } 00258 00259 PB_DS_CLASS_T_DEC 00260 typename PB_DS_CLASS_C_DEC::node_pointer 00261 PB_DS_CLASS_C_DEC:: 00262 rec_join(leaf_pointer p_l, inode_pointer p_r, size_type checked_ind, 00263 branch_bag& r_bag) 00264 { 00265 #ifdef _GLIBCXX_DEBUG 00266 const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l); 00267 const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r); 00268 #endif 00269 00270 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 00271 node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag); 00272 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == lhs_leafs + rhs_leafs); 00273 return p_ret; 00274 } 00275 00276 PB_DS_CLASS_T_DEC 00277 typename PB_DS_CLASS_C_DEC::node_pointer 00278 PB_DS_CLASS_C_DEC:: 00279 rec_join(inode_pointer p_l, leaf_pointer p_r, size_type checked_ind, branch_bag& r_bag) 00280 { 00281 _GLIBCXX_DEBUG_ASSERT(p_l != 0); 00282 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 00283 00284 #ifdef _GLIBCXX_DEBUG 00285 const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l); 00286 const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r); 00287 #endif 00288 00289 if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this)) 00290 { 00291 node_pointer p_ret = insert_branch(p_l, p_r, r_bag); 00292 PB_DS_ASSERT_NODE_VALID(p_ret) 00293 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == 00294 lhs_leafs + rhs_leafs); 00295 return p_ret; 00296 } 00297 00298 node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r), 00299 pref_end(p_r), this); 00300 if (p_pot_child != p_r) 00301 { 00302 node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(), 00303 r_bag); 00304 00305 p_l->replace_child(p_new_child, pref_begin(p_new_child), 00306 pref_end(p_new_child), this); 00307 } 00308 00309 PB_DS_ASSERT_NODE_VALID(p_l) 00310 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_l) == lhs_leafs + rhs_leafs); 00311 return p_l; 00312 } 00313 00314 PB_DS_CLASS_T_DEC 00315 typename PB_DS_CLASS_C_DEC::node_pointer 00316 PB_DS_CLASS_C_DEC:: 00317 rec_join(inode_pointer p_l, inode_pointer p_r, 00318 branch_bag& r_bag) 00319 { 00320 _GLIBCXX_DEBUG_ASSERT(p_l != 0); 00321 _GLIBCXX_DEBUG_ASSERT(p_r != 0); 00322 00323 #ifdef _GLIBCXX_DEBUG 00324 const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l); 00325 const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r); 00326 #endif 00327 00328 if (p_l->get_e_ind() == p_r->get_e_ind() && 00329 synth_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), 00330 p_r->pref_b_it(), p_r->pref_e_it())) 00331 { 00332 for (typename inode::iterator it = p_r->begin(); 00333 it != p_r->end(); ++ it) 00334 { 00335 node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this), 00336 * it, 0, r_bag); 00337 p_l->replace_child(p_new_child, pref_begin(p_new_child), 00338 pref_end(p_new_child), this); 00339 } 00340 00341 p_r->~inode(); 00342 s_inode_allocator.deallocate(p_r, 1); 00343 PB_DS_ASSERT_NODE_VALID(p_l) 00344 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_l) == lhs_leafs + rhs_leafs); 00345 return p_l; 00346 } 00347 00348 if (p_l->get_e_ind() < p_r->get_e_ind() && 00349 p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this)) 00350 { 00351 node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this), 00352 p_r, 0, r_bag); 00353 p_l->replace_child(p_new_child, pref_begin(p_new_child), 00354 pref_end(p_new_child), this); 00355 PB_DS_ASSERT_NODE_VALID(p_l) 00356 return p_l; 00357 } 00358 00359 if (p_r->get_e_ind() < p_l->get_e_ind() && 00360 p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) 00361 { 00362 node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l, 00363 0, r_bag); 00364 00365 p_r->replace_child(p_new_child, pref_begin(p_new_child), 00366 pref_end(p_new_child), this); 00367 00368 PB_DS_ASSERT_NODE_VALID(p_r) 00369 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_r) == lhs_leafs + rhs_leafs); 00370 return p_r; 00371 } 00372 00373 node_pointer p_ret = insert_branch(p_l, p_r, r_bag); 00374 PB_DS_ASSERT_NODE_VALID(p_ret) 00375 _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == lhs_leafs + rhs_leafs); 00376 return p_ret; 00377 } 00378 00379 PB_DS_CLASS_T_DEC 00380 inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool> 00381 PB_DS_CLASS_C_DEC:: 00382 insert(const_reference r_val) 00383 { 00384 node_pointer p_lf = find_imp(PB_DS_V2F(r_val)); 00385 if (p_lf != 0 && p_lf->m_type == leaf_node && 00386 synth_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val))) 00387 { 00388 PB_DS_CHECK_KEY_EXISTS(PB_DS_V2F(r_val)) 00389 PB_DS_ASSERT_VALID((*this)) 00390 return std::make_pair(iterator(p_lf), false); 00391 } 00392 00393 PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_val)) 00394 00395 leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); 00396 cond_dealtor cond(p_new_lf); 00397 00398 new (p_new_lf) leaf(r_val); 00399 apply_update(p_new_lf, (node_update*)this); 00400 cond.set_call_destructor(); 00401 branch_bag bag; 00402 bag.add_branch(); 00403 m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag); 00404 m_p_head->m_p_parent->m_p_parent = m_p_head; 00405 cond.set_no_action_dtor(); 00406 ++m_size; 00407 update_min_max_for_inserted_leaf(p_new_lf); 00408 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) 00409 PB_DS_ASSERT_VALID((*this)) 00410 return std::make_pair(point_iterator(p_new_lf), true); 00411 } 00412 00413 PB_DS_CLASS_T_DEC 00414 typename PB_DS_CLASS_C_DEC::size_type 00415 PB_DS_CLASS_C_DEC:: 00416 keys_diff_ind(typename access_traits::const_iterator b_l, 00417 typename access_traits::const_iterator e_l, 00418 typename access_traits::const_iterator b_r, 00419 typename access_traits::const_iterator e_r) 00420 { 00421 size_type diff_pos = 0; 00422 while (b_l != e_l) 00423 { 00424 if (b_r == e_r) 00425 return (diff_pos); 00426 if (access_traits::e_pos(*b_l) != access_traits::e_pos(*b_r)) 00427 return (diff_pos); 00428 ++b_l; 00429 ++b_r; 00430 ++diff_pos; 00431 } 00432 _GLIBCXX_DEBUG_ASSERT(b_r != e_r); 00433 return diff_pos; 00434 } 00435 00436 PB_DS_CLASS_T_DEC 00437 typename PB_DS_CLASS_C_DEC::inode_pointer 00438 PB_DS_CLASS_C_DEC:: 00439 insert_branch(node_pointer p_l, node_pointer p_r, branch_bag& r_bag) 00440 { 00441 typename synth_access_traits::const_iterator left_b_it = pref_begin(p_l); 00442 typename synth_access_traits::const_iterator left_e_it = pref_end(p_l); 00443 typename synth_access_traits::const_iterator right_b_it = pref_begin(p_r); 00444 typename synth_access_traits::const_iterator right_e_it = pref_end(p_r); 00445 00446 const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it, 00447 right_b_it, right_e_it); 00448 00449 inode_pointer p_new_nd = r_bag.get_branch(); 00450 new (p_new_nd) inode(diff_ind, left_b_it); 00451 p_new_nd->add_child(p_l, left_b_it, left_e_it, this); 00452 p_new_nd->add_child(p_r, right_b_it, right_e_it, this); 00453 p_l->m_p_parent = p_new_nd; 00454 p_r->m_p_parent = p_new_nd; 00455 PB_DS_ASSERT_NODE_VALID(p_new_nd) 00456 return (p_new_nd); 00457 } 00458 00459 PB_DS_CLASS_T_DEC 00460 void 00461 PB_DS_CLASS_C_DEC:: 00462 update_min_max_for_inserted_leaf(leaf_pointer p_new_lf) 00463 { 00464 if (m_p_head->m_p_min == m_p_head || 00465 synth_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()), 00466 PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value()))) 00467 m_p_head->m_p_min = p_new_lf; 00468 00469 if (m_p_head->m_p_max == m_p_head || 00470 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()))) 00471 m_p_head->m_p_max = p_new_lf; 00472 }