1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2013 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_/split_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 split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other) 45 { 46 PB_DS_ASSERT_VALID((*this)) 47 PB_DS_ASSERT_VALID(other) 48 branch_bag bag; 49 leaf_pointer p_split_lf = split_prep(r_key, other, bag); 50 if (p_split_lf == 0) 51 { 52 _GLIBCXX_DEBUG_ASSERT(bag.empty()); 53 PB_DS_ASSERT_VALID((*this)) 54 PB_DS_ASSERT_VALID(other) 55 return; 56 } 57 58 _GLIBCXX_DEBUG_ASSERT(!bag.empty()); 59 other.clear(); 60 61 m_p_head->m_p_parent = rec_split(m_p_head->m_p_parent, pref_begin(p_split_lf), 62 pref_end(p_split_lf), other, bag); 63 64 m_p_head->m_p_parent->m_p_parent = m_p_head; 65 66 head_pointer __ohead = other.m_p_head; 67 __ohead->m_p_max = m_p_head->m_p_max; 68 m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); 69 __ohead->m_p_min = other.leftmost_descendant(__ohead->m_p_parent); 70 71 other.m_size = std::distance(other.PB_DS_CLASS_C_DEC::begin(), 72 other.PB_DS_CLASS_C_DEC::end()); 73 m_size -= other.m_size; 74 PB_DS_ASSERT_VALID((*this)) 75 PB_DS_ASSERT_VALID(other) 76 } 77 78 PB_DS_CLASS_T_DEC 79 typename PB_DS_CLASS_C_DEC::leaf_pointer 80 PB_DS_CLASS_C_DEC:: 81 split_prep(key_const_reference r_key, PB_DS_CLASS_C_DEC& other, 82 branch_bag& r_bag) 83 { 84 _GLIBCXX_DEBUG_ASSERT(r_bag.empty()); 85 if (m_size == 0) 86 { 87 other.clear(); 88 PB_DS_ASSERT_VALID((*this)) 89 PB_DS_ASSERT_VALID(other) 90 return 0; 91 } 92 93 if (synth_access_traits::cmp_keys(r_key, 94 PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value()))) 95 { 96 other.clear(); 97 value_swap(other); 98 PB_DS_ASSERT_VALID((*this)) 99 PB_DS_ASSERT_VALID(other) 100 return 0; 101 } 102 103 if (!synth_access_traits::cmp_keys(r_key, 104 PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()))) 105 { 106 PB_DS_ASSERT_VALID((*this)) 107 PB_DS_ASSERT_VALID(other) 108 return 0; 109 } 110 111 iterator it = lower_bound(r_key); 112 113 if (!synth_access_traits::equal_keys(PB_DS_V2F(*it), r_key)) 114 --it; 115 116 node_pointer p_nd = it.m_p_nd; 117 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == leaf_node); 118 leaf_pointer p_ret_l = static_cast<leaf_pointer>(p_nd); 119 while (p_nd->m_type != head_node) 120 { 121 r_bag.add_branch(); 122 p_nd = p_nd->m_p_parent; 123 } 124 _GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(synth_access_traits&)(*this), other);) 125 126 return p_ret_l; 127 } 128 129 PB_DS_CLASS_T_DEC 130 typename PB_DS_CLASS_C_DEC::node_pointer 131 PB_DS_CLASS_C_DEC:: 132 rec_split(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it, 133 PB_DS_CLASS_C_DEC& other, branch_bag& r_bag) 134 { 135 if (p_nd->m_type == leaf_node) 136 { 137 _GLIBCXX_DEBUG_ASSERT(other.m_p_head->m_p_parent == 0); 138 return p_nd; 139 } 140 141 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); 142 inode_pointer p_ind = static_cast<inode_pointer>(p_nd); 143 144 node_pointer pfirst = p_ind->get_child_node(b_it, e_it, this); 145 node_pointer p_child_ret = rec_split(pfirst, b_it, e_it, other, r_bag); 146 PB_DS_ASSERT_NODE_VALID(p_child_ret) 147 p_ind->replace_child(p_child_ret, b_it, e_it, this); 148 apply_update(p_ind, (node_update*)this); 149 150 inode_iterator child_it = p_ind->get_child_it(b_it, e_it, this); 151 const size_type lhs_dist = std::distance(p_ind->begin(), child_it); 152 const size_type lhs_num_children = lhs_dist + 1; 153 _GLIBCXX_DEBUG_ASSERT(lhs_num_children > 0); 154 155 const size_type rhs_dist = std::distance(p_ind->begin(), p_ind->end()); 156 size_type rhs_num_children = rhs_dist - lhs_num_children; 157 if (rhs_num_children == 0) 158 { 159 apply_update(p_ind, (node_update*)this); 160 return p_ind; 161 } 162 163 other.split_insert_branch(p_ind->get_e_ind(), b_it, child_it, 164 rhs_num_children, r_bag); 165 166 child_it = p_ind->get_child_it(b_it, e_it, this); 167 while (rhs_num_children != 0) 168 { 169 ++child_it; 170 p_ind->remove_child(child_it); 171 --rhs_num_children; 172 } 173 apply_update(p_ind, (node_update*)this); 174 175 const size_type int_dist = std::distance(p_ind->begin(), p_ind->end()); 176 _GLIBCXX_DEBUG_ASSERT(int_dist >= 1); 177 if (int_dist > 1) 178 { 179 p_ind->update_prefixes(this); 180 PB_DS_ASSERT_NODE_VALID(p_ind) 181 apply_update(p_ind, (node_update*)this); 182 return p_ind; 183 } 184 185 node_pointer p_ret = *p_ind->begin(); 186 p_ind->~inode(); 187 s_inode_allocator.deallocate(p_ind, 1); 188 apply_update(p_ret, (node_update*)this); 189 return p_ret; 190 } 191 192 PB_DS_CLASS_T_DEC 193 void 194 PB_DS_CLASS_C_DEC:: 195 split_insert_branch(size_type e_ind, a_const_iterator b_it, 196 inode_iterator child_b_it, 197 size_type num_children, branch_bag& r_bag) 198 { 199 #ifdef _GLIBCXX_DEBUG 200 if (m_p_head->m_p_parent != 0) 201 PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) 202 #endif 203 204 const size_type start = m_p_head->m_p_parent == 0 ? 0 : 1; 205 const size_type total_num_children = start + num_children; 206 if (total_num_children == 0) 207 { 208 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0); 209 return; 210 } 211 212 if (total_num_children == 1) 213 { 214 if (m_p_head->m_p_parent != 0) 215 { 216 PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) 217 return; 218 } 219 220 _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0); 221 ++child_b_it; 222 m_p_head->m_p_parent = *child_b_it; 223 m_p_head->m_p_parent->m_p_parent = m_p_head; 224 apply_update(m_p_head->m_p_parent, (node_update*)this); 225 PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) 226 return; 227 } 228 229 _GLIBCXX_DEBUG_ASSERT(total_num_children > 1); 230 inode_pointer p_new_root = r_bag.get_branch(); 231 new (p_new_root) inode(e_ind, b_it); 232 size_type num_inserted = 0; 233 while (num_inserted++ < num_children) 234 { 235 ++child_b_it; 236 PB_DS_ASSERT_NODE_VALID((*child_b_it)) 237 p_new_root->add_child(*child_b_it, pref_begin(*child_b_it), 238 pref_end(*child_b_it), this); 239 } 240 241 if (m_p_head->m_p_parent != 0) 242 p_new_root->add_child(m_p_head->m_p_parent, 243 pref_begin(m_p_head->m_p_parent), 244 pref_end(m_p_head->m_p_parent), this); 245 246 m_p_head->m_p_parent = p_new_root; 247 p_new_root->m_p_parent = m_p_head; 248 apply_update(m_p_head->m_p_parent, (node_update*)this); 249 PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) 250 } 251
