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