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_/split_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 split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other) 00045 { 00046 PB_DS_ASSERT_VALID((*this)) 00047 PB_DS_ASSERT_VALID(other) 00048 branch_bag bag; 00049 leaf_pointer p_split_lf = split_prep(r_key, other, bag); 00050 if (p_split_lf == 0) 00051 { 00052 _GLIBCXX_DEBUG_ASSERT(bag.empty()); 00053 PB_DS_ASSERT_VALID((*this)) 00054 PB_DS_ASSERT_VALID(other) 00055 return; 00056 } 00057 00058 _GLIBCXX_DEBUG_ASSERT(!bag.empty()); 00059 other.clear(); 00060 00061 m_p_head->m_p_parent = rec_split(m_p_head->m_p_parent, pref_begin(p_split_lf), 00062 pref_end(p_split_lf), other, bag); 00063 00064 m_p_head->m_p_parent->m_p_parent = m_p_head; 00065 00066 head_pointer __ohead = other.m_p_head; 00067 __ohead->m_p_max = m_p_head->m_p_max; 00068 m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); 00069 __ohead->m_p_min = other.leftmost_descendant(__ohead->m_p_parent); 00070 00071 other.m_size = std::distance(other.PB_DS_CLASS_C_DEC::begin(), 00072 other.PB_DS_CLASS_C_DEC::end()); 00073 m_size -= other.m_size; 00074 PB_DS_ASSERT_VALID((*this)) 00075 PB_DS_ASSERT_VALID(other) 00076 } 00077 00078 PB_DS_CLASS_T_DEC 00079 typename PB_DS_CLASS_C_DEC::leaf_pointer 00080 PB_DS_CLASS_C_DEC:: 00081 split_prep(key_const_reference r_key, PB_DS_CLASS_C_DEC& other, 00082 branch_bag& r_bag) 00083 { 00084 _GLIBCXX_DEBUG_ASSERT(r_bag.empty()); 00085 if (m_size == 0) 00086 { 00087 other.clear(); 00088 PB_DS_ASSERT_VALID((*this)) 00089 PB_DS_ASSERT_VALID(other) 00090 return 0; 00091 } 00092 00093 if (synth_access_traits::cmp_keys(r_key, 00094 PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value()))) 00095 { 00096 other.clear(); 00097 value_swap(other); 00098 PB_DS_ASSERT_VALID((*this)) 00099 PB_DS_ASSERT_VALID(other) 00100 return 0; 00101 } 00102 00103 if (!synth_access_traits::cmp_keys(r_key, 00104 PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()))) 00105 { 00106 PB_DS_ASSERT_VALID((*this)) 00107 PB_DS_ASSERT_VALID(other) 00108 return 0; 00109 } 00110 00111 iterator it = lower_bound(r_key); 00112 00113 if (!synth_access_traits::equal_keys(PB_DS_V2F(*it), r_key)) 00114 --it; 00115 00116 node_pointer p_nd = it.m_p_nd; 00117 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == leaf_node); 00118 leaf_pointer p_ret_l = static_cast<leaf_pointer>(p_nd); 00119 while (p_nd->m_type != head_node) 00120 { 00121 r_bag.add_branch(); 00122 p_nd = p_nd->m_p_parent; 00123 } 00124 _GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(synth_access_traits&)(*this), other);) 00125 00126 return p_ret_l; 00127 } 00128 00129 PB_DS_CLASS_T_DEC 00130 typename PB_DS_CLASS_C_DEC::node_pointer 00131 PB_DS_CLASS_C_DEC:: 00132 rec_split(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it, 00133 PB_DS_CLASS_C_DEC& other, branch_bag& r_bag) 00134 { 00135 if (p_nd->m_type == leaf_node) 00136 { 00137 _GLIBCXX_DEBUG_ASSERT(other.m_p_head->m_p_parent == 0); 00138 return p_nd; 00139 } 00140 00141 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); 00142 inode_pointer p_ind = static_cast<inode_pointer>(p_nd); 00143 00144 node_pointer pfirst = p_ind->get_child_node(b_it, e_it, this); 00145 node_pointer p_child_ret = rec_split(pfirst, b_it, e_it, other, r_bag); 00146 PB_DS_ASSERT_NODE_VALID(p_child_ret) 00147 p_ind->replace_child(p_child_ret, b_it, e_it, this); 00148 apply_update(p_ind, (node_update*)this); 00149 00150 inode_iterator child_it = p_ind->get_child_it(b_it, e_it, this); 00151 const size_type lhs_dist = std::distance(p_ind->begin(), child_it); 00152 const size_type lhs_num_children = lhs_dist + 1; 00153 _GLIBCXX_DEBUG_ASSERT(lhs_num_children > 0); 00154 00155 const size_type rhs_dist = std::distance(p_ind->begin(), p_ind->end()); 00156 size_type rhs_num_children = rhs_dist - lhs_num_children; 00157 if (rhs_num_children == 0) 00158 { 00159 apply_update(p_ind, (node_update*)this); 00160 return p_ind; 00161 } 00162 00163 other.split_insert_branch(p_ind->get_e_ind(), b_it, child_it, 00164 rhs_num_children, r_bag); 00165 00166 child_it = p_ind->get_child_it(b_it, e_it, this); 00167 while (rhs_num_children != 0) 00168 { 00169 ++child_it; 00170 p_ind->remove_child(child_it); 00171 --rhs_num_children; 00172 } 00173 apply_update(p_ind, (node_update*)this); 00174 00175 const size_type int_dist = std::distance(p_ind->begin(), p_ind->end()); 00176 _GLIBCXX_DEBUG_ASSERT(int_dist >= 1); 00177 if (int_dist > 1) 00178 { 00179 p_ind->update_prefixes(this); 00180 PB_DS_ASSERT_NODE_VALID(p_ind) 00181 apply_update(p_ind, (node_update*)this); 00182 return p_ind; 00183 } 00184 00185 node_pointer p_ret = *p_ind->begin(); 00186 p_ind->~inode(); 00187 s_inode_allocator.deallocate(p_ind, 1); 00188 apply_update(p_ret, (node_update*)this); 00189 return p_ret; 00190 } 00191 00192 PB_DS_CLASS_T_DEC 00193 void 00194 PB_DS_CLASS_C_DEC:: 00195 split_insert_branch(size_type e_ind, a_const_iterator b_it, 00196 inode_iterator child_b_it, 00197 size_type num_children, branch_bag& r_bag) 00198 { 00199 #ifdef _GLIBCXX_DEBUG 00200 if (m_p_head->m_p_parent != 0) 00201 PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) 00202 #endif 00203 00204 const size_type start = m_p_head->m_p_parent == 0 ? 0 : 1; 00205 const size_type total_num_children = start + num_children; 00206 if (total_num_children == 0) 00207 { 00208 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0); 00209 return; 00210 } 00211 00212 if (total_num_children == 1) 00213 { 00214 if (m_p_head->m_p_parent != 0) 00215 { 00216 PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) 00217 return; 00218 } 00219 00220 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0); 00221 ++child_b_it; 00222 m_p_head->m_p_parent = *child_b_it; 00223 m_p_head->m_p_parent->m_p_parent = m_p_head; 00224 apply_update(m_p_head->m_p_parent, (node_update*)this); 00225 PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) 00226 return; 00227 } 00228 00229 _GLIBCXX_DEBUG_ASSERT(total_num_children > 1); 00230 inode_pointer p_new_root = r_bag.get_branch(); 00231 new (p_new_root) inode(e_ind, b_it); 00232 size_type num_inserted = 0; 00233 while (num_inserted++ < num_children) 00234 { 00235 ++child_b_it; 00236 PB_DS_ASSERT_NODE_VALID((*child_b_it)) 00237 p_new_root->add_child(*child_b_it, pref_begin(*child_b_it), 00238 pref_end(*child_b_it), this); 00239 } 00240 00241 if (m_p_head->m_p_parent != 0) 00242 p_new_root->add_child(m_p_head->m_p_parent, 00243 pref_begin(m_p_head->m_p_parent), 00244 pref_end(m_p_head->m_p_parent), this); 00245 00246 m_p_head->m_p_parent = p_new_root; 00247 p_new_root->m_p_parent = m_p_head; 00248 apply_update(m_p_head->m_p_parent, (node_update*)this); 00249 PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) 00250 }